bisection

Description:

bisection

bisection #
Library for searching in sorted lists and adding items while maintaining the
sort order.
Port of the Python bisect with
binary search functions
.
If you import bisect.dart, you will get functions with names like in the
Python bisect package. If you import extension.dart, you will get methods
that are more consistent with Dart design standards.



package:bisection/bisect.dart
package:bisection/extension.dart




bisect(arr, x)
arr.bisectRight(x)


bisect_left(arr, x)
arr.bisectLeft(x)


bisect_right(arr, x)
arr.bisectRight(x)


insort(arr, x)
arr.insortRight(x)


insort_left(arr, x)
arr.insortLeft(x)


insort_right(arr, x)
arr.insortRight(x)


index(arr, x)
arr[arr.bsearch(x)]]


find_lt(arr, x)
arr[arr.bsearchLessThan(x)]


find_le(arr, x)
arr[arr.bsearchLessThanOrEqualTo(x)]


find_gt(arr, x)
arr[arr.bsearchGreaterThan(x)]


find_ge(arr, x)
arr[arr.bsearchGreaterThanOrEqualTo(x)]



Use bisect functions #
import 'package:bisection/bisect.dart';

void main() {
// The list must be sorted
final arr = ['A', 'B', 'C', 'E'];

// Find the index of an item in a sorted list
print(bisect(arr, 'B')); // 2

// Find the future index for a non-existent item
print(bisect_left(arr, 'D')); // 3

// Add an item to the list while keeping the list sorted
insort(arr, 'D');
print(arr); // [A, B, C, D, E]

// Locate leftmost value equal to 'C'
print(index(arr, 'C')); // 2

// Find leftmost value greater than 'C'
print(find_gt(arr, 'C')); // D
}
copied to clipboard
Use list extensions #
import 'package:bisection/extension.dart';

void main() {
// The list must be sorted
final arr = ['A', 'B', 'C', 'E'];

// Find the index of an item in a sorted list
print(arr.bisectRight('B')); // 2

// Find the future index for a non-existent item
print(arr.bisectLeft('D')); // 3

// Add an item to the list while keeping the list sorted
arr.insortRight('D');
print(arr); // [A, B, C, D, E]

// Locate leftmost value equal to 'C'
print(arr.bsearch('C')); // 2

// Locate leftmost value greater than 'C'
print(arr.bsearchGreaterThan('C')); // 3
}
copied to clipboard
Custom sorting #
Functions bisect_* and insort_* take the key argument, similar to the
argument with the same name in Python.
import 'package:bisection/bisect.dart';

void main() {
final arr = ['zebrA', 'craB', 'coyotE'];
// sorting by last char
insort(arr, 'lizarD', key: (String s) => s[s.length - 1]);
print(arr); // [zebrA, craB, lizarD, coyotE]
}
copied to clipboard
The other functions and methods take the compare argument,
a Comparator
similar to the argument
in List.sort.
import 'package:bisection/extension.dart';

void main() {
final arr = ['zebrA', 'craB', 'coyotE'];

String lastChar(String s) => s[s.length - 1];

arr.insortRight(
'lizarD',
compare: (a, b) => lastChar(a).compareTo(lastChar(b)));

print(arr); // [zebrA, craB, lizarD, coyotE]
}
copied to clipboard
Differences from Python bisect #
The library is written with the intention of repeating the results of Python
functions as accurately as possible. The consistency of the results is
by Dart unit tests
, generated by
Python scripts
.
The only difference is that this library does not accept negative values of the
hi argument. If hi value is negative, an exception will be thrown. In the
case of Python, a rather mysterious value would be returned.