- Last update
- Version History
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.
- (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 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? xpr) procedure
- (treap-empty? trp) procedure
checks it the treap argument is empty.
- (treap-key? trp) procedure
returns a predicate,which checks if its argument is a valid key.
- (treap-value? trp) procedure
returns a predicate,which checks if its argument is a valid value.
- (treap-compare trp) procedure
returns the numerical comparison operator as used by the constructor.
- (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 trp) procedure
returns the key-value pair with minimal key.
- (treap-get-max trp) procedure
returns the key-value pair with maximal key.
- (treap-size trp) procedure
returns the number of key-value pairs.
- (treap-depth trp) procedure
returns the depth of the treap traversing it completely.
- (treap-delete-min! trp) procedure
removes the key-value pair with minimal key.
- (treap-delete-max! trp) procedure
removes the key-value pair with maximal key.
- (treap-delete! trp key [default]) procedure
removes the key-value pair corresponding to key or evaluates default.
- (treap-clear! trp) procedure
makes the treap empty removing all key-value pairs.
- (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 trp proc) procedure
applies proc to each key-value pair traversing trp in ascending order.
- (treap-for-each-descending trp proc) procedure
applies proc to each key-value pair traversing trp in descending order.
- (treap-debugpring trp) procedure
prints whole treap with debug information.
Nov 27, 2013
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/>.
- tests updated
- tests updated
- initial import