1 Scapegoat Trees

8.12

1 Scapegoat Trees🔗ℹ

1.1 Introduction🔗ℹ

This module provides a dictionary type implemented using scapegoat trees.

A scapegoat tree implements the gen:dict and gen:ordered-dict interfaces. Trees are immutable; side-effect versions of functions update a pointer to the root of the tree as a convienence.

1.2 Dictionary Interface🔗ℹ

In addition to the dict? and ordered-dict? APIs, scapegoat trees support the following functions.

1.2.1 Parameters🔗ℹ

parameter
(scapegoat-tree-height-factor) → (and/c (>/c 0.5) (</c 1))
(scapegoat-tree-height-factor factor) → void?
factor : (and/c (>/c 0.5) (</c 1))
= 2/3

The height factor used in calculating if a tree needs to be rebalanced. The higher the number, the more unbalanced the tree is allowed to become.

parameter
(scapegoat-tree-rebalance-on-copy) → boolean?
(scapegoat-tree-rebalance-on-copy rebalance?) → void?
rebalance? : boolean?
= #t

If true, dict-copy and scapegoat-tree-copy return a fully rebalanced tree instead of a straight copy of the original.

1.2.2 Predicates🔗ℹ

procedure
(scapegoat-tree? obj) → boolean?
obj : any/c

Tests if an object is a scapegoat tree or not.

procedure
(scapegoat-tree-iterator? obj) → boolean?
obj : any/c

Tests if an object is a scapegoat tree iterator or not.

1.2.3 Constructors🔗ℹ

procedure
(make-scapegoat-tree [ order
#:key-contract key-contract
#:value-contract value-contract])
→ scapegoat-tree?
  order : order? = datum-order
  key-contract : contract? = (order-datum-contract order)
  value-contract : contract? = any/c

Makes a new empty scapegoat tree. The tree uses order to order keys; in addition, the domain contract of order is combined with key-contract to check keys.

procedure
(scapegoat-tree-copy s) → scapegoat-tree?
s : scapegoat-tree?

Returns a new copy of the given tree.

procedure
(scapegoat-tree-clear s) → scapegoat-tree?
s : scapegoat-tree?

Returns a new empty tree with the same order and contracts as the original.

syntax
(for/scapegoat-tree [#:order order order? order-datum]
[#:key-contract key-contract contract? (order-datum-contract order)]
[#:value-contract value-contract contract? any/c]
(sequence-binding ...)
body ...)

{

A "for" comprehension that returns a scapegoat tree with the optionally provided order and contracts. The body should return two values, used as the key and value to be inserted into the returned scapegoat tree. Later keys overrwrite earlier duplicates.

}

syntax
(for*/scapegoat-tree [#:order order order? order-datum]
[#:key-contract key-contract contract? (order-datum-contract order)]
[#:value-contract value-contract contract? any/c]
(sequence-binding ...)
body ...)

{

A "for*" comprehension that returns a scapegoat tree with the optionally provided order and contracts. The body should return two values, used as the key and value to be inserted into the returned scapegoat tree. Later keys overrwrite earlier duplicates.

}

1.2.4 Queries🔗ℹ

procedure
(scapegoat-tree-order s) → order?
s : scapegoat-tree?

Returns the order object used to compare keys in the tree.

procedure
(scapegoat-tree-key-contract s) → contract?
s : scapegoat-tree?

Returns the contract used on keys stored in the tree.

procedure
(scapegoat-tree-value-contract s) → contract?
s : scapegoat-tree?

Returns the contract used on values stored in the tree.

procedure
(scapegoat-tree-empty? s) → boolean?
s : scapegoat-tree?

Tests to see if the tree if empty or not.

procedure
(scapegoat-tree-count s) → natural-number/c
s : scapegoat-tree?

Returns the number of elements stored in the tree.

procedure
(scapegoat-tree-ref s key [default]) → any
  s : scapegoat-tree?
  key : any/c
   default : any/c
= (lambda () (error "key not found\n    key: " key))

Returns the value associated with the given tree. If not found and default is a procedure, returns the value it returns, otherwise returns default.

1.2.4.1 Iterators🔗ℹ

procedure
(scapegoat-tree-iterate-first s)
→ (or/c scapegoat-tree-iterator? #f)
s : scapegoat-tree?

Returns an iterator to the first element of the tree. Elements are returned in order through the iterator interface.

Returns #f if the tree is empty.

procedure
(scapegoat-tree-iterate-next s i)
→ (or/c scapegoat-tree-iterator? #f)
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns the iterator to the next element after the given position, or #f if at the end of the tree.

procedure
(scapegoat-tree-iterate-key s i) → any
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns the key of the indicated element of the tree.

procedure
(scapegoat-tree-iterate-value s i) → any
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns the value of the indicated element of the tree.

procedure
(scapegoat-tree-iterator->list s i) → list?
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns an alist of the elements of the tree starting with the given iterator. The car of each element of the list is the key and the cdr is the value.

procedure
(scapegoat-tree-iterator->key-list s i) → list?
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns a list of the keys of the tree starting with the given iterator.

procedure
(scapegoat-tree-iterator->value-list s i) → list?
s : scapegoat-tree?
i : scapegoat-tree-iterator?

Returns a list of the values of the tree starting with the given iterator.

1.2.5 Mutators🔗ℹ

procedure
(scapegoat-tree-set s key value) → scapegoat-tree?
  s : scapegoat-tree?
  key : any/c
  value : any/c

Returns a new tree with the given key and value inserted into it. If the key already exists, the value is updated in the returned tree. The original tree is unmodified.

procedure
(scapegoat-tree-set! s key value) → any
  s : scapegoat-tree?
  key : any/c
  value : any/c

Inserts the given key and value in the tree in-place. If the key already exists, the value is updated.

procedure
(scapegoat-tree-delete s key) → scapegoat-tree?
s : scapegoat-tree?
key : any/c

Returns a new tree with the given key removed from it. The original tree is unmodified. It is not an error if the key was not present.

procedure
(scapegoat-tree-delete! s key) → any
s : scapegoat-tree?
key : any/c

Removes the given key from the tree in-place. It is not an error if the key was not present.