funds-cvs August 2007

funds-cvs@common-lisp.net

1 participants
113 discussions

[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

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

19 Aug '07

Author: abaine Date: Sun Aug 19 12:40:17 2007 New Revision: 168 Removed: trunk/funds/src/stack/ Log: Removed stack directory.

1 0

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

19 Aug '07

Author: abaine Date: Sun Aug 19 12:38:18 2007 New Revision: 167 Modified: trunk/funds/src/queue.lisp Log: Documented queue functions. Modified: trunk/funds/src/queue.lisp ============================================================================== --- trunk/funds/src/queue.lisp (original) +++ trunk/funds/src/queue.lisp Sun Aug 19 12:38:18 2007 @@ -23,20 +23,25 @@ (heap (make-heap))) (defun queue-first (q) + "The value at the head of the given queue." (heap-first (queue-heap q))) (defun queue-enqueue (q item) + "The queue that results when the given item is equeued on the given queue." (make-queue :next-priority (1+ (queue-next-priority q)) :heap (heap-insert (queue-heap q) item (queue-next-priority q)))) (defun queue-dequeue (q) + "The queue that results when the first item is removed from the given queue." (if (queue-empty-p q) q (make-queue :next-priority (1- (queue-next-priority q)) :heap (heap-remove (queue-heap q))))) (defun queue-size (q) + "The number of items in the given queue." (tree-weight (queue-heap q))) (defun queue-empty-p (q) + "Whether the given queue does not contain any items." (tree-empty-p (queue-heap q)))

1 0

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

19 Aug '07

Author: abaine Date: Sun Aug 19 12:36:10 2007 New Revision: 166 Modified: trunk/funds/src/trees/tree-empty-p.lisp Log: Edited documentation. Modified: trunk/funds/src/trees/tree-empty-p.lisp ============================================================================== --- trunk/funds/src/trees/tree-empty-p.lisp (original) +++ trunk/funds/src/trees/tree-empty-p.lisp Sun Aug 19 12:36:10 2007 @@ -19,8 +19,7 @@ (defgeneric tree-empty-p (tree) (:documentation -"Whether this tree has any key-value pairs.")) - +"Whether the given tree does not contain key-value pairs.")) (defmethod tree-empty-p ((tree t)) nil)

1 0

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

19 Aug '07

Author: abaine Date: Sun Aug 19 12:30:28 2007 New Revision: 165 Modified: trunk/funds/src/queue.lisp Log: Documented queue. Modified: trunk/funds/src/queue.lisp ============================================================================== --- trunk/funds/src/queue.lisp (original) +++ trunk/funds/src/queue.lisp Sun Aug 19 12:30:28 2007 @@ -18,6 +18,7 @@ (in-package :funds) (defstruct queue + "A FIFO queue." (next-priority 0) (heap (make-heap)))

1 0

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

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

funds-cvs August 2007