| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, 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 library dart_style.src.line_splitting.solve_state_queue; | |
| 6 | |
| 7 import 'line_splitter.dart'; | |
| 8 import 'solve_state.dart'; | |
| 9 | |
| 10 /// A priority queue of [SolveStates] to consider while line splitting. | |
| 11 /// | |
| 12 /// This is based on the [HeapPriorityQueue] class from the "collection" | |
| 13 /// package, but is modified to handle the "overlap" logic that allows one | |
| 14 /// [SolveState] to supercede another. | |
| 15 /// | |
| 16 /// States are stored internally in a heap ordered by cost, the number of | |
| 17 /// overflow characters. When a new state is added to the heap, it will be | |
| 18 /// discarded, or a previously enqueued one will be discarded, if two overlap. | |
| 19 class SolveStateQueue { | |
| 20 /// Initial capacity of a queue when created, or when added to after a [clear]
. | |
| 21 /// Number can be any positive value. Picking a size that gives a whole | |
| 22 /// number of "tree levels" in the heap is only done for aesthetic reasons. | |
| 23 static const int _INITIAL_CAPACITY = 7; | |
| 24 | |
| 25 LineSplitter _splitter; | |
| 26 | |
| 27 /// List implementation of a heap. | |
| 28 List<SolveState> _queue = new List<SolveState>(_INITIAL_CAPACITY); | |
| 29 | |
| 30 /// Number of elements in queue. | |
| 31 /// The heap is implemented in the first [_length] entries of [_queue]. | |
| 32 int _length = 0; | |
| 33 | |
| 34 bool get isNotEmpty => _length != 0; | |
| 35 | |
| 36 void bindSplitter(LineSplitter splitter) { | |
| 37 // Only do this once. | |
| 38 assert(_splitter == null); | |
| 39 | |
| 40 _splitter = splitter; | |
| 41 } | |
| 42 | |
| 43 /// Add [state] to the queue. | |
| 44 /// | |
| 45 /// Grows the capacity if the backing list is full. | |
| 46 void add(SolveState state) { | |
| 47 if (_tryOverlap(state)) return; | |
| 48 | |
| 49 if (_length == _queue.length) { | |
| 50 var newCapacity = _queue.length * 2 + 1; | |
| 51 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; | |
| 52 | |
| 53 var newQueue = new List<SolveState>(newCapacity); | |
| 54 newQueue.setRange(0, _length, _queue); | |
| 55 _queue = newQueue; | |
| 56 } | |
| 57 | |
| 58 _bubbleUp(state, _length++); | |
| 59 } | |
| 60 | |
| 61 SolveState removeFirst() { | |
| 62 assert(_length > 0); | |
| 63 | |
| 64 // Remove the highest priority state. | |
| 65 var result = _queue[0]; | |
| 66 _length--; | |
| 67 | |
| 68 // Fill the gap with the one at the end of the list and re-heapify. | |
| 69 if (_length > 0) { | |
| 70 var last = _queue[_length]; | |
| 71 _queue[_length] = null; | |
| 72 _bubbleDown(last, 0); | |
| 73 } | |
| 74 | |
| 75 return result; | |
| 76 } | |
| 77 | |
| 78 /// Orders this state relative to [other]. | |
| 79 /// | |
| 80 /// This is a best-first ordering that prefers cheaper states even if they | |
| 81 /// overflow because this ensures it finds the best solution first as soon as | |
| 82 /// it finds one that fits in the page so it can early out. | |
| 83 int _compare(SolveState a, SolveState b) { | |
| 84 // TODO(rnystrom): It may be worth sorting by the estimated lowest number | |
| 85 // of overflow characters first. That doesn't help in cases where there is | |
| 86 // a solution that fits, but may help in corner cases where there is no | |
| 87 // fitting solution. | |
| 88 | |
| 89 var comparison = _compareScore(a, b); | |
| 90 if (comparison != 0) return comparison; | |
| 91 | |
| 92 return _compareRules(a, b); | |
| 93 } | |
| 94 | |
| 95 /// Compares the overflow and cost of [a] to [b]. | |
| 96 int _compareScore(SolveState a, SolveState b) { | |
| 97 if (a.splits.cost != b.splits.cost) { | |
| 98 return a.splits.cost.compareTo(b.splits.cost); | |
| 99 } | |
| 100 | |
| 101 return a.overflowChars.compareTo(b.overflowChars); | |
| 102 } | |
| 103 | |
| 104 /// Distinguish states based on the rule values just so that states with the | |
| 105 /// same cost range but different rule values don't get considered identical | |
| 106 /// and inadvertantly merged. | |
| 107 int _compareRules(SolveState a, SolveState b) { | |
| 108 for (var rule in _splitter.rules) { | |
| 109 var aValue = a.getValue(rule); | |
| 110 var bValue = b.getValue(rule); | |
| 111 | |
| 112 if (aValue != bValue) return aValue.compareTo(bValue); | |
| 113 } | |
| 114 | |
| 115 // The way SolveStates are expanded should guarantee that we never generate | |
| 116 // the exact same state twice. Getting here implies that that failed. | |
| 117 throw "unreachable"; | |
| 118 } | |
| 119 | |
| 120 /// Determines if any already enqueued state overlaps [state]. | |
| 121 /// | |
| 122 /// If so, chooses the best and discards the other. Returns `true` in this | |
| 123 /// case. Otherwise, returns `false`. | |
| 124 bool _tryOverlap(SolveState state) { | |
| 125 if (_length == 0) return false; | |
| 126 | |
| 127 // Count positions from one instead of zero. This gives the numbers some | |
| 128 // nice properties. For example, all right children are odd, their left | |
| 129 // sibling is even, and the parent is found by shifting right by one. | |
| 130 // Valid range for position is [1.._length], inclusive. | |
| 131 var position = 1; | |
| 132 | |
| 133 // Pre-order depth first search, omit child nodes if the current node has | |
| 134 // lower priority than [object], because all nodes lower in the heap will | |
| 135 // also have lower priority. | |
| 136 do { | |
| 137 var index = position - 1; | |
| 138 var enqueued = _queue[index]; | |
| 139 | |
| 140 var comparison = _compareScore(enqueued, state); | |
| 141 | |
| 142 if (comparison == 0) { | |
| 143 var overlap = enqueued.compareOverlap(state); | |
| 144 if (overlap < 0) { | |
| 145 // The old state is better, so just discard the new one. | |
| 146 return true; | |
| 147 } else if (overlap > 0) { | |
| 148 // The new state is better than the enqueued one, so replace it. | |
| 149 _queue[index] = state; | |
| 150 return true; | |
| 151 } else { | |
| 152 // We can't merge them, so sort by their bound rule values. | |
| 153 comparison = _compareRules(enqueued, state); | |
| 154 } | |
| 155 } | |
| 156 | |
| 157 if (comparison < 0) { | |
| 158 // Element may be in subtree. Continue with the left child, if any. | |
| 159 var leftChildPosition = position * 2; | |
| 160 if (leftChildPosition <= _length) { | |
| 161 position = leftChildPosition; | |
| 162 continue; | |
| 163 } | |
| 164 } | |
| 165 | |
| 166 // Find the next right sibling or right ancestor sibling. | |
| 167 do { | |
| 168 while (position.isOdd) { | |
| 169 // While position is a right child, go to the parent. | |
| 170 position >>= 1; | |
| 171 } | |
| 172 | |
| 173 // Then go to the right sibling of the left child. | |
| 174 position += 1; | |
| 175 } while (position > _length); // Happens if last element is a left child. | |
| 176 } while (position != 1); // At root again. Happens for right-most element. | |
| 177 | |
| 178 return false; | |
| 179 } | |
| 180 | |
| 181 /// Place [element] in heap at [index] or above. | |
| 182 /// | |
| 183 /// Put element into the empty cell at `index`. While the `element` has | |
| 184 /// higher priority than the parent, swap it with the parent. | |
| 185 void _bubbleUp(SolveState element, int index) { | |
| 186 while (index > 0) { | |
| 187 var parentIndex = (index - 1) ~/ 2; | |
| 188 var parent = _queue[parentIndex]; | |
| 189 | |
| 190 if (_compare(element, parent) > 0) break; | |
| 191 | |
| 192 _queue[index] = parent; | |
| 193 index = parentIndex; | |
| 194 } | |
| 195 | |
| 196 _queue[index] = element; | |
| 197 } | |
| 198 | |
| 199 /// Place [element] in heap at [index] or above. | |
| 200 /// | |
| 201 /// Put element into the empty cell at `index`. While the `element` has lower | |
| 202 /// priority than either child, swap it with the highest priority child. | |
| 203 void _bubbleDown(SolveState element, int index) { | |
| 204 var rightChildIndex = index * 2 + 2; | |
| 205 | |
| 206 while (rightChildIndex < _length) { | |
| 207 var leftChildIndex = rightChildIndex - 1; | |
| 208 var leftChild = _queue[leftChildIndex]; | |
| 209 var rightChild = _queue[rightChildIndex]; | |
| 210 | |
| 211 var comparison = _compare(leftChild, rightChild); | |
| 212 var minChildIndex; | |
| 213 var minChild; | |
| 214 | |
| 215 if (comparison < 0) { | |
| 216 minChild = leftChild; | |
| 217 minChildIndex = leftChildIndex; | |
| 218 } else { | |
| 219 minChild = rightChild; | |
| 220 minChildIndex = rightChildIndex; | |
| 221 } | |
| 222 | |
| 223 comparison = _compare(element, minChild); | |
| 224 | |
| 225 if (comparison <= 0) { | |
| 226 _queue[index] = element; | |
| 227 return; | |
| 228 } | |
| 229 | |
| 230 _queue[index] = minChild; | |
| 231 index = minChildIndex; | |
| 232 rightChildIndex = index * 2 + 2; | |
| 233 } | |
| 234 | |
| 235 var leftChildIndex = rightChildIndex - 1; | |
| 236 if (leftChildIndex < _length) { | |
| 237 var child = _queue[leftChildIndex]; | |
| 238 var comparison = _compare(element, child); | |
| 239 | |
| 240 if (comparison > 0) { | |
| 241 _queue[index] = child; | |
| 242 index = leftChildIndex; | |
| 243 } | |
| 244 } | |
| 245 | |
| 246 _queue[index] = element; | |
| 247 } | |
| 248 } | |
| 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