bisect module

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)))