1// Copyright ©2018 The Gonum Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package graph
6
7// Iterator is an item iterator.
8type Iterator interface {
9	// Next advances the iterator and returns whether
10	// the next call to the item method will return a
11	// non-nil item.
12	//
13	// Next should be called prior to any call to the
14	// iterator's item retrieval method after the
15	// iterator has been obtained or reset.
16	//
17	// The order of iteration is implementation
18	// dependent.
19	Next() bool
20
21	// Len returns the number of items remaining in the
22	// iterator.
23	//
24	// If the number of items in the iterator is unknown,
25	// too large to materialize or too costly to calculate
26	// then Len may return a negative value.
27	// In this case the consuming function must be able
28	// to operate on the items of the iterator directly
29	// without materializing the items into a slice.
30	// The magnitude of a negative length has
31	// implementation-dependent semantics.
32	Len() int
33
34	// Reset returns the iterator to its start position.
35	Reset()
36}
37
38// Nodes is a Node iterator.
39type Nodes interface {
40	Iterator
41
42	// Node returns the current Node from the iterator.
43	Node() Node
44}
45
46// NodeSlicer wraps the NodeSlice method.
47type NodeSlicer interface {
48	// NodeSlice returns the set of nodes remaining
49	// to be iterated by a Nodes iterator.
50	// The holder of the iterator may arbitrarily
51	// change elements in the returned slice, but
52	// those changes may be reflected to other
53	// iterators.
54	NodeSlice() []Node
55}
56
57// NodesOf returns it.Len() nodes from it. If it is a NodeSlicer, the NodeSlice method
58// is used to obtain the nodes. It is safe to pass a nil Nodes to NodesOf.
59func NodesOf(it Nodes) []Node {
60	if it == nil {
61		return nil
62	}
63	n := it.Len()
64	switch {
65	case n == 0:
66		return nil
67	case n < 0:
68		n = 0
69	}
70	switch it := it.(type) {
71	case NodeSlicer:
72		return it.NodeSlice()
73	}
74	nodes := make([]Node, 0, n)
75	for it.Next() {
76		nodes = append(nodes, it.Node())
77	}
78	if len(nodes) == 0 {
79		return nil
80	}
81	return nodes
82}
83
84// Edges is an Edge iterator.
85type Edges interface {
86	Iterator
87
88	// Edge returns the current Edge from the iterator.
89	Edge() Edge
90}
91
92// EdgeSlicer wraps the EdgeSlice method.
93type EdgeSlicer interface {
94	// EdgeSlice returns the set of edges remaining
95	// to be iterated by an Edges iterator.
96	// The holder of the iterator may arbitrarily
97	// change elements in the returned slice, but
98	// those changes may be reflected to other
99	// iterators.
100	EdgeSlice() []Edge
101}
102
103// EdgesOf returns it.Len() nodes from it. If it is an EdgeSlicer, the EdgeSlice method is used
104// to obtain the edges. It is safe to pass a nil Edges to EdgesOf.
105func EdgesOf(it Edges) []Edge {
106	if it == nil {
107		return nil
108	}
109	n := it.Len()
110	switch {
111	case n == 0:
112		return nil
113	case n < 0:
114		n = 0
115	}
116	switch it := it.(type) {
117	case EdgeSlicer:
118		return it.EdgeSlice()
119	}
120	edges := make([]Edge, 0, n)
121	for it.Next() {
122		edges = append(edges, it.Edge())
123	}
124	if len(edges) == 0 {
125		return nil
126	}
127	return edges
128}
129
130// WeightedEdges is a WeightedEdge iterator.
131type WeightedEdges interface {
132	Iterator
133
134	// Edge returns the current Edge from the iterator.
135	WeightedEdge() WeightedEdge
136}
137
138// WeightedEdgeSlicer wraps the WeightedEdgeSlice method.
139type WeightedEdgeSlicer interface {
140	// EdgeSlice returns the set of edges remaining
141	// to be iterated by an Edges iterator.
142	// The holder of the iterator may arbitrarily
143	// change elements in the returned slice, but
144	// those changes may be reflected to other
145	// iterators.
146	WeightedEdgeSlice() []WeightedEdge
147}
148
149// WeightedEdgesOf returns it.Len() weighted edge from it. If it is a WeightedEdgeSlicer, the
150// WeightedEdgeSlice method is used to obtain the edges. It is safe to pass a nil WeightedEdges
151// to WeightedEdgesOf.
152func WeightedEdgesOf(it WeightedEdges) []WeightedEdge {
153	if it == nil {
154		return nil
155	}
156	n := it.Len()
157	switch {
158	case n == 0:
159		return nil
160	case n < 0:
161		n = 0
162	}
163	switch it := it.(type) {
164	case WeightedEdgeSlicer:
165		return it.WeightedEdgeSlice()
166	}
167	edges := make([]WeightedEdge, 0, n)
168	for it.Next() {
169		edges = append(edges, it.WeightedEdge())
170	}
171	if len(edges) == 0 {
172		return nil
173	}
174	return edges
175}
176
177// Lines is a Line iterator.
178type Lines interface {
179	Iterator
180
181	// Line returns the current Line from the iterator.
182	Line() Line
183}
184
185// LineSlicer wraps the LineSlice method.
186type LineSlicer interface {
187	// LineSlice returns the set of lines remaining
188	// to be iterated by an Lines iterator.
189	// The holder of the iterator may arbitrarily
190	// change elements in the returned slice, but
191	// those changes may be reflected to other
192	// iterators.
193	LineSlice() []Line
194}
195
196// LinesOf returns it.Len() nodes from it. If it is a LineSlicer, the LineSlice method is used
197// to obtain the lines. It is safe to pass a nil Lines to LinesOf.
198func LinesOf(it Lines) []Line {
199	if it == nil {
200		return nil
201	}
202	n := it.Len()
203	switch {
204	case n == 0:
205		return nil
206	case n < 0:
207		n = 0
208	}
209	switch it := it.(type) {
210	case LineSlicer:
211		return it.LineSlice()
212	}
213	lines := make([]Line, 0, n)
214	for it.Next() {
215		lines = append(lines, it.Line())
216	}
217	if len(lines) == 0 {
218		return nil
219	}
220	return lines
221}
222
223// WeightedLines is a WeightedLine iterator.
224type WeightedLines interface {
225	Iterator
226
227	// Line returns the current Line from the iterator.
228	WeightedLine() WeightedLine
229}
230
231// WeightedLineSlicer wraps the WeightedLineSlice method.
232type WeightedLineSlicer interface {
233	// LineSlice returns the set of lines remaining
234	// to be iterated by an Lines iterator.
235	// The holder of the iterator may arbitrarily
236	// change elements in the returned slice, but
237	// those changes may be reflected to other
238	// iterators.
239	WeightedLineSlice() []WeightedLine
240}
241
242// WeightedLinesOf returns it.Len() weighted line from it. If it is a WeightedLineSlicer, the
243// WeightedLineSlice method is used to obtain the lines. It is safe to pass a nil WeightedLines
244// to WeightedLinesOf.
245func WeightedLinesOf(it WeightedLines) []WeightedLine {
246	if it == nil {
247		return nil
248	}
249	n := it.Len()
250	switch {
251	case n == 0:
252		return nil
253	case n < 0:
254		n = 0
255	}
256	switch it := it.(type) {
257	case WeightedLineSlicer:
258		return it.WeightedLineSlice()
259	}
260	lines := make([]WeightedLine, 0, n)
261	for it.Next() {
262		lines = append(lines, it.WeightedLine())
263	}
264	if len(lines) == 0 {
265		return nil
266	}
267	return lines
268}
269
270// Empty is an empty set of nodes, edges or lines. It should be used when
271// a graph returns a zero-length Iterator. Empty implements the slicer
272// interfaces for nodes, edges and lines, returning nil for each of these.
273const Empty = nothing
274
275var (
276	_ Iterator           = Empty
277	_ Nodes              = Empty
278	_ NodeSlicer         = Empty
279	_ Edges              = Empty
280	_ EdgeSlicer         = Empty
281	_ WeightedEdges      = Empty
282	_ WeightedEdgeSlicer = Empty
283	_ Lines              = Empty
284	_ LineSlicer         = Empty
285	_ WeightedLines      = Empty
286	_ WeightedLineSlicer = Empty
287)
288
289const nothing = empty(0)
290
291type empty int
292
293func (empty) Next() bool                        { return false }
294func (empty) Len() int                          { return 0 }
295func (empty) Reset()                            {}
296func (empty) Node() Node                        { return nil }
297func (empty) NodeSlice() []Node                 { return nil }
298func (empty) Edge() Edge                        { return nil }
299func (empty) EdgeSlice() []Edge                 { return nil }
300func (empty) WeightedEdge() WeightedEdge        { return nil }
301func (empty) WeightedEdgeSlice() []WeightedEdge { return nil }
302func (empty) Line() Line                        { return nil }
303func (empty) LineSlice() []Line                 { return nil }
304func (empty) WeightedLine() WeightedLine        { return nil }
305func (empty) WeightedLineSlice() []WeightedLine { return nil }
306
307func (empty) String() string   { return "<empty>" }
308func (empty) GoString() string { return "graph.Empty" }
309