1 Scapegoat Trees

8.6

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 the 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? = any/c
  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.

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 a list 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.