funds-cvs

funds-cvs@common-lisp.net

225 discussions

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

14 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

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

funds-cvs