funds-cvs

funds-cvs@common-lisp.net

225 discussions

[funds-cvs] r178 - trunk/funds/src
by abaine＠common-lisp.net 20 Aug '07

20 Aug '07

Author: abaine Date: Sun Aug 19 21:18:02 2007 New Revision: 178 Modified: trunk/funds/src/package.lisp Log: Exported bt-key and bt-value. Modified: trunk/funds/src/package.lisp ============================================================================== --- trunk/funds/src/package.lisp (original) +++ trunk/funds/src/package.lisp Sun Aug 19 21:18:02 2007 @@ -22,6 +22,9 @@ (:export :make-avl-tree :make-binary-tree + :bt-key + :bt-value + :tree-insert :tree-remove :tree-find

1 0

[funds-cvs] r177 - trunk/funds/src/examples
by abaine＠common-lisp.net 20 Aug '07

20 Aug '07

Author: abaine Date: Sun Aug 19 21:04:25 2007 New Revision: 177 Modified: trunk/funds/src/examples/sudoku.lisp Log: Removed stupid 'optimization' from solver. Modified: trunk/funds/src/examples/sudoku.lisp ============================================================================== --- trunk/funds/src/examples/sudoku.lisp (original) +++ trunk/funds/src/examples/sudoku.lisp Sun Aug 19 21:04:25 2007 @@ -135,8 +135,6 @@ (iter (for f in x-y-z-functions) (for (values x y n) = (best-group puzzle f)) (finding (list f x y) minimizing n into (best-list min)) - (when (= min 1) - (return (apply #'solve-group puzzle best-list))) (finally (return (apply #'solve-group puzzle best-list))))) nil)) @@ -147,13 +145,9 @@ (iter (for y below size) (for n = (group-freedom puzzle x-y-z-function x y)) (finding y minimizing n into (best-y min)) - (when (= min 1) - (return (values best-y min))) (finally (return (values best-y min))))) (finding x minimizing n into best-x) (finding y minimizing n into (best-y best-n)) - (when (= best-n 1) - (return (values best-x best-y best-n))) (finally (return (values best-x best-y best-n)))))) (defun group-freedom (puzzle x-y-z-function x y)

1 0

[funds-cvs] r176 - trunk/funds/src/trees
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 17:46:09 2007 New Revision: 176 Modified: trunk/funds/src/trees/utilities.lisp Log: Fixed tree-count and tree-count-if. Modified: trunk/funds/src/trees/utilities.lisp ============================================================================== --- trunk/funds/src/trees/utilities.lisp (original) +++ trunk/funds/src/trees/utilities.lisp Sun Aug 19 17:46:09 2007 @@ -1,18 +1,18 @@ (in-package :funds) -(defun tree-count (item tree &key (key #'bt-value) (test #'eql)) +(defun tree-count (item tree &key (key #'identity) (test #'eql)) "The number of sub-trees in the tree that satisfy the test." - (tree-count #'(lambda (x) - (funcall test x item)) - :key key)) + (tree-count-if #'(lambda (x) (funcall test x item)) + tree + :key key)) -(defun tree-count-if (predicate tree &key (key #'bt-value)) +(defun tree-count-if (predicate tree &key (key #'identity)) "The number of sub-trees in the given tree that satisfy the test." (if (tree-empty-p tree) 0 (+ (tree-count-if predicate (bt-left tree) :key key) - (funcall predicate (funcall key tree)) + (if (funcall predicate (funcall key tree)) + 1 + 0) (tree-count-if predicate (bt-right tree) :key key)))) - -

1 0

[funds-cvs] r175 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 17:45:44 2007 New Revision: 175 Modified: trunk/funds/src/package.lisp Log: Exported tree-as-alist, tree-count, and tree-count-if. Modified: trunk/funds/src/package.lisp ============================================================================== --- trunk/funds/src/package.lisp (original) +++ trunk/funds/src/package.lisp Sun Aug 19 17:45:44 2007 @@ -28,6 +28,9 @@ :tree-empty-p :tree-height :tree-weight + :tree-as-alist + :tree-count + :tree-count-if :make-heap :heap-empty-p

1 0

[funds-cvs] r174 - trunk/funds/src/trees
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 17:22:39 2007 New Revision: 174 Added: trunk/funds/src/trees/utilities.lisp Log: Added tree-count and tree-count-if. Added: trunk/funds/src/trees/utilities.lisp ============================================================================== --- (empty file) +++ trunk/funds/src/trees/utilities.lisp Sun Aug 19 17:22:39 2007 @@ -0,0 +1,18 @@ + +(in-package :funds) + +(defun tree-count (item tree &key (key #'bt-value) (test #'eql)) + "The number of sub-trees in the tree that satisfy the test." + (tree-count #'(lambda (x) + (funcall test x item)) + :key key)) + +(defun tree-count-if (predicate tree &key (key #'bt-value)) + "The number of sub-trees in the given tree that satisfy the test." + (if (tree-empty-p tree) + 0 + (+ (tree-count-if predicate (bt-left tree) :key key) + (funcall predicate (funcall key tree)) + (tree-count-if predicate (bt-right tree) :key key)))) + +

1 0

[funds-cvs] r173 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 17:22:12 2007 New Revision: 173 Modified: trunk/funds/src/funds.asd Log: Added utilities to defsystem. Modified: trunk/funds/src/funds.asd ============================================================================== --- trunk/funds/src/funds.asd (original) +++ trunk/funds/src/funds.asd Sun Aug 19 17:22:12 2007 @@ -40,7 +40,8 @@ (:file "tree-remove") (:file "tree-find") (:file "tree-weight") - (:file "tree-height"))) + (:file "tree-height") + (:file "utilities"))) (:module heap :serial t :components ((:file "heap")

1 0

[funds-cvs] r172 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 13:34:53 2007 New Revision: 172 Modified: trunk/funds/src/dictionary.lisp Log: Added dictionary-as-alist. Modified: trunk/funds/src/dictionary.lisp ============================================================================== --- trunk/funds/src/dictionary.lisp (original) +++ trunk/funds/src/dictionary.lisp Sun Aug 19 13:34:53 2007 @@ -47,3 +47,12 @@ (values nil nil) (values (cdr pair) t)))) +(defun dictionary-as-alist (d) + "An alist containing the same key-value pairs as the given dictionary." + (labels ((f (tree) + (if (tree-empty-p tree) + nil + (append (f (bt-left tree)) + (bt-value tree) + (f (bt-right tree)))))) + (f (dict-tree d))))

1 0

[funds-cvs] r171 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 12:58:53 2007 New Revision: 171 Modified: trunk/funds/src/package.lisp Log: Exported dictionary-as-alist. Modified: trunk/funds/src/package.lisp ============================================================================== --- trunk/funds/src/package.lisp (original) +++ trunk/funds/src/package.lisp Sun Aug 19 12:58:53 2007 @@ -52,6 +52,7 @@ :dictionary-add :dictionary-remove :dictionary-lookup + :dictionary-as-alist :make-f-array :f-array-elt

1 0

[funds-cvs] r170 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 12:57:02 2007 New Revision: 170 Modified: trunk/funds/src/f-array.lisp Log: Documented f-array. Modified: trunk/funds/src/f-array.lisp ============================================================================== --- trunk/funds/src/f-array.lisp (original) +++ trunk/funds/src/f-array.lisp Sun Aug 19 12:57:02 2007 @@ -2,6 +2,7 @@ (in-package :funds) (defun make-f-array (size &key (initial-contents nil)) + "A functional array of the given size with the given initial contents." (let ((length (length initial-contents))) (labels ((f (start end) (if (= start end) @@ -16,12 +17,16 @@ (f 0 size)))) (defun f-array-elt (array index) + "The element at the given index of the given array." (tree-find array index :test #'=)) -(defun f-array-replace (array index item) - (tree-insert array index item :test #'=)) +(defun f-array-replace (array index element) + "An array similar to the given array except that index and element are +associated in the returned array." + (tree-insert array index element :test #'=)) (defun f-array-size (array) + "The number of elements in the given array." (labels ((f (tree amount) (if (tree-empty-p tree) amount

1 0

[funds-cvs] r169 - trunk/funds/src
by abaine＠common-lisp.net 19 Aug '07

19 Aug '07

Author: abaine Date: Sun Aug 19 12:46:27 2007 New Revision: 169 Modified: trunk/funds/src/dictionary.lisp Log: Documented dictionary. Modified: trunk/funds/src/dictionary.lisp ============================================================================== --- trunk/funds/src/dictionary.lisp (original) +++ trunk/funds/src/dictionary.lisp Sun Aug 19 12:46:27 2007 @@ -7,9 +7,14 @@ tree) (defun make-dictionary (&key (hash #'sxhash) (test #'eql)) + "An empty dictionary that hashes occording to the given hash function, +which defaults to #'sxhash and and tests according to the given test +function, which defaults to #'eql." (make-dict :hash hash :test test :tree (make-avl-tree))) (defun dictionary-add (d k v) + "A dictionary similar to the given dictionary except that k maps to +v in the returned dictionary." (let* ((h (funcall (dict-hash d) k)) (old-alist (tree-find (dict-tree d) h)) (new-alist (acons k v (remove (assoc k old-alist :test (dict-test d)) @@ -19,6 +24,8 @@ :tree (tree-insert (dict-tree d) h new-alist)))) (defun dictionary-remove (d k) + "A dictionary similar to the given dictionary, except that k does +not map to any value in the returned dictionary." (let* ((h (funcall (dict-hash d) k)) (old-alist (tree-find (dict-tree d) h)) (new-alist (remove (assoc k old-alist :test (dict-test d)) @@ -30,6 +37,9 @@ (tree-insert (dict-tree d) h new-alist))))) (defun dictionary-lookup (d k) + "The value associated with the given key in the given dictionary. A second +value is returned to indicate whether the key is associated with any value or +is not found." (let ((pair (assoc k (tree-find (dict-tree d) (funcall (dict-hash d) k)) :test (dict-test d))))

1 0

← Newer
1
2
3
4
5
6
7
8
...
23
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

funds-cvs