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