June 2007 - funds-cvs@common-lisp.net - mailman3.common-lisp.net

[funds-cvs] r36 - trunk/funds/tests/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 18:28:06 2007 New Revision: 36 Modified: trunk/funds/tests/trees/avl-tree-test.lisp Log: Modified tests to include keyword arguments to avl-insert. Modified: trunk/funds/tests/trees/avl-tree-test.lisp ============================================================================== --- trunk/funds/tests/trees/avl-tree-test.lisp (original) +++ trunk/funds/tests/trees/avl-tree-test.lisp Wed Jun 20 18:28:06 2007 @@ -1,17 +1,19 @@ (in-package :funds.tests.trees) -(defun random-tree () - (reduce #'(lambda (tr v) - (avl-insert tr v v)) - (loop for i below 20 collect (random 10)) - :initial-value (empty-avl-tree))) +(defun random-tree (&key (test #'eql) (order #'<)) + (print (reduce #'(lambda (tr v) + (avl-insert tr v v :test test :order order)) + (loop for i below 40 collect (random 20)) + :initial-value (empty-avl-tree)))) -(defmacro assert-avl-valid (tree) +(defconstant +never-equal+ #'(lambda (a b) (declare (ignore a b)) nil)) + +(defmacro assert-avl-valid (tree &key (order #'<)) `(progn (assert-true (height-correct-p ,tree) ,tree) (assert-true (balanced-p ,tree) ,tree) - (assert-true (ordered-p ,tree) ,tree))) + (assert-true (ordered-p ,tree :order ,order) ,tree))) (define-test test-avl-empty-p (assert-true (avl-empty-p (empty-avl-tree))) @@ -49,7 +51,7 @@ (avl-height (avl-right tree))) 2)))) -(defun ordered-p (tree &optional (less-than #'<)) +(defun ordered-p (tree &key (order #'<)) "Whether this AVL tree is properly ordered. To be ordered, the tree must be either (a) empty or (b) satisfy each of the following requirements: @@ -64,10 +66,10 @@ (and (ordered-p (avl-left tree)) (ordered-p (avl-right tree)) (or (avl-empty-p (avl-left tree)) - (not (funcall less-than (avl-key tree) + (not (funcall order (avl-key tree) (greatest-key (avl-left tree))))) (or (avl-empty-p (avl-right tree)) - (not (funcall less-than (least-key (avl-right tree)) + (not (funcall order (least-key (avl-right tree)) (avl-key tree))))))) (defun least-key (tree)

1 0

[funds-cvs] r35 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 18:27:13 2007 New Revision: 35 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Rearranged avl-tree.lisp to put public interface at top. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 18:27:13 2007 @@ -1,12 +1,8 @@ (in-package :funds.trees) -(defstruct avl - ht - key - value - left - right) +;;;; Public Interface + (defun empty-avl-tree () "An empty AVL Tree." @@ -37,6 +33,32 @@ ((funcall order key (avl-key tree)) (left-insert tree key value test order)) (t (right-insert tree key value test order)))) +(defun avl-find-value (tree key &key (order #'<) (test #'eql)) + "The value associated with the given key in the given AVL Tree. The function +returns nil if the key is not found in the given tree; a second value is returned +to indicate whether nil is returned because it is in fact the value associated with +the given key or, instead, the key could not be found." + (cond ((avl-empty-p tree) (values nil nil)) + ((funcall test key (avl-key tree)) (values (avl-value tree) t)) + ((funcall order key (avl-key tree)) + (avl-find-value (avl-left tree) key :order order :test test)) + (t (avl-find-value (avl-right tree) key :order order :test test)))) + +(defstruct avl + ht + key + value + left + right) + +(defun avl-height (tree) + "The height of the given AVL Tree." + (if (avl-empty-p tree) + 0 + (avl-ht tree))) + +;;;; Insertion Helpers + (defun left-insert (tree key value test order) "The AVL tree that results when the given key-value pair is inserted into left sub-tree of the given AVL tree. Only non-empty avl-trees @@ -77,6 +99,8 @@ :left left :right right)))) +;;;; Rotation Functions + (defun left-rotate (t0 a b) (let ((c (avl-right b)) (new-a (make-avl :ht (1- (avl-ht a)) ; re-calculate? @@ -103,16 +127,7 @@ :left a :right new-c))) -(defun avl-find-value (tree key &key (order #'<) (test #'eql)) - "The value associated with the given key in the given AVL Tree. The function -returns nil if the key is not found in the given tree; a second value is returned -to indicate whether nil is returned because it is in fact the value associated with -the given key or, instead, the key could not be found." - (cond ((avl-empty-p tree) (values nil nil)) - ((funcall test key (avl-key tree)) (values (avl-value tree) t)) - ((funcall order key (avl-key tree)) - (avl-find-value (avl-left tree) key :order order :test test)) - (t (avl-find-value (avl-right tree) key :order order :test test)))) +;;;; AVL Tree utility functions (defun imbalanced (left right) "Whether the heights of the given sub-trees differ, @@ -128,12 +143,6 @@ "The difference in heights of the given sub-trees." (- (avl-height a) (avl-height b))) -(defun avl-height (tree) - "The height of the given AVL Tree." - (if (avl-empty-p tree) - 0 - (avl-ht tree))) - (defun left-heavy (tree) "Whether the given imbalanced AVL Tree has a left sub-tree taller than its right sub-tree." @@ -151,7 +160,7 @@ (avl-left tree))) (defun parent-height (left right) - "The height of the parent of the given sub-trees." + "The height the tree should be, whose children are the given sub-trees." (let ((a (avl-height left)) (b (avl-height right))) (1+ (if (> a b) a b))))

1 0

[funds-cvs] r34 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 18:25:29 2007 New Revision: 34 Modified: trunk/funds/src/trees/package.lisp Log: Added avl-find-value to public interface of avl-tree. Modified: trunk/funds/src/trees/package.lisp ============================================================================== --- trunk/funds/src/trees/package.lisp (original) +++ trunk/funds/src/trees/package.lisp Wed Jun 20 18:25:29 2007 @@ -8,6 +8,7 @@ :avl-empty-p :avl-insert :avl-remove + :avl-find-value :avl-key :avl-value

1 0

[funds-cvs] r33 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 14:50:14 2007 New Revision: 33 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Commented avl-find-value Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 14:50:14 2007 @@ -104,6 +104,10 @@ :right new-c))) (defun avl-find-value (tree key &key (order #'<) (test #'eql)) + "The value associated with the given key in the given AVL Tree. The function +returns nil if the key is not found in the given tree; a second value is returned +to indicate whether nil is returned because it is in fact the value associated with +the given key or, instead, the key could not be found." (cond ((avl-empty-p tree) (values nil nil)) ((funcall test key (avl-key tree)) (values (avl-value tree) t)) ((funcall order key (avl-key tree))

1 0

[funds-cvs] r32 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 14:47:38 2007 New Revision: 32 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Added avl-find-value function. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 14:47:38 2007 @@ -43,7 +43,7 @@ should be supplied as arguments." (let ((left (avl-insert (avl-left tree) key value :test test :order order)) (right (avl-right tree))) - (if (imbalanced left right)n + (if (imbalanced left right) (if (left-heavy left) (right-rotate left tree right) (right-rotate (left-rotate (avl-left left) @@ -103,6 +103,13 @@ :left a :right new-c))) +(defun avl-find-value (tree key &key (order #'<) (test #'eql)) + (cond ((avl-empty-p tree) (values nil nil)) + ((funcall test key (avl-key tree)) (values (avl-value tree) t)) + ((funcall order key (avl-key tree)) + (avl-find-value (avl-left tree) key :order order :test test)) + (t (avl-find-value (avl-right tree) key :order order :test test)))) + (defun imbalanced (left right) "Whether the heights of the given sub-trees differ, in their absolute values, by more than one."

1 0

[funds-cvs] r31 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 14:22:40 2007 New Revision: 31 Modified: trunk/funds/src/trees/avl-tree.lisp Log: AVL-Insert properly documented. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 14:22:40 2007 @@ -18,12 +18,17 @@ (null tree)) (defun avl-insert (tree key value &key (test #'eql) (order #'<)) + "The AVL Tree that results when the given key-value pair is inserted +into the given tree. If the test function determines that the given key +and the root key af the given tree are \"equal\", then a new AVL Tree is +created as if the given key-value pair replaced the root key-value pair. +The given order function, < by default, is used to determine the order of +the resulting AVL Tree." (cond ((avl-empty-p tree) (make-avl :ht 1 :key key :value value :left (empty-avl-tree) :right (empty-avl-tree))) - ((funcall test key (avl-key tree)) (make-avl :ht (avl-ht tree) :key key :value value @@ -38,7 +43,7 @@ should be supplied as arguments." (let ((left (avl-insert (avl-left tree) key value :test test :order order)) (right (avl-right tree))) - (if (imbalanced left right) + (if (imbalanced left right)n (if (left-heavy left) (right-rotate left tree right) (right-rotate (left-rotate (avl-left left) @@ -124,7 +129,7 @@ (minusp (balance-factor tree))) (defun right-heavy (tree) - "Whether the given imbalanced AVL Tre has a right sub-tree + "Whether the given imbalanced AVL Tree has a right sub-tree taller than its left sub-tree." (plusp (balance-factor tree)))

1 0

[funds-cvs] r30 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 13:06:54 2007 New Revision: 30 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Minor semantic changes. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 13:06:54 2007 @@ -103,6 +103,11 @@ in their absolute values, by more than one." (> (abs (height-difference left right)) 1)) +(defun balanced (left right) + "Whether the heights of the given sub-trees differ, +in their absolute values, by no more than one." + (< -2 (height-difference left right) 2)) + (defun height-difference (a b) "The difference in heights of the given sub-trees." (- (avl-height a) (avl-height b))) @@ -116,12 +121,12 @@ (defun left-heavy (tree) "Whether the given imbalanced AVL Tree has a left sub-tree taller than its right sub-tree." - (< (balance-factor tree) 0)) + (minusp (balance-factor tree))) (defun right-heavy (tree) "Whether the given imbalanced AVL Tre has a right sub-tree taller than its left sub-tree." - (> (balance-factor tree) 0)) + (plusp (balance-factor tree))) (defun balance-factor (tree) "The difference in heights of the right sub-tree and left

1 0

[funds-cvs] r29 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 12:37:53 2007 New Revision: 29 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Changed left-insert and right-insert to provide for test and order arguments. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 12:37:53 2007 @@ -29,14 +29,14 @@ :value value :left (avl-left tree) :right (avl-right tree))) - ((funcall order key (avl-key tree)) (left-insert tree key value)) - (t (right-insert tree key value)))) + ((funcall order key (avl-key tree)) (left-insert tree key value test order)) + (t (right-insert tree key value test order)))) -(defun left-insert (tree key value) +(defun left-insert (tree key value test order) "The AVL tree that results when the given key-value pair is inserted into left sub-tree of the given AVL tree. Only non-empty avl-trees should be supplied as arguments." - (let ((left (avl-insert (avl-left tree) key value)) + (let ((left (avl-insert (avl-left tree) key value :test test :order order)) (right (avl-right tree))) (if (imbalanced left right) (if (left-heavy left) @@ -52,11 +52,11 @@ :left left :right right)))) -(defun right-insert (tree key value) +(defun right-insert (tree key value test order) "The AVL tree that results when the given key-value pair is inserted into the right sub-tree of the given AVL tree. Only non-empty avl-trees should be supplied as the tree argument." - (let ((right (avl-insert (avl-right tree) key value)) + (let ((right (avl-insert (avl-right tree) key value :test test :order order)) (left (avl-left tree))) (if (imbalanced left right) (if (right-heavy right)

1 0

[funds-cvs] r28 - trunk/funds/src/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 12:27:20 2007 New Revision: 28 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Changed avl-insert signature to accept keyword arguments test and order Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 12:27:20 2007 @@ -17,13 +17,19 @@ t if it is empty; nil else." (null tree)) -(defun avl-insert (tree key value) +(defun avl-insert (tree key value &key (test #'eql) (order #'<)) (cond ((avl-empty-p tree) (make-avl :ht 1 :key key :value value - :left nil - :right nil)) - ((< key (avl-key tree)) (left-insert tree key value)) + :left (empty-avl-tree) + :right (empty-avl-tree))) + + ((funcall test key (avl-key tree)) (make-avl :ht (avl-ht tree) + :key key + :value value + :left (avl-left tree) + :right (avl-right tree))) + ((funcall order key (avl-key tree)) (left-insert tree key value)) (t (right-insert tree key value)))) (defun left-insert (tree key value)

1 0

[funds-cvs] r27 - trunk/funds/tests/trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 12:15:00 2007 New Revision: 27 Modified: trunk/funds/tests/trees/avl-tree-test.lisp Log: Changed a couple of comments. Modified: trunk/funds/tests/trees/avl-tree-test.lisp ============================================================================== --- trunk/funds/tests/trees/avl-tree-test.lisp (original) +++ trunk/funds/tests/trees/avl-tree-test.lisp Wed Jun 20 12:15:00 2007 @@ -29,14 +29,14 @@ 2. the height of the right sub-tree is correct; 3. the height of the given tree is 1 more than the greater of the heights of the left and right sub-trees." - (if (avl-empty-p tree) - (zerop (avl-height tree)) - (and (height-correct-p (avl-left tree)) - (height-correct-p (avl-right tree)) + (or (and (avl-empty-p tree) + (zerop (avl-height tree))) ; (a) + (and (height-correct-p (avl-left tree)) ; (1) + (height-correct-p (avl-right tree)) ; (2) (let* ((a (avl-height (avl-left tree))) (b (avl-height (avl-right tree))) (c (if (> a b) a b))) - (eql (1+ c) (avl-height tree)))))) + (eql (1+ c) (avl-height tree)))))) ; (3) (defun balanced-p (tree) "Whether the given AVL Tree is properly balanced. To be balanced,

1 0

[funds-cvs] r26 - trunk/funds/tests
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 12:14:34 2007 New Revision: 26 Modified: trunk/funds/tests/funds-tests.asd Log: Added funds dependency. Modified: trunk/funds/tests/funds-tests.asd ============================================================================== --- trunk/funds/tests/funds-tests.asd (original) +++ trunk/funds/tests/funds-tests.asd Wed Jun 20 12:14:34 2007 @@ -14,4 +14,5 @@ :serial t :components ((:file "package") (:file "avl-tree-test")))) - :depends-on (:lisp-unit)) + :depends-on (:funds + :lisp-unit))

1 0

[funds-cvs] r25 - trunk/funds/tests
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 11:57:32 2007 New Revision: 25 Added: trunk/funds/tests/funds-tests.asd Log: Created new test system and added trees tests. Added: trunk/funds/tests/funds-tests.asd ============================================================================== --- (empty file) +++ trunk/funds/tests/funds-tests.asd Wed Jun 20 11:57:32 2007 @@ -0,0 +1,17 @@ + +;;;; -*- Lisp -*- + +(in-package :cl-user) + +(defpackage #:funds-tests-asd + (:use :cl :asdf)) + +(in-package #:funds-tests-asd) + +(defsystem funds-tests + :serial t + :components ((:module trees + :serial t + :components ((:file "package") + (:file "avl-tree-test")))) + :depends-on (:lisp-unit))

1 0

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

20 Jun '07

Author: abaine Date: Wed Jun 20 11:56:54 2007 New Revision: 24 Modified: trunk/funds/src/funds.asd Log: Removed test modules from defsystem form. Modified: trunk/funds/src/funds.asd ============================================================================== --- trunk/funds/src/funds.asd (original) +++ trunk/funds/src/funds.asd Wed Jun 20 11:56:54 2007 @@ -13,13 +13,5 @@ :components ((:module trees :serial t :components ((:file "package") - (:file "avl-tree"))) - - (:module tests - :serial t - :components ((:module trees - :serial t - :components ((:file "package") - (:file "avl-tree-test"))))) - (:file "package")) - :depends-on (:lisp-unit)) + (:file "avl-tree"))) + (:file "package")))

1 0

[funds-cvs] r23 - trunk/funds/src/tests
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 11:50:29 2007 New Revision: 23 Removed: trunk/funds/src/tests/ Log: Deleted old tests directory.

1 0

[funds-cvs] r22 - in trunk/funds/tests: . trees
by abaine＠common-lisp.net 20 Jun '07

20 Jun '07

Author: abaine Date: Wed Jun 20 11:45:04 2007 New Revision: 22 Added: trunk/funds/tests/ - copied from r18, trunk/funds/src/tests/ trunk/funds/tests/trees/ - copied from r19, trunk/funds/src/tests/trees/ trunk/funds/tests/trees/avl-tree-test.lisp - copied unchanged from r21, trunk/funds/src/tests/trees/avl-tree-test.lisp trunk/funds/tests/trees/package.lisp - copied unchanged from r21, trunk/funds/src/tests/trees/package.lisp Removed: trunk/funds/tests/avl-tree-test.lisp trunk/funds/tests/package.lisp Log: Moved tests directory to project root

1 0

[funds-cvs] r21 - trunk/funds/src/tests/trees
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:48:45 2007 New Revision: 21 Modified: trunk/funds/src/tests/trees/avl-tree-test.lisp trunk/funds/src/tests/trees/package.lisp Log: Renamed funds-trees-tests to funds.tests.trees Modified: trunk/funds/src/tests/trees/avl-tree-test.lisp ============================================================================== --- trunk/funds/src/tests/trees/avl-tree-test.lisp (original) +++ trunk/funds/src/tests/trees/avl-tree-test.lisp Fri Jun 15 14:48:45 2007 @@ -1,5 +1,5 @@ -(in-package :funds-trees-tests) +(in-package :funds.tests.trees) (defun random-tree () (reduce #'(lambda (tr v) Modified: trunk/funds/src/tests/trees/package.lisp ============================================================================== --- trunk/funds/src/tests/trees/package.lisp (original) +++ trunk/funds/src/tests/trees/package.lisp Fri Jun 15 14:48:45 2007 @@ -1,7 +1,7 @@ (in-package :cl-user) -(defpackage funds-trees-tests +(defpackage funds.tests.trees (:use :cl :funds.trees :lisp-unit))

1 0

[funds-cvs] r20 - trunk/funds/src/tests/trees
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:40:49 2007 New Revision: 20 Modified: trunk/funds/src/tests/trees/package.lisp Log: Fixed package name Modified: trunk/funds/src/tests/trees/package.lisp ============================================================================== --- trunk/funds/src/tests/trees/package.lisp (original) +++ trunk/funds/src/tests/trees/package.lisp Fri Jun 15 14:40:49 2007 @@ -3,5 +3,5 @@ (defpackage funds-trees-tests (:use :cl - :funds-trees + :funds.trees :lisp-unit))

1 0

[funds-cvs] r19 - in trunk/funds/src/tests: . trees
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:38:39 2007 New Revision: 19 Added: trunk/funds/src/tests/trees/ trunk/funds/src/tests/trees/avl-tree-test.lisp - copied unchanged from r18, trunk/funds/src/tests/avl-tree-test.lisp trunk/funds/src/tests/trees/package.lisp - copied unchanged from r18, trunk/funds/src/tests/package.lisp Removed: trunk/funds/src/tests/avl-tree-test.lisp trunk/funds/src/tests/package.lisp Log: Now I think I've really fixed the directory structure?

1 0

[funds-cvs] r18 - in trunk/funds/src: tests trees/tests
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:34:07 2007 New Revision: 18 Added: trunk/funds/src/tests/ - copied from r17, trunk/funds/src/trees/tests/ Removed: trunk/funds/src/trees/tests/ Log: Fixed directory structure.

1 0

[funds-cvs] r17 - trunk/funds/src
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:30:15 2007 New Revision: 17 Modified: trunk/funds/src/funds.asd Log: Rewrote defsystem form to account for changed directory structure Modified: trunk/funds/src/funds.asd ============================================================================== --- trunk/funds/src/funds.asd (original) +++ trunk/funds/src/funds.asd Fri Jun 15 14:30:15 2007 @@ -13,8 +13,12 @@ :components ((:module trees :serial t :components ((:file "package") - (:file "avl-tree") - (:module "tests" + (:file "avl-tree"))) + + (:module tests + :serial t + :components ((:module trees + :serial t :components ((:file "package") (:file "avl-tree-test"))))) (:file "package"))

1 0

[funds-cvs] r16 - trunk/funds/src/trees
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:29:33 2007 New Revision: 16 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Renamed trees package to funds.trees Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Fri Jun 15 14:29:33 2007 @@ -1,5 +1,5 @@ -(in-package :funds-trees) +(in-package :funds.trees) (defstruct avl ht

1 0

[funds-cvs] r15 - trunk/funds/src/trees
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 14:29:02 2007 New Revision: 15 Modified: trunk/funds/src/trees/package.lisp Log: Renamed trees package to funds.trees Modified: trunk/funds/src/trees/package.lisp ============================================================================== --- trunk/funds/src/trees/package.lisp (original) +++ trunk/funds/src/trees/package.lisp Fri Jun 15 14:29:02 2007 @@ -1,7 +1,7 @@ (in-package :cl-user) -(defpackage :funds-trees +(defpackage :funds.trees (:use :cl) (:export ; AVL Tree public interface :empty-avl-tree

1 0

[funds-cvs] r14 - trunk/funds/src/trees/tests
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 13:57:14 2007 New Revision: 14 Modified: trunk/funds/src/trees/tests/avl-tree-test.lisp Log: Wrote unit tests for insert and empty Modified: trunk/funds/src/trees/tests/avl-tree-test.lisp ============================================================================== --- trunk/funds/src/trees/tests/avl-tree-test.lisp (original) +++ trunk/funds/src/trees/tests/avl-tree-test.lisp Fri Jun 15 13:57:14 2007 @@ -4,29 +4,80 @@ (defun random-tree () (reduce #'(lambda (tr v) (avl-insert tr v v)) - (loop for i below 100 collect (random 10000)) + (loop for i below 20 collect (random 10)) :initial-value (empty-avl-tree))) -(define-test empty-avl-tree - (assert-true (avl-empty-p (empty-avl-tree))) - (assert-equal 0 (avl-height (empty-avl-tree)))) - +(defmacro assert-avl-valid (tree) + `(progn + (assert-true (height-correct-p ,tree) ,tree) + (assert-true (balanced-p ,tree) ,tree) + (assert-true (ordered-p ,tree) ,tree))) -(define-test avl-insert - (assert-true (balanced (random-tree)))) +(define-test test-avl-empty-p + (assert-true (avl-empty-p (empty-avl-tree))) + (assert-avl-valid (empty-avl-tree))) -(defun balanced (tree) +(define-test test-avl-insert + (let ((tree (random-tree))) + (assert-avl-valid tree))) + +(defun height-correct-p (tree) + "Whether (avl-height tree) returns the correct height of the given +AVL Tree. The height is correct if (a) the tree is empty and zero +is returned or (b) each of the following is true: + 1. the height of the left sub-tree is correct; + 2. the height of the right sub-tree is correct; + 3. the height of the given tree is 1 more than the greater + of the heights of the left and right sub-trees." + (if (avl-empty-p tree) + (zerop (avl-height tree)) + (and (height-correct-p (avl-left tree)) + (height-correct-p (avl-right tree)) + (let* ((a (avl-height (avl-left tree))) + (b (avl-height (avl-right tree))) + (c (if (> a b) a b))) + (eql (1+ c) (avl-height tree)))))) + +(defun balanced-p (tree) + "Whether the given AVL Tree is properly balanced. To be balanced, +the tree must be either (a) empty or (b) have left and right sub-trees +that differ in height by no more than 1." (or (avl-empty-p tree) - (and (balanced (avl-left tree)) - (balanced (avl-right tree)) + (and (balanced-p (avl-left tree)) + (balanced-p (avl-right tree)) (< -2 (- (avl-height (avl-left tree)) (avl-height (avl-right tree))) 2)))) - -(defun root-height-correct (tree) - (let* ((a (avl-height (avl-left tree))) - (b (avl-height (avl-right tree))) - (c (if (> a b) a b))) - (eql (1+ c) (avl-height tree)))) - +(defun ordered-p (tree &optional (less-than #'<)) + "Whether this AVL tree is properly ordered. To be ordered, +the tree must be either (a) empty or (b) satisfy each of the following +requirements: + + 1. the left sub-tree is properly ordered; + 2. the right sub-tree is properly ordered; + 3. every key in the left sub-tree is less than + the root key; and + 4. every key in the right sub-tree is not less + than the root key." + (or (avl-empty-p tree) + (and (ordered-p (avl-left tree)) + (ordered-p (avl-right tree)) + (or (avl-empty-p (avl-left tree)) + (not (funcall less-than (avl-key tree) + (greatest-key (avl-left tree))))) + (or (avl-empty-p (avl-right tree)) + (not (funcall less-than (least-key (avl-right tree)) + (avl-key tree))))))) + +(defun least-key (tree) + "The least key in a properly ordered AVL tree." + (if (avl-empty-p (avl-left tree)) + (avl-key tree) + (least-key (avl-left tree)))) + +(defun greatest-key (tree) + "The greatest key in a properly ordered AVL tree." + (if (avl-empty-p (avl-right tree)) + (avl-key tree) + (greatest-key (avl-right tree))))

1 0

[funds-cvs] r13 - trunk/public_html
by abaine＠common-lisp.net 15 Jun '07

15 Jun '07

Author: abaine Date: Fri Jun 15 11:56:02 2007 New Revision: 13 Modified: trunk/public_html/index.html Log: Changed CVS header to SVN Modified: trunk/public_html/index.html ============================================================================== --- trunk/public_html/index.html (original) +++ trunk/public_html/index.html Fri Jun 15 11:56:02 2007 @@ -50,17 +50,13 @@ <a href="mailto:andrew.baine@gmail.com">Andrew Baine</a> </li> </ul> - <h3>CVS</h3> + <h3>Subversion</h3> <p>You can <a - - - href="http://common-lisp.net/websvn/listing.php?repname=funds"> browse our Subversion repository</a> or download the current development tree via anonymous SVN, as described <a href="http://common-lisp.net/faq.shtml">here</a></p> - <div class="footer"> </div>

1 0

[funds-cvs] r12 - trunk/funds/src/trees/tests
by abaine＠common-lisp.net 14 Jun '07

14 Jun '07

Author: abaine Date: Wed Jun 13 22:09:33 2007 New Revision: 12 Added: trunk/funds/src/trees/tests/ trunk/funds/src/trees/tests/avl-tree-test.lisp trunk/funds/src/trees/tests/package.lisp Log: Began to implement unit tests for AVL Trees Added: trunk/funds/src/trees/tests/avl-tree-test.lisp ============================================================================== --- (empty file) +++ trunk/funds/src/trees/tests/avl-tree-test.lisp Wed Jun 13 22:09:33 2007 @@ -0,0 +1,32 @@ + +(in-package :funds-trees-tests) + +(defun random-tree () + (reduce #'(lambda (tr v) + (avl-insert tr v v)) + (loop for i below 100 collect (random 10000)) + :initial-value (empty-avl-tree))) + +(define-test empty-avl-tree + (assert-true (avl-empty-p (empty-avl-tree))) + (assert-equal 0 (avl-height (empty-avl-tree)))) + + +(define-test avl-insert + (assert-true (balanced (random-tree)))) + +(defun balanced (tree) + (or (avl-empty-p tree) + (and (balanced (avl-left tree)) + (balanced (avl-right tree)) + (< -2 (- (avl-height (avl-left tree)) + (avl-height (avl-right tree))) + 2)))) + + +(defun root-height-correct (tree) + (let* ((a (avl-height (avl-left tree))) + (b (avl-height (avl-right tree))) + (c (if (> a b) a b))) + (eql (1+ c) (avl-height tree)))) + Added: trunk/funds/src/trees/tests/package.lisp ============================================================================== --- (empty file) +++ trunk/funds/src/trees/tests/package.lisp Wed Jun 13 22:09:33 2007 @@ -0,0 +1,7 @@ + +(in-package :cl-user) + +(defpackage funds-trees-tests + (:use :cl + :funds-trees + :lisp-unit))

1 0

[funds-cvs] r11 - trunk/funds/src
by abaine＠common-lisp.net 14 Jun '07

14 Jun '07

Author: abaine Date: Wed Jun 13 22:08:32 2007 New Revision: 11 Modified: trunk/funds/src/funds.asd Log: Added lisp-unit dependency Modified: trunk/funds/src/funds.asd ============================================================================== --- trunk/funds/src/funds.asd (original) +++ trunk/funds/src/funds.asd Wed Jun 13 22:08:32 2007 @@ -1,13 +1,21 @@ ;;;; -*- Lisp -*- +(in-package :cl-user) + (defpackage #:funds-asd (:use :cl :asdf)) (in-package :funds-asd) (defsystem funds - :components ((:file "package") - (:module trees - :components ((:file "avl-tree")) - :depends-on ("package")))) + :serial t + :components ((:module trees + :serial t + :components ((:file "package") + (:file "avl-tree") + (:module "tests" + :components ((:file "package") + (:file "avl-tree-test"))))) + (:file "package")) + :depends-on (:lisp-unit))

1 0

[funds-cvs] r10 - trunk/funds/src/trees
by abaine＠common-lisp.net 14 Jun '07

14 Jun '07

Author: abaine Date: Wed Jun 13 22:07:48 2007 New Revision: 10 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Added comments and fixed problem with right-rotate. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 13 22:07:48 2007 @@ -1,29 +1,35 @@ -(in-package :funds) +(in-package :funds-trees) (defstruct avl - height + ht key value left right) -(defun make-avl-tree () +(defun empty-avl-tree () + "An empty AVL Tree." nil) +(defun avl-empty-p (tree) + "Whether the given AVL Tree is empty: +t if it is empty; nil else." + (null tree)) + (defun avl-insert (tree key value) - (cond ((avl-empty tree) (make-avl :height 1 - :key key - :value value - :left nil - :right nil)) + (cond ((avl-empty-p tree) (make-avl :ht 1 + :key key + :value value + :left nil + :right nil)) ((< key (avl-key tree)) (left-insert tree key value)) (t (right-insert tree key value)))) -(defun avl-empty (tree) - (null tree)) - (defun left-insert (tree key value) + "The AVL tree that results when the given key-value pair is inserted +into left sub-tree of the given AVL tree. Only non-empty avl-trees +should be supplied as arguments." (let ((left (avl-insert (avl-left tree) key value)) (right (avl-right tree))) (if (imbalanced left right) @@ -34,22 +40,27 @@ (avl-right left)) tree right)) - (make-avl :height (parent-height left right) + (make-avl :ht (parent-height left right) :key (avl-key tree) :value (avl-value tree) :left left :right right)))) (defun right-insert (tree key value) + "The AVL tree that results when the given key-value pair is inserted +into the right sub-tree of the given AVL tree. Only non-empty avl-trees +should be supplied as the tree argument." (let ((right (avl-insert (avl-right tree) key value)) (left (avl-left tree))) (if (imbalanced left right) (if (right-heavy right) (left-rotate left tree right) - (left-rotate (right-rotate (avl-right right) + (left-rotate left + tree + (right-rotate (avl-left right) right - (avl-left right)))) - (make-avl :height (parent-height left right) + (avl-right right)))) + (make-avl :ht (parent-height left right) :key (avl-key tree) :value (avl-value tree) :left left @@ -57,12 +68,12 @@ (defun left-rotate (t0 a b) (let ((c (avl-right b)) - (new-a (make-avl :height (1- (avl-height a)) ; re-calculate? + (new-a (make-avl :ht (1- (avl-ht a)) ; re-calculate? :key (avl-key a) :value (avl-value a) :left t0 :right (avl-left b)))) - (make-avl :height (1+ (avl-height new-a)) + (make-avl :ht (1+ (avl-ht new-a)) :key (avl-key b) :value (avl-value b) :left new-a @@ -70,37 +81,50 @@ (defun right-rotate (b c t3) (let ((a (avl-left b)) - (new-c (make-avl :height (1- (avl-height c)); re-calculate? + (new-c (make-avl :ht (1- (avl-ht c)); re-calculate? :key (avl-key c) :value (avl-value c) :left (avl-right b) :right t3))) - (make-avl :height (1+ (avl-height new-c)) ; re-calculate? + (make-avl :ht (1+ (avl-ht new-c)) ; re-calculate? :key (avl-key b) :value (avl-value b) :left a :right new-c))) (defun imbalanced (left right) - (> (abs (- (height right) (height left))) - 1)) + "Whether the heights of the given sub-trees differ, +in their absolute values, by more than one." + (> (abs (height-difference left right)) 1)) + +(defun height-difference (a b) + "The difference in heights of the given sub-trees." + (- (avl-height a) (avl-height b))) + +(defun avl-height (tree) + "The height of the given AVL Tree." + (if (avl-empty-p tree) + 0 + (avl-ht tree))) (defun left-heavy (tree) + "Whether the given imbalanced AVL Tree has a left sub-tree +taller than its right sub-tree." (< (balance-factor tree) 0)) (defun right-heavy (tree) + "Whether the given imbalanced AVL Tre has a right sub-tree +taller than its left sub-tree." (> (balance-factor tree) 0)) (defun balance-factor (tree) - (- (height (avl-right tree)) - (height (avl-left tree)))) - -(defun height (tree) - (if (null tree) - 0 - (avl-height tree))) + "The difference in heights of the right sub-tree and left +sub-tree of the given AVL Tree." + (height-difference (avl-right tree) + (avl-left tree))) (defun parent-height (left right) - (let ((a (height left)) - (b (height right))) + "The height of the parent of the given sub-trees." + (let ((a (avl-height left)) + (b (avl-height right))) (1+ (if (> a b) a b))))

1 0

[funds-cvs] r9 - trunk/funds/src
by abaine＠common-lisp.net 14 Jun '07

14 Jun '07

Author: abaine Date: Wed Jun 13 22:04:25 2007 New Revision: 9 Modified: trunk/funds/src/package.lisp Log: formatting changes Modified: trunk/funds/src/package.lisp ============================================================================== --- trunk/funds/src/package.lisp (original) +++ trunk/funds/src/package.lisp Wed Jun 13 22:04:25 2007 @@ -1,3 +1,5 @@ +(in-package :cl-user) + (defpackage :funds - (:use :common-lisp)) \ No newline at end of file + (:use :common-lisp))

1 0

[funds-cvs] r8 - trunk/funds/src/trees
by abaine＠common-lisp.net 13 Jun '07

13 Jun '07

Author: abaine Date: Wed Jun 13 19:12:10 2007 New Revision: 8 Added: trunk/funds/src/trees/package.lisp Log: funds-trees package Added: trunk/funds/src/trees/package.lisp ============================================================================== --- (empty file) +++ trunk/funds/src/trees/package.lisp Wed Jun 13 19:12:10 2007 @@ -0,0 +1,16 @@ + +(in-package :cl-user) + +(defpackage :funds-trees + (:use :cl) + (:export ; AVL Tree public interface + :empty-avl-tree + :avl-empty-p + :avl-insert + :avl-remove + + :avl-key + :avl-value + :avl-height + :avl-left + :avl-right))

1 0

[funds-cvs] r7 - trunk/funds/src/trees
by abaine＠common-lisp.net 12 Jun '07

12 Jun '07

Author: abaine Date: Tue Jun 12 10:11:16 2007 New Revision: 7 Modified: trunk/funds/src/trees/avl-tree.lisp Log: avl insertion now seems to work. Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Tue Jun 12 10:11:16 2007 @@ -8,60 +8,79 @@ left right) -(defun make-avl () +(defun make-avl-tree () nil) (defun avl-insert (tree key value) - (cond ((null tree) (make-avl :height 1 - :key key - :value value - :left nil - :right nil)) - ((< key (avl-key tree)) (left-insert tree)) - (t (right-insert tree)))) + (cond ((avl-empty tree) (make-avl :height 1 + :key key + :value value + :left nil + :right nil)) + ((< key (avl-key tree)) (left-insert tree key value)) + (t (right-insert tree key value)))) + +(defun avl-empty (tree) + (null tree)) (defun left-insert (tree key value) - (let* ((left (avl-insert (avl-left tree))) - (right (avl-right tree))) + (let ((left (avl-insert (avl-left tree) key value)) + (right (avl-right tree))) (if (imbalanced left right) (if (left-heavy left) (right-rotate left tree right) - (right-rotate (left-rotate left (avl-left left) ) + (right-rotate (left-rotate (avl-left left) + left + (avl-right left)) tree - right) - ()) + right)) (make-avl :height (parent-height left right) :key (avl-key tree) :value (avl-value tree) :left left :right right)))) -(defun right-rotate (b c t3) - (let ((a (avl-left b)) - (new-c (make-avl :height (avl-height c); not sure if this needs to be recalculated - :key (avl-key c) - :value (avl-value c) - :left (avl-right b) - :right t3))) - (make-avl :height (parent-height a new-c) - :key (avl-key b) - :value (avl-value b) - :left a - :right new-c))) +(defun right-insert (tree key value) + (let ((right (avl-insert (avl-right tree) key value)) + (left (avl-left tree))) + (if (imbalanced left right) + (if (right-heavy right) + (left-rotate left tree right) + (left-rotate (right-rotate (avl-right right) + right + (avl-left right)))) + (make-avl :height (parent-height left right) + :key (avl-key tree) + :value (avl-value tree) + :left left + :right right)))) (defun left-rotate (t0 a b) (let ((c (avl-right b)) - (new-a (make-avl :height (avl-height a) + (new-a (make-avl :height (1- (avl-height a)) ; re-calculate? :key (avl-key a) :value (avl-value a) :left t0 :right (avl-left b)))) - (make-avl :height (parent-height (new-a) c) + (make-avl :height (1+ (avl-height new-a)) :key (avl-key b) :value (avl-value b) :left new-a :right c))) +(defun right-rotate (b c t3) + (let ((a (avl-left b)) + (new-c (make-avl :height (1- (avl-height c)); re-calculate? + :key (avl-key c) + :value (avl-value c) + :left (avl-right b) + :right t3))) + (make-avl :height (1+ (avl-height new-c)) ; re-calculate? + :key (avl-key b) + :value (avl-value b) + :left a + :right new-c))) + (defun imbalanced (left right) (> (abs (- (height right) (height left))) 1)) @@ -72,9 +91,6 @@ (defun right-heavy (tree) (> (balance-factor tree) 0)) -(defun right-insert (tree key value) - ()) - (defun balance-factor (tree) (- (height (avl-right tree)) (height (avl-left tree)))) @@ -83,3 +99,8 @@ (if (null tree) 0 (avl-height tree))) + +(defun parent-height (left right) + (let ((a (height left)) + (b (height right))) + (1+ (if (> a b) a b))))

1 0

[funds-cvs] r6 - trunk/funds/src/trees
by abaine＠common-lisp.net 11 Jun '07

11 Jun '07

Author: abaine Date: Mon Jun 11 17:58:22 2007 New Revision: 6 Modified: trunk/funds/src/trees/avl-tree.lisp Log: Initial version of avl-tree.lisp Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Mon Jun 11 17:58:22 2007 @@ -0,0 +1,85 @@ + +(in-package :funds) + +(defstruct avl + height + key + value + left + right) + +(defun make-avl () + nil) + +(defun avl-insert (tree key value) + (cond ((null tree) (make-avl :height 1 + :key key + :value value + :left nil + :right nil)) + ((< key (avl-key tree)) (left-insert tree)) + (t (right-insert tree)))) + +(defun left-insert (tree key value) + (let* ((left (avl-insert (avl-left tree))) + (right (avl-right tree))) + (if (imbalanced left right) + (if (left-heavy left) + (right-rotate left tree right) + (right-rotate (left-rotate left (avl-left left) ) + tree + right) + ()) + (make-avl :height (parent-height left right) + :key (avl-key tree) + :value (avl-value tree) + :left left + :right right)))) + +(defun right-rotate (b c t3) + (let ((a (avl-left b)) + (new-c (make-avl :height (avl-height c); not sure if this needs to be recalculated + :key (avl-key c) + :value (avl-value c) + :left (avl-right b) + :right t3))) + (make-avl :height (parent-height a new-c) + :key (avl-key b) + :value (avl-value b) + :left a + :right new-c))) + +(defun left-rotate (t0 a b) + (let ((c (avl-right b)) + (new-a (make-avl :height (avl-height a) + :key (avl-key a) + :value (avl-value a) + :left t0 + :right (avl-left b)))) + (make-avl :height (parent-height (new-a) c) + :key (avl-key b) + :value (avl-value b) + :left new-a + :right c))) + +(defun imbalanced (left right) + (> (abs (- (height right) (height left))) + 1)) + +(defun left-heavy (tree) + (< (balance-factor tree) 0)) + +(defun right-heavy (tree) + (> (balance-factor tree) 0)) + +(defun right-insert (tree key value) + ()) + +(defun balance-factor (tree) + (- (height (avl-right tree)) + (height (avl-left tree)))) + +(defun height (tree) + (if (null tree) + 0 + (avl-height tree)))

1 0

[funds-cvs] r5 - trunk/funds/src
by abaine＠common-lisp.net 11 Jun '07

11 Jun '07

Author: abaine Date: Sun Jun 10 23:10:17 2007 New Revision: 5 Modified: trunk/funds/src/funds.asd Log: Added defsystem form Modified: trunk/funds/src/funds.asd ============================================================================== --- trunk/funds/src/funds.asd (original) +++ trunk/funds/src/funds.asd Sun Jun 10 23:10:17 2007 @@ -0,0 +1,13 @@ + +;;;; -*- Lisp -*- + +(defpackage #:funds-asd + (:use :cl :asdf)) + +(in-package :funds-asd) + +(defsystem funds + :components ((:file "package") + (:module trees + :components ((:file "avl-tree")) + :depends-on ("package"))))

1 0

[funds-cvs] r4 - trunk/funds/src/trees
by abaine＠common-lisp.net 08 Jun '07

08 Jun '07

Author: abaine Date: Fri Jun 8 10:50:38 2007 New Revision: 4 Added: trunk/funds/src/trees/avl-tree.lisp Log: Added avl-tree.lisp Added: trunk/funds/src/trees/avl-tree.lisp ==============================================================================

1 0

[funds-cvs] r3 - trunk/funds/src/trees
by abaine＠common-lisp.net 08 Jun '07

08 Jun '07

Author: abaine Date: Fri Jun 8 10:49:48 2007 New Revision: 3 Added: trunk/funds/src/trees/ Log: Added trees directory.

1 0

[funds-cvs] r2 - trunk/public_html
by abaine＠common-lisp.net 07 Jun '07

07 Jun '07

Author: abaine Date: Thu Jun 7 14:38:38 2007 New Revision: 2 Modified: trunk/public_html/index.html Log: Edited web page to reflect transfer from CVS to Subversion. Modified: trunk/public_html/index.html ============================================================================== --- trunk/public_html/index.html (original) +++ trunk/public_html/index.html Thu Jun 7 14:38:38 2007 @@ -27,7 +27,7 @@ funds-devel</a><br>for developers</li> <li> <a href="http://www.common-lisp.net/mailman/listinfo/funds-cvs"> - funds-cvs</a><br>CVS log feed.</li> + funds-cvs</a><br>Subversion log feed.</li> <li> <a href="http://www.common-lisp.net/mailman/listinfo/funds-announce"> funds-announce</a><br>for announcements.</li> @@ -53,9 +53,12 @@ <h3>CVS</h3> <p>You can <a - href="http://common-lisp.net/cgi-bin/viewcvs.cgi/?cvsroot=funds"> - browse our CVS repository</a> or download the current development - tree via anonymous cvs, as described <a + + + + href="http://common-lisp.net/websvn/listing.php?repname=funds"> + browse our Subversion repository</a> or download the current development + tree via anonymous SVN, as described <a href="http://common-lisp.net/faq.shtml">here</a></p> <div class="footer">

1 0

[funds-cvs] r1 - branches tags trunk trunk/funds trunk/funds/doc trunk/funds/src trunk/public_html
by abaine＠common-lisp.net 07 Jun '07

07 Jun '07

Author: abaine Date: Thu Jun 7 14:29:41 2007 New Revision: 1 Added: branches/ tags/ trunk/ trunk/funds/ trunk/funds/doc/ trunk/funds/src/ trunk/funds/src/funds.asd trunk/funds/src/package.lisp trunk/public_html/ trunk/public_html/index.html trunk/public_html/project-name trunk/public_html/style.css Log: Initial import Added: trunk/funds/src/funds.asd ============================================================================== Added: trunk/funds/src/package.lisp ============================================================================== --- (empty file) +++ trunk/funds/src/package.lisp Thu Jun 7 14:29:41 2007 @@ -0,0 +1,3 @@ + +(defpackage :funds + (:use :common-lisp)) \ No newline at end of file Added: trunk/public_html/index.html ============================================================================== --- (empty file) +++ trunk/public_html/index.html Thu Jun 7 14:29:41 2007 @@ -0,0 +1,68 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><title>Funds</title> + + + + + <link rel="stylesheet" type="text/css" href="style.css"> + <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"></head><body> + <div class="header"> + <h1>Funds</h1> + <h2>Functional Data Structures in Common Lisp</h2> + </div> + + <h3>Introduction</h3> + + <p>The goal of the Funds project is to provide portable, purely + functional, efficient data structures written in Common Lisp. Funds + is open source software released under the + <a href="http://www.opensource.org/licenses/mit-license.php"> + MIT License + </a>.</p> + + <h3>Mailing Lists</h3> + <ul> + <li> + <a href="http://www.common-lisp.net/mailman/listinfo/funds-devel"> + funds-devel</a><br>for developers</li> + <li> + <a href="http://www.common-lisp.net/mailman/listinfo/funds-cvs"> + funds-cvs</a><br>CVS log feed.</li> + <li> + <a href="http://www.common-lisp.net/mailman/listinfo/funds-announce"> + funds-announce</a><br>for announcements.</li> + + </ul> + + <h3>Download</h3> + + <p>This project has not released any files. It is under active + development as a <a + href="http://code.google.com/soc/lispnyc/appinfo.html?csaid=F098323F679401F6"> + Google Summer of Code Project</a>, and a release is planned for + July 6, 2007. + +</p> + + <h3>Project members</h3> +<ul> +<li> + <a href="mailto:andrew.baine@gmail.com">Andrew Baine</a> +</li> +</ul> + <h3>CVS</h3> + + <p>You can <a + href="http://common-lisp.net/cgi-bin/viewcvs.cgi/?cvsroot=funds"> + browse our CVS repository</a> or download the current development + tree via anonymous cvs, as described <a + href="http://common-lisp.net/faq.shtml">here</a></p> + + <div class="footer"> + </div> + + <div class="check"> + <a href="http://validator.w3.org/check/referer"> + Valid XHTML 1.0 Strict</a> + </div> + </body></html> Added: trunk/public_html/project-name ============================================================================== --- (empty file) +++ trunk/public_html/project-name Thu Jun 7 14:29:41 2007 @@ -0,0 +1 @@ +funds Added: trunk/public_html/style.css ============================================================================== --- (empty file) +++ trunk/public_html/style.css Thu Jun 7 14:29:41 2007 @@ -0,0 +1,54 @@ + +.header { + font-size: medium; + background-color:#336699; + color:#ffffff; + border-style:solid; + border-width: 5px; + border-color:#002244; + padding: 1mm 1mm 1mm 5mm; +} + +.footer { + font-size: small; + font-style: italic; + text-align: right; + background-color:#336699; + color:#ffffff; + border-style:solid; + border-width: 2px; + border-color:#002244; + padding: 1mm 1mm 1mm 1mm; +} + +.footer a:link { + font-weight:bold; + color:#ffffff; + text-decoration:underline; +} + +.footer a:visited { + font-weight:bold; + color:#ffffff; + text-decoration:underline; +} + +.footer a:hover { + font-weight:bold; + color:#002244; + text-decoration:underline; } + +.check {font-size: x-small; + text-align:right;} + +.check a:link { font-weight:bold; + color:#a0a0ff; + text-decoration:underline; } + +.check a:visited { font-weight:bold; + color:#a0a0ff; + text-decoration:underline; } + +.check a:hover { font-weight:bold; + color:#000000; + text-decoration:underline; }

1 0

[funds-cvs] CVS public_html
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/public_html In directory clnet:/tmp/cvs-serv4029/public_html Modified Files: index.html Log Message: updated project page. --- /project/funds/cvsroot/public_html/index.html 2007/06/07 16:25:26 1.1.1.1 +++ /project/funds/cvsroot/public_html/index.html 2007/06/07 16:50:52 1.2 @@ -36,29 +36,27 @@ <h3>Download</h3> - <p>This project has not released any files. It is being developed as - a <a + <p>This project has not released any files. It is under active + development as a <a href="http://code.google.com/soc/lispnyc/appinfo.html?csaid=F098323F679401F6"> - Google Summer of Code Project</a>, and a release is expected by - mid-July. + Google Summer of Code Project</a>, and a release is planned for + July 6, 2007. </p> <h3>Project members</h3> <ul> <li> - <a href="mailto:andrew.baine@gmail.com">Andrew L. Baine</a> + <a href="mailto:andrew.baine@gmail.com">Andrew Baine</a> </li> </ul> <h3>CVS</h3> - <p>As of June 6, 2007, the project sources have not yet been moved -to the common-lisp.net servers. Once they are, in mid-June, you will -be able to <a -href="http://common-lisp.net/cgi-bin/viewcvs.cgi/?cvsroot=funds"> -browse our CVS repository</a> or download the current development tree -via anonymous cvs, as described <a -href="http://common-lisp.net/faq.shtml">here</a></p> + <p>You can <a + href="http://common-lisp.net/cgi-bin/viewcvs.cgi/?cvsroot=funds"> + browse our CVS repository</a> or download the current development + tree via anonymous cvs, as described <a + href="http://common-lisp.net/faq.shtml">here</a></p> <div class="footer"> </div>

1 0

[funds-cvs] CVS public_html
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/public_html In directory clnet:/tmp/cvs-serv31078 Log Message: Import web page. Status: Vendor Tag: abaine Release Tags: start N public_html/index.html N public_html/project-name N public_html/style.css No conflicts created by this import

1 0

[funds-cvs] CVS funds/src
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/funds/src In directory clnet:/tmp/cvs-serv23402/funds/src Modified Files: package.lisp Log Message: Added defpackage form. --- /project/funds/cvsroot/funds/src/package.lisp 2007/06/07 15:20:10 1.1 +++ /project/funds/cvsroot/funds/src/package.lisp 2007/06/07 15:42:38 1.2 @@ -0,0 +1,3 @@ + +(defpackage :funds + (:use :common-lisp)) \ No newline at end of file

1 0

[funds-cvs] CVS funds/src
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/funds/src In directory clnet:/tmp/cvs-serv17708/src Added Files: funds.asd package.lisp Log Message: Added funds.asd and package.lisp --- /project/funds/cvsroot/funds/src/funds.asd 2007/06/07 15:20:11 NONE +++ /project/funds/cvsroot/funds/src/funds.asd 2007/06/07 15:20:11 1.1 --- /project/funds/cvsroot/funds/src/package.lisp 2007/06/07 15:20:11 NONE +++ /project/funds/cvsroot/funds/src/package.lisp 2007/06/07 15:20:11 1.1

1 0

[funds-cvs] CVS funds/src
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/funds/src In directory clnet:/tmp/cvs-serv16807/src Log Message: Directory /project/funds/cvsroot/funds/src added to the repository

1 0

[funds-cvs] CVS funds/doc
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/funds/doc In directory clnet:/tmp/cvs-serv16629/doc Log Message: Directory /project/funds/cvsroot/funds/doc added to the repository

1 0

[funds-cvs] CVS funds
by abaine 07 Jun '07

07 Jun '07

Update of /project/funds/cvsroot/funds In directory clnet:/tmp/cvs-serv15932 Log Message: Initial import into CVS Status: Vendor Tag: abaine Release Tags: start No conflicts created by this import

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

funds-cvs June 2007