Creating version control for Scheme programs.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@24 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Worked out attempt at tree-deletion operation via addition of a generalized rebalance function (after working out a remove-min function which was not general enough...)

git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@25 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further corrections to the key-deletion function, named "remove-from-tree" to fix bugs from original specification (got details wrong in:  base case of the node which contains the key to be deleted having no children, and did not hand the successor's key to the recursive call to remove that successor's key from a right-hand subtree.)

git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@26 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Corrected error in b-insert2 (due to blindly copying structure over from the original version of b-insert, b-insert2 ended up with calls to b-insert in its body, instead of recursive calls to b-insert2.

git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@27 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further error corrections.  Added in a rudimentary concat function, a range-searching function, and some rudimentary functions that could be used to build really long lists, in order to to comparison and benchmarking between dumb linear list searching and balanced tree searching.

git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@28 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further commentary, and removal of redundant code.

git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@29 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Corrected error in the list-range balanced tree range-searching function.  The reasoning about the keys stored in the tree relative to the starting and ending range values had to be corrected.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@30 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further corrections to function list-range in order to remove the dependency on directly comparing key values using <=.  Changed it to work with the provided kcomp function, to make it more portable.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@31 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further corrections to the remove-from-tree function to correctly capture the special case of the key-to-be-removed being in a node with no right child, and a single leaf as the left child.  Also added a little test-loop called del-test-350.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@32 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further simplifications to the insertion function, and renamed it to b-insert.  Was able to further simplify the balanced tree insertion function by moving the creation of the new key's node outside the main recursive work (to reduce unnecessary cons-ing) and also used letrec expression to further simplify the expressions used, hopefully to make it easier to understand (and perhaps a better performer.)


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@33 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further commentary added, modest refinements to the rebalance and b-insert functions, mainly to make tracing output possible.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@34 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further refinements, corrections, comments, especially commentary on the issue of rebalancing in this context versus an imperative context.  Seems that trying to put bounds of rebalancing operations is less crucial in a purely functional context because nodes on the root-to-target path must always be rebuilt/rederived anyway.  This seems to remove the opportunity to stop or arrest the unwinding of the recursive stack or tree-traversal stack when inserting into an AVL tree.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@35 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Derived a split function to split an avl-tree into two separate trees given a key to split by.  The concat, lconcat, and rconcat functions are not quite correct, and should probably be rewritten in terms of the correct lconcat-key and rconcat-key anyhow.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@36 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Rewrote "regular concatenations," called lconcat and rconcat, in terms of lconcat-key and rconcat-key, respectively.  Added notes on how to use other comparison operators for other kinds of data.  This is a step towards a solution which allows us to set the data type when we create a new balanced search tree.  This means that we wouldchoose the comparison function the tree searching functions shall use upon the specification of the initial, empty tree structure.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@37 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
More corrections in the use of let-binding forms to make the code more portable across slightly varying Scheme dialects.  For example, many of the places in which I had used letrec really should have been using let*.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@38 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further refinements to make it simpler for the user to provide their own comparison function, thus generalizing the search tree structure for use with any kind of set which provides a total ordering operator.  This change turned out to make accessing parts of the structures uglier, expecially in the remove-from-tree function.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@39 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Reworked the remove-from-tree, factored its core out into a separate internal-remove-from-tree to get rid of the ugliness introduced by packaging the comparison function into the tree structure.  Now, remove-from-tree is a wrapper around internal-remove-from-tree.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@40 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Deleted the older remove-from-tree, called "remove-from-tree-old."


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@41 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Further clean-up of b-list-range to ensure it uses the comparison function provided in the data structure instead of one from the enclosing scope.  Also commented out the existing global kcomp function to ensure it won't be used by accident in the future.


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@42 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7
Derived a version of the split function which uses potentially cheaper list-concatenation-as-function-composition.  Also performed further clean-up on the b-split function:  it contained references to an unbound symbol kcomp which was left over from earlier revisions, and which made it incorrect!


git-svn-id: file:///home/rstewart/svn_storage/scheme_programs@43 c9869a52-8a54-4101-b2b4-6ecaa1f5aaf7