You can edit this page using wiki syntax for markup.

Article contents:== slib-wt-tree This egg is a CHICKEN port of the {{(slib wt-tree)}} library. It provides [[https://en.wikipedia.org/wiki/Weight-balanced_tree|weight-balanced trees]], a kind of self-balancing binary trees which are excellent for working with large collections of ordered-key/value-structured data. While the name of this egg is {{slib-wt-tree}}, the module it provides is {{(slib wt-tree)}}. This difference is due to the names allowed by the Henrietta egg server. This egg is licensed under the GNU General Public License, version 2. [[toc:]] == Library A weight-balanced tree is a self-balancing binary search tree. Abstractly, it is a dictionary, a set of associations between objects of a ''key'' type and of a ''value'' type. In this implementation, all keys must be of the same type, but value types may differ within a single tree. Weight-balanced trees are an easy drop-in replacement for alists, basic binary trees, hash-tables, and other familiar dictionary structures. Since they're also ordered by key, they can also be used to implement queues. Weight-balanced tree operations marked "O(log ''n'')" in this document run in time proportional to the logarithm of the number of associations in the given tree. === Tree types {{wt-trees}} are constructed in two steps: First, you create a tree type, an object which holds key-type information, and second, you construct a new tree using this type object. A few tree-types are built-in. <procedure>(make-wt-tree-type key<?) -> wt-tree-type</procedure> Returns a new tree type based on the ordering predicate ''key?'', which compares two key values and returns a boolean. ''key?'' should be a total ordering; for all key values ''a'', ''b'', and ''c'', the following must hold: <enscript hilight="scheme">(key<? a a) ; -> #f (and (key<? a b) (key<? b a)) ; -> #f (if (and (key<? a b) (key<? b c)) (key <? a c) #t) ; -> #t </enscript> Two wt-trees are compatible if their tree type objects are {{eqv?}}, so trees whose types result from different calls to {{make-wt-tree-type}} are always incompatible. <procedure>(wt-tree-type? obj) -> boolean</procedure> Returns {{#t}} if ''obj'' is a tree type object and {{#f}} otherwise. <constant>number-wt-type</constant> A standard tree type for trees with numeric keys. <constant>string-wt-type</constant> A standard tree type for trees with string keys. === Constructors <procedure>(make-wt-tree tree-type) -> wt-tree</procedure> Returns a new, empty weight-balanced tree specialized on ''tree-type''. <procedure>(singleton-wt-tree tree-type key value) -> wt-tree</procedure> Reterns a new weight-balanced tree with type ''tree-type'' and containing the single association (''key'', ''value''). Example: <enscript hilight="scheme">(singleton-wt-tree number-wt-type 1 2) ; -> wt-tree</enscript> <procedure>(alist->wt-tree tree-type alist) -> wt-tree</procedure> Returns a new weight-balanced tree with type ''tree-type'' and containing all the associations of ''alist''. Example: <enscript hilight="scheme">(alist->wt-tree number-wt-type '((1 . 2) (2 . 4) (3 . 6))) ; -> wt-tree </enscript> <procedure>(wt-tree/add tree key value) -> wt-tree</procedure> Returns a new tree containing all the associations of ''tree'' as well as the association (''key'', ''value''). Any existing association for ''key'' is replaced. (O(log ''n'')) Example: <enscript hilight="scheme"> (let ((t (wt-tree/add (alist->wt-tree number-wt-type '((1 . 2) (2 . 4))) 5 10))) (wt-tree/lookup t 5 #f)) ; -> 10 </enscript> <procedure>(wt-tree/delete tree key) -> wt-tree</procedure> Returns a new tree containing all the associations of ''tree'' except for the association for ''key'', if one exists. (O(log ''n'')) <procedure>(wt-tree/delete-min tree key) -> wt-tree</procedure> ''tree'' must not be empty. Returns a new tree containing all the associations of ''tree'' except the one with the least key in the sorted sequence of keys. (O(log ''n'')) === Predicates <procedure>(wt-tree? obj) -> boolean</procedure> Returns {{#t}} if ''obj'' is a weight-balanced tree and {{#f}} otherwise. <procedure>(wt-tree/empty? tree) -> boolean</procedure> Returns {{#t}} if ''tree'' contains no associations and {{#f}} otherwise. === Size <procedure>(wt-tree/size tree) -> integer</procedure> Returns the number of associations in ''tree''. === Accessors <procedure>(wt-tree/member? key tree) -> boolean</procedure> Returns {{#t}} if ''tree'' contains an association for ''key'' and {{#f}} otherwise. (O(log ''n'')) <procedure>(wt-tree/lookup tree key default) -> *</procedure> Returns the value associated with ''key'' in ''tree'', or ''default'' (which can be any Scheme value) if there is no such association. (O(log ''n'')) <procedure>(wt-tree/index tree k) -> *</procedure> <procedure>(wt-tree/index-datum tree k) -> *</procedure> <procedure>(wt-tree/index-pair tree k) -> pair(*, *)</procedure> ''tree'' must not be empty, and ''k'' must be a positive exact integer. Returns the 0-based ''k''th association of ''tree'' in the sorted sequence of keys. {{wt-tree/index}} returns the ''k''th key, {{wt-tree/index-datum}} returns the value associated with the ''k''th key, and {{wt-tree/index-pair}} returns the ''k''th association as a {{(KEY . VALUE)}} pair. If ''k'' ≥ {{(wt-tree/size tree)}}, an error is signalled. (O(log ''n'')) Example: <enscript hilight="scheme"> (let ((t (alist->wt-tree string-wt-type '(("rincewind" . 23) ("twoflower" . 11) ("the luggage" . 31))))) (list (wt-tree/index t 1) (wt-tree/index-datum t 0) (wt-tree/index-pair t 2))) ; -> ("the luggage" 23 ("twoflower" . 11)) </enscript> <procedure>(wt-tree/min tree) -> *</procedure> <procedure>(wt-tree/min-datum tree) -> *</procedure> <procedure>(wt-tree/min-pair tree) -> pair(*, *)</procedure> ''tree'' must not be empty. Returns the association of ''tree'' with the least key in the sorted sequence of keys. {{wt-tree/min}} returns the least key, {{wt-tree/min-datum}} returns the value associated with the least key, and {{wt-tree/min-pair}} returns the least association as a {{(KEY . VALUE)}} pair. (O(log ''n'')) {{(wt-tree/min tree)}} is equivalent to {{(wt-tree/index tree 0)}}, and similarly for the other forms. <enscript hilight="scheme"> (let ((t (alist->wt-tree string-wt-type '(("rincewind" . 23) ("twoflower" . 11) ("the luggage" . 31))))) (list (wt-tree/min t) (wt-tree/min-datum t))) ; -> ("rincewind" 23) </enscript> <procedure>(wt-tree/rank tree key) -> integer or #f</procedure> Returns the 0-based position of ''key'' in the sorted sequence of keys of ''tree''. If ''key'' has no association in ''tree'', then {{#f}} is returned instead. <enscript hilight="scheme"> (let ((t (alist->wt-tree string-wt-type '(("rincewind" . 23) ("twoflower" . 11) ("the luggage" . 31))))) (wt-tree/rank "twoflower")) ; -> 1 </enscript> === Iteration <procedure>(wt-tree/fold kons knil tree) -> *</procedure> Folds ''tree'', applying ''kons'' to the key, value, and the accumulated result, in that order, at each step. ''knil'' is passed to ''kons'' as the initial accumulator value. ''tree'' is traversed in reverse order. Provided ''kons'' runs in O(1) time, {{wt-tree/fold}} takes time proportional to the size of ''tree''. Example: <enscript hilight="scheme"> (let ((t (alist->wt-tree string-wt-type '(("rincewind" . 23) ("twoflower" . 11) ("the luggage" . 31))))) (list (wt-tree/fold (lambda (_k v sum) (+ v sum)) 0 t) (wt-tree/fold (lambda (k _v keys) (cons k keys)) '() t))) ; -> (65 ("rincewind" "the luggage" "twoflower")) </enscript> <procedure>(wt-tree/for-each proc tree) -> unspecified</procedure> Traverses ''tree'' in increasing order of key, applying ''proc'' to the key and value of each association. Any values returned by ''proc'' are ignored. Provided ''proc'' runs in O(1) time, {{wt-tree/for-each}} takes time proportional to the size of ''tree''. <enscript hilight="scheme"> (let ((t (alist->wt-tree string-wt-type '(("rincewind" . 23) ("twoflower" . 11) ("the luggage" . 31)))) (acc 0)) (wt-tree/for-each (lambda (_k v) (set! acc (+ v acc))) t) acc) ; -> 65 </enscript> === Subtrees <procedure>(wt-tree/split< tree bound) -> wt-tree</procedure> <procedure>(wt-tree/split> tree bound) -> wt-tree</procedure> Returns a new tree containing the associations of ''tree'' whose keys are less than/greater than ''bound''. (O(log ''n'')) === Set theory operations <procedure>(wt-tree/union tree1 tree2) -> wt-tree</procedure> Returns a new tree containing all the associations from both ''tree1'' and ''tree2''. When both trees have an association for the same key, the returned tree contains the one from ''tree1''. The worst-case time required by this operation is proportional to the sum of the sizes of both trees. If the minimum key of one tree is greater than the maximum key of the other tree then the time required is at worst proportional to the logarithm of the size of the larger tree. <procedure>(wt-tree/intersection tree1 tree2) -> wt-tree</procedure> Returns a new tree containing all and only those associations from ''tree1'' which also have associations in ''tree2''. All the associations in the result are drawn from ''tree1''. The time required by this operation is at worst proportional to the sum of the sizes of the trees. <procedure>(wt-tree/difference tree1 tree2) -> wt-tree</procedure> Returns a new tree containing all and only those associations from ''tree1'' whose keys do not have an association in ''tree2''. The time required by this operation is at worst proportional to the sum of the sizes of the trees. <procedure>(wt-tree/subset? tree1 tree2) -> boolean</procedure> Returns {{#t}} if the key of each association in ''tree1'' has an association in ''tree2'', and {{#f}} otherwise. Note that {{wt-tree/subset?}} only compares keys. The time required by this operation is at worst proportional to the size of ''tree1''. <procedure>(wt-tree/set-equal? tree1 tree2) -> boolean</procedure> Returns {{#t}} if and only if the key of each association in ''tree1'' has an association in ''tree2'', and vice-versa. Note that {{wt-tree/set-equal?}} only compares keys. <procedure>(wt-tree/union-merge tree1 tree2 combine) -> wt-tree</procedure> ''combine'' is a procedure of three arguments returning a single value. Returns a new tree containing all the associations from both ''tree1'' and ''tree2''. When both trees have an association for the same key, ''combine'' is applied to the key and to both associated values, in that order, and the result is associated with the key. Assuming that ''combine'' runs in O(1) time, the worst-case time required by this operation is proportional to the sum of the sizes of both trees. If the minimum key of one tree is greater than the maximum key of the other tree then the time required is at worst proportional to the logarithm of the size of the larger tree. Example: <enscript hilight="scheme"> (let ((t1 (singleton-wt-tree number-wt-type 4 8)) (t2 (singleton-wt-tree number-wt-type 4 71))) (wt-tree/lookup (wt-tree/union-merge t1 t2 (lambda (_key v1 v2) (+ v1 v2))) 4 #f)) ; -> 79 </enscript> === Destructive operations All of the following procedures mutate their wt-tree argument and return an unspecified value. They should be called for their effects alone. <procedure>(wt-tree/add! tree key value) -> unspecified</procedure> Associates ''key'' with ''value'' in ''tree''. If ''tree'' already has an association for ''key'', then it is replaced. (O(log ''n'')) <procedure>(wt-tree/delete! tree key) -> unspecified</procedure> Deletes any association for ''key'' from ''tree''. (O(log ''n'')) <procedure>(wt-tree/delete-min! tree) -> unspecified</procedure> Deletes the association of ''tree'' with the least ''key'', in the sense of the tree's ordering predicate. (O(log ''n'')) === Exceptions Following CHICKEN's libraries, procedures from this egg abort with {{(exn type)}} and {{(exn bounds)}} conditions when type- and bounds-checking assertions fail, respectively. See the [[Module (chicken condition)]] page for more details. == About this egg === Dependencies The [[typed-records]] egg is required. To run the included tests, you'll also need the [[test]] and [[test-generative]] eggs. === Author Stephen Adams. Ported to CHICKEN 5 and edited by Wolfgang Corcoran-Mathe. === Maintainer Wolfgang Corcoran-Mathe Contact: {{wcm at sigwinch dot xyzzy without the zy}} === Repository [[https://github.com/Zipheir/wt-tree-chicken|GitHub]] === Version history Versions before 0.1.5 were bookkeeping fixes. ; 0.1.5 : (2022-05-26) Initial release. ; 0.1.6 : (2022-08-11) Rework exceptions, add more checks. === License [[https://www.gnu.org/licenses/old-licenses/gpl-2.0.txt|GNU GPL version 2]] Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 23 to 7?