iterator

package
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 26, 2014 License: Apache-2.0 Imports: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func BasicEquality

func BasicEquality(a, b graph.Value) bool

Define an equality function of purely ==, which works for native types.

func NextUID

func NextUID() uint64

func OutputQueryShapeForIterator

func OutputQueryShapeForIterator(it graph.Iterator, ts graph.TripleStore, outputMap map[string]interface{})

func RunIntOp

func RunIntOp(a int64, op Operator, b int64) bool

Types

type And

type And struct {
	// contains filtered or unexported fields
}

The And iterator. Consists of a number of subiterators, the primary of which will be Next()ed if next is called.

func NewAnd

func NewAnd() *And

Creates a new And iterator.

func (*And) AddSubIterator

func (it *And) AddSubIterator(sub graph.Iterator)

Add a subiterator to this And iterator.

The first iterator that is added becomes the primary iterator. This is important. Calling Optimize() is the way to change the order based on subiterator statistics. Without Optimize(), the order added is the order used.

func (*And) Clone

func (it *And) Clone() graph.Iterator

func (*And) Close

func (it *And) Close()

Close this iterator, and, by extension, close the subiterators. Close should be idempotent, and it follows that if it's subiterators follow this contract, the And follows the contract.

func (*And) Contains

func (it *And) Contains(val graph.Value) bool

Check a value against the entire iterator, in order.

func (*And) DebugString

func (it *And) DebugString(indent int) string

Prints information about this iterator.

func (*And) Next

func (it *And) Next() bool

Returns advances the And iterator. Because the And is the intersection of its subiterators, it must choose one subiterator to produce a candidate, and check this value against the subiterators. A productive choice of primary iterator is therefore very important.

func (*And) NextPath added in v0.4.0

func (it *And) NextPath() bool

An And has no NextPath of its own -- that is, there are no other values which satisfy our previous result that are not the result itself. Our subiterators might, however, so just pass the call recursively.

func (*And) Optimize

func (it *And) Optimize() (graph.Iterator, bool)

Optimizes the And, by picking the most efficient way to Next() and Contains() its subiterators. For SQL fans, this is equivalent to JOIN.

func (*And) Reset

func (it *And) Reset()

Reset all internal iterators

func (*And) Result

func (it *And) Result() graph.Value

func (*And) ResultTree

func (it *And) ResultTree() *graph.ResultTree

DEPRECATED Returns the ResultTree for this iterator, recurses to it's subiterators.

func (*And) Size

func (it *And) Size() (int64, bool)

Returns the approximate size of the And iterator. Because we're dealing with an intersection, we know that the largest we can be is the size of the smallest iterator. This is the heuristic we shall follow. Better heuristics welcome.

func (*And) Stats

func (it *And) Stats() graph.IteratorStats

and.Stats() lives here in and-iterator-optimize.go because it may in the future return different statistics based on how it is optimized. For now, however, it's pretty static.

func (*And) SubIterators

func (it *And) SubIterators() []graph.Iterator

Returns a slice of the subiterators, in order (primary iterator first).

func (*And) TagResults

func (it *And) TagResults(dst map[string]graph.Value)

An extended TagResults, as it needs to add it's own results and recurse down it's subiterators.

func (*And) Tagger

func (it *And) Tagger() *graph.Tagger

func (*And) Type

func (it *And) Type() graph.Type

Register this as an "and" iterator.

func (*And) UID

func (it *And) UID() uint64

type Comparison

type Comparison struct {
	// contains filtered or unexported fields
}

func NewComparison

func NewComparison(sub graph.Iterator, op Operator, val interface{}, ts graph.TripleStore) *Comparison

func (*Comparison) Clone

func (it *Comparison) Clone() graph.Iterator

func (*Comparison) Close

func (it *Comparison) Close()

func (*Comparison) Contains

func (it *Comparison) Contains(val graph.Value) bool

func (*Comparison) DebugString

func (it *Comparison) DebugString(indent int) string

Prints the value-comparison and its subiterator.

func (*Comparison) Next

func (it *Comparison) Next() bool

func (*Comparison) NextPath added in v0.4.0

func (it *Comparison) NextPath() bool

func (*Comparison) Optimize

func (it *Comparison) Optimize() (graph.Iterator, bool)

