((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/treaps" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (tags "egg") (toc)) (section 2 "treaps" (p "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.") (section 3 "The routines" (section 4 "treaps" (def (sig (procedure "(treaps [sym])" (id treaps))) (p "documentation procedure. If called without arguments prints the list of exported symbols, otherwise the documentation of the exported symbol sym."))) (section 4 "make-treap" (def (sig (procedure "(make-treap compare value?)" (id make-treap))) (p "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."))) (section 4 "treap?" (def (sig (procedure "(treap? xpr)" (id treap?))) (p "type predicate."))) (section 4 "treap-empty?" (def (sig (procedure "(treap-empty? trp)" (id treap-empty?))) (p "checks it the treap argument is empty."))) (section 4 "treap-key?" (def (sig (procedure "(treap-key? trp)" (id treap-key?))) (p "returns a predicate,which checks if its argument is a valid key."))) (section 4 "treap-value?" (def (sig (procedure "(treap-value? trp)" (id treap-value?))) (p "returns a predicate,which checks if its argument is a valid value."))) (section 4 "treap-compare" (def (sig (procedure "(treap-compare trp)" (id treap-compare))) (p "returns the numerical comparison operator as used by the constructor."))) (section 4 "treap-get" (def (sig (procedure "(treap-get trp key [default])" (id treap-get))) (p "returns the key-value pair matching the key argument, if there is any. If not evaluates default, if provided, else signals an error."))) (section 4 "treap-get-min" (def (sig (procedure "(treap-get-min trp)" (id treap-get-min))) (p "returns the key-value pair with minimal key."))) (section 4 "treap-get-max" (def (sig (procedure "(treap-get-max trp)" (id treap-get-max))) (p "returns the key-value pair with maximal key."))) (section 4 "treap-size" (def (sig (procedure "(treap-size trp)" (id treap-size))) (p "returns the number of key-value pairs."))) (section 4 "treap-depth" (def (sig (procedure "(treap-depth trp)" (id treap-depth))) (p "returns the depth of the treap traversing it completely."))) (section 4 "treap-delete-min!" (def (sig (procedure "(treap-delete-min! trp)" (id treap-delete-min!))) (p "removes the key-value pair with minimal key."))) (section 4 "treap-delete-max!" (def (sig (procedure "(treap-delete-max! trp)" (id treap-delete-max!))) (p "removes the key-value pair with maximal key."))) (section 4 "treap-delete!" (def (sig (procedure "(treap-delete! trp key [default])" (id treap-delete!))) (p "removes the key-value pair corresponding to key or evaluates default."))) (section 4 "treap-clear!" (def (sig (procedure "(treap-clear! trp)" (id treap-clear!))) (p "makes the treap empty removing all key-value pairs."))) (section 4 "treap-put" (def (sig (procedure "(treap-put key val)" (id treap-put))) (p "inserts a new key-value pair returning #f or updates the value of an existing key returning the old pair."))) (section 4 "treap-for-each-ascending" (def (sig (procedure "(treap-for-each-ascending trp proc)" (id treap-for-each-ascending))) (p "applies proc to each key-value pair traversing trp in ascending order."))) (section 4 "treap-for-each-descending" (def (sig (procedure "(treap-for-each-descending trp proc)" (id treap-for-each-descending))) (p "applies proc to each key-value pair traversing trp in descending order."))) (section 4 "treap-debugprint" (def (sig (procedure "(treap-debugpring trp)" (id treap-debugpring))) (p "prints whole treap with debug information."))))) (section 2 "Requirements" (p "treap")) (section 2 "Last update" (p "Nov 27, 2013")) (section 2 "Author" (p (int-link "/users/juergen-lorenz" "Juergen Lorenz"))) (section 2 "License" (pre "Copyright (c) 2013, Juergen Lorenz\nAll rights reserved.\n\nThis program is free software: you can redistribute it and/or modify\nit under the terms of the GNU General Public License as published by\nthe Free Software Foundation, either version 3 of the License, or (at\nyour option) any later version.\n\nThis program is distributed in the hope that it will be useful, but\nWITHOUT ANY WARRANTY; without even the implied warranty of\nMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\nGeneral Public License for more details.\n\nA full copy of the GPL license can be found at\n<http://www.gnu.org/licenses/>.")) (section 2 "Version History" (dl (dt "0.1.2") (dd "tests updated") (dt "0.1.1") (dd "tests updated") (dt "0.1") (dd "initial import"))))