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 import "dart:math" as math; | 5 import "dart:math" as math; |
| 6 | 6 |
| 7 /// Version of [binarySearch] optimized for comparable keys | 7 /// Version of [binarySearch] optimized for comparable keys |
| 8 int _comparableBinarySearch(List<Comparable> list, Comparable value) { | 8 int _comparableBinarySearch/*<T extends Comparable<T>>*/( |
| 9 List<Comparable/*<T>*/> list, Comparable/*<T>*/ value) { | |
| 9 int min = 0; | 10 int min = 0; |
| 10 int max = list.length; | 11 int max = list.length; |
| 11 while (min < max) { | 12 while (min < max) { |
| 12 int mid = min + ((max - min) >> 1); | 13 int mid = min + ((max - min) >> 1); |
| 13 var element = list[mid]; | 14 var element = list[mid]; |
| 14 int comp = element.compareTo(value); | 15 int comp = element.compareTo(value); |
| 15 if (comp == 0) return mid; | 16 if (comp == 0) return mid; |
| 16 if (comp < 0) { | 17 if (comp < 0) { |
| 17 min = mid + 1; | 18 min = mid + 1; |
| 18 } else { | 19 } else { |
| 19 max = mid; | 20 max = mid; |
| 20 } | 21 } |
| 21 } | 22 } |
| 22 return -1; | 23 return -1; |
| 23 } | 24 } |
| 24 | 25 |
| 25 /// Returns a position of the [value] in [sortedList], if it is there. | 26 /// Returns a position of the [value] in [sortedList], if it is there. |
| 26 /// | 27 /// |
| 27 /// If the list isn't sorted according to the [compare] function, the result | 28 /// If the list isn't sorted according to the [compare] function, the result |
| 28 /// is unpredictable. | 29 /// is unpredictable. |
| 29 /// | 30 /// |
| 30 /// If [compare] is omitted, it defaults to calling [Comparable.compareTo] on | 31 /// If [compare] is omitted, it defaults to calling [Comparable.compareTo] on |
| 31 /// the objects. | 32 /// the objects. |
| 32 /// | 33 /// |
| 33 /// Returns -1 if [value] is not in the list by default. | 34 /// Returns -1 if [value] is not in the list by default. |
| 34 int binarySearch(List sortedList, value, { int compare(a, b) }) { | 35 int binarySearch/*<T extends Comparable<T>>*/( |
| 36 List/*<T>*/ sortedList, /*=T*/ value, { int compare(/*=T*/ a, /*=T*/ b) }) { | |
| 35 if (compare == null) { | 37 if (compare == null) { |
| 36 return _comparableBinarySearch(sortedList, value); | 38 return _comparableBinarySearch(sortedList, value); |
| 37 } | 39 } |
| 38 int min = 0; | 40 int min = 0; |
| 39 int max = sortedList.length; | 41 int max = sortedList.length; |
| 40 while (min < max) { | 42 while (min < max) { |
| 41 int mid = min + ((max - min) >> 1); | 43 int mid = min + ((max - min) >> 1); |
| 42 var element = sortedList[mid]; | 44 var element = sortedList[mid]; |
| 43 int comp = compare(element, value); | 45 int comp = compare(element, value); |
| 44 if (comp == 0) return mid; | 46 if (comp == 0) return mid; |
| (...skipping 27 matching lines...) Expand all Loading... | |
| 72 /// [value]. | 74 /// [value]. |
| 73 /// | 75 /// |
| 74 /// If the list isn't sorted according to the [compare] function, the result | 76 /// If the list isn't sorted according to the [compare] function, the result |
| 75 /// is unpredictable. | 77 /// is unpredictable. |
| 76 /// | 78 /// |
| 77 /// If [compare] is omitted, it defaults to calling [Comparable.compareTo] on | 79 /// If [compare] is omitted, it defaults to calling [Comparable.compareTo] on |
| 78 /// the objects. | 80 /// the objects. |
| 79 /// | 81 /// |
| 80 /// Returns [sortedList.length] if all the items in [sortedList] compare less | 82 /// Returns [sortedList.length] if all the items in [sortedList] compare less |
| 81 /// than [value]. | 83 /// than [value]. |
| 82 int lowerBound(List sortedList, value, { int compare(a, b) }) { | 84 int lowerBound/*<T extends Comparable<T>>*/( |
|
abarth
2016/03/26 07:13:23
This change isn't correct. The arguments to this
| |
| 85 List/*<T>*/ sortedList, /*=T*/ value, { int compare(/*=T*/ a, /*=T*/ b) }) { | |
| 83 if (compare == null) { | 86 if (compare == null) { |
| 84 return _comparableLowerBound(sortedList, value); | 87 return _comparableLowerBound(sortedList, value); |
| 85 } | 88 } |
| 86 int min = 0; | 89 int min = 0; |
| 87 int max = sortedList.length; | 90 int max = sortedList.length; |
| 88 while (min < max) { | 91 while (min < max) { |
| 89 int mid = min + ((max - min) >> 1); | 92 int mid = min + ((max - min) >> 1); |
| 90 var element = sortedList[mid]; | 93 var element = sortedList[mid]; |
| 91 int comp = compare(element, value); | 94 int comp = compare(element, value); |
| 92 if (comp < 0) { | 95 if (comp < 0) { |
| (...skipping 221 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 314 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), | 317 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), |
| 315 firstList, cursor1); | 318 firstList, cursor1); |
| 316 return; | 319 return; |
| 317 } | 320 } |
| 318 } | 321 } |
| 319 // First list empties first. Reached by break above. | 322 // First list empties first. Reached by break above. |
| 320 target[targetOffset++] = secondElement; | 323 target[targetOffset++] = secondElement; |
| 321 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), | 324 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), |
| 322 secondList, cursor2); | 325 secondList, cursor2); |
| 323 } | 326 } |
| OLD | NEW |