Linter Demo

Errors: 0

Warnings: 2

File: /home/fstrocco/Dart/dart/benchmark/dartstyle/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; } }