| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 // This code was auto-generated, is not intended to be edited, and is subject to | |
| 6 // significant change. Please see the README file for more information. | |
| 7 | |
| 8 library engine.utilities.collection; | |
| 9 | |
| 10 import "dart:math" as math; | |
| 11 import 'dart:collection'; | |
| 12 | |
| 13 import 'java_core.dart'; | |
| 14 import 'scanner.dart' show Token; | |
| 15 | |
| 16 /** | |
| 17 * The class `BooleanArray` defines methods for operating on integers as if they
were arrays | |
| 18 * of booleans. These arrays can be indexed by either integers or by enumeration
constants. | |
| 19 */ | |
| 20 class BooleanArray { | |
| 21 /** | |
| 22 * Return the value of the element at the given index. | |
| 23 * | |
| 24 * @param array the array being accessed | |
| 25 * @param index the index of the element being accessed | |
| 26 * @return the value of the element at the given index | |
| 27 * @throws IndexOutOfBoundsException if the index is not between zero (0) and
31, inclusive | |
| 28 */ | |
| 29 static bool get(int array, int index) { | |
| 30 _checkIndex(index); | |
| 31 return (array & (1 << index)) > 0; | |
| 32 } | |
| 33 | |
| 34 /** | |
| 35 * Return the value of the element at the given index. | |
| 36 * | |
| 37 * @param array the array being accessed | |
| 38 * @param index the index of the element being accessed | |
| 39 * @return the value of the element at the given index | |
| 40 * @throws IndexOutOfBoundsException if the index is not between zero (0) and
31, inclusive | |
| 41 */ | |
| 42 static bool getEnum(int array, Enum index) => get(array, index.ordinal); | |
| 43 | |
| 44 /** | |
| 45 * Set the value of the element at the given index to the given value. | |
| 46 * | |
| 47 * @param array the array being modified | |
| 48 * @param index the index of the element being set | |
| 49 * @param value the value to be assigned to the element | |
| 50 * @return the updated value of the array | |
| 51 * @throws IndexOutOfBoundsException if the index is not between zero (0) and
31, inclusive | |
| 52 */ | |
| 53 static int set(int array, int index, bool value) { | |
| 54 _checkIndex(index); | |
| 55 if (value) { | |
| 56 return array | (1 << index); | |
| 57 } else { | |
| 58 return array & ~(1 << index); | |
| 59 } | |
| 60 } | |
| 61 | |
| 62 /** | |
| 63 * Set the value of the element at the given index to the given value. | |
| 64 * | |
| 65 * @param array the array being modified | |
| 66 * @param index the index of the element being set | |
| 67 * @param value the value to be assigned to the element | |
| 68 * @return the updated value of the array | |
| 69 * @throws IndexOutOfBoundsException if the index is not between zero (0) and
31, inclusive | |
| 70 */ | |
| 71 static int setEnum(int array, Enum index, bool value) => | |
| 72 set(array, index.ordinal, value); | |
| 73 | |
| 74 /** | |
| 75 * Throw an exception if the index is not within the bounds allowed for an int
eger-encoded array | |
| 76 * of boolean values. | |
| 77 * | |
| 78 * @throws IndexOutOfBoundsException if the index is not between zero (0) and
31, inclusive | |
| 79 */ | |
| 80 static void _checkIndex(int index) { | |
| 81 if (index < 0 || index > 30) { | |
| 82 throw new RangeError("Index not between 0 and 30: $index"); | |
| 83 } | |
| 84 } | |
| 85 } | |
| 86 | |
| 87 /** | |
| 88 * Instances of the class `DirectedGraph` implement a directed graph in which th
e nodes are | |
| 89 * arbitrary (client provided) objects and edges are represented implicitly. The
graph will allow an | |
| 90 * edge from any node to any other node, including itself, but will not represen
t multiple edges | |
| 91 * between the same pair of nodes. | |
| 92 * | |
| 93 * @param N the type of the nodes in the graph | |
| 94 */ | |
| 95 class DirectedGraph<N> { | |
| 96 /** | |
| 97 * The table encoding the edges in the graph. An edge is represented by an ent
ry mapping the head | |
| 98 * to a set of tails. Nodes that are not the head of any edge are represented
by an entry mapping | |
| 99 * the node to an empty set of tails. | |
| 100 */ | |
| 101 HashMap<N, HashSet<N>> _edges = new HashMap<N, HashSet<N>>(); | |
| 102 | |
| 103 /** | |
| 104 * Return `true` if this graph is empty. | |
| 105 * | |
| 106 * @return `true` if this graph is empty | |
| 107 */ | |
| 108 bool get isEmpty => _edges.isEmpty; | |
| 109 | |
| 110 /** | |
| 111 * Return the number of nodes in this graph. | |
| 112 * | |
| 113 * @return the number of nodes in this graph | |
| 114 */ | |
| 115 int get nodeCount => _edges.length; | |
| 116 | |
| 117 /** | |
| 118 * Return a set of all nodes in the graph. | |
| 119 */ | |
| 120 Set<N> get nodes => _edges.keys.toSet(); | |
| 121 | |
| 122 /** | |
| 123 * Add an edge from the given head node to the given tail node. Both nodes wil
l be a part of the | |
| 124 * graph after this method is invoked, whether or not they were before. | |
| 125 * | |
| 126 * @param head the node at the head of the edge | |
| 127 * @param tail the node at the tail of the edge | |
| 128 */ | |
| 129 void addEdge(N head, N tail) { | |
| 130 // | |
| 131 // First, ensure that the tail is a node known to the graph. | |
| 132 // | |
| 133 if (_edges[tail] == null) { | |
| 134 _edges[tail] = new HashSet<N>(); | |
| 135 } | |
| 136 // | |
| 137 // Then create the edge. | |
| 138 // | |
| 139 HashSet<N> tails = _edges[head]; | |
| 140 if (tails == null) { | |
| 141 tails = new HashSet<N>(); | |
| 142 _edges[head] = tails; | |
| 143 } | |
| 144 tails.add(tail); | |
| 145 } | |
| 146 | |
| 147 /** | |
| 148 * Add the given node to the set of nodes in the graph. | |
| 149 * | |
| 150 * @param node the node to be added | |
| 151 */ | |
| 152 void addNode(N node) { | |
| 153 HashSet<N> tails = _edges[node]; | |
| 154 if (tails == null) { | |
| 155 _edges[node] = new HashSet<N>(); | |
| 156 } | |
| 157 } | |
| 158 | |
| 159 /** | |
| 160 * Run a topological sort of the graph. Since the graph may contain cycles, th
is results in a list | |
| 161 * of strongly connected components rather than a list of nodes. The nodes in
each strongly | |
| 162 * connected components only have edges that point to nodes in the same compon
ent or earlier | |
| 163 * components. | |
| 164 */ | |
| 165 List<List<N>> computeTopologicalSort() { | |
| 166 DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this); | |
| 167 return finder.computeTopologicalSort(); | |
| 168 } | |
| 169 | |
| 170 /** | |
| 171 * Return true if the graph contains at least one path from `source` to `desti
nation`. | |
| 172 */ | |
| 173 bool containsPath(N source, N destination) { | |
| 174 HashSet<N> nodesVisited = new HashSet<N>(); | |
| 175 return _containsPathInternal(source, destination, nodesVisited); | |
| 176 } | |
| 177 | |
| 178 /** | |
| 179 * Return a list of nodes that form a cycle containing the given node. If the
node is not part of | |
| 180 * this graph, then a list containing only the node itself will be returned. | |
| 181 * | |
| 182 * @return a list of nodes that form a cycle containing the given node | |
| 183 */ | |
| 184 List<N> findCycleContaining(N node) { | |
| 185 if (node == null) { | |
| 186 throw new IllegalArgumentException(); | |
| 187 } | |
| 188 DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this); | |
| 189 return finder.componentContaining(node); | |
| 190 } | |
| 191 | |
| 192 /** | |
| 193 * Return a set containing the tails of edges that have the given node as thei
r head. The set will | |
| 194 * be empty if there are no such edges or if the node is not part of the graph
. Clients must not | |
| 195 * modify the returned set. | |
| 196 * | |
| 197 * @param head the node at the head of all of the edges whose tails are to be
returned | |
| 198 * @return a set containing the tails of edges that have the given node as the
ir head | |
| 199 */ | |
| 200 Set<N> getTails(N head) { | |
| 201 HashSet<N> tails = _edges[head]; | |
| 202 if (tails == null) { | |
| 203 return new HashSet<N>(); | |
| 204 } | |
| 205 return tails; | |
| 206 } | |
| 207 | |
| 208 /** | |
| 209 * Remove all of the given nodes from this graph. As a consequence, any edges
for which those | |
| 210 * nodes were either a head or a tail will also be removed. | |
| 211 * | |
| 212 * @param nodes the nodes to be removed | |
| 213 */ | |
| 214 void removeAllNodes(List<N> nodes) { | |
| 215 for (N node in nodes) { | |
| 216 removeNode(node); | |
| 217 } | |
| 218 } | |
| 219 | |
| 220 /** | |
| 221 * Remove the edge from the given head node to the given tail node. If there w
as no such edge then | |
| 222 * the graph will be unmodified: the number of edges will be the same and the
set of nodes will be | |
| 223 * the same (neither node will either be added or removed). | |
| 224 * | |
| 225 * @param head the node at the head of the edge | |
| 226 * @param tail the node at the tail of the edge | |
| 227 * @return `true` if the graph was modified as a result of this operation | |
| 228 */ | |
| 229 void removeEdge(N head, N tail) { | |
| 230 HashSet<N> tails = _edges[head]; | |
| 231 if (tails != null) { | |
| 232 tails.remove(tail); | |
| 233 } | |
| 234 } | |
| 235 | |
| 236 /** | |
| 237 * Remove the given node from this graph. As a consequence, any edges for whic
h that node was | |
| 238 * either a head or a tail will also be removed. | |
| 239 * | |
| 240 * @param node the node to be removed | |
| 241 */ | |
| 242 void removeNode(N node) { | |
| 243 _edges.remove(node); | |
| 244 for (HashSet<N> tails in _edges.values) { | |
| 245 tails.remove(node); | |
| 246 } | |
| 247 } | |
| 248 | |
| 249 /** | |
| 250 * Find one node (referred to as a sink node) that has no outgoing edges (that
is, for which there | |
| 251 * are no edges that have that node as the head of the edge) and remove it fro
m this graph. Return | |
| 252 * the node that was removed, or `null` if there are no such nodes either beca
use the graph | |
| 253 * is empty or because every node in the graph has at least one outgoing edge.
As a consequence of | |
| 254 * removing the node from the graph any edges for which that node was a tail w
ill also be removed. | |
| 255 * | |
| 256 * @return the sink node that was removed | |
| 257 */ | |
| 258 N removeSink() { | |
| 259 N sink = _findSink(); | |
| 260 if (sink == null) { | |
| 261 return null; | |
| 262 } | |
| 263 removeNode(sink); | |
| 264 return sink; | |
| 265 } | |
| 266 | |
| 267 bool _containsPathInternal(N source, N destination, HashSet<N> nodesVisited) { | |
| 268 if (identical(source, destination)) { | |
| 269 return true; | |
| 270 } | |
| 271 HashSet<N> tails = _edges[source]; | |
| 272 if (tails != null) { | |
| 273 nodesVisited.add(source); | |
| 274 for (N tail in tails) { | |
| 275 if (!nodesVisited.contains(tail)) { | |
| 276 if (_containsPathInternal(tail, destination, nodesVisited)) { | |
| 277 return true; | |
| 278 } | |
| 279 } | |
| 280 } | |
| 281 } | |
| 282 return false; | |
| 283 } | |
| 284 | |
| 285 /** | |
| 286 * Return one node that has no outgoing edges (that is, for which there are no
edges that have | |
| 287 * that node as the head of the edge), or `null` if there are no such nodes. | |
| 288 * | |
| 289 * @return a sink node | |
| 290 */ | |
| 291 N _findSink() { | |
| 292 for (N key in _edges.keys) { | |
| 293 if (_edges[key].isEmpty) return key; | |
| 294 } | |
| 295 return null; | |
| 296 } | |
| 297 } | |
| 298 | |
| 299 /** | |
| 300 * Instances of the class `NodeInfo` are used by the [SccFinder] to maintain | |
| 301 * information about the nodes that have been examined. | |
| 302 * | |
| 303 * @param N the type of the nodes corresponding to the entries | |
| 304 */ | |
| 305 class DirectedGraph_NodeInfo<N> { | |
| 306 /** | |
| 307 * The depth of this node. | |
| 308 */ | |
| 309 int index = 0; | |
| 310 | |
| 311 /** | |
| 312 * The depth of the first node in a cycle. | |
| 313 */ | |
| 314 int lowlink = 0; | |
| 315 | |
| 316 /** | |
| 317 * A flag indicating whether the corresponding node is on the stack. Used to r
emove the need for | |
| 318 * searching a collection for the node each time the question needs to be aske
d. | |
| 319 */ | |
| 320 bool onStack = false; | |
| 321 | |
| 322 /** | |
| 323 * The component that contains the corresponding node. | |
| 324 */ | |
| 325 List<N> component; | |
| 326 | |
| 327 /** | |
| 328 * Initialize a newly created information holder to represent a node at the gi
ven depth. | |
| 329 * | |
| 330 * @param depth the depth of the node being represented | |
| 331 */ | |
| 332 DirectedGraph_NodeInfo(int depth) { | |
| 333 index = depth; | |
| 334 lowlink = depth; | |
| 335 onStack = false; | |
| 336 } | |
| 337 } | |
| 338 | |
| 339 /** | |
| 340 * Instances of the class `SccFinder` implement Tarjan's Algorithm for finding t
he strongly | |
| 341 * connected components in a graph. | |
| 342 */ | |
| 343 class DirectedGraph_SccFinder<N> { | |
| 344 /** | |
| 345 * The graph to work with. | |
| 346 */ | |
| 347 final DirectedGraph<N> _graph; | |
| 348 | |
| 349 /** | |
| 350 * The index used to uniquely identify the depth of nodes. | |
| 351 */ | |
| 352 int _index = 0; | |
| 353 | |
| 354 /** | |
| 355 * The stack of nodes that are being visited in order to identify components. | |
| 356 */ | |
| 357 List<N> _stack = new List<N>(); | |
| 358 | |
| 359 /** | |
| 360 * A table mapping nodes to information about the nodes that is used by this a
lgorithm. | |
| 361 */ | |
| 362 HashMap<N, DirectedGraph_NodeInfo<N>> _nodeMap = | |
| 363 new HashMap<N, DirectedGraph_NodeInfo<N>>(); | |
| 364 | |
| 365 /** | |
| 366 * A list of all strongly connected components found, in topological sort orde
r (each node in a | |
| 367 * strongly connected component only has edges that point to nodes in the same
component or | |
| 368 * earlier components). | |
| 369 */ | |
| 370 List<List<N>> _allComponents = new List<List<N>>(); | |
| 371 | |
| 372 /** | |
| 373 * Initialize a newly created finder. | |
| 374 */ | |
| 375 DirectedGraph_SccFinder(this._graph) : super(); | |
| 376 | |
| 377 /** | |
| 378 * Return a list containing the nodes that are part of the strongly connected
component that | |
| 379 * contains the given node. | |
| 380 * | |
| 381 * @param node the node used to identify the strongly connected component to b
e returned | |
| 382 * @return the nodes that are part of the strongly connected component that co
ntains the given | |
| 383 * node | |
| 384 */ | |
| 385 List<N> componentContaining(N node) => _strongConnect(node).component; | |
| 386 | |
| 387 /** | |
| 388 * Run Tarjan's algorithm and return the resulting list of strongly connected
components. The | |
| 389 * list is in topological sort order (each node in a strongly connected compon
ent only has edges | |
| 390 * that point to nodes in the same component or earlier components). | |
| 391 */ | |
| 392 List<List<N>> computeTopologicalSort() { | |
| 393 for (N node in _graph._edges.keys.toSet()) { | |
| 394 DirectedGraph_NodeInfo<N> nodeInfo = _nodeMap[node]; | |
| 395 if (nodeInfo == null) { | |
| 396 _strongConnect(node); | |
| 397 } | |
| 398 } | |
| 399 return _allComponents; | |
| 400 } | |
| 401 | |
| 402 /** | |
| 403 * Remove and return the top-most element from the stack. | |
| 404 * | |
| 405 * @return the element that was removed | |
| 406 */ | |
| 407 N _pop() { | |
| 408 N node = _stack.removeAt(_stack.length - 1); | |
| 409 _nodeMap[node].onStack = false; | |
| 410 return node; | |
| 411 } | |
| 412 | |
| 413 /** | |
| 414 * Add the given node to the stack. | |
| 415 * | |
| 416 * @param node the node to be added to the stack | |
| 417 */ | |
| 418 void _push(N node) { | |
| 419 _nodeMap[node].onStack = true; | |
| 420 _stack.add(node); | |
| 421 } | |
| 422 | |
| 423 /** | |
| 424 * Compute the strongly connected component that contains the given node as we
ll as any | |
| 425 * components containing nodes that are reachable from the given component. | |
| 426 * | |
| 427 * @param v the node from which the search will begin | |
| 428 * @return the information about the given node | |
| 429 */ | |
| 430 DirectedGraph_NodeInfo<N> _strongConnect(N v) { | |
| 431 // | |
| 432 // Set the depth index for v to the smallest unused index | |
| 433 // | |
| 434 DirectedGraph_NodeInfo<N> vInfo = new DirectedGraph_NodeInfo<N>(_index++); | |
| 435 _nodeMap[v] = vInfo; | |
| 436 _push(v); | |
| 437 // | |
| 438 // Consider successors of v | |
| 439 // | |
| 440 HashSet<N> tails = _graph._edges[v]; | |
| 441 if (tails != null) { | |
| 442 for (N w in tails) { | |
| 443 DirectedGraph_NodeInfo<N> wInfo = _nodeMap[w]; | |
| 444 if (wInfo == null) { | |
| 445 // Successor w has not yet been visited; recurse on it | |
| 446 wInfo = _strongConnect(w); | |
| 447 vInfo.lowlink = math.min(vInfo.lowlink, wInfo.lowlink); | |
| 448 } else if (wInfo.onStack) { | |
| 449 // Successor w is in stack S and hence in the current SCC | |
| 450 vInfo.lowlink = math.min(vInfo.lowlink, wInfo.index); | |
| 451 } | |
| 452 } | |
| 453 } | |
| 454 // | |
| 455 // If v is a root node, pop the stack and generate an SCC | |
| 456 // | |
| 457 if (vInfo.lowlink == vInfo.index) { | |
| 458 List<N> component = new List<N>(); | |
| 459 N w; | |
| 460 do { | |
| 461 w = _pop(); | |
| 462 component.add(w); | |
| 463 _nodeMap[w].component = component; | |
| 464 } while (!identical(w, v)); | |
| 465 _allComponents.add(component); | |
| 466 } | |
| 467 return vInfo; | |
| 468 } | |
| 469 } | |
| 470 | |
| 471 /** | |
| 472 * The class `ListUtilities` defines utility methods useful for working with [Li
st | |
| 473 ]. | |
| 474 */ | |
| 475 class ListUtilities { | |
| 476 /** | |
| 477 * Add all of the elements in the given array to the given list. | |
| 478 * | |
| 479 * @param list the list to which the elements are to be added | |
| 480 * @param elements the elements to be added to the list | |
| 481 */ | |
| 482 static void addAll(List list, List<Object> elements) { | |
| 483 int count = elements.length; | |
| 484 for (int i = 0; i < count; i++) { | |
| 485 list.add(elements[i]); | |
| 486 } | |
| 487 } | |
| 488 } | |
| 489 | |
| 490 /** | |
| 491 * The interface `MapIterator` defines the behavior of objects that iterate over
the entries | |
| 492 * in a map. | |
| 493 * | |
| 494 * This interface defines the concept of a current entry and provides methods to
access the key and | |
| 495 * value in the current entry. When an iterator is first created it will be posi
tioned before the | |
| 496 * first entry and there is no current entry until [moveNext] is invoked. When a
ll of the | |
| 497 * entries have been accessed there will also be no current entry. | |
| 498 * | |
| 499 * There is no guarantee made about the order in which the entries are accessibl
e. | |
| 500 */ | |
| 501 abstract class MapIterator<K, V> { | |
| 502 /** | |
| 503 * Return the key associated with the current element. | |
| 504 * | |
| 505 * @return the key associated with the current element | |
| 506 * @throws NoSuchElementException if there is no current element | |
| 507 */ | |
| 508 K get key; | |
| 509 | |
| 510 /** | |
| 511 * Return the value associated with the current element. | |
| 512 * | |
| 513 * @return the value associated with the current element | |
| 514 * @throws NoSuchElementException if there is no current element | |
| 515 */ | |
| 516 V get value; | |
| 517 | |
| 518 /** | |
| 519 * Set the value associated with the current element to the given value. | |
| 520 * | |
| 521 * @param newValue the new value to be associated with the current element | |
| 522 * @throws NoSuchElementException if there is no current element | |
| 523 */ | |
| 524 void set value(V newValue); | |
| 525 | |
| 526 /** | |
| 527 * Advance to the next entry in the map. Return `true` if there is a current e
lement that | |
| 528 * can be accessed after this method returns. It is safe to invoke this method
even if the | |
| 529 * previous invocation returned `false`. | |
| 530 * | |
| 531 * @return `true` if there is a current element that can be accessed | |
| 532 */ | |
| 533 bool moveNext(); | |
| 534 } | |
| 535 | |
| 536 /** | |
| 537 * Instances of the class `MultipleMapIterator` implement an iterator that can b
e used to | |
| 538 * sequentially access the entries in multiple maps. | |
| 539 */ | |
| 540 class MultipleMapIterator<K, V> implements MapIterator<K, V> { | |
| 541 /** | |
| 542 * The iterators used to access the entries. | |
| 543 */ | |
| 544 List<MapIterator<K, V>> _iterators; | |
| 545 | |
| 546 /** | |
| 547 * The index of the iterator currently being used to access the entries. | |
| 548 */ | |
| 549 int _iteratorIndex = -1; | |
| 550 | |
| 551 /** | |
| 552 * The current iterator, or `null` if there is no current iterator. | |
| 553 */ | |
| 554 MapIterator<K, V> _currentIterator; | |
| 555 | |
| 556 /** | |
| 557 * Initialize a newly created iterator to return the entries from the given ma
ps. | |
| 558 * | |
| 559 * @param maps the maps containing the entries to be iterated | |
| 560 */ | |
| 561 MultipleMapIterator(List<Map<K, V>> maps) { | |
| 562 int count = maps.length; | |
| 563 _iterators = new List<MapIterator<K, V>>(count); | |
| 564 for (int i = 0; i < count; i++) { | |
| 565 _iterators[i] = new SingleMapIterator<K, V>(maps[i]); | |
| 566 } | |
| 567 } | |
| 568 | |
| 569 @override | |
| 570 K get key { | |
| 571 if (_currentIterator == null) { | |
| 572 throw new NoSuchElementException(); | |
| 573 } | |
| 574 return _currentIterator.key; | |
| 575 } | |
| 576 | |
| 577 @override | |
| 578 V get value { | |
| 579 if (_currentIterator == null) { | |
| 580 throw new NoSuchElementException(); | |
| 581 } | |
| 582 return _currentIterator.value; | |
| 583 } | |
| 584 | |
| 585 @override | |
| 586 void set value(V newValue) { | |
| 587 if (_currentIterator == null) { | |
| 588 throw new NoSuchElementException(); | |
| 589 } | |
| 590 _currentIterator.value = newValue; | |
| 591 } | |
| 592 | |
| 593 @override | |
| 594 bool moveNext() { | |
| 595 if (_iteratorIndex < 0) { | |
| 596 if (_iterators.length == 0) { | |
| 597 _currentIterator = null; | |
| 598 return false; | |
| 599 } | |
| 600 if (_advanceToNextIterator()) { | |
| 601 return true; | |
| 602 } else { | |
| 603 _currentIterator = null; | |
| 604 return false; | |
| 605 } | |
| 606 } | |
| 607 if (_currentIterator.moveNext()) { | |
| 608 return true; | |
| 609 } else if (_advanceToNextIterator()) { | |
| 610 return true; | |
| 611 } else { | |
| 612 _currentIterator = null; | |
| 613 return false; | |
| 614 } | |
| 615 } | |
| 616 | |
| 617 /** | |
| 618 * Under the assumption that there are no more entries that can be returned us
ing the current | |
| 619 * iterator, advance to the next iterator that has entries. | |
| 620 * | |
| 621 * @return `true` if there is a current iterator that has entries | |
| 622 */ | |
| 623 bool _advanceToNextIterator() { | |
| 624 _iteratorIndex++; | |
| 625 while (_iteratorIndex < _iterators.length) { | |
| 626 MapIterator<K, V> iterator = _iterators[_iteratorIndex]; | |
| 627 if (iterator.moveNext()) { | |
| 628 _currentIterator = iterator; | |
| 629 return true; | |
| 630 } | |
| 631 _iteratorIndex++; | |
| 632 } | |
| 633 return false; | |
| 634 } | |
| 635 } | |
| 636 | |
| 637 /** | |
| 638 * Instances of the class `SingleMapIterator` implement an iterator that can be
used to access | |
| 639 * the entries in a single map. | |
| 640 */ | |
| 641 class SingleMapIterator<K, V> implements MapIterator<K, V> { | |
| 642 /** | |
| 643 * The [Map] containing the entries to be iterated over. | |
| 644 */ | |
| 645 final Map<K, V> _map; | |
| 646 | |
| 647 /** | |
| 648 * The iterator used to access the entries. | |
| 649 */ | |
| 650 Iterator<K> _keyIterator; | |
| 651 | |
| 652 /** | |
| 653 * The current key, or `null` if there is no current key. | |
| 654 */ | |
| 655 K _currentKey; | |
| 656 | |
| 657 /** | |
| 658 * The current value. | |
| 659 */ | |
| 660 V _currentValue; | |
| 661 | |
| 662 /** | |
| 663 * Initialize a newly created iterator to return the entries from the given ma
p. | |
| 664 * | |
| 665 * @param map the map containing the entries to be iterated over | |
| 666 */ | |
| 667 SingleMapIterator(this._map) { | |
| 668 this._keyIterator = _map.keys.iterator; | |
| 669 } | |
| 670 | |
| 671 @override | |
| 672 K get key { | |
| 673 if (_currentKey == null) { | |
| 674 throw new NoSuchElementException(); | |
| 675 } | |
| 676 return _currentKey; | |
| 677 } | |
| 678 | |
| 679 @override | |
| 680 V get value { | |
| 681 if (_currentKey == null) { | |
| 682 throw new NoSuchElementException(); | |
| 683 } | |
| 684 if (_currentValue == null) { | |
| 685 _currentValue = _map[_currentKey]; | |
| 686 } | |
| 687 return _currentValue; | |
| 688 } | |
| 689 | |
| 690 @override | |
| 691 void set value(V newValue) { | |
| 692 if (_currentKey == null) { | |
| 693 throw new NoSuchElementException(); | |
| 694 } | |
| 695 _currentValue = newValue; | |
| 696 _map[_currentKey] = newValue; | |
| 697 } | |
| 698 | |
| 699 @override | |
| 700 bool moveNext() { | |
| 701 if (_keyIterator.moveNext()) { | |
| 702 _currentKey = _keyIterator.current; | |
| 703 _currentValue = null; | |
| 704 return true; | |
| 705 } else { | |
| 706 _currentKey = null; | |
| 707 return false; | |
| 708 } | |
| 709 } | |
| 710 | |
| 711 /** | |
| 712 * Returns a new [SingleMapIterator] instance for the given [Map]. | |
| 713 */ | |
| 714 static SingleMapIterator forMap(Map map) => new SingleMapIterator(map); | |
| 715 } | |
| 716 | |
| 717 /** | |
| 718 * Instances of the class `TokenMap` map one set of tokens to another set of tok
ens. | |
| 719 */ | |
| 720 class TokenMap { | |
| 721 /** | |
| 722 * A table mapping tokens to tokens. This should be replaced by a more perform
ant implementation. | |
| 723 * One possibility is a pair of parallel arrays, with keys being sorted by the
ir offset and a | |
| 724 * cursor indicating where to start searching. | |
| 725 */ | |
| 726 HashMap<Token, Token> _map = new HashMap<Token, Token>(); | |
| 727 | |
| 728 /** | |
| 729 * Return the token that is mapped to the given token, or `null` if there is n
o token | |
| 730 * corresponding to the given token. | |
| 731 * | |
| 732 * @param key the token being mapped to another token | |
| 733 * @return the token that is mapped to the given token | |
| 734 */ | |
| 735 Token get(Token key) => _map[key]; | |
| 736 | |
| 737 /** | |
| 738 * Map the key to the value. | |
| 739 * | |
| 740 * @param key the token being mapped to the value | |
| 741 * @param value the token to which the key will be mapped | |
| 742 */ | |
| 743 void put(Token key, Token value) { | |
| 744 _map[key] = value; | |
| 745 } | |
| 746 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1400473008:
Roll Observatory packages and add a roll script (Closed)
Base URL: git@github.com:dart-lang/observatory_pub_packages.git@master