Reduce consing and recursion in split-delimited-string
authorUtz-Uwe Haus <lisp@uuhaus.de>
Tue, 22 Jun 2010 20:42:48 +0000 (22 22:42 +0200)
committerUtz-Uwe Haus <lisp@uuhaus.de>
Tue, 22 Jun 2010 20:42:48 +0000 (22 22:42 +0200)
ACL did not recognize tail-recursion

Signed-off-by: Utz-Uwe Haus <lisp@uuhaus.de>
dimacs.lisp
satwrap.lisp

index 0073690..c408ee2 100644 (file)
   "Return a list of the substrings of STRING that are separated by CHAR. Without CHAR."
   (declare (type string string)
            (type character char))
-  (let ((next-separator (position char string :test #'char=)))
-    (if next-separator
-        (cons (subseq string 0 next-separator)
-              (split-delimited-string (subseq string (1+ next-separator))
-                                      char))
-        `(,string))))
+  (let ((res '()))
+    (loop :as last-pos := 0 :then (1+ next-pos)
+       :as next-pos := (position char string :start last-pos :test #'char=)
+       :while next-pos
+       :do (push (subseq string last-pos next-pos) res)
+       :finally (push (subseq string last-pos) res))
+    (nreverse res)))
 
 (defgeneric read-dimacs (solver source)
   (:documentation "Read DIMACS-style sat problem from SOURCE into SOLVER.")
index 9bd436c..116b7b2 100644 (file)
      :always (and (not (zerop v))
                  (<= min v max))))
 
-(defmethod clause-valid ((solver sat-solver) (clause vector))
-  "Check that CLAUSE is a valid clause for SOLVER."
-  (loop
-     :with max := (sat-solver-numvars solver)
-     :with min := (- max)
-     :for v :across clause
-     :always (and (not (zerop v))
-                 (<= min v max))))
-
 (defmacro iota (n &optional (start 1))
   "Return a list of the N sequential integers starting at START (default: 1)."
   (let ((i (gensym "i")))