You are looking at historical revision 29103 of this page. It may differ significantly from its current revision.
- 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[procedure] (treaps [sym])
documentation procedure. If called without arguments prints the list of exported symbols, otherwise the documentation of the exported symbol sym.
make-treap[procedure] (make-treap compare value?)
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?[procedure] (treap? xpr)
treap-empty?[procedure] (treap-empty? trp)
checks it the treap argument is empty.
treap-key?[procedure] (treap-key? trp)
returns a predicate,which checks if its argument is a valid key.
treap-value?[procedure] (treap-value? trp)
returns a predicate,which checks if its argument is a valid value.
treap-compare[procedure] (treap-compare trp)
returns the numerical comparison operator as used by the constructor.
treap-get[procedure] (treap-get trp key [default])
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[procedure] (treap-get-min trp)
returns the key-value pair with minimal key.
treap-get-max[procedure] (treap-get-max trp)
returns the key-value pair with maximal key.
treap-size[procedure] (treap-size trp)
returns the number of key-value pairs.
treap-depth[procedure] (treap-depth trp)
returns the depth of the treap traversing it completely.
treap-delete-min![procedure] (treap-delete-min! trp)
removes the key-value pair with minimal key.
treap-delete-max![procedure] (treap-delete-max! trp)
removes the key-value pair with maximal key.
treap-delete![procedure] (treap-delete! trp key [default])
removes the key-value pair corresponding to key or evaluates default.
treap-clear![procedure] (treap-clear! trp)
makes the treap empty removing all key-value pairs.
<procedure(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[procedure] (treap-for-each-ascending trp proc)
applies proc to each key-value pair traversing trp in ascending order.
treap-for-each-descending[procedure] (treap-for-each-descending trp proc)
applies proc to each key-value pair traversing trp in descending order.
treap-debugprint[procedure] (treap-debugpring trp)
prints whole treap with debug information.
Jun 15, 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/>.
- initial import