| 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 import 'package:unittest/unittest.dart'; | |
| 6 import 'package:source_span/src/utils.dart'; | |
| 7 | |
| 8 main() { | |
| 9 group('binary search', () { | |
| 10 test('empty', () { | |
| 11 expect(binarySearch([], (x) => true), -1); | |
| 12 }); | |
| 13 | |
| 14 test('single element', () { | |
| 15 expect(binarySearch([1], (x) => true), 0); | |
| 16 expect(binarySearch([1], (x) => false), 1); | |
| 17 }); | |
| 18 | |
| 19 test('no matches', () { | |
| 20 var list = [1, 2, 3, 4, 5, 6, 7]; | |
| 21 expect(binarySearch(list, (x) => false), list.length); | |
| 22 }); | |
| 23 | |
| 24 test('all match', () { | |
| 25 var list = [1, 2, 3, 4, 5, 6, 7]; | |
| 26 expect(binarySearch(list, (x) => true), 0); | |
| 27 }); | |
| 28 | |
| 29 test('compare with linear search', () { | |
| 30 for (int size = 0; size < 100; size++) { | |
| 31 var list = []; | |
| 32 for (int i = 0; i < size; i++) { | |
| 33 list.add(i); | |
| 34 } | |
| 35 for (int pos = 0; pos <= size; pos++) { | |
| 36 expect(binarySearch(list, (x) => x >= pos), | |
| 37 _linearSearch(list, (x) => x >= pos)); | |
| 38 } | |
| 39 } | |
| 40 }); | |
| 41 }); | |
| 42 } | |
| 43 | |
| 44 _linearSearch(list, predicate) { | |
| 45 if (list.length == 0) return -1; | |
| 46 for (int i = 0; i < list.length; i++) { | |
| 47 if (predicate(list[i])) return i; | |
| 48 } | |
| 49 return list.length; | |
| 50 } | |
| 51 | |
| OLD | NEW |