[prev in list] [next in list] [prev in thread] [next in thread] 

List:       sbcl-commits
Subject:    [Sbcl-commits] master: Change binary-search to return an index rathar than found item
From:       Douglas Katzman via Sbcl-commits <sbcl-commits () lists ! sourceforge ! net>
Date:       2017-11-30 19:26:22
Message-ID: 1512069982.921312.1531 () sfp-scm-8 ! v30 ! ch3 ! sourceforge ! com
[Download RAW message or body]

The branch "master" has been updated in SBCL:
       via  5f1bc41c0648f2b9b1a028c1ee24197789c187b1 (commit)
      from  2808fab8abd9cd98905f44bd6f961006efd0a723 (commit)

- Log -----------------------------------------------------------------
commit 5f1bc41c0648f2b9b1a028c1ee24197789c187b1
Author: Douglas Katzman <dougk@google.com>
Date:   Thu Nov 30 14:23:59 2017 -0500

    Change binary-search to return an index rathar than found item
    
    Useful if the key vector has a parallel value vector.
---
 src/code/target-extensions.lisp | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/src/code/target-extensions.lisp b/src/code/target-extensions.lisp
index 8c48807..e420d4e 100644
--- a/src/code/target-extensions.lisp
+++ b/src/code/target-extensions.lisp
@@ -49,8 +49,9 @@ these hooks.")
 
 
 ;;; Binary search for simple vectors
-(defun binary-search (value seq &key (key #'identity))
+(defun binary-search* (value seq key)
   (declare (simple-vector seq))
+  (declare (function key))
   (labels ((recurse (start end)
              (when (< start end)
                (let* ((i (+ start (truncate (- end start) 2)))
@@ -61,9 +62,14 @@ these hooks.")
                        ((> value key-value)
                         (recurse (1+ i) end))
                        (t
-                        elt))))))
+                        i))))))
     (recurse 0 (length seq))))
 
+(defun binary-search (value seq &key (key #'identity))
+  (let ((index (binary-search* value seq key)))
+    (if index
+        (svref seq index))))
+
 (defun double-vector-binary-search (value vector)
   (declare (simple-vector vector)
            (optimize speed)

-----------------------------------------------------------------------


hooks/post-receive
-- 
SBCL

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Sbcl-commits mailing list
Sbcl-commits@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-commits
[prev in list] [next in list] [prev in thread] [next in thread]