- 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 #!optional symprocedure
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? xprprocedure
- treap-empty? trpprocedure
checks it the treap argument is empty.
- treap-key? trpprocedure
returns a predicate,which checks if its argument is a valid key.
- treap-value? trpprocedure
returns a predicate,which checks if its argument is a valid value.
- treap-compare trpprocedure
returns the numerical comparison operator as used by the constructor.
- 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 trpprocedure
returns the key-value pair with minimal key.
- treap-get-max trpprocedure
returns the key-value pair with maximal key.
- treap-size trpprocedure
returns the number of key-value pairs.
- treap-depth trpprocedure
returns the depth of the treap traversing it completely.
- treap-delete-min! trpprocedure
removes the key-value pair with minimal key.
- treap-delete-max! trpprocedure
removes the key-value pair with maximal key.
- treap-delete! trp key #!optional defaultprocedure
removes the key-value pair corresponding to key or evaluates default.
- treap-clear! trpprocedure
makes the treap empty removing all key-value pairs.
- 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 trp procprocedure
applies proc to each key-value pair traversing trp in ascending order.
- treap-for-each-descending trp procprocedure
applies proc to each key-value pair traversing trp in descending order.
- treap-debugpring trpprocedure
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