There's nothing to optimize, locally, for a value-comparison iterator. Replace the underlying iterator if need be. potentially replace it.

func (*Comparison) Reset

func (it *Comparison) Reset()

func (*Comparison) Result

func (it *Comparison) Result() graph.Value

func (*Comparison) ResultTree

func (it *Comparison) ResultTree() *graph.ResultTree

DEPRECATED

func (*Comparison) Size

func (it *Comparison) Size() (int64, bool)

func (*Comparison) Stats

func (it *Comparison) Stats() graph.IteratorStats

We're only as expensive as our subiterator. Again, optimized value comparison iterators should do better.

func (*Comparison) SubIterators

func (it *Comparison) SubIterators() []graph.Iterator

No subiterators.

func (*Comparison) TagResults

func (it *Comparison) TagResults(dst map[string]graph.Value)

If we failed the check, then the subiterator should not contribute to the result set. Otherwise, go ahead and tag it.

func (*Comparison) Tagger

func (it *Comparison) Tagger() *graph.Tagger

func (*Comparison) Type

func (it *Comparison) Type() graph.Type

Registers the value-comparison iterator.

func (*Comparison) UID

func (it *Comparison) UID() uint64

type Equality

type Equality func(a, b graph.Value) bool

Define the signature of an equality function.

type Fixed

type Fixed struct {
	// contains filtered or unexported fields
}

A Fixed iterator consists of it's values, an index (where it is in the process of Next()ing) and an equality function.

func NewFixedIteratorWithCompare

func NewFixedIteratorWithCompare(compareFn Equality) *Fixed

Creates a new Fixed iterator with a custom comparitor.

func (*Fixed) Add

func (it *Fixed) Add(v graph.Value)

Add a value to the iterator. The array now contains this value. TODO(barakmich): This ought to be a set someday, disallowing repeated values.

func (*Fixed) Clone

func (it *Fixed) Clone() graph.Iterator

func (*Fixed) Close

func (it *Fixed) Close()

func (*Fixed) Contains

func (it *Fixed) Contains(v graph.Value) bool

Check if the passed value is equal to one of the values stored in the iterator.

func (*Fixed) DebugString

func (it *Fixed) DebugString(indent int) string

Print some information about the iterator.

func (*Fixed) Next

func (it *Fixed) Next() bool

Next advances the iterator.

func (*Fixed) NextPath added in v0.4.0

func (it *Fixed) NextPath() bool

func (*Fixed) Optimize

func (it *Fixed) Optimize() (graph.Iterator, bool)

Optimize() for a Fixed iterator is simple. Returns a Null iterator if it's empty (so that other iterators upstream can treat this as null) or there is no optimization.

func (*Fixed) Reset

func (it *Fixed) Reset()

func (*Fixed) Result

func (it *Fixed) Result() graph.Value

func (*Fixed) ResultTree

func (it *Fixed) ResultTree() *graph.ResultTree

DEPRECATED

func (*Fixed) Size

func (it *Fixed) Size() (int64, bool)

Size is the number of values stored.

func (*Fixed) Stats

func (it *Fixed) Stats() graph.IteratorStats

As we right now have to scan the entire list, Next and Contains are linear with the size. However, a better data structure could remove these limits.

func (*Fixed) SubIterators

func (it *Fixed) SubIterators() []graph.Iterator

No sub-iterators.

func (*Fixed) TagResults

func (it *Fixed) TagResults(dst map[string]graph.Value)

func (*Fixed) Tagger

func (it *Fixed) Tagger() *graph.Tagger

func (*Fixed) Type

func (it *Fixed) Type() graph.Type

Register this iterator as a Fixed iterator.

func (*Fixed) UID

func (it *Fixed) UID() uint64

type HasA

type HasA struct {
	// contains filtered or unexported fields
}

A HasA consists of a reference back to the graph.TripleStore that it references, a primary subiterator, a direction in which the triples for that subiterator point, and a temporary holder for the iterator generated on Contains().

func NewHasA

func NewHasA(ts graph.TripleStore, subIt graph.Iterator, d quad.Direction) *HasA

Construct a new HasA iterator, given the triple subiterator, and the triple direction for which it stands.

func (*HasA) Clone

func (it *HasA) Clone() graph.Iterator

