graph/iterator: add fast paths for node slices and add tests
Fix bugs in NodeSlice methods:
ImplicitNodes did not return nil for an empty set of nodes.
OrderedNodes returned one too many nodes if Next has been called.
MODIFY
graph/iterator/nodes.go
graph/iterator/nodes.go
@@ -59,10 +59,7 @@ func (n *OrderedNodes) NodeSlice() []graph.Node {
if n.idx >= len(n.nodes) {
return nil
}
- idx := n.idx
- if idx == -1 {
- idx = 0
- }
+ idx := n.idx + 1
n.idx = len(n.nodes)
return n.nodes[idx:]
}
@@ -121,6 +118,9 @@ func (n *ImplicitNodes) Reset() {
// NodeSlice returns all the remaining nodes in the iterator and advances
// the iterator.
func (n *ImplicitNodes) NodeSlice() []graph.Node {
+ if n.Len() == 0 {
+ return nil
+ }
nodes := make([]graph.Node, 0, n.Len())
for n.curr++; n.curr < n.end; n.curr++ {
nodes = append(nodes, n.newNode(n.curr))
@@ -179,6 +179,21 @@ func (n *Nodes) Reset() {
n.iter = n.nodes.MapRange()
}
+// NodeSlice returns all the remaining nodes in the iterator and advances
+// the iterator. The order of nodes within the returned slice is not
+// specified.
+func (n *Nodes) NodeSlice() []graph.Node {
+ if n.Len() == 0 {
+ return nil
+ }
+ nodes := make([]graph.Node, 0, n.Len())
+ for n.iter.Next() {
+ nodes = append(nodes, n.iter.Value().Interface().(graph.Node))
+ }
+ n.pos = n.nodes.Len()
+ return nodes
+}
+
// NodesByEdge implements the graph.Nodes interfaces.
// The iteration order of Nodes is randomized.
type NodesByEdge struct {
@@ -275,3 +290,18 @@ func (n *NodesByEdge) Reset() {
n.pos = 0
n.iter = n.edges.MapRange()
}
+
+// NodeSlice returns all the remaining nodes in the iterator and advances
+// the iterator. The order of nodes within the returned slice is not
+// specified.
+func (n *NodesByEdge) NodeSlice() []graph.Node {
+ if n.Len() == 0 {
+ return nil
+ }
+ nodes := make([]graph.Node, 0, n.Len())
+ for n.iter.Next() {
+ nodes = append(nodes, n.nodes[n.iter.Key().Int()])
+ }
+ n.pos = n.edges.Len()
+ return nodes
+}

MODIFY
graph/iterator/nodes_test.go
graph/iterator/nodes_test.go
@@ -6,9 +6,11 @@ package iterator_test
import (
"reflect"
+ "sort"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
)
@@ -443,3 +445,108 @@ func TestNodesByWeightedLinesIterate(t *testing.T) {
}
}
}
+
+type nodeSlicer interface {
+ graph.Nodes
+ graph.NodeSlicer
+}
+
+var nodeSlicerTests = []struct {
+ nodes nodeSlicer
+ want []graph.Node
+}{
+ {
+ nodes: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}),
+ want: []graph.Node{simple.Node(1)},
+ },
+ {
+ nodes: iterator.NewOrderedNodes([]graph.Node{simple.Node(1), simple.Node(2), simple.Node(3)}),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3)},
+ },
+
+ {
+ nodes: iterator.NewImplicitNodes(1, 2, func(id int) graph.Node { return simple.Node(id) }),
+ want: []graph.Node{simple.Node(1)},
+ },
+ {
+ nodes: iterator.NewImplicitNodes(1, 4, func(id int) graph.Node { return simple.Node(id) }),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3)},
+ },
+
+ {
+ nodes: iterator.NewNodes(map[int64]graph.Node{1: simple.Node(1)}),
+ want: []graph.Node{simple.Node(1)},
+ },
+ {
+ nodes: iterator.NewNodes(map[int64]graph.Node{1: simple.Node(1), 2: simple.Node(2), 3: simple.Node(3)}),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3)},
+ },
+ {
+ nodes: iterator.NewNodes(map[int64]graph.Node{1: simple.Node(1), 2: simple.Node(2), 3: simple.Node(3), 4: simple.Node(4), 5: simple.Node(5)}),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3), simple.Node(4), simple.Node(5)},
+ },
+ {
+ nodes: iterator.NewNodes(map[int64]graph.Node{5: simple.Node(5), 3: simple.Node(3), 2: simple.Node(2), 1: simple.Node(1)}),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3), simple.Node(5)},
+ },
+
+ // The actual values of the edges stored in the edge
+ // map leading to each node are not used, so they are
+ // filled with nil values.
+ //
+ // The three other constructors for NodesByEdge are not
+ // tested for this behaviour since they have already
+ // been tested above.
+ {
+ nodes: iterator.NewNodesByEdge(
+ map[int64]graph.Node{1: simple.Node(1), 2: simple.Node(2), 3: simple.Node(3), 4: simple.Node(4), 5: simple.Node(5)},
+ map[int64]graph.Edge{1: nil},
+ ),
+ want: []graph.Node{simple.Node(1)},
+ },
+ {
+ nodes: iterator.NewNodesByEdge(
+ map[int64]graph.Node{1: simple.Node(1), 2: simple.Node(2), 3: simple.Node(3), 4: simple.Node(4), 5: simple.Node(5)},
+ map[int64]graph.Edge{1: nil, 2: nil, 3: nil, 5: nil},
+ ),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3), simple.Node(5)},
+ },
+ {
+ nodes: iterator.NewNodesByEdge(
+ map[int64]graph.Node{1: simple.Node(1), 2: simple.Node(2), 3: simple.Node(3), 4: simple.Node(4), 5: simple.Node(5)},
+ map[int64]graph.Edge{5: nil, 3: nil, 2: nil, 1: nil},
+ ),
+ want: []graph.Node{simple.Node(1), simple.Node(2), simple.Node(3), simple.Node(5)},
+ },
+}
+
+func TestNodeSlicers(t *testing.T) {
+ for k, test := range nodeSlicerTests {
+ wantLen := test.nodes.Len()
+ for i := 0; i < wantLen; i++ {
+ var gotIter []graph.Node
+ for n := 0; n < i; n++ {
+ ok := test.nodes.Next()
+ if !ok {
+ t.Errorf("test %d: unexpected failed Next call at position %d of len %d", k, n, wantLen)
+ }
+ gotIter = append(gotIter, test.nodes.Node())
+ }
+ gotSlice := test.nodes.NodeSlice()
+ if test.nodes.Next() {
+ t.Errorf("test %d: expected no further iteration possible after NodeSlice with %d pre-iterations of %d", k, i, wantLen)
+ }
+
+ if gotLen := len(gotIter) + len(gotSlice); gotLen != wantLen {
+ t.Errorf("test %d: unexpected total node count: got:%d want:%d", k, gotLen, wantLen)
+ }
+ got := append(gotIter, gotSlice...)
+ sort.Sort(ordered.ByID(got))
+ if !reflect.DeepEqual(got, test.want) {
+ t.Errorf("test %d: unexpected node slice:\ngot: %v\nwant:%v", k, got, test.want)
+ }
+
+ test.nodes.Reset()
+ }
+ }
+}

graph/iterator: add fast paths for node slices and add tests

Fix bugs in NodeSlice methods:

- ImplicitNodes did not return nil for an empty set of nodes.
- OrderedNodes returned one too many nodes if Next has been called.