extra/trees/trees-docs.factor

   1 USING: arrays assocs help.markup help.syntax kernel math ;
   2 IN: trees
   3
   4 HELP: TREE{
   5 { $syntax "TREE{ { key value }... }" }
   6 { $values { "key" "a key" } { "value" "a value" } }
   7 { $description "Literal syntax for an unbalanced tree." } ;
   8
   9 HELP: <tree>
  10 { $values { "tree" tree } }
  11 { $description "Creates an empty unbalanced binary tree" } ;
  12
  13 HELP: >tree
  14 { $values { "assoc" assoc } { "tree" tree } }
  15 { $description "Converts any " { $link assoc } " into an unbalanced binary tree. If the input assoc is any kind of " { $link tree } ", the elements are added in level order (breadth-first search) to copy it's shape." } ;
  16
  17 HELP: tree
  18 { $class-description "This is the class for unbalanced binary search trees. It is not usually intended to be used directly but rather as a basis for other trees." } ;
  19
  20 HELP: height
  21 { $values
  22     { "tree" tree }
  23     { "n" integer }
  24 }
  25 { $description "Returns the height of " { $snippet "tree" } "." } ;
  26
  27 HELP: headtree>alist[)
  28 { $values
  29     { "to-key" "a key" } { "tree" tree }
  30     { "alist" "an array of key/value pairs" }
  31 }
  32 { $description "Returns an alist of the portion of this tree whose keys are strictly less than to-key." } ;
  33
  34 HELP: headtree>alist[]
  35 { $values
  36     { "to-key" "a key" } { "tree" tree }
  37     { "alist" "an array of key/value pairs" }
  38 }
  39 { $description "Returns an alist of the portion of this tree whose keys are less than or equal to to-key." } ;
  40
  41 HELP: subtree>alist()
  42 { $values
  43     { "from-key" "a key" } { "to-key" "a key" } { "tree" tree }
  44     { "alist" "an array of key/value pairs" }
  45 }
  46 { $description "Returns an alist of the portion of this map whose keys range from fromKey (exclusive) to toKey (exclusive)." } ;
  47
  48 HELP: subtree>alist(]
  49 { $values
  50     { "from-key" "a key" } { "to-key" "a key" } { "tree" tree }
  51     { "alist" "an array of key/value pairs" }
  52 }
  53 { $description "Returns an alist of the portion of this map whose keys range from fromKey (exclusive) to toKey (inclusive)." } ;
  54
  55 HELP: subtree>alist[)
  56 { $values
  57     { "from-key" "a key" } { "to-key" "a key" } { "tree" tree }
  58     { "alist" "an array of key/value pairs" }
  59 }
  60 { $description "Returns an alist of the portion of this map whose keys range from fromKey (inclusive) to toKey (exclusive)." } ;
  61
  62 HELP: subtree>alist[]
  63 { $values
  64     { "from-key" "a key" } { "to-key" "a key" } { "tree" tree }
  65     { "alist" "an array of key/value pairs" }
  66 }
  67 { $description "Returns an alist of the portion of this map whose keys range from fromKey (inclusive) to toKey (inclusive)." } ;
  68
  69 HELP: tailtree>alist(]
  70 { $values
  71     { "from-key" "a key" } { "tree" tree }
  72     { "alist" "an array of key/value pairs" }
  73 }
  74 { $description "Returns an alist of the portion of this tree whose keys are strictly greater than to-key." } ;
  75
  76 HELP: tailtree>alist[]
  77 { $values
  78     { "from-key" "a key" } { "tree" tree }
  79     { "alist" "an array of key/value pairs" }
  80 }
  81 { $description "Returns an alist of the portion of this tree whose keys are greater than or equal to to-key." } ;
  82
  83 {
  84     headtree>alist[) headtree>alist[] tailtree>alist(] tailtree>alist[]
  85     subtree>alist() subtree>alist(] subtree>alist[) subtree>alist[]
  86 } related-words
  87
  88 HELP: ceiling-entry
  89 { $values
  90     { "key" "a key" } { "tree" tree }
  91     { "pair/f" { $maybe pair } }
  92 }
  93 { $description "Returns a key-value mapping associated with the least key greater than or equal to the given key, or " { $link f } " if there is no such key." } ;
  94
  95 HELP: ceiling-key
  96 { $values
  97     { "key" "a key" } { "tree" tree }
  98     { "key/f" { $maybe "a key" } }
  99 }
 100 { $description "Returns the least key greater than or equal to the given key, or " { $link f } " if there is no such key." } ;
 101
 102 HELP: floor-entry
 103 { $values
 104     { "key" "a key" } { "tree" tree }
 105     { "pair/f" { $maybe pair } }
 106 }
 107 { $description "Returns a key-value mapping associated with the greatest key less than or equal to the given key, or " { $link f } " if there is no such key." } ;
 108
 109 HELP: floor-key
 110 { $values
 111     { "key" "a key" } { "tree" tree }
 112     { "key/f" { $maybe "a key" } }
 113 }
 114 { $description "Returns the greatest key less than or equal to the given key, or " { $link f } " if there is no such key." } ;
 115
 116 HELP: higher-entry
 117 { $values
 118     { "key" "a key" } { "tree" tree }
 119     { "pair/f" { $maybe pair } }
 120 }
 121 { $description "Returns a key-value mapping associated with the least key strictly greater than the given key, or " { $link f } " if there is no such key." } ;
 122
 123 HELP: higher-key
 124 { $values
 125     { "key" "a key" } { "tree" tree }
 126     { "key/f" { $maybe "a key" } }
 127 }
 128 { $description "Returns the least key strictly greater than the given key, or " { $link f } " if there is no such key." } ;
 129
 130 HELP: lower-entry
 131 { $values
 132     { "key" "a key" } { "tree" tree }
 133     { "pair/f" { $maybe pair } }
 134 }
 135 { $description "Returns a key-value mapping associated with the greatest key strictly less than the given key, or " { $link f } " if there is no such key." } ;
 136
 137 HELP: lower-key
 138 { $values
 139     { "key" "a key" } { "tree" tree }
 140     { "key/f" { $maybe "a key" } }
 141 }
 142 { $description "Returns the greatest key strictly less than the given key, or " { $link f } " if there is no such key." } ;
 143
 144 { lower-key lower-entry higher-key higher-entry
 145   floor-key floor-entry ceiling-key ceiling-entry } related-words
 146
 147 HELP: last-entry
 148 { $values
 149     { "tree" tree }
 150     { "pair/f" { $maybe pair } }
 151 }
 152 { $description "Returns a key-value mapping associated with the last (highest) key in this tree, or " { $link f } " if the tree is empty." } ;
 153
 154 HELP: last-key
 155 { $values
 156     { "tree" tree }
 157     { "key/f" { $maybe "a key" } }
 158 }
 159 { $description "Returns the last (highest) key in this tree, or " { $link f } " if the tree is empty." } ;
 160
 161 HELP: first-entry
 162 { $values
 163     { "tree" tree }
 164     { "pair/f" { $maybe pair } }
 165 }
 166 { $description "Returns a key-value mapping associated with the first (lowest) key in this tree, or " { $link f } " if the tree is empty." } ;
 167
 168 HELP: first-key
 169 { $values
 170     { "tree" tree }
 171     { "key/f" { $maybe pair } }
 172 }
 173 { $description "Returns the first (lowest) key in this tree, or " { $link f } " if the tree is empty." } ;
 174
 175 { first-key first-entry last-key last-entry } related-words
 176
 177 HELP: pop-tree-left
 178 { $values
 179     { "tree" tree }
 180     { "node/f" { $maybe pair } }
 181 }
 182 { $description "Removes and returns a key-value mapping associated with the lowest key in this map, or " { $link f } " if the map is empty." } ;
 183
 184 HELP: pop-tree-right
 185 { $values
 186     { "tree" tree }
 187     { "node/f" { $maybe pair } }
 188 }
 189 { $description "Removes and returns a key-value mapping associated with the highest key in this map, or " { $link f } " if the map is empty." } ;
 190
 191 { pop-tree-left pop-tree-right } related-words
 192
 193 HELP: slurp-tree-left
 194 { $values
 195     { "tree" tree } { "quot" { $quotation ( ... entry -- ... ) } }
 196 }
 197 { $description "Removes entries from a tree from the left (lowest key) and processes them with the quotation until the tree is empty." } ;
 198
 199 HELP: slurp-tree-right
 200 { $values
 201     { "tree" tree } { "quot" { $quotation ( ... entry -- ... ) } }
 202 }
 203 { $description "Removes entries from a tree from the right (highest key) and processes them with the quotation until the tree is empty." } ;
 204
 205 { slurp-tree-left slurp-tree-right } related-words
 206
 207 ARTICLE: "trees" "Binary search trees"
 208 "The " { $vocab-link "trees" } " vocabulary is a library for unbalanced binary search trees. A " { $link tree } " is not intended to be used directly in most situations but rather as a base class for new trees, because performance can degrade to linear time storage/retrieval by the number of keys. These binary search trees conform to the assoc protocol."
 209 $nl
 210 "Constructing trees:"
 211 { $subsections
 212     <tree>
 213     >tree
 214     POSTPONE: TREE{
 215 }
 216 "Operations on trees: "
 217 { $subsections
 218     height
 219     first-entry first-key
 220     last-entry last-key
 221 }
 222 "Range operations on trees:"
 223 { $subsections
 224     headtree>alist[) headtree>alist[] tailtree>alist(] tailtree>alist[]
 225     subtree>alist() subtree>alist(] subtree>alist[) subtree>alist[]
 226 }
 227 "Navigation operations on trees:"
 228 { $subsections
 229     lower-key lower-entry higher-key higher-entry
 230     floor-key floor-entry ceiling-key ceiling-entry
 231 }
 232 "Pop/Slurp operations on trees:"
 233 { $subsections
 234     pop-tree-left pop-tree-right
 235     slurp-tree-left slurp-tree-right
 236 }
 237 ;
 238
 239 ABOUT: "trees"