Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(8)

Side by Side Diff: packages/observe/lib/src/list_diff.dart

Issue 2989763002: Update charted to 0.4.8 and roll (Closed)
Patch Set: Removed Cutch from list of reviewers Created 3 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright (c) 2013, 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 observe.src.list_diff;
6
7 import 'dart:math' as math;
8 import 'dart:collection' show UnmodifiableListView;
9 import 'change_record.dart' show ChangeRecord;
10
11 /// A summary of an individual change to a [List].
12 ///
13 /// Each delta represents that at the [index], [removed] sequence of items were
14 /// removed, and counting forward from [index], [addedCount] items were added.
15 class ListChangeRecord extends ChangeRecord {
16 /// The list that changed.
17 final List object;
18
19 /// The index of the change.
20 int get index => _index;
21
22 /// The items removed, if any. Otherwise this will be an empty list.
23 List get removed => _unmodifiableRemoved;
24 UnmodifiableListView _unmodifiableRemoved;
25
26 /// Mutable version of [removed], used during the algorithms as they are
27 /// constructing the object.
28 List _removed;
29
30 /// The number of items added.
31 int get addedCount => _addedCount;
32
33 // Note: conceptually these are final, but for convenience we increment it as
34 // we build the object. It will be "frozen" by the time it is returned the the
35 // user.
36 int _index, _addedCount;
37
38 ListChangeRecord._(this.object, this._index, removed, this._addedCount)
39 : _removed = removed,
40 _unmodifiableRemoved = new UnmodifiableListView(removed);
41
42 factory ListChangeRecord(List object, int index,
43 {List removed, int addedCount}) {
44
45 if (removed == null) removed = [];
46 if (addedCount == null) addedCount = 0;
47 return new ListChangeRecord._(object, index, removed, addedCount);
48 }
49
50 /// Returns true if the provided index was changed by this operation.
51 bool indexChanged(key) {
52 // If key isn't an int, or before the index, then it wasn't changed.
53 if (key is! int || key < index) return false;
54
55 // If this was a shift operation, anything after index is changed.
56 if (addedCount != removed.length) return true;
57
58 // Otherwise, anything in the update range was changed.
59 return key < index + addedCount;
60 }
61
62 String toString() => '#<ListChangeRecord index: $index, '
63 'removed: $removed, addedCount: $addedCount>';
64 }
65
66 // Note: This function is *based* on the computation of the Levenshtein
67 // "edit" distance. The one change is that "updates" are treated as two
68 // edits - not one. With List splices, an update is really a delete
69 // followed by an add. By retaining this, we optimize for "keeping" the
70 // maximum array items in the original array. For example:
71 //
72 // 'xxxx123' -> '123yyyy'
73 //
74 // With 1-edit updates, the shortest path would be just to update all seven
75 // characters. With 2-edit updates, we delete 4, leave 3, and add 4. This
76 // leaves the substring '123' intact.
77 List<List<int>> _calcEditDistances(List current, int currentStart,
78 int currentEnd, List old, int oldStart, int oldEnd) {
79 // "Deletion" columns
80 var rowCount = oldEnd - oldStart + 1;
81 var columnCount = currentEnd - currentStart + 1;
82 var distances = new List(rowCount);
83
84 // "Addition" rows. Initialize null column.
85 for (var i = 0; i < rowCount; i++) {
86 distances[i] = new List(columnCount);
87 distances[i][0] = i;
88 }
89
90 // Initialize null row
91 for (var j = 0; j < columnCount; j++) {
92 distances[0][j] = j;
93 }
94
95 for (var i = 1; i < rowCount; i++) {
96 for (var j = 1; j < columnCount; j++) {
97 if (old[oldStart + i - 1] == current[currentStart + j - 1]) {
98 distances[i][j] = distances[i - 1][j - 1];
99 } else {
100 var north = distances[i - 1][j] + 1;
101 var west = distances[i][j - 1] + 1;
102 distances[i][j] = math.min(north, west);
103 }
104 }
105 }
106
107 return distances;
108 }
109
110 const _EDIT_LEAVE = 0;
111 const _EDIT_UPDATE = 1;
112 const _EDIT_ADD = 2;
113 const _EDIT_DELETE = 3;
114
115 // This starts at the final weight, and walks "backward" by finding
116 // the minimum previous weight recursively until the origin of the weight
117 // matrix.
118 List<int> _spliceOperationsFromEditDistances(List<List<int>> distances) {
119 var i = distances.length - 1;
120 var j = distances[0].length - 1;
121 var current = distances[i][j];
122 var edits = [];
123 while (i > 0 || j > 0) {
124 if (i == 0) {
125 edits.add(_EDIT_ADD);
126 j--;
127 continue;
128 }
129 if (j == 0) {
130 edits.add(_EDIT_DELETE);
131 i--;
132 continue;
133 }
134 var northWest = distances[i - 1][j - 1];
135 var west = distances[i - 1][j];
136 var north = distances[i][j - 1];
137
138 var min = math.min(math.min(west, north), northWest);
139
140 if (min == northWest) {
141 if (northWest == current) {
142 edits.add(_EDIT_LEAVE);
143 } else {
144 edits.add(_EDIT_UPDATE);
145 current = northWest;
146 }
147 i--;
148 j--;
149 } else if (min == west) {
150 edits.add(_EDIT_DELETE);
151 i--;
152 current = west;
153 } else {
154 edits.add(_EDIT_ADD);
155 j--;
156 current = north;
157 }
158 }
159
160 return edits.reversed.toList();
161 }
162
163 int _sharedPrefix(List arr1, List arr2, int searchLength) {
164 for (var i = 0; i < searchLength; i++) {
165 if (arr1[i] != arr2[i]) {
166 return i;
167 }
168 }
169 return searchLength;
170 }
171
172 int _sharedSuffix(List arr1, List arr2, int searchLength) {
173 var index1 = arr1.length;
174 var index2 = arr2.length;
175 var count = 0;
176 while (count < searchLength && arr1[--index1] == arr2[--index2]) {
177 count++;
178 }
179 return count;
180 }
181
182 /// Lacking individual splice mutation information, the minimal set of
183 /// splices can be synthesized given the previous state and final state of an
184 /// array. The basic approach is to calculate the edit distance matrix and
185 /// choose the shortest path through it.
186 ///
187 /// Complexity: O(l * p)
188 /// l: The length of the current array
189 /// p: The length of the old array
190 List<ListChangeRecord> calcSplices(List current, int currentStart,
191 int currentEnd, List old, int oldStart, int oldEnd) {
192
193 var prefixCount = 0;
194 var suffixCount = 0;
195
196 var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
197 if (currentStart == 0 && oldStart == 0) {
198 prefixCount = _sharedPrefix(current, old, minLength);
199 }
200
201 if (currentEnd == current.length && oldEnd == old.length) {
202 suffixCount = _sharedSuffix(current, old, minLength - prefixCount);
203 }
204
205 currentStart += prefixCount;
206 oldStart += prefixCount;
207 currentEnd -= suffixCount;
208 oldEnd -= suffixCount;
209
210 if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
211 return const [];
212 }
213
214 if (currentStart == currentEnd) {
215 var splice = new ListChangeRecord(current, currentStart);
216 while (oldStart < oldEnd) {
217 splice._removed.add(old[oldStart++]);
218 }
219
220 return [splice ];
221 } else if (oldStart == oldEnd)
222 return [new ListChangeRecord(current, currentStart,
223 addedCount: currentEnd - currentStart)];
224
225 var ops = _spliceOperationsFromEditDistances(
226 _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
227 oldEnd));
228
229 ListChangeRecord splice = null;
230 var splices = <ListChangeRecord>[];
231 var index = currentStart;
232 var oldIndex = oldStart;
233 for (var i = 0; i < ops.length; i++) {
234 switch(ops[i]) {
235 case _EDIT_LEAVE:
236 if (splice != null) {
237 splices.add(splice);
238 splice = null;
239 }
240
241 index++;
242 oldIndex++;
243 break;
244 case _EDIT_UPDATE:
245 if (splice == null) splice = new ListChangeRecord(current, index);
246
247 splice._addedCount++;
248 index++;
249
250 splice._removed.add(old[oldIndex]);
251 oldIndex++;
252 break;
253 case _EDIT_ADD:
254 if (splice == null) splice = new ListChangeRecord(current, index);
255
256 splice._addedCount++;
257 index++;
258 break;
259 case _EDIT_DELETE:
260 if (splice == null) splice = new ListChangeRecord(current, index);
261
262 splice._removed.add(old[oldIndex]);
263 oldIndex++;
264 break;
265 }
266 }
267
268 if (splice != null) splices.add(splice);
269 return splices;
270 }
271
272 int _intersect(int start1, int end1, int start2, int end2) =>
273 math.min(end1, end2) - math.max(start1, start2);
274
275 void _mergeSplice(List<ListChangeRecord> splices, ListChangeRecord record) {
276 var splice = new ListChangeRecord(record.object, record.index,
277 removed: record._removed.toList(), addedCount: record.addedCount);
278
279 var inserted = false;
280 var insertionOffset = 0;
281
282 // I think the way this works is:
283 // - the loop finds where the merge should happen
284 // - it applies the merge in a particular splice
285 // - then continues and updates the subsequent splices with any offset diff.
286 for (var i = 0; i < splices.length; i++) {
287 final current = splices[i];
288 current._index += insertionOffset;
289
290 if (inserted) continue;
291
292 var intersectCount = _intersect(
293 splice.index, splice.index + splice.removed.length,
294 current.index, current.index + current.addedCount);
295
296 if (intersectCount >= 0) {
297 // Merge the two splices
298
299 splices.removeAt(i);
300 i--;
301
302 insertionOffset -= current.addedCount - current.removed.length;
303
304 splice._addedCount += current.addedCount - intersectCount;
305 var deleteCount = splice.removed.length +
306 current.removed.length - intersectCount;
307
308 if (splice.addedCount == 0 && deleteCount == 0) {
309 // merged splice is a noop. discard.
310 inserted = true;
311 } else {
312 var removed = current._removed;
313
314 if (splice.index < current.index) {
315 // some prefix of splice.removed is prepended to current.removed.
316 removed.insertAll(0,
317 splice.removed.getRange(0, current.index - splice.index));
318 }
319
320 if (splice.index + splice.removed.length >
321 current.index + current.addedCount) {
322 // some suffix of splice.removed is appended to current.removed.
323 removed.addAll(splice.removed.getRange(
324 current.index + current.addedCount - splice.index,
325 splice.removed.length));
326 }
327
328 splice._removed = removed;
329 splice._unmodifiableRemoved = current._unmodifiableRemoved;
330 if (current.index < splice.index) {
331 splice._index = current.index;
332 }
333 }
334 } else if (splice.index < current.index) {
335 // Insert splice here.
336
337 inserted = true;
338
339 splices.insert(i, splice);
340 i++;
341
342 var offset = splice.addedCount - splice.removed.length;
343 current._index += offset;
344 insertionOffset += offset;
345 }
346 }
347
348 if (!inserted) splices.add(splice);
349 }
350
351 List<ListChangeRecord> _createInitialSplices(List<Object> list,
352 List<ListChangeRecord> records) {
353
354 var splices = <ListChangeRecord>[];
355 for (var record in records) {
356 _mergeSplice(splices, record);
357 }
358 return splices;
359 }
360
361 /// We need to summarize change records. Consumers of these records want to
362 /// apply the batch sequentially, and ensure that they can find inserted
363 /// items by looking at that position in the list. This property does not
364 /// hold in our record-as-you-go records. Consider:
365 ///
366 /// var model = toObservable(['a', 'b']);
367 /// model.removeAt(1);
368 /// model.insertAll(0, ['c', 'd', 'e']);
369 /// model.removeRange(1, 3);
370 /// model.insert(1, 'f');
371 ///
372 /// Here, we inserted some records and then removed some of them.
373 /// If someone processed these records naively, they would "play back" the
374 /// insert incorrectly, because those items will be shifted.
375 List<ListChangeRecord> projectListSplices(List list,
376 List<ListChangeRecord> records) {
377 if (records.length <= 1) return records;
378
379 var splices = [];
380 for (var splice in _createInitialSplices(list, records)) {
381 if (splice.addedCount == 1 && splice.removed.length == 1) {
382 if (splice.removed[0] != list[splice.index]) splices.add(splice);
383 continue;
384 }
385
386 splices.addAll(calcSplices(list, splice.index,
387 splice.index + splice.addedCount, splice._removed, 0,
388 splice.removed.length));
389 }
390
391 return splices;
392 }
OLDNEW
« no previous file with comments | « packages/observe/lib/src/dirty_check.dart ('k') | packages/observe/lib/src/list_path_observer.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698