Repository navigation
Expand file tree
/
Copy pathstdlib_bisect.py
More file actions
73 lines (49 loc) · 2.01 KB
/
Copy pathstdlib_bisect.py
File metadata and controls
73 lines (49 loc) · 2.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from bisect import bisect_left, bisect_right, insort, insort_left, insort_right
# A key decides where the item goes, but the item is what gets stored.
for insort_fn in (insort, insort_left, insort_right):
words = ["a", "ccc"]
insort_fn(words, "bb", key=len)
assert words == ["a", "bb", "ccc"], (insort_fn.__name__, words)
numbers = [1, 3]
insort_fn(numbers, -2, key=abs)
assert numbers == [1, -2, 3], (insort_fn.__name__, numbers)
pairs = [(1, "a"), (3, "b")]
insort_fn(pairs, (2, "x"), key=lambda pair: pair[0])
assert pairs == [(1, "a"), (2, "x"), (3, "b")], (insort_fn.__name__, pairs)
descending = [3, 1]
insort(descending, 2, key=lambda value: -value)
assert descending == [3, 2, 1], descending
class Tagged:
def __init__(self, size, tag):
self.size = size
self.tag = tag
def sizes_and_tags(items):
return [(item.size, item.tag) for item in items]
by_size = [Tagged(1, "old"), Tagged(2, "old")]
# On a tie, left goes before the equal element and right goes after it.
left = list(by_size)
insort_left(left, Tagged(2, "new"), key=lambda item: item.size)
assert sizes_and_tags(left) == [(1, "old"), (2, "new"), (2, "old")]
right = list(by_size)
insort_right(right, Tagged(2, "new"), key=lambda item: item.size)
assert sizes_and_tags(right) == [(1, "old"), (2, "old"), (2, "new")]
# The key runs once on the new item, whatever the search does afterwards.
seen = []
def counting_key(value):
seen.append(value)
return value
data = [1, 3, 5, 7]
insort(data, 4, key=counting_key)
assert data == [1, 3, 4, 5, 7], data
assert seen.count(4) == 1, seen
# lo and hi bound the search and leave the inserted item alone.
bounded = [3, 1]
insort(bounded, 2, 0, 1, key=lambda value: -value)
assert bounded == [3, 2, 1], bounded
plain = [1, 3]
insort(plain, 2)
assert plain == [1, 2, 3], plain
# The search takes the key value itself, so these two stay where they were.
sizes = ["a", "bb", "ccc"]
assert bisect_left(sizes, 2, key=len) == 1
assert bisect_right(sizes, 2, key=len) == 2