forked from cayleygraph/cayley
-
Notifications
You must be signed in to change notification settings - Fork 0
/
not_iterator.go
185 lines (154 loc) · 4.23 KB
/
not_iterator.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
package iterator
import (
"github.com/google/cayley/graph"
)
// Not iterator acts like a complement for the primary iterator.
// It will return all the vertices which are not part of the primary iterator.
type Not struct {
uid uint64
tags graph.Tagger
primaryIt graph.Iterator
allIt graph.Iterator
result graph.Value
runstats graph.IteratorStats
err error
}
func NewNot(primaryIt, allIt graph.Iterator) *Not {
return &Not{
uid: NextUID(),
primaryIt: primaryIt,
allIt: allIt,
}
}
func (it *Not) UID() uint64 {
return it.uid
}
// Reset resets the internal iterators and the iterator itself.
func (it *Not) Reset() {
it.result = nil
it.primaryIt.Reset()
it.allIt.Reset()
}
func (it *Not) Tagger() *graph.Tagger {
return &it.tags
}
func (it *Not) TagResults(dst map[string]graph.Value) {
for _, tag := range it.tags.Tags() {
dst[tag] = it.Result()
}
for tag, value := range it.tags.Fixed() {
dst[tag] = value
}
if it.primaryIt != nil {
it.primaryIt.TagResults(dst)
}
}
func (it *Not) Clone() graph.Iterator {
not := NewNot(it.primaryIt.Clone(), it.allIt.Clone())
not.tags.CopyFrom(it)
return not
}
// SubIterators returns a slice of the sub iterators.
// The first iterator is the primary iterator, for which the complement
// is generated.
func (it *Not) SubIterators() []graph.Iterator {
return []graph.Iterator{it.primaryIt, it.allIt}
}
// DEPRECATED
func (it *Not) ResultTree() *graph.ResultTree {
tree := graph.NewResultTree(it.Result())
tree.AddSubtree(it.primaryIt.ResultTree())
tree.AddSubtree(it.allIt.ResultTree())
return tree
}
// Next advances the Not iterator. It returns whether there is another valid
// new value. It fetches the next value of the all iterator which is not
// contained by the primary iterator.
func (it *Not) Next() bool {
graph.NextLogIn(it)
it.runstats.Next += 1
for graph.Next(it.allIt) {
if curr := it.allIt.Result(); !it.primaryIt.Contains(curr) {
it.result = curr
it.runstats.ContainsNext += 1
return graph.NextLogOut(it, curr, true)
}
}
it.err = it.allIt.Err()
return graph.NextLogOut(it, nil, false)
}
func (it *Not) Err() error {
return it.err
}
func (it *Not) Result() graph.Value {
return it.result
}
// Contains checks whether the passed value is part of the primary iterator's
// complement. For a valid value, it updates the Result returned by the iterator
// to the value itself.
func (it *Not) Contains(val graph.Value) bool {
graph.ContainsLogIn(it, val)
it.runstats.Contains += 1
if it.primaryIt.Contains(val) {
return graph.ContainsLogOut(it, val, false)
}
it.err = it.primaryIt.Err()
if it.err != nil {
// Explicitly return 'false', since an error occurred.
return false
}
it.result = val
return graph.ContainsLogOut(it, val, true)
}
// NextPath checks whether there is another path. Not applicable, hence it will
// return false.
func (it *Not) NextPath() bool {
return false
}
// Close closes the primary and all iterators. It closes all subiterators
// it can, but returns the first error it encounters.
func (it *Not) Close() error {
err := it.primaryIt.Close()
_err := it.allIt.Close()
if _err != nil && err == nil {
err = _err
}
return err
}
func (it *Not) Type() graph.Type { return graph.Not }
func (it *Not) Optimize() (graph.Iterator, bool) {
// TODO - consider wrapping the primaryIt with a MaterializeIt
optimizedPrimaryIt, optimized := it.primaryIt.Optimize()
if optimized {
it.primaryIt = optimizedPrimaryIt
}
return it, false
}
func (it *Not) Stats() graph.IteratorStats {
primaryStats := it.primaryIt.Stats()
allStats := it.allIt.Stats()
return graph.IteratorStats{
NextCost: allStats.NextCost + primaryStats.ContainsCost,
ContainsCost: primaryStats.ContainsCost,
Size: allStats.Size - primaryStats.Size,
Next: it.runstats.Next,
Contains: it.runstats.Contains,
ContainsNext: it.runstats.ContainsNext,
}
}
func (it *Not) Size() (int64, bool) {
return it.Stats().Size, false
}
func (it *Not) Describe() graph.Description {
subIts := []graph.Description{
it.primaryIt.Describe(),
it.allIt.Describe(),
}
return graph.Description{
UID: it.UID(),
Type: it.Type(),
Tags: it.tags.Tags(),
Iterators: subIts,
}
}
var _ graph.Nexter = &Not{}