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>>*/( |
| 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 |