Roll Observatory packages and add a roll script

dart_style/lib/src/line_splitting/solve_state_queue.dart

Index: dart_style/lib/src/line_splitting/solve_state_queue.dart
diff --git a/dart_style/lib/src/line_splitting/solve_state_queue.dart b/dart_style/lib/src/line_splitting/solve_state_queue.dart
deleted file mode 100644
index 2247cb3cb3c3aeebf8de15021163b8a954d4ab0c..0000000000000000000000000000000000000000
--- a/dart_style/lib/src/line_splitting/solve_state_queue.dart
+++ /dev/null
@@ -1,248 +0,0 @@
-// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-library dart_style.src.line_splitting.solve_state_queue;
-
-import 'line_splitter.dart';
-import 'solve_state.dart';
-
-/// A priority queue of [SolveStates] to consider while line splitting.
-///
-/// This is based on the [HeapPriorityQueue] class from the "collection"
-/// package, but is modified to handle the "overlap" logic that allows one
-/// [SolveState] to supercede another.
-///
-/// States are stored internally in a heap ordered by cost, the number of
-/// overflow characters. When a new state is added to the heap, it will be
-/// discarded, or a previously enqueued one will be discarded, if two overlap.
-class SolveStateQueue {
-  /// Initial capacity of a queue when created, or when added to after a [clear].
-  /// Number can be any positive value. Picking a size that gives a whole
-  /// number of "tree levels" in the heap is only done for aesthetic reasons.
-  static const int _INITIAL_CAPACITY = 7;
-
-  LineSplitter _splitter;
-
-  /// List implementation of a heap.
-  List<SolveState> _queue = new List<SolveState>(_INITIAL_CAPACITY);
-
-  /// Number of elements in queue.
-  /// The heap is implemented in the first [_length] entries of [_queue].
-  int _length = 0;
-
-  bool get isNotEmpty => _length != 0;
-
-  void bindSplitter(LineSplitter splitter) {
-    // Only do this once.
-    assert(_splitter == null);
-
-    _splitter = splitter;
-  }
-
-  /// Add [state] to the queue.
-  ///
-  /// Grows the capacity if the backing list is full.
-  void add(SolveState state) {
-    if (_tryOverlap(state)) return;
-
-    if (_length == _queue.length) {
-      var newCapacity = _queue.length * 2 + 1;
-      if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
-
-      var newQueue = new List<SolveState>(newCapacity);
-      newQueue.setRange(0, _length, _queue);
-      _queue = newQueue;
-    }
-
-    _bubbleUp(state, _length++);
-  }
-
-  SolveState removeFirst() {
-    assert(_length > 0);
-
-    // Remove the highest priority state.
-    var result = _queue[0];
-    _length--;
-
-    // Fill the gap with the one at the end of the list and re-heapify.
-    if (_length > 0) {
-      var last = _queue[_length];
-      _queue[_length] = null;
-      _bubbleDown(last, 0);
-    }
-
-    return result;
-  }
-
-  /// Orders this state relative to [other].
-  ///
-  /// This is a best-first ordering that prefers cheaper states even if they
-  /// overflow because this ensures it finds the best solution first as soon as
-  /// it finds one that fits in the page so it can early out.
-  int _compare(SolveState a, SolveState b) {
-    // TODO(rnystrom): It may be worth sorting by the estimated lowest number
-    // of overflow characters first. That doesn't help in cases where there is
-    // a solution that fits, but may help in corner cases where there is no
-    // fitting solution.
-
-    var comparison = _compareScore(a, b);
-    if (comparison != 0) return comparison;
-
-    return _compareRules(a, b);
-  }
-
-  /// Compares the overflow and cost of [a] to [b].
-  int _compareScore(SolveState a, SolveState b) {
-    if (a.splits.cost != b.splits.cost) {
-      return a.splits.cost.compareTo(b.splits.cost);
-    }
-
-    return a.overflowChars.compareTo(b.overflowChars);
-  }
-
-  /// Distinguish states based on the rule values just so that states with the
-  /// same cost range but different rule values don't get considered identical
-  /// and inadvertantly merged.
-  int _compareRules(SolveState a, SolveState b) {
-    for (var rule in _splitter.rules) {
-      var aValue = a.getValue(rule);
-      var bValue = b.getValue(rule);
-
-      if (aValue != bValue) return aValue.compareTo(bValue);
-    }
-
-    // The way SolveStates are expanded should guarantee that we never generate
-    // the exact same state twice. Getting here implies that that failed.
-    throw "unreachable";
-  }
-
-  /// Determines if any already enqueued state overlaps [state].
-  ///
-  /// If so, chooses the best and discards the other. Returns `true` in this
-  /// case. Otherwise, returns `false`.
-  bool _tryOverlap(SolveState state) {
-    if (_length == 0) return false;
-
-    // Count positions from one instead of zero. This gives the numbers some
-    // nice properties. For example, all right children are odd, their left
-    // sibling is even, and the parent is found by shifting right by one.
-    // Valid range for position is [1.._length], inclusive.
-    var position = 1;
-
-    // Pre-order depth first search, omit child nodes if the current node has
-    // lower priority than [object], because all nodes lower in the heap will
-    // also have lower priority.
-    do {
-      var index = position - 1;
-      var enqueued = _queue[index];
-
-      var comparison = _compareScore(enqueued, state);
-
-      if (comparison == 0) {
-        var overlap = enqueued.compareOverlap(state);
-        if (overlap < 0) {
-          // The old state is better, so just discard the new one.
-          return true;
-        } else if (overlap > 0) {
-          // The new state is better than the enqueued one, so replace it.
-          _queue[index] = state;
-          return true;
-        } else {
-          // We can't merge them, so sort by their bound rule values.
-          comparison = _compareRules(enqueued, state);
-        }
-      }
-
-      if (comparison < 0) {
-        // Element may be in subtree. Continue with the left child, if any.
-        var leftChildPosition = position * 2;
-        if (leftChildPosition <= _length) {
-          position = leftChildPosition;
-          continue;
-        }
-      }
-
-      // Find the next right sibling or right ancestor sibling.
-      do {
-        while (position.isOdd) {
-          // While position is a right child, go to the parent.
-          position >>= 1;
-        }
-
-        // Then go to the right sibling of the left child.
-        position += 1;
-      } while (position > _length); // Happens if last element is a left child.
-    } while (position != 1); // At root again. Happens for right-most element.
-
-    return false;
-  }
-
-  /// Place [element] in heap at [index] or above.
-  ///
-  /// Put element into the empty cell at `index`. While the `element` has
-  /// higher priority than the parent, swap it with the parent.
-  void _bubbleUp(SolveState element, int index) {
-    while (index > 0) {
-      var parentIndex = (index - 1) ~/ 2;
-      var parent = _queue[parentIndex];
-
-      if (_compare(element, parent) > 0) break;
-
-      _queue[index] = parent;
-      index = parentIndex;
-    }
-
-    _queue[index] = element;
-  }
-
-  /// Place [element] in heap at [index] or above.
-  ///
-  /// Put element into the empty cell at `index`. While the `element` has lower
-  /// priority than either child, swap it with the highest priority child.
-  void _bubbleDown(SolveState element, int index) {
-    var rightChildIndex = index * 2 + 2;
-
-    while (rightChildIndex < _length) {
-      var leftChildIndex = rightChildIndex - 1;
-      var leftChild = _queue[leftChildIndex];
-      var rightChild = _queue[rightChildIndex];
-
-      var comparison = _compare(leftChild, rightChild);
-      var minChildIndex;
-      var minChild;
-
-      if (comparison < 0) {
-        minChild = leftChild;
-        minChildIndex = leftChildIndex;
-      } else {
-        minChild = rightChild;
-        minChildIndex = rightChildIndex;
-      }
-
-      comparison = _compare(element, minChild);
-
-      if (comparison <= 0) {
-        _queue[index] = element;
-        return;
-      }
-
-      _queue[index] = minChild;
-      index = minChildIndex;
-      rightChildIndex = index * 2 + 2;
-    }
-
-    var leftChildIndex = rightChildIndex - 1;
-    if (leftChildIndex < _length) {
-      var child = _queue[leftChildIndex];
-      var comparison = _compare(element, child);
-
-      if (comparison > 0) {
-        _queue[index] = child;
-        index = leftChildIndex;
-      }
-    }
-
-    _queue[index] = element;
-  }
-}