((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/suffix-tree" "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")) (section 2 "suffix-tree" (p "An implementation of the suffix tree data structure.") (toc)) (section 2 "Usage" (p "(require-extension suffix-tree)")) (section 2 "Documentation" (p "In this implementation, a suffix tree is a tree where and each branch has a label that represents an element from a list with branches ordered on the basis of their labels. Only one branch per distinct label value is allowed per node.  Ends of lists are designated by an EOL marker; a value may be associated with the EOL symbol.") (p "The suffix tree permits partial look ups; that is, if the tree contains the lists " (tt "'(a b c)") " and " (tt "'(a b d)") ", then looking up key " (tt "'(a b)") " will return the subtree that contains " (tt "'(c)") " and " (tt "'(d)") " as branches.") (section 3 "Procedures" (p "The library defines a suffix tree \"object\" -- a procedure that takes a method name as a symbol, and returns the procedure that implements the respective operation.") (p "The suffix tree object is created by procedure " (tt "make-suffix-tree") ":") (def (sig (procedure "make-suffix-tree:: LEQ? KEY->LIST -> SELECTOR" (id make-suffix-tree))) (p "where:") (ul (li (tt "LEQ?") " is a less-than-or-equal procedure for comparing elements of the member lists") (li "{{KEY->LIST} is a procedure that takes in a key value and returns a list")) (p "The returned selector procedure can take one of the following arguments:") (dl (dt (tt "'insert")) (dd "inserts a new element (list); a procedure of the form " (tt "(LAMBDA (K BVAL) ...)") " where " (tt "K") " is a value of the type recognized by " (tt "KEY->LIST") " and " (tt "BVAL") " is the end-of-list value") (dt (tt "'lookup")) (dd "looks up an element (list); a procedure of the form " (tt "(LAMBDA (K) ...)") " where " (tt "K") " is a value of the type recognized by " (tt "KEY->LIST") "; returns the EOL value or " (tt "#F") " if the given element is not found") (dt (tt "'lookup/partial")) (dd "partial lookup; returns the EOL value, " (tt "#f") " or the subtree that corresponds to the given partial key") (dt (tt "'remove")) (dd "removes an element") (dt (tt "'merge")) (dd "merges the suffix tree with another; if there is a list that appears in both suffix trees, an exception is raised") (dt (tt "'partition")) (dd "splits the tree into three suffix-trees on the basis of the given element a.  The first suffix-tree consists of branches with keys less than a (plus any EOL value), the second contains the branch (if any) associated with a, and the third consists of branches for keys greater than a"))))) (section 2 "Examples") (section 2 "About this egg" (section 3 "Author" (p (int-link "/users/ivan-raikov" "Ivan Raikov"))) (section 3 "Version history" (dl (dt "1.0") (dd "Initial release"))) (section 3 "License" (pre "Copyright 2011-2012 Ivan Raikov and the Okinawa Institute of Science and Technology.\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/>."))))