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.

  1. Outdated egg!
  2. treaps
    1. The routines
      1. treaps
      2. make-treap
      3. treap?
      4. treap-empty?
      5. treap-key?
      6. treap-value?
      7. treap-compare
      8. treap-get
      9. treap-get-min
      10. treap-get-max
      11. treap-size
      12. treap-depth
      13. treap-delete-min!
      14. treap-delete-max!
      15. treap-delete!
      16. treap-clear!
      17. treap-put
      18. treap-for-each-ascending
      19. treap-for-each-descending
      20. treap-debugprint
  3. Requirements
  4. Last update
  5. Author
  6. License
  7. Version History

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)

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

Nov 27, 2013

Author

Juergen Lorenz

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