| OLD | NEW |
|---|
| (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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 817483003:
delete observe from the repo (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart