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) { |
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 |
225 var ops = _spliceOperationsFromEditDistances( | 226 var ops = _spliceOperationsFromEditDistances(_calcEditDistances( |
226 _calcEditDistances(current, currentStart, currentEnd, old, oldStart, | 227 current, currentStart, currentEnd, old, oldStart, oldEnd)); |
227 oldEnd)); | |
228 | 228 |
229 ListChangeRecord splice = null; | 229 ListChangeRecord splice = null; |
230 var splices = <ListChangeRecord>[]; | 230 var splices = <ListChangeRecord>[]; |
231 var index = currentStart; | 231 var index = currentStart; |
232 var oldIndex = oldStart; | 232 var oldIndex = oldStart; |
233 for (var i = 0; i < ops.length; i++) { | 233 for (var i = 0; i < ops.length; i++) { |
234 switch(ops[i]) { | 234 switch (ops[i]) { |
235 case _EDIT_LEAVE: | 235 case _EDIT_LEAVE: |
236 if (splice != null) { | 236 if (splice != null) { |
237 splices.add(splice); | 237 splices.add(splice); |
238 splice = null; | 238 splice = null; |
239 } | 239 } |
240 | 240 |
241 index++; | 241 index++; |
242 oldIndex++; | 242 oldIndex++; |
243 break; | 243 break; |
244 case _EDIT_UPDATE: | 244 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 | 283 // - the loop finds where the merge should happen |
284 // - it applies the merge in a particular splice | 284 // - it applies the merge in a particular splice |
285 // - then continues and updates the subsequent splices with any offset diff. | 285 // - then continues and updates the subsequent splices with any offset diff. |
286 for (var i = 0; i < splices.length; i++) { | 286 for (var i = 0; i < splices.length; i++) { |
287 final current = splices[i]; | 287 final current = splices[i]; |
288 current._index += insertionOffset; | 288 current._index += insertionOffset; |
289 | 289 |
290 if (inserted) continue; | 290 if (inserted) continue; |
291 | 291 |
292 var intersectCount = _intersect( | 292 var intersectCount = _intersect( |
293 splice.index, splice.index + splice.removed.length, | 293 splice.index, |
294 current.index, current.index + current.addedCount); | 294 splice.index + splice.removed.length, |
| 295 current.index, |
| 296 current.index + current.addedCount); |
295 | 297 |
296 if (intersectCount >= 0) { | 298 if (intersectCount >= 0) { |
297 // Merge the two splices | 299 // Merge the two splices |
298 | 300 |
299 splices.removeAt(i); | 301 splices.removeAt(i); |
300 i--; | 302 i--; |
301 | 303 |
302 insertionOffset -= current.addedCount - current.removed.length; | 304 insertionOffset -= current.addedCount - current.removed.length; |
303 | 305 |
304 splice._addedCount += current.addedCount - intersectCount; | 306 splice._addedCount += current.addedCount - intersectCount; |
305 var deleteCount = splice.removed.length + | 307 var deleteCount = |
306 current.removed.length - intersectCount; | 308 splice.removed.length + current.removed.length - intersectCount; |
307 | 309 |
308 if (splice.addedCount == 0 && deleteCount == 0) { | 310 if (splice.addedCount == 0 && deleteCount == 0) { |
309 // merged splice is a noop. discard. | 311 // merged splice is a noop. discard. |
310 inserted = true; | 312 inserted = true; |
311 } else { | 313 } else { |
312 var removed = current._removed; | 314 var removed = current._removed; |
313 | 315 |
314 if (splice.index < current.index) { | 316 if (splice.index < current.index) { |
315 // some prefix of splice.removed is prepended to current.removed. | 317 // some prefix of splice.removed is prepended to current.removed. |
316 removed.insertAll(0, | 318 removed.insertAll( |
317 splice.removed.getRange(0, current.index - splice.index)); | 319 0, splice.removed.getRange(0, current.index - splice.index)); |
318 } | 320 } |
319 | 321 |
320 if (splice.index + splice.removed.length > | 322 if (splice.index + splice.removed.length > |
321 current.index + current.addedCount) { | 323 current.index + current.addedCount) { |
322 // some suffix of splice.removed is appended to current.removed. | 324 // some suffix of splice.removed is appended to current.removed. |
323 removed.addAll(splice.removed.getRange( | 325 removed.addAll(splice.removed.getRange( |
324 current.index + current.addedCount - splice.index, | 326 current.index + current.addedCount - splice.index, |
325 splice.removed.length)); | 327 splice.removed.length)); |
326 } | 328 } |
327 | 329 |
(...skipping 13 matching lines...) Expand all Loading... |
341 | 343 |
342 var offset = splice.addedCount - splice.removed.length; | 344 var offset = splice.addedCount - splice.removed.length; |
343 current._index += offset; | 345 current._index += offset; |
344 insertionOffset += offset; | 346 insertionOffset += offset; |
345 } | 347 } |
346 } | 348 } |
347 | 349 |
348 if (!inserted) splices.add(splice); | 350 if (!inserted) splices.add(splice); |
349 } | 351 } |
350 | 352 |
351 List<ListChangeRecord> _createInitialSplices(List<Object> list, | 353 List<ListChangeRecord> _createInitialSplices( |
352 List<ListChangeRecord> records) { | 354 List<Object> list, List<ListChangeRecord> records) { |
353 | |
354 var splices = <ListChangeRecord>[]; | 355 var splices = <ListChangeRecord>[]; |
355 for (var record in records) { | 356 for (var record in records) { |
356 _mergeSplice(splices, record); | 357 _mergeSplice(splices, record); |
357 } | 358 } |
358 return splices; | 359 return splices; |
359 } | 360 } |
360 | 361 |
361 /// We need to summarize change records. Consumers of these records want to | 362 /// 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 /// 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 /// items by looking at that position in the list. This property does not |
364 /// hold in our record-as-you-go records. Consider: | 365 /// hold in our record-as-you-go records. Consider: |
365 /// | 366 /// |
366 /// var model = toObservable(['a', 'b']); | 367 /// var model = toObservable(['a', 'b']); |
367 /// model.removeAt(1); | 368 /// model.removeAt(1); |
368 /// model.insertAll(0, ['c', 'd', 'e']); | 369 /// model.insertAll(0, ['c', 'd', 'e']); |
369 /// model.removeRange(1, 3); | 370 /// model.removeRange(1, 3); |
370 /// model.insert(1, 'f'); | 371 /// model.insert(1, 'f'); |
371 /// | 372 /// |
372 /// Here, we inserted some records and then removed some of them. | 373 /// Here, we inserted some records and then removed some of them. |
373 /// If someone processed these records naively, they would "play back" the | 374 /// If someone processed these records naively, they would "play back" the |
374 /// insert incorrectly, because those items will be shifted. | 375 /// insert incorrectly, because those items will be shifted. |
375 List<ListChangeRecord> projectListSplices(List list, | 376 List<ListChangeRecord> projectListSplices( |
376 List<ListChangeRecord> records) { | 377 List<Object> list, List<ListChangeRecord> records) { |
377 if (records.length <= 1) return records; | 378 if (records.length <= 1) return records; |
378 | 379 |
379 var splices = []; | 380 var splices = <ListChangeRecord>[]; |
380 for (var splice in _createInitialSplices(list, records)) { | 381 for (var splice in _createInitialSplices(list, records)) { |
381 if (splice.addedCount == 1 && splice.removed.length == 1) { | 382 if (splice.addedCount == 1 && splice.removed.length == 1) { |
382 if (splice.removed[0] != list[splice.index]) splices.add(splice); | 383 if (splice.removed[0] != list[splice.index]) splices.add(splice); |
383 continue; | 384 continue; |
384 } | 385 } |
385 | 386 |
386 splices.addAll(calcSplices(list, splice.index, | 387 splices.addAll(calcSplices( |
387 splice.index + splice.addedCount, splice._removed, 0, | 388 list, |
| 389 splice.index, |
| 390 splice.index + splice.addedCount, |
| 391 splice._removed, |
| 392 0, |
388 splice.removed.length)); | 393 splice.removed.length)); |
389 } | 394 } |
390 | 395 |
391 return splices; | 396 return splices; |
392 } | 397 } |
OLD | NEW |