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

Side by Side Diff: pkg/observe/lib/src/list_diff.dart

Issue 178683003: [observe] use consistent comment style (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 9 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 | Annotate | Revision Log
« no previous file with comments | « pkg/observe/lib/src/dirty_check.dart ('k') | pkg/observe/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 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
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
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 }
OLDNEW
« no previous file with comments | « pkg/observe/lib/src/dirty_check.dart ('k') | pkg/observe/lib/src/list_path_observer.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698