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

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

Issue 1616953004: Fixed strong mode errors and warnings reachable from lib/observe.dart (Closed) Base URL: https://github.com/dart-lang/observe.git@master
Patch Set: Reformat Created 4 years, 11 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
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file 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 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. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 library observe.src.list_diff; 5 library observe.src.list_diff;
6 6
7 import 'dart:math' as math; 7 import 'dart:math' as math;
8 import 'dart:collection' show UnmodifiableListView; 8 import 'dart:collection' show UnmodifiableListView;
9 import 'change_record.dart' show ChangeRecord; 9 import 'change_record.dart' show ChangeRecord;
10 10
(...skipping 23 matching lines...) Expand all
34 // we build the object. It will be "frozen" by the time it is returned the the 34 // we build the object. It will be "frozen" by the time it is returned the the
35 // user. 35 // user.
36 int _index, _addedCount; 36 int _index, _addedCount;
37 37
38 ListChangeRecord._(this.object, this._index, removed, this._addedCount) 38 ListChangeRecord._(this.object, this._index, removed, this._addedCount)
39 : _removed = removed, 39 : _removed = removed,
40 _unmodifiableRemoved = new UnmodifiableListView(removed); 40 _unmodifiableRemoved = new UnmodifiableListView(removed);
41 41
42 factory ListChangeRecord(List object, int index, 42 factory ListChangeRecord(List object, int index,
43 {List removed, int addedCount}) { 43 {List removed, int addedCount}) {
44
45 if (removed == null) removed = []; 44 if (removed == null) removed = [];
46 if (addedCount == null) addedCount = 0; 45 if (addedCount == null) addedCount = 0;
47 return new ListChangeRecord._(object, index, removed, addedCount); 46 return new ListChangeRecord._(object, index, removed, addedCount);
48 } 47 }
49 48
50 /// Returns true if the provided index was changed by this operation. 49 /// Returns true if the provided index was changed by this operation.
51 bool indexChanged(key) { 50 bool indexChanged(key) {
52 // If key isn't an int, or before the index, then it wasn't changed. 51 // If key isn't an int, or before the index, then it wasn't changed.
53 if (key is! int || key < index) return false; 52 if (key is! int || key < index) return false;
54 53
(...skipping 17 matching lines...) Expand all
72 // 'xxxx123' -> '123yyyy' 71 // 'xxxx123' -> '123yyyy'
73 // 72 //
74 // With 1-edit updates, the shortest path would be just to update all seven 73 // 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 74 // characters. With 2-edit updates, we delete 4, leave 3, and add 4. This
76 // leaves the substring '123' intact. 75 // leaves the substring '123' intact.
77 List<List<int>> _calcEditDistances(List current, int currentStart, 76 List<List<int>> _calcEditDistances(List current, int currentStart,
78 int currentEnd, List old, int oldStart, int oldEnd) { 77 int currentEnd, List old, int oldStart, int oldEnd) {
79 // "Deletion" columns 78 // "Deletion" columns
80 var rowCount = oldEnd - oldStart + 1; 79 var rowCount = oldEnd - oldStart + 1;
81 var columnCount = currentEnd - currentStart + 1; 80 var columnCount = currentEnd - currentStart + 1;
82 var distances = new List(rowCount); 81 var distances = new List<List<int>>(rowCount);
83 82
84 // "Addition" rows. Initialize null column. 83 // "Addition" rows. Initialize null column.
85 for (var i = 0; i < rowCount; i++) { 84 for (var i = 0; i < rowCount; i++) {
86 distances[i] = new List(columnCount); 85 distances[i] = new List(columnCount);
87 distances[i][0] = i; 86 distances[i][0] = i;
88 } 87 }
89 88
90 // Initialize null row 89 // Initialize null row
91 for (var j = 0; j < columnCount; j++) { 90 for (var j = 0; j < columnCount; j++) {
92 distances[0][j] = j; 91 distances[0][j] = j;
(...skipping 19 matching lines...) Expand all
112 const _EDIT_ADD = 2; 111 const _EDIT_ADD = 2;
113 const _EDIT_DELETE = 3; 112 const _EDIT_DELETE = 3;
114 113
115 // This starts at the final weight, and walks "backward" by finding 114 // This starts at the final weight, and walks "backward" by finding
116 // the minimum previous weight recursively until the origin of the weight 115 // the minimum previous weight recursively until the origin of the weight
117 // matrix. 116 // matrix.
118 List<int> _spliceOperationsFromEditDistances(List<List<int>> distances) { 117 List<int> _spliceOperationsFromEditDistances(List<List<int>> distances) {
119 var i = distances.length - 1; 118 var i = distances.length - 1;
120 var j = distances[0].length - 1; 119 var j = distances[0].length - 1;
121 var current = distances[i][j]; 120 var current = distances[i][j];
122 var edits = []; 121 var edits = <int>[];
123 while (i > 0 || j > 0) { 122 while (i > 0 || j > 0) {
124 if (i == 0) { 123 if (i == 0) {
125 edits.add(_EDIT_ADD); 124 edits.add(_EDIT_ADD);
126 j--; 125 j--;
127 continue; 126 continue;
128 } 127 }
129 if (j == 0) { 128 if (j == 0) {
130 edits.add(_EDIT_DELETE); 129 edits.add(_EDIT_DELETE);
131 i--; 130 i--;
132 continue; 131 continue;
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
182 /// Lacking individual splice mutation information, the minimal set of 181 /// Lacking individual splice mutation information, the minimal set of
183 /// splices can be synthesized given the previous state and final state of an 182 /// 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 183 /// array. The basic approach is to calculate the edit distance matrix and
185 /// choose the shortest path through it. 184 /// choose the shortest path through it.
186 /// 185 ///
187 /// Complexity: O(l * p) 186 /// Complexity: O(l * p)
188 /// l: The length of the current array 187 /// l: The length of the current array
189 /// p: The length of the old array 188 /// p: The length of the old array
190 List<ListChangeRecord> calcSplices(List current, int currentStart, 189 List<ListChangeRecord> calcSplices(List current, int currentStart,
191 int currentEnd, List old, int oldStart, int oldEnd) { 190 int currentEnd, List old, int oldStart, int oldEnd) {
192
193 var prefixCount = 0; 191 var prefixCount = 0;
194 var suffixCount = 0; 192 var suffixCount = 0;
195 193
196 var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart); 194 var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
197 if (currentStart == 0 && oldStart == 0) { 195 if (currentStart == 0 && oldStart == 0) {
198 prefixCount = _sharedPrefix(current, old, minLength); 196 prefixCount = _sharedPrefix(current, old, minLength);
199 } 197 }
200 198
201 if (currentEnd == current.length && oldEnd == old.length) { 199 if (currentEnd == current.length && oldEnd == old.length) {
202 suffixCount = _sharedSuffix(current, old, minLength - prefixCount); 200 suffixCount = _sharedSuffix(current, old, minLength - prefixCount);
203 } 201 }
204 202
205 currentStart += prefixCount; 203 currentStart += prefixCount;
206 oldStart += prefixCount; 204 oldStart += prefixCount;
207 currentEnd -= suffixCount; 205 currentEnd -= suffixCount;
208 oldEnd -= suffixCount; 206 oldEnd -= suffixCount;
209 207
210 if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) { 208 if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
211 return const []; 209 return const [];
212 } 210 }
213 211
214 if (currentStart == currentEnd) { 212 if (currentStart == currentEnd) {
215 var splice = new ListChangeRecord(current, currentStart); 213 var splice = new ListChangeRecord(current, currentStart);
216 while (oldStart < oldEnd) { 214 while (oldStart < oldEnd) {
217 splice._removed.add(old[oldStart++]); 215 splice._removed.add(old[oldStart++]);
218 } 216 }
219 217
220 return [splice ]; 218 return [splice];
221 } else if (oldStart == oldEnd) 219 } else if (oldStart == oldEnd)
Bob Nystrom 2016/01/22 18:50:25 Braces around the else.
vsm 2016/01/22 19:05:05 Done.
222 return [new ListChangeRecord(current, currentStart, 220 return [
223 addedCount: currentEnd - currentStart)]; 221 new ListChangeRecord(current, currentStart,
222 addedCount: currentEnd - currentStart)
223 ];
224 224
225 var ops = _spliceOperationsFromEditDistances( 225 var ops = _spliceOperationsFromEditDistances(_calcEditDistances(
226 _calcEditDistances(current, currentStart, currentEnd, old, oldStart, 226 current, currentStart, currentEnd, old, oldStart, oldEnd));
227 oldEnd));
228 227
229 ListChangeRecord splice = null; 228 ListChangeRecord splice = null;
230 var splices = <ListChangeRecord>[]; 229 var splices = <ListChangeRecord>[];
231 var index = currentStart; 230 var index = currentStart;
232 var oldIndex = oldStart; 231 var oldIndex = oldStart;
233 for (var i = 0; i < ops.length; i++) { 232 for (var i = 0; i < ops.length; i++) {
234 switch(ops[i]) { 233 switch (ops[i]) {
235 case _EDIT_LEAVE: 234 case _EDIT_LEAVE:
236 if (splice != null) { 235 if (splice != null) {
237 splices.add(splice); 236 splices.add(splice);
238 splice = null; 237 splice = null;
239 } 238 }
240 239
241 index++; 240 index++;
242 oldIndex++; 241 oldIndex++;
243 break; 242 break;
244 case _EDIT_UPDATE: 243 case _EDIT_UPDATE:
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
283 // - the loop finds where the merge should happen 282 // - the loop finds where the merge should happen
284 // - it applies the merge in a particular splice 283 // - it applies the merge in a particular splice
285 // - then continues and updates the subsequent splices with any offset diff. 284 // - then continues and updates the subsequent splices with any offset diff.
286 for (var i = 0; i < splices.length; i++) { 285 for (var i = 0; i < splices.length; i++) {
287 final current = splices[i]; 286 final current = splices[i];
288 current._index += insertionOffset; 287 current._index += insertionOffset;
289 288
290 if (inserted) continue; 289 if (inserted) continue;
291 290
292 var intersectCount = _intersect( 291 var intersectCount = _intersect(
293 splice.index, splice.index + splice.removed.length, 292 splice.index,
294 current.index, current.index + current.addedCount); 293 splice.index + splice.removed.length,
294 current.index,
295 current.index + current.addedCount);
295 296
296 if (intersectCount >= 0) { 297 if (intersectCount >= 0) {
297 // Merge the two splices 298 // Merge the two splices
298 299
299 splices.removeAt(i); 300 splices.removeAt(i);
300 i--; 301 i--;
301 302
302 insertionOffset -= current.addedCount - current.removed.length; 303 insertionOffset -= current.addedCount - current.removed.length;
303 304
304 splice._addedCount += current.addedCount - intersectCount; 305 splice._addedCount += current.addedCount - intersectCount;
305 var deleteCount = splice.removed.length + 306 var deleteCount =
306 current.removed.length - intersectCount; 307 splice.removed.length + current.removed.length - intersectCount;
307 308
308 if (splice.addedCount == 0 && deleteCount == 0) { 309 if (splice.addedCount == 0 && deleteCount == 0) {
309 // merged splice is a noop. discard. 310 // merged splice is a noop. discard.
310 inserted = true; 311 inserted = true;
311 } else { 312 } else {
312 var removed = current._removed; 313 var removed = current._removed;
313 314
314 if (splice.index < current.index) { 315 if (splice.index < current.index) {
315 // some prefix of splice.removed is prepended to current.removed. 316 // some prefix of splice.removed is prepended to current.removed.
316 removed.insertAll(0, 317 removed.insertAll(
317 splice.removed.getRange(0, current.index - splice.index)); 318 0, splice.removed.getRange(0, current.index - splice.index));
318 } 319 }
319 320
320 if (splice.index + splice.removed.length > 321 if (splice.index + splice.removed.length >
321 current.index + current.addedCount) { 322 current.index + current.addedCount) {
322 // some suffix of splice.removed is appended to current.removed. 323 // some suffix of splice.removed is appended to current.removed.
323 removed.addAll(splice.removed.getRange( 324 removed.addAll(splice.removed.getRange(
324 current.index + current.addedCount - splice.index, 325 current.index + current.addedCount - splice.index,
325 splice.removed.length)); 326 splice.removed.length));
326 } 327 }
327 328
(...skipping 13 matching lines...) Expand all
341 342
342 var offset = splice.addedCount - splice.removed.length; 343 var offset = splice.addedCount - splice.removed.length;
343 current._index += offset; 344 current._index += offset;
344 insertionOffset += offset; 345 insertionOffset += offset;
345 } 346 }
346 } 347 }
347 348
348 if (!inserted) splices.add(splice); 349 if (!inserted) splices.add(splice);
349 } 350 }
350 351
351 List<ListChangeRecord> _createInitialSplices(List<Object> list, 352 List<ListChangeRecord> _createInitialSplices(
352 List<ListChangeRecord> records) { 353 List<Object> list, List<ListChangeRecord> records) {
353
354 var splices = <ListChangeRecord>[]; 354 var splices = <ListChangeRecord>[];
355 for (var record in records) { 355 for (var record in records) {
356 _mergeSplice(splices, record); 356 _mergeSplice(splices, record);
357 } 357 }
358 return splices; 358 return splices;
359 } 359 }
360 360
361 /// We need to summarize change records. Consumers of these records want to 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 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 363 /// items by looking at that position in the list. This property does not
364 /// hold in our record-as-you-go records. Consider: 364 /// hold in our record-as-you-go records. Consider:
365 /// 365 ///
366 /// var model = toObservable(['a', 'b']); 366 /// var model = toObservable(['a', 'b']);
367 /// model.removeAt(1); 367 /// model.removeAt(1);
368 /// model.insertAll(0, ['c', 'd', 'e']); 368 /// model.insertAll(0, ['c', 'd', 'e']);
369 /// model.removeRange(1, 3); 369 /// model.removeRange(1, 3);
370 /// model.insert(1, 'f'); 370 /// model.insert(1, 'f');
371 /// 371 ///
372 /// Here, we inserted some records and then removed some of them. 372 /// Here, we inserted some records and then removed some of them.
373 /// If someone processed these records naively, they would "play back" the 373 /// If someone processed these records naively, they would "play back" the
374 /// insert incorrectly, because those items will be shifted. 374 /// insert incorrectly, because those items will be shifted.
375 List<ListChangeRecord> projectListSplices(List list, 375 List<ListChangeRecord> projectListSplices(
376 List<ListChangeRecord> records) { 376 List list, List<ListChangeRecord> records) {
Bob Nystrom 2016/01/22 18:50:25 List -> List<Object>?
vsm 2016/01/22 19:05:05 Done.
377 if (records.length <= 1) return records; 377 if (records.length <= 1) return records;
378 378
379 var splices = []; 379 var splices = <ListChangeRecord>[];
380 for (var splice in _createInitialSplices(list, records)) { 380 for (var splice in _createInitialSplices(list, records)) {
381 if (splice.addedCount == 1 && splice.removed.length == 1) { 381 if (splice.addedCount == 1 && splice.removed.length == 1) {
382 if (splice.removed[0] != list[splice.index]) splices.add(splice); 382 if (splice.removed[0] != list[splice.index]) splices.add(splice);
383 continue; 383 continue;
384 } 384 }
385 385
386 splices.addAll(calcSplices(list, splice.index, 386 splices.addAll(calcSplices(
387 splice.index + splice.addedCount, splice._removed, 0, 387 list,
388 splice.index,
389 splice.index + splice.addedCount,
390 splice._removed,
391 0,
388 splice.removed.length)); 392 splice.removed.length));
389 } 393 }
390 394
391 return splices; 395 return splices;
392 } 396 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698