bisect

Binary search over a sorted list: insertion points, membership, and order-preserving insert. Pure - no capabilities.

ecko get github.com/ecko-lang/bisect
import bisect

Pure computation: it declares no capabilities, so it cannot touch the network, the filesystem or the environment.

Version 0.39.0 - source - MIT.


left(items, x)

Returns the leftmost index where x could be inserted with the list still sorted.

When x is present this is the index of its first copy, so left answers "where does this value start". The list must already be sorted.

errors: bug/bad_argument when items is not a list.

bisect.left([10, 20, 20, 30], 20)   # 1

right(items, x)

Returns the rightmost index where x could be inserted with the list still sorted.

When x is present this is one past its last copy. The list must already be sorted.

errors: bug/bad_argument when items is not a list.

bisect.right([10, 20, 20, 30], 20)   # 3

left_by(items, x, key)

Returns the leftmost insertion index for x, comparing key(item) rather than each item itself.

errors: bug/bad_argument when items is not a list or key is not a function.

bisect.left_by(people, 35, fn(p) p.age)

right_by(items, x, key)

Returns the rightmost insertion index for x, comparing key(item) rather than each item itself.

errors: bug/bad_argument when items is not a list or key is not a function.

bisect.right_by(people, 35, fn(p) p.age)

insert_left(items, x)

Returns a new list with x inserted before any equal items, still sorted.

errors: bug/bad_argument when items is not a list.

bisect.insert_left([1, 3], 2)   # [1, 2, 3]

insert_right(items, x)

Returns a new list with x inserted after any equal items, still sorted.

errors: bug/bad_argument when items is not a list.

bisect.insert_right([1, 3], 2)   # [1, 2, 3]

insert_by(items, item, key)

Returns a new list with item inserted by key(item), after any items with an equal key, keeping the list sorted by that key.

errors: bug/bad_argument when items is not a list or key is not a function.

bisect.insert_by(people, { name: "Barbara", age: 38 }, fn(p) p.age)

at(items, x, index)

Returns a new list with x inserted at index, which must be between 0 and len(items) inclusive; len(items) appends. The list is unchanged.

errors: bug/bad_index when index is not an Int in that range; bug/bad_argument when items is not a list.

bisect.at([1, 2, 3], 9, 1)   # [1, 9, 2, 3]

has(items, x)

Returns true when the sorted list contains x, in O(log n).

errors: bug/bad_argument when items is not a list.

bisect.has([10, 20, 30], 20)   # true

index(items, x)

Returns the index of the first x in the sorted list, or null when it is absent.

errors: bug/bad_argument when items is not a list.

bisect.index([10, 20, 20], 20)   # 1

count(items, x)

Returns how many copies of x the sorted list holds.

errors: bug/bad_argument when items is not a list.

bisect.count([10, 20, 20, 30], 20)   # 2