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