blob: a974cf6d1b77c156f01db71ee70e97fe9e7b2991 (
about) (
plain)
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
(define-module (language python module bisect)
#:use-module (oop pf-objects)
#:use-module (language python list)
#:use-module (language python def)
#:use-module (language python try)
#:use-module (language python exceptions)
#:export (insort_right insort bisect bisect_right
bisect_left insort_left))
(def (insort_right a x (= lo 0) (= hi None))
"Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"
(if (< lo 0)
(raise ValueError "lo must be non-negative"))
(if (eq? hi None)
(set! hi (len a)))
(call-with-values
(lambda ()
(let lp ((lo lo) (hi hi))
(if (< lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(if (< x (pylist-ref a mid))
(lp lo mid)
(lp (+ mid 1) hi )))
(values lo hi))))
(lambda (lo hi)
(pylist-insert! a lo x))))
(define insort insort_right)
(def (bisect_right a x (= lo 0) (= hi None))
"Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"
(if (< lo 0)
(raise ValueError "lo must be non-negative"))
(if (eq? hi None)
(set! hi (len a)))
(call-with-values
(lambda ()
(let lp ((lo lo) (hi hi))
(if (< lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(if (< x (pylist-ref a mid))
(lp lo mid)
(lp (+ mid 1) hi )))
(values lo hi))))
(lambda (lo hi)
lo)))
(define bisect bisect_right)
(def (insort_left a x (= lo 0) (= hi None))
"Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the left of the leftmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"
(if (< lo 0)
(raise ValueError "lo must be non-negative"))
(if (eq? hi None)
(set! hi (len a)))
(call-with-values
(lambda ()
(let lp ((lo lo) (hi hi))
(if (< lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(if (< (pylist-ref a mid) x)
(lp (+ mid 1) hi )
(lp lo mid)))
(values lo hi))))
(lambda (lo hi)
(pylist-insert! a lo x))))
(def (bisect_left a x (= lo 0) (= hi None))
"Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"
(if (< lo 0)
(raise ValueError "lo must be non-negative"))
(if (eq? hi None)
(set! hi (len a)))
(call-with-values
(lambda ()
(let lp ((lo lo) (hi hi))
(if (< lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(if (< (pylist-ref a mid) x)
(lp (+ mid 1) hi )
(lp lo mid)))
(values lo hi))))
(lambda (lo hi)
lo)))
|
