chickadee » treaps

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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 #!optional symprocedure

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? xprprocedure

type predicate.

treap-empty?

treap-empty? trpprocedure

checks it the treap argument is empty.

treap-key?

treap-key? trpprocedure

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

treap-value?

treap-value? trpprocedure

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

treap-compare

treap-compare trpprocedure

returns the numerical comparison operator as used by the constructor.

treap-get

treap-get trp key #!optional defaultprocedure

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 trpprocedure

returns the key-value pair with minimal key.

treap-get-max

treap-get-max trpprocedure

returns the key-value pair with maximal key.

treap-size

treap-size trpprocedure

returns the number of key-value pairs.

treap-depth

treap-depth trpprocedure

returns the depth of the treap traversing it completely.

treap-delete-min!

treap-delete-min! trpprocedure

removes the key-value pair with minimal key.

treap-delete-max!

treap-delete-max! trpprocedure

removes the key-value pair with maximal key.

treap-delete!

treap-delete! trp key #!optional defaultprocedure

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

treap-clear!

treap-clear! trpprocedure

makes the treap empty removing all key-value pairs.

treap-put

treap-put key valprocedure

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 procprocedure

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

treap-for-each-descending

treap-for-each-descending trp procprocedure

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

treap-debugprint

treap-debugpring trpprocedure

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 »