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