Optimize splitting long, complex lines.

lib/src/line_splitting/solve_state_queue.dart

+// 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;
+  }
+}