func (*HasA) Close

func (it *HasA) Close()

Close the subiterator, the result iterator (if any) and the HasA.

func (*HasA) Contains

func (it *HasA) Contains(val graph.Value) bool

Check a value against our internal iterator. In order to do this, we must first open a new iterator of "triples that have `val` in our direction", given to us by the triple store, and then Next() values out of that iterator and Contains() them against our subiterator.

func (*HasA) DebugString

func (it *HasA) DebugString(indent int) string

Print some information about this iterator.

func (*HasA) Direction

func (it *HasA) Direction() quad.Direction

Direction accessor.

func (*HasA) Next

func (it *HasA) Next() bool

Next advances the iterator. This is simpler than Contains. We have a subiterator we can get a value from, and we can take that resultant triple, pull our direction out of it, and return that.

func (*HasA) NextContains

func (it *HasA) NextContains() bool

NextContains() is shared code between Contains() and GetNextResult() -- calls next on the result iterator (a triple iterator based on the last checked value) and returns true if another match is made.

func (*HasA) NextPath added in v0.4.0

func (it *HasA) NextPath() bool

Get the next result that matches this branch.

func (*HasA) Optimize

func (it *HasA) Optimize() (graph.Iterator, bool)

Pass the Optimize() call along to the subiterator. If it becomes Null, then the HasA becomes Null (there are no triples that have any directions).

func (*HasA) Reset

func (it *HasA) Reset()

func (*HasA) Result

func (it *HasA) Result() graph.Value

func (*HasA) ResultTree

func (it *HasA) ResultTree() *graph.ResultTree

DEPRECATED Return results in a ResultTree.

func (*HasA) Size

func (it *HasA) Size() (int64, bool)

func (*HasA) Stats

func (it *HasA) Stats() graph.IteratorStats

GetStats() returns the statistics on the HasA iterator. This is curious. Next cost is easy, it's an extra call or so on top of the subiterator Next cost. ContainsCost involves going to the graph.TripleStore, iterating out values, and hoping one sticks -- potentially expensive, depending on fanout. Size, however, is potentially smaller. we know at worst it's the size of the subiterator, but if there are many repeated values, it could be much smaller in totality.

func (*HasA) SubIterators

func (it *HasA) SubIterators() []graph.Iterator

Return our sole subiterator.

func (*HasA) TagResults

func (it *HasA) TagResults(dst map[string]graph.Value)

Pass the TagResults down the chain.

func (*HasA) Tagger

func (it *HasA) Tagger() *graph.Tagger

func (*HasA) Type

func (it *HasA) Type() graph.Type

Register this iterator as a HasA.

func (*HasA) UID

func (it *HasA) UID() uint64

type Int64

type Int64 struct {
	// contains filtered or unexported fields
}

An All iterator across a range of int64 values, from `max` to `min`.

func NewInt64

func NewInt64(min, max int64) *Int64

Creates a new Int64 with the given range.

func (*Int64) Clone

func (it *Int64) Clone() graph.Iterator

func (*Int64) Close

func (it *Int64) Close()

func (*Int64) Contains

func (it *Int64) Contains(tsv graph.Value) bool

Contains() for an Int64 is merely seeing if the passed value is withing the range, assuming the value is an int64.

func (*Int64) DebugString

func (it *Int64) DebugString(indent int) string

Prints the All iterator as just an "all".

func (*Int64) Next

func (it *Int64) Next() bool

Next() on an Int64 all iterator is a simple incrementing counter. Return the next integer, and mark it as the result.

func (*Int64) NextPath added in v0.4.0

func (it *Int64) NextPath() bool

func (*Int64) Optimize

func (it *Int64) Optimize() (graph.Iterator, bool)

There's nothing to optimize about this little iterator.

func (*Int64) Reset

func (it *Int64) Reset()

Start back at the beginning

func (*Int64) Result

func (it *Int64) Result() graph.Value

func (*Int64) ResultTree

func (it *Int64) ResultTree() *graph.ResultTree

DEPRECATED

func (*Int64) Size

func (it *Int64) Size() (int64, bool)

The number of elements in an Int64 is the size of the range. The size is exact.

func (*Int64) Stats

func (it *Int64) Stats() graph.IteratorStats

