Chromium Code Reviews| 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 import 'change_record.dart' show ChangeRecord; | 9 import 'change_record.dart' show ChangeRecord; |
| 10 | 10 |
| (...skipping 23 matching lines...) Expand all Loading... | |
| 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 Loading... | |
| 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 Loading... | |
| 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 Loading... | |
| 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 Loading... | |
| 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 Loading... | |
| 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 } |
| OLD | NEW |