chickadee » treaps

treaps

This module provides a functional interface to Oleg Kiselyov's and Ivan Raikov's treap egg. Remember, that treaps are fast search-trees where balancing is replaced by inserting elements in some random fashion. Insofar, treaps are similar to skiplists. The name, treap, is a combination of tree and heap.

The routines

treaps

(treaps [sym]) procedure

documentation procedure. If called without arguments prints the list of exported symbols, otherwise the documentation of the exported symbol sym.

make-treap

(make-treap compare value?) procedure

constructor. Creates a new treap which compares keys with a numerical compare procedure and stores key-value pairs with value-type checked by the value? predicate.

treap?

(treap? xpr) procedure

type predicate.

treap-empty?

(treap-empty? trp) procedure

checks it the treap argument is empty.

treap-key?

(treap-key? trp) procedure

returns a predicate,which checks if its argument is a valid key.

treap-value?

(treap-value? trp) procedure

returns a predicate,which checks if its argument is a valid value.

treap-compare

(treap-compare trp) procedure

returns the numerical comparison operator as used by the constructor.

treap-get

(treap-get trp key [default]) procedure

returns the key-value pair matching the key argument, if there is any. If not evaluates default, if provided, else signals an error.

treap-get-min

(treap-get-min trp) procedure

returns the key-value pair with minimal key.

treap-get-max

(treap-get-max trp) procedure

returns the key-value pair with maximal key.

treap-size

(treap-size trp) procedure

returns the number of key-value pairs.

treap-depth

(treap-depth trp) procedure

returns the depth of the treap traversing it completely.

treap-delete-min!

(treap-delete-min! trp) procedure

removes the key-value pair with minimal key.

treap-delete-max!

(treap-delete-max! trp) procedure

removes the key-value pair with maximal key.

treap-delete!

(treap-delete! trp key [default]) procedure

removes the key-value pair corresponding to key or evaluates default.

treap-clear!

(treap-clear! trp) procedure

makes the treap empty removing all key-value pairs.

treap-put

(treap-put key val) procedure

inserts a new key-value pair returning #f or updates the value of an existing key returning the old pair.

treap-for-each-ascending

(treap-for-each-ascending trp proc) procedure

applies proc to each key-value pair traversing trp in ascending order.

treap-for-each-descending

(treap-for-each-descending trp proc) procedure

applies proc to each key-value pair traversing trp in descending order.

treap-debugprint

(treap-debugpring trp) procedure

prints whole treap with debug information.

Requirements

treap

Last update

Nov 27, 2013

Author

Juergen Lorenz

License

Copyright (c) 2013, Juergen Lorenz
All rights reserved.

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

A full copy of the GPL license can be found at
<http://www.gnu.org/licenses/>.

Version History

0.1.2
tests updated
0.1.1
tests updated
0.1
initial import

Contents »