| OLD | NEW |
| 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 | 9 |
| 10 /** | 10 /// A summary of an individual change to a [List]. |
| 11 * A summary of an individual change to a [List]. | 11 /// |
| 12 * | 12 /// Each delta represents that at the [index], [removed] sequence of items were |
| 13 * Each delta represents that at the [index], [removed] sequence of items were | 13 /// removed, and counting forward from [index], [addedCount] items were added. |
| 14 * removed, and counting forward from [index], [addedCount] items were added. | |
| 15 */ | |
| 16 class ListChangeRecord { | 14 class ListChangeRecord { |
| 17 /** The list that changed. */ | 15 /// The list that changed. |
| 18 final List object; | 16 final List object; |
| 19 | 17 |
| 20 /** The index of the change. */ | 18 /// The index of the change. |
| 21 int get index => _index; | 19 int get index => _index; |
| 22 | 20 |
| 23 /** The items removed, if any. Otherwise this will be an empty list. */ | 21 /// The items removed, if any. Otherwise this will be an empty list. |
| 24 List get removed => _unmodifiableRemoved; | 22 List get removed => _unmodifiableRemoved; |
| 25 UnmodifiableListView _unmodifiableRemoved; | 23 UnmodifiableListView _unmodifiableRemoved; |
| 26 | 24 |
| 27 /** | 25 /// Mutable version of [removed], used during the algorithms as they are |
| 28 * Mutable version of [removed], used during the algorithms as they are | 26 /// constructing the object. |
| 29 * constructing the object. | |
| 30 */ | |
| 31 List _removed; | 27 List _removed; |
| 32 | 28 |
| 33 /** The number of items added. */ | 29 /// The number of items added. |
| 34 int get addedCount => _addedCount; | 30 int get addedCount => _addedCount; |
| 35 | 31 |
| 36 // Note: conceptually these are final, but for convenience we increment it as | 32 // Note: conceptually these are final, but for convenience we increment it as |
| 37 // we build the object. It will be "frozen" by the time it is returned the the | 33 // we build the object. It will be "frozen" by the time it is returned the the |
| 38 // user. | 34 // user. |
| 39 int _index, _addedCount; | 35 int _index, _addedCount; |
| 40 | 36 |
| 41 ListChangeRecord._(this.object, this._index, removed, this._addedCount) | 37 ListChangeRecord._(this.object, this._index, removed, this._addedCount) |
| 42 : _removed = removed, | 38 : _removed = removed, |
| 43 _unmodifiableRemoved = new UnmodifiableListView(removed); | 39 _unmodifiableRemoved = new UnmodifiableListView(removed); |
| 44 | 40 |
| 45 factory ListChangeRecord(List object, int index, | 41 factory ListChangeRecord(List object, int index, |
| 46 {List removed, int addedCount}) { | 42 {List removed, int addedCount}) { |
| 47 | 43 |
| 48 if (removed == null) removed = []; | 44 if (removed == null) removed = []; |
| 49 if (addedCount == null) addedCount = 0; | 45 if (addedCount == null) addedCount = 0; |
| 50 return new ListChangeRecord._(object, index, removed, addedCount); | 46 return new ListChangeRecord._(object, index, removed, addedCount); |
| 51 } | 47 } |
| 52 | 48 |
| 53 /** Returns true if the provided index was changed by this operation. */ | 49 /// Returns true if the provided index was changed by this operation. |
| 54 bool indexChanged(key) { | 50 bool indexChanged(key) { |
| 55 // 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. |
| 56 if (key is! int || key < index) return false; | 52 if (key is! int || key < index) return false; |
| 57 | 53 |
| 58 // If this was a shift operation, anything after index is changed. | 54 // If this was a shift operation, anything after index is changed. |
| 59 if (addedCount != removed.length) return true; | 55 if (addedCount != removed.length) return true; |
| 60 | 56 |
| 61 // Otherwise, anything in the update range was changed. | 57 // Otherwise, anything in the update range was changed. |
| 62 return key < index + addedCount; | 58 return key < index + addedCount; |
| 63 } | 59 } |
| (...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 175 int _sharedSuffix(List arr1, List arr2, int searchLength) { | 171 int _sharedSuffix(List arr1, List arr2, int searchLength) { |
| 176 var index1 = arr1.length; | 172 var index1 = arr1.length; |
| 177 var index2 = arr2.length; | 173 var index2 = arr2.length; |
| 178 var count = 0; | 174 var count = 0; |
| 179 while (count < searchLength && arr1[--index1] == arr2[--index2]) { | 175 while (count < searchLength && arr1[--index1] == arr2[--index2]) { |
| 180 count++; | 176 count++; |
| 181 } | 177 } |
| 182 return count; | 178 return count; |
| 183 } | 179 } |
| 184 | 180 |
| 185 /** | 181 /// Lacking individual splice mutation information, the minimal set of |
| 186 * Lacking individual splice mutation information, the minimal set of | 182 /// splices can be synthesized given the previous state and final state of an |
| 187 * splices can be synthesized given the previous state and final state of an | 183 /// array. The basic approach is to calculate the edit distance matrix and |
| 188 * array. The basic approach is to calculate the edit distance matrix and | 184 /// choose the shortest path through it. |
| 189 * choose the shortest path through it. | 185 /// |
| 190 * | 186 /// Complexity: O(l * p) |
| 191 * Complexity: O(l * p) | 187 /// l: The length of the current array |
| 192 * l: The length of the current array | 188 /// p: The length of the old array |
| 193 * p: The length of the old array | |
| 194 */ | |
| 195 List<ListChangeRecord> calcSplices(List current, int currentStart, | 189 List<ListChangeRecord> calcSplices(List current, int currentStart, |
| 196 int currentEnd, List old, int oldStart, int oldEnd) { | 190 int currentEnd, List old, int oldStart, int oldEnd) { |
| 197 | 191 |
| 198 var prefixCount = 0; | 192 var prefixCount = 0; |
| 199 var suffixCount = 0; | 193 var suffixCount = 0; |
| 200 | 194 |
| 201 var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart); | 195 var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart); |
| 202 if (currentStart == 0 && oldStart == 0) { | 196 if (currentStart == 0 && oldStart == 0) { |
| 203 prefixCount = _sharedPrefix(current, old, minLength); | 197 prefixCount = _sharedPrefix(current, old, minLength); |
| 204 } | 198 } |
| (...skipping 151 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 356 List<ListChangeRecord> _createInitialSplices(List<Object> list, | 350 List<ListChangeRecord> _createInitialSplices(List<Object> list, |
| 357 List<ListChangeRecord> records) { | 351 List<ListChangeRecord> records) { |
| 358 | 352 |
| 359 var splices = <ListChangeRecord>[]; | 353 var splices = <ListChangeRecord>[]; |
| 360 for (var record in records) { | 354 for (var record in records) { |
| 361 _mergeSplice(splices, record); | 355 _mergeSplice(splices, record); |
| 362 } | 356 } |
| 363 return splices; | 357 return splices; |
| 364 } | 358 } |
| 365 | 359 |
| 366 /** | 360 /// We need to summarize change records. Consumers of these records want to |
| 367 * We need to summarize change records. Consumers of these records want to | 361 /// apply the batch sequentially, and ensure that they can find inserted |
| 368 * apply the batch sequentially, and ensure that they can find inserted | 362 /// items by looking at that position in the list. This property does not |
| 369 * items by looking at that position in the list. This property does not | 363 /// hold in our record-as-you-go records. Consider: |
| 370 * hold in our record-as-you-go records. Consider: | 364 /// |
| 371 * | 365 /// var model = toObservable(['a', 'b']); |
| 372 * var model = toObservable(['a', 'b']); | 366 /// model.removeAt(1); |
| 373 * model.removeAt(1); | 367 /// model.insertAll(0, ['c', 'd', 'e']); |
| 374 * model.insertAll(0, ['c', 'd', 'e']); | 368 /// model.removeRange(1, 3); |
| 375 * model.removeRange(1, 3); | 369 /// model.insert(1, 'f'); |
| 376 * model.insert(1, 'f'); | 370 /// |
| 377 * | 371 /// Here, we inserted some records and then removed some of them. |
| 378 * Here, we inserted some records and then removed some of them. | 372 /// If someone processed these records naively, they would "play back" the |
| 379 * If someone processed these records naively, they would "play back" the | 373 /// insert incorrectly, because those items will be shifted. |
| 380 * insert incorrectly, because those items will be shifted. | |
| 381 */ | |
| 382 List<ListChangeRecord> projectListSplices(List list, | 374 List<ListChangeRecord> projectListSplices(List list, |
| 383 List<ListChangeRecord> records) { | 375 List<ListChangeRecord> records) { |
| 384 if (records.length <= 1) return records; | 376 if (records.length <= 1) return records; |
| 385 | 377 |
| 386 var splices = []; | 378 var splices = []; |
| 387 for (var splice in _createInitialSplices(list, records)) { | 379 for (var splice in _createInitialSplices(list, records)) { |
| 388 if (splice.addedCount == 1 && splice.removed.length == 1) { | 380 if (splice.addedCount == 1 && splice.removed.length == 1) { |
| 389 if (splice.removed[0] != list[splice.index]) splices.add(splice); | 381 if (splice.removed[0] != list[splice.index]) splices.add(splice); |
| 390 continue; | 382 continue; |
| 391 } | 383 } |
| 392 | 384 |
| 393 splices.addAll(calcSplices(list, splice.index, | 385 splices.addAll(calcSplices(list, splice.index, |
| 394 splice.index + splice.addedCount, splice._removed, 0, | 386 splice.index + splice.addedCount, splice._removed, 0, |
| 395 splice.removed.length)); | 387 splice.removed.length)); |
| 396 } | 388 } |
| 397 | 389 |
| 398 return splices; | 390 return splices; |
| 399 } | 391 } |
| OLD | NEW |