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 | 9 | bool get isNotEmpty => _length != 0;
|
35 | |
|
36 | 3 | void bindSplitter(LineSplitter splitter) {
|
37 | | // Only do this once.
|
38 | 3 | assert(_splitter == null);
|
39 | |
|
40 | 3 | _splitter = splitter;
|
41 | | }
|
42 | |
|
43 | | /// Add [state] to the queue.
|
44 | | ///
|
45 | | /// Grows the capacity if the backing list is full.
|
46 | 3 | void add(SolveState state) {
|
47 | 3 | if (_tryOverlap(state)) return;
|
48 | |
|
49 | 12 | if (_length == _queue.length) {
|
50 | 8 | var newCapacity = _queue.length * 2 + 1;
|
51 | 2 | if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
|
52 | |
|
53 | 2 | var newQueue = new List<SolveState>(newCapacity);
|
54 | 6 | newQueue.setRange(0, _length, _queue);
|
55 | 2 | _queue = newQueue;
|
56 | | }
|
57 | |
|
58 | 9 | _bubbleUp(state, _length++);
|
59 | | }
|
60 | |
|
61 | 3 | SolveState removeFirst() {
|
62 | 6 | assert(_length > 0);
|
63 | |
|
64 | | // Remove the highest priority state.
|
65 | 6 | var result = _queue[0];
|
66 | 6 | _length--;
|
67 | |
|
68 | | // Fill the gap with the one at the end of the list and re-heapify.
|
69 | 6 | if (_length > 0) {
|
70 | 6 | var last = _queue[_length];
|
71 | 6 | _queue[_length] = null;
|
72 | 2 | _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 | 2 | 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 | 2 | var comparison = _compareScore(a, b);
|
90 | 2 | if (comparison != 0) return comparison;
|
91 | |
|
92 | 2 | return _compareRules(a, b);
|
93 | | }
|
94 | |
|
95 | | /// Compares the overflow and cost of [a] to [b].
|
96 | 2 | int _compareScore(SolveState a, SolveState b) {
|
97 | 10 | if (a.splits.cost != b.splits.cost) {
|
98 | 10 | return a.splits.cost.compareTo(b.splits.cost);
|
99 | | }
|
100 | |
|
101 | 6 | 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 | 2 | int _compareRules(SolveState a, SolveState b) {
|
108 | 6 | for (var rule in _splitter.rules) {
|
109 | 2 | var aValue = a.getValue(rule);
|
110 | 2 | var bValue = b.getValue(rule);
|
111 | |
|
112 | 4 | 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 | 3 | bool _tryOverlap(SolveState state) {
|
125 | 6 | 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 | 2 | var index = position - 1;
|
138 | 4 | var enqueued = _queue[index];
|
139 | |
|
140 | 2 | var comparison = _compareScore(enqueued, state);
|
141 | |
|
142 | 2 | if (comparison == 0) {
|
143 | 2 | var overlap = enqueued.compareOverlap(state);
|
144 | 2 | if (overlap < 0) {
|
145 | | // The old state is better, so just discard the new one.
|
146 | | return true;
|
147 | 2 | } else if (overlap > 0) {
|
148 | | // The new state is better than the enqueued one, so replace it.
|
149 | 4 | _queue[index] = state;
|
150 | | return true;
|
151 | | } else {
|
152 | | // We can't merge them, so sort by their bound rule values.
|
153 | 2 | comparison = _compareRules(enqueued, state);
|
154 | | }
|
155 | | }
|
156 | |
|
157 | 2 | if (comparison < 0) {
|
158 | | // Element may be in subtree. Continue with the left child, if any.
|
159 | 2 | var leftChildPosition = position * 2;
|
160 | 4 | if (leftChildPosition <= _length) {
|
161 | | position = leftChildPosition;
|
162 | | continue;
|
163 | | }
|
164 | | }
|
165 | |
|
166 | | // Find the next right sibling or right ancestor sibling.
|
167 | | do {
|
168 | 2 | while (position.isOdd) {
|
169 | | // While position is a right child, go to the parent.
|
170 | 2 | position >>= 1;
|
171 | | }
|
172 | |
|
173 | | // Then go to the right sibling of the left child.
|
174 | 2 | position += 1;
|
175 | 4 | } while (position > _length); // Happens if last element is a left child.
|
176 | 2 | } 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 | 3 | void _bubbleUp(SolveState element, int index) {
|
186 | 3 | while (index > 0) {
|
187 | 4 | var parentIndex = (index - 1) ~/ 2;
|
188 | 4 | var parent = _queue[parentIndex];
|
189 | |
|
190 | 4 | if (_compare(element, parent) > 0) break;
|
191 | |
|
192 | 4 | _queue[index] = parent;
|
193 | | index = parentIndex;
|
194 | | }
|
195 | |
|
196 | 6 | _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 | 2 | void _bubbleDown(SolveState element, int index) {
|
204 | 4 | var rightChildIndex = index * 2 + 2;
|
205 | |
|
206 | 4 | while (rightChildIndex < _length) {
|
207 | 2 | var leftChildIndex = rightChildIndex - 1;
|
208 | 4 | var leftChild = _queue[leftChildIndex];
|
209 | 4 | var rightChild = _queue[rightChildIndex];
|
210 | |
|
211 | 2 | var comparison = _compare(leftChild, rightChild);
|
212 | | var minChildIndex;
|
213 | | var minChild;
|
214 | |
|
215 | 2 | if (comparison < 0) {
|
216 | | minChild = leftChild;
|
217 | | minChildIndex = leftChildIndex;
|
218 | | } else {
|
219 | | minChild = rightChild;
|
220 | | minChildIndex = rightChildIndex;
|
221 | | }
|
222 | |
|
223 | 2 | comparison = _compare(element, minChild);
|
224 | |
|
225 | 2 | if (comparison <= 0) {
|
226 | 4 | _queue[index] = element;
|
227 | | return;
|
228 | | }
|
229 | |
|
230 | 4 | _queue[index] = minChild;
|
231 | | index = minChildIndex;
|
232 | 4 | rightChildIndex = index * 2 + 2;
|
233 | | }
|
234 | |
|
235 | 2 | var leftChildIndex = rightChildIndex - 1;
|
236 | 4 | if (leftChildIndex < _length) {
|
237 | 4 | var child = _queue[leftChildIndex];
|
238 | 2 | var comparison = _compare(element, child);
|
239 | |
|
240 | 2 | if (comparison > 0) {
|
241 | 4 | _queue[index] = child;
|
242 | | index = leftChildIndex;
|
243 | | }
|
244 | | }
|
245 | |
|
246 | 4 | _queue[index] = element;
|
247 | | }
|
248 | | }
|