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

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: Removed inferrable type param 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
« no previous file with comments | « lib/src/dirty_check.dart ('k') | lib/src/list_path_observer.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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) {
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
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
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 }
OLDNEW
« no previous file with comments | « lib/src/dirty_check.dart ('k') | lib/src/list_path_observer.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698