Stats for an Int64 are simple. Super cheap to do any operation, and as big as the range.

func (*Int64) SubIterators

func (it *Int64) SubIterators() []graph.Iterator

No sub-iterators.

func (*Int64) TagResults

func (it *Int64) TagResults(dst map[string]graph.Value)

Fill the map based on the tags assigned to this iterator.

func (*Int64) Tagger

func (it *Int64) Tagger() *graph.Tagger

func (*Int64) Type

func (it *Int64) Type() graph.Type

The type of this iterator is an "all". This is important, as it puts it in the class of "all iterators.

func (*Int64) UID

func (it *Int64) UID() uint64

type Keyer added in v0.4.0

type Keyer interface {
	Key() interface{}
}

Keyer provides a method for comparing types that are not otherwise comparable. The Key method must return a dynamic type that is comparable according to the Go language specification. The returned value must be unique for each receiver value.

type Link struct {
	Source   int `json:"source"`
	Target   int `json:"target"`
	Pred     int `json:"type"`
	LinkNode int `json:"link_node"`
}

type LinksTo

type LinksTo struct {
	// contains filtered or unexported fields
}

A LinksTo has a reference back to the graph.TripleStore (to create the iterators for each node) the subiterator, and the direction the iterator comes from. `next_it` is the tempoarary iterator held per result in `primary_it`.

func NewLinksTo

func NewLinksTo(ts graph.TripleStore, it graph.Iterator, d quad.Direction) *LinksTo

Construct a new LinksTo iterator around a direction and a subiterator of nodes.

func (*LinksTo) Clone

func (it *LinksTo) Clone() graph.Iterator

func (*LinksTo) Close

func (it *LinksTo) Close()

Close our subiterators.

func (*LinksTo) Contains

func (it *LinksTo) Contains(val graph.Value) bool

If it checks in the right direction for the subiterator, it is a valid link for the LinksTo.

func (*LinksTo) DebugString

func (it *LinksTo) DebugString(indent int) string

Print the iterator.

func (*LinksTo) Direction

func (it *LinksTo) Direction() quad.Direction

Return the direction under consideration.

func (*LinksTo) Next

func (it *LinksTo) Next() bool

Next()ing a LinksTo operates as described above.

func (*LinksTo) NextPath added in v0.4.0

func (it *LinksTo) NextPath() bool

We won't ever have a new result, but our subiterators might.

func (*LinksTo) Optimize

func (it *LinksTo) Optimize() (graph.Iterator, bool)

Optimize the LinksTo, by replacing it if it can be.

func (*LinksTo) Reset

func (it *LinksTo) Reset()

func (*LinksTo) Result

func (it *LinksTo) Result() graph.Value

func (*LinksTo) ResultTree

func (it *LinksTo) ResultTree() *graph.ResultTree

DEPRECATED

func (*LinksTo) Size

func (it *LinksTo) Size() (int64, bool)

func (*LinksTo) Stats

func (it *LinksTo) Stats() graph.IteratorStats

Return a guess as to how big or costly it is to next the iterator.

func (*LinksTo) SubIterators

func (it *LinksTo) SubIterators() []graph.Iterator

Return a list containing only our subiterator.

func (*LinksTo) TagResults

func (it *LinksTo) TagResults(dst map[string]graph.Value)

Tag these results, and our subiterator's results.

func (*LinksTo) Tagger

func (it *LinksTo) Tagger() *graph.Tagger

func (*LinksTo) Type

func (it *LinksTo) Type() graph.Type

Register the LinksTo.

func (*LinksTo) UID

func (it *LinksTo) UID() uint64

type Materialize added in v0.4.0

type Materialize struct {
	// contains filtered or unexported fields
}

func NewMaterialize added in v0.4.0

func NewMaterialize(sub graph.Iterator) *Materialize

func (*Materialize) Clone added in v0.4.0

func (it *Materialize) Clone() graph.Iterator

func (*Materialize) Close added in v0.4.0

func (it *Materialize) Close()

func (*Materialize) Contains added in v0.4.0

func (it *Materialize) Contains(v graph.Value) bool

func (*Materialize) DebugString added in v0.4.0

func (it *Materialize) DebugString(indent int) string

Print some information about the iterator.

func (*Materialize) Next added in v0.4.0

func (it *Materialize) Next() bool

func (*Materialize) NextPath added in v0.4.0

func (it *Materialize) NextPath() bool

func (*Materialize) Optimize added in v0.4.0

func (it *Materialize) Optimize() (graph.Iterator, bool)

func (*Materialize) Reset added in v0.4.0

func (it *Materialize) Reset()

func (*Materialize) Result added in v0.4.0

func (it *Materialize) Result() graph.Value

func (*Materialize) ResultTree added in v0.4.0

func (it *Materialize) ResultTree() *graph.ResultTree

DEPRECATED

func (*Materialize) Size added in v0.4.0

func (it *Materialize) Size() (int64, bool)

Size is the number of values stored, if we've got them all. Otherwise, guess based on the size of the subiterator.

func (*Materialize) Stats added in v0.4.0

func (it *Materialize) Stats() graph.IteratorStats

The entire point of Materialize is to amortize the cost by putting it all up front.

func (*Materialize) SubIterators added in v0.4.0

func (it *Materialize) SubIterators() []graph.Iterator

func (*Materialize) TagResults added in v0.4.0

func (it *Materialize) TagResults(dst map[string]graph.Value)

func (*Materialize) Tagger added in v0.4.0

func (it *Materialize) Tagger() *graph.Tagger

func (*Materialize) Type added in v0.4.0

func (it *Materialize) Type() graph.Type

Register this iterator as a Materialize iterator.

func (*Materialize) UID added in v0.4.0

func (it *Materialize) UID() uint64

type Node

type Node struct {
	Id         int      `json:"id"`
	Tags       []string `json:"tags,omitempty"`
	Values     []string `json:"values,omitempty"`
	IsLinkNode bool     `json:"is_link_node"`
	IsFixed    bool     `json:"is_fixed"`
}

type Null

type Null struct {
	// contains filtered or unexported fields
}

Here we define the simplest iterator -- the Null iterator. It contains nothing. It is the empty set. Often times, queries that contain one of these match nothing, so it's important to give it a special iterator.

func NewNull

func NewNull() *Null

Fairly useless New function.

func (*Null) Clone

func (it *Null) Clone() graph.Iterator

func (*Null) Close

func (it *Null) Close()

func (*Null) Contains

func (it *Null) Contains(graph.Value) bool

func (*Null) DebugString

func (it *Null) DebugString(indent int) string

Print the null iterator.

func (*Null) Next

func (it *Null) Next() bool

func (*Null) NextPath added in v0.4.0

func (it *Null) NextPath() bool

func (*Null) Optimize

func (it *Null) Optimize() (graph.Iterator, bool)

A good iterator will close itself when it returns true. Null has nothing it needs to do.

func (*Null) Reset

func (it *Null) Reset()

func (*Null) Result

func (it *Null) Result() graph.Value

func (*Null) ResultTree

func (it *Null) ResultTree() *graph.ResultTree

func (*Null) Size

func (it *Null) Size() (int64, bool)

func (*Null) Stats

func (it *Null) Stats() graph.IteratorStats

A null iterator costs nothing. Use it!

func (*Null) SubIterators

func (it *Null) SubIterators() []graph.Iterator

func (*Null) TagResults

func (it *Null) TagResults(dst map[string]graph.Value)

Fill the map based on the tags assigned to this iterator.

func (*Null) Tagger

func (it *Null) Tagger() *graph.Tagger

func (*Null) Type

func (it *Null) Type() graph.Type

Name the null iterator.

func (*Null) UID

func (it *Null) UID() uint64

type Operator

type Operator int

type Optional

type Optional struct {
	// contains filtered or unexported fields
}

An optional iterator has the sub-constraint iterator we wish to be optional and whether the last check we received was true or false.

func NewOptional

func NewOptional(it graph.Iterator) *Optional

Creates a new optional iterator.

func (*Optional) Clone

func (it *Optional) Clone() graph.Iterator

func (*Optional) Close

func (it *Optional) Close()

func (*Optional) Contains

func (it *Optional) Contains(val graph.Value) bool

Contains() is the real hack of this iterator. It always returns true, regardless of whether the subiterator matched. But we keep track of whether the subiterator matched for results purposes.

func (*Optional) DebugString

