== 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.

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) -> * or #f</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''))

== 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

; 0.1 : (2022-05-25) Initial release.
; 0.1.1 : (2022-05-25) Fix missing dependency.
; 0.1.2 : (2022-05-25) Rename egg to make Henrietta happy.
; 0.1.3 : (2022-05-25) Fix test import.
; 0.1.4 : (2022-05-25) Revert renaming, keep the dot, just rename the egg file.

=== License

[[https://www.gnu.org/licenses/old-licenses/gpl-2.0.txt|GNU GPL version 2]]