bisect module
authorStefan Israelsson Tampe <stefan.itampe@gmail.com>
Thu, 22 Mar 2018 09:40:49 +0000 (10:40 +0100)
committerStefan Israelsson Tampe <stefan.itampe@gmail.com>
Thu, 22 Mar 2018 09:40:49 +0000 (10:40 +0100)
modules/language/python/module/bisect.scm [new file with mode: 0644]

diff --git a/modules/language/python/module/bisect.scm b/modules/language/python/module/bisect.scm
new file mode 100644 (file)
index 0000000..a974cf6
--- /dev/null
@@ -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)))