bisection 0.3.1+1

Searching in sorted lists. Adding items while maintaining the sort order. Port of the Python bisect library.

bisection

Library for searching in sorted lists and adding items while maintaining the sort order.

Port of the Python bisect with search functions.

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
}

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
}

Python bisect	Dart bisection extension methods
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)]

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 the value is negative, an exception will be thrown. In the case of Python, a rather mysterious value would be returned.