diff options
author | Stefan Israelsson Tampe <stefan.itampe@gmail.com> | 2018-03-22 10:40:49 +0100 |
---|---|---|
committer | Stefan Israelsson Tampe <stefan.itampe@gmail.com> | 2018-03-22 10:40:49 +0100 |
commit | 03095ee8a6b3564dc48e6a8382192a5044824681 (patch) | |
tree | 07d40ef2c500ae0efe17d5b7e7646f1d4e0d667a /modules/language/python | |
parent | 1f86ca7767d661a42b3e66f667bb044f9c861346 (diff) |
bisect module
Diffstat (limited to 'modules/language/python')
-rw-r--r-- | modules/language/python/module/bisect.scm | 123 |
1 files changed, 123 insertions, 0 deletions
diff --git a/modules/language/python/module/bisect.scm b/modules/language/python/module/bisect.scm new file mode 100644 index 0000000..a974cf6 --- /dev/null +++ b/modules/language/python/module/bisect.scm @@ -0,0 +1,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))) |