func (it *Optional) DebugString(indent int) string

Prints the optional and it's subiterator.

func (*Optional) NextPath added in v0.4.0

func (it *Optional) NextPath() bool

An optional iterator only has a next result if, (a) last time we checked we had any results whatsoever, and (b) there was another subresult in our optional subbranch.

func (*Optional) Optimize

func (it *Optional) Optimize() (graph.Iterator, bool)

There's nothing to optimize for an optional. Optimize the subiterator and potentially replace it.

func (*Optional) Reset

func (it *Optional) Reset()

func (*Optional) Result

func (it *Optional) Result() graph.Value

func (*Optional) ResultTree

func (it *Optional) ResultTree() *graph.ResultTree

DEPRECATED

func (*Optional) Size

func (it *Optional) Size() (int64, bool)

If you're empty and you know it, clap your hands.

func (*Optional) Stats

func (it *Optional) Stats() graph.IteratorStats

We're only as expensive as our subiterator. Except, we can't be nexted.

func (*Optional) SubIterators

func (it *Optional) SubIterators() []graph.Iterator

No subiterators.

func (*Optional) TagResults

func (it *Optional) TagResults(dst map[string]graph.Value)

If we failed the check, then the subiterator should not contribute to the result set. Otherwise, go ahead and tag it.

func (*Optional) Tagger

func (it *Optional) Tagger() *graph.Tagger

func (*Optional) Type

func (it *Optional) Type() graph.Type

Registers the optional iterator.

func (*Optional) UID

func (it *Optional) UID() uint64

type Or

type Or struct {
	// contains filtered or unexported fields
}

func NewOr

func NewOr() *Or

func NewShortCircuitOr

func NewShortCircuitOr() *Or

func (*Or) AddSubIterator

func (it *Or) AddSubIterator(sub graph.Iterator)

Add a subiterator to this Or graph.iterator. Order matters.

func (*Or) Clone

func (it *Or) Clone() graph.Iterator

func (*Or) Close

func (it *Or) Close()

Close this graph.iterator, and, by extension, close the subiterators. Close should be idempotent, and it follows that if it's subiterators follow this contract, the And follows the contract.

func (*Or) Contains

func (it *Or) Contains(val graph.Value) bool

Check a value against the entire graph.iterator, in order.

func (*Or) DebugString

func (it *Or) DebugString(indent int) string

Prints information about this graph.iterator.

func (*Or) Next

func (it *Or) Next() bool

Next advances the Or graph.iterator. Because the Or is the union of its subiterators, it must produce from all subiterators -- unless it it shortcircuiting, in which case, it is the first one that returns anything.

func (*Or) NextPath added in v0.4.0

func (it *Or) NextPath() bool

An Or has no NextPath of its own -- that is, there are no other values which satisfy our previous result that are not the result itself. Our subiterators might, however, so just pass the call recursively. In the case of shortcircuiting, only allow new results from the currently checked graph.iterator

func (*Or) Optimize

func (it *Or) Optimize() (graph.Iterator, bool)

func (*Or) Reset

func (it *Or) Reset()

Reset all internal iterators

func (*Or) Result

func (it *Or) Result() graph.Value

func (*Or) ResultTree

func (it *Or) ResultTree() *graph.ResultTree

DEPRECATED Returns the ResultTree for this graph.iterator, recurses to it's subiterators.

func (*Or) Size

func (it *Or) Size() (int64, bool)

Returns the approximate size of the Or graph.iterator. Because we're dealing with a union, we know that the largest we can be is the sum of all the iterators, or in the case of short-circuiting, the longest.

func (*Or) Stats

func (it *Or) Stats() graph.IteratorStats

func (*Or) SubIterators

func (it *Or) SubIterators() []graph.Iterator

Returns a list.List of the subiterators, in order. The returned slice must not be modified.

func (*Or) TagResults

func (it *Or) TagResults(dst map[string]graph.Value)

Overrides BaseIterator TagResults, as it needs to add it's own results and recurse down it's subiterators.

func (*Or) Tagger

func (it *Or) Tagger() *graph.Tagger

func (*Or) Type

func (it *Or) Type() graph.Type

Register this as an "or" graph.iterator.

func (*Or) UID

func (it *Or) UID() uint64

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL