You are looking at historical revision 29103 of this page. It may differ significantly from its current revision.

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

*[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)`

type predicate.

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

#### treap-put

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

## Requirements

treap

## Last update

Jun 15, 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
- initial import