core/collections/hashtables.facts

   1 IN: hashtables
   2 USING: hashtables-internals help tools kernel prettyprint ;
   3
   4 HELP: hashtable
   5 { $description "The class of hashtables. See " { $link "syntax-hashtables" } " for syntax and " { $link "hashtables" } " for general information." } ;
   6
   7 HELP: hash@
   8 { $values { "key" "a key" } { "array" "the underlying array of a hashtable" } { "i" "the index to begin hashtable search" } }
   9 { $description "Computes the index to begin searching from the hashcode of the key. Always outputs an even value since keys are stored at even indices of the underlying array." } ;
  10
  11 HELP: probe
  12 { $values { "array" "the underlying array of a hashtable" } { "i" "a search index" } }
  13 { $description "Outputs the next hashtable search index." } ;
  14
  15 HELP: key@
  16 { $values { "key" "a key" } { "hash" "a hashtable" } { "i" "the index of the key, or -1 if it is not present" } }
  17 { $description "Searches the hashtable for the key using a linear probing strategy. Searches stop if either the key or an " { $link ((empty)) } " sentinel is found. Searches skip the " { $link ((tombstone)) } " sentinel." }
  18 { $see-also new-key@ } ;
  19
  20 HELP: new-key@
  21 { $values { "key" "a key" } { "hash" "a hashtable" } { "i" "the index where the key would be stored" } }
  22 { $description "Searches the hashtable for the key using a linear probing strategy. If the key is not present in the hashtable, outputs the index where it should be stored." }
  23 { $see-also new-key@ } ;
  24
  25 HELP: if-key
  26 { $values { "key" "a key" } { "hash" "a hashtable" } { "true" "a quotation to call if the key is found, with stack effect " { $snippet "( true: index key hash -- )" } } { "false" "a quotation to call if the key is not found" } }
  27 { $description "Searches the hashtable for the key, calling one of the two quotations depending on the outcome." } ;
  28
  29 HELP: nth-pair
  30 { $values { "n" "an index in the sequence" } { "seq" "a sequence" } { "key" "the first element of the pair" } { "value" "the second element of the pair" } }
  31 { $description "Fetches the elements with index " { $snippet "n" } " and " { $snippet "n+1" } ", respectively." }
  32 { $warning "This word is in the " { $vocab-link "hashtables-internals" } " vocabulary because it does not perform bounds checks." }
  33 { $see-also set-nth-pair } ;
  34
  35 HELP: set-nth-pair
  36 { $values { "value" "the second element of the pair" } { "key" "the first element of the pair" } { "n" "an index in the sequence" } { "seq" "a sequence" } }
  37 { $description "Stores a pair of values into the elements with index " { $snippet "n" } " and " { $snippet "n+1" } ", respectively." }
  38 { $warning "This word is in the " { $vocab-link "hashtables-internals" } " vocabulary because it does not perform bounds checks." }
  39 { $side-effects "seq" }
  40 { $see-also nth-pair } ;
  41
  42 HELP: each-pair
  43 { $values { "array" "an array of pairs" } { "quot" "a quotation with stack effect " { $snippet "( key value -- )" } } }
  44 { $description "Applies a quotation to successive pairs in the array." }
  45 { $warning "This word is in the " { $vocab-link "hashtables-internals" } " vocabulary because passing an array of odd length can lead to memory corruption." } ;
  46
  47 HELP: all-pairs?
  48 { $values { "array" "an array of pairs" } { "quot" "a quotation with stack effect " { $snippet "( key value -- ? )" } } { "?" "conjunction of quotation outputs" } }
  49 { $description "Applies a predicate quotation to successive pairs in the array, and outputs true if the array is empty or if the quotation yields true for each pair." }
  50 { $warning "This word is in the " { $vocab-link "hashtables-internals" } " vocabulary because passing an array of odd length can lead to memory corruption." } ;
  51
  52 HELP: reset-hash
  53 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" "a hashtable" } }
  54 { $description "Resets the underlying array of the hashtable to a new array with the given capacity. Removes all entries from the hashtable." }
  55 { $side-effects "hash" } ;
  56
  57 HELP: hash-count+
  58 { $values { "hash" "a hashtable" } }
  59 { $description "Called to increment the hashtable size when a new entry is added with " { $link set-hash } }
  60 { $side-effects "hash" } ;
  61
  62 HELP: hash-deleted+
  63 { $values { "hash" "a hashtable" } }
  64 { $description "Called to increment the deleted entry counter when an entry is removed with " { $link remove-hash } }
  65 { $side-effects "hash" } ;
  66
  67 HELP: change-size
  68 { $values { "hash" "a hashtable" } { "old" "the key about to be overwritten" } }
  69 { $description "Called to update the hashtable counters when a new entry is added with " { $link set-hash } "." }
  70 { $side-effects "hash" } ;
  71
  72 HELP: (set-hash)
  73 { $values { "value" "a value" } { "key" "a key to add" } { "hash" "a hashtable" } }
  74 { $description "Stores the key/value pair into the hashtable. This word does not grow the hashtable if it exceeds capacity, therefore a hang can result. User code should use " { $link set-hash } " instead, which grows the hashtable if necessary." }
  75 { $side-effects "hash" } ;
  76
  77 HELP: grow-hash
  78 { $values { "hash" "a hashtable" } }
  79 { $description "Enlarges the capacity of a hashtable. User code does not need to call this word directly." }
  80 { $see-also (set-hash) ?grow-hash set-hash }
  81 { $side-effects "hash" } ;
  82
  83 HELP: ?grow-hash
  84 { $values { "hash" "a hashtable" } }
  85 { $description "Enlarges the capacity of a hashtable if it is almost full. User code does not need to call this word directly." }
  86 { $see-also (set-hash) grow-hash set-hash }
  87 { $side-effects "hash" } ;
  88
  89 HELP: <hashtable>
  90 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" "a new hashtable" } }
  91 { $description "Create a new hashtable capable of storing " { $snippet "n" } " key/value pairs before growing." }
  92 { $see-also clear-hash hash-size hash-empty? } ;
  93
  94 HELP: (hashtable) ( -- hash )
  95 { $values { "hash" "a new hashtable" } }
  96 { $description "Allocates a hashtable stub object without an underlying array. User code should call " { $link <hashtable> } " instead." } ;
  97
  98 HELP: associate
  99 { $values { "value" "a value" } { "key" "a key" } }
 100 { $description "Create a new hashtable holding one key/value pair." } ;
 101
 102 HELP: clear-hash
 103 { $values { "hash" "a hashtable" } }
 104 { $description "Removes all entries from the hashtable."  }
 105 { $see-also remove-hash }
 106 { $side-effects "hash" } ;
 107
 108 HELP: hash-size
 109 { $values { "hash" "a hashtable" } { "n" "a non-negative integer" } }
 110 { $description "Outputs the number of entries stored in the hashtable." } ;
 111
 112 HELP: hash-empty?
 113 { $values { "hash" "a hashtable" } { "?" "a boolean" } }
 114 { $description "Tests if the hashtable does not contain any entries." } ;
 115
 116 HELP: hash*
 117 { $values { "key" "an object to look up in the hashtable" } { "hash" "a hashtable" } { "value" "the value associated to the key, or " { $link f } " if the key is not present in the hashtable" } { "?" "a boolean indicating if the key was present" } }
 118 { $description "Looks up the value associated with a key. The boolean flag can decide between the case of a missing value, and a value of " { $link f } "." }
 119 { $see-also hash-member? hash ?hash ?hash* } ;
 120
 121 HELP: hash-member?
 122 { $values { "key" "an object to look up in the hashtable" } { "hash" "a hashtable" } }
 123 { $description "Tests if the hashtable contains a key/value pair whose key is equal to the given key." }
 124 { $see-also hash hash* ?hash ?hash* } ;
 125
 126 HELP: ?hash*
 127 { $values { "key" "an object to look up in the hashtable" } { "hash/f" "a hashtable or " { $link f } } }
 128 { $description "A variant of " { $link hash* } " overloaded to return " { $link f } " if the given mapping is " { $link f } "."  }
 129 { $see-also hash-member? hash hash* ?hash } ;
 130
 131 HELP: hash
 132 { $values { "key" "an object to look up in the hashtable" } { "hash" "a hashtable" } { "value" "the value associated to the key, or " { $link f } " if the key is not present in the hashtable" } }
 133 { $description "Looks up the value associated with a key. No distinction is made between a missing value and a value set to " { $link f } "." }
 134 { $see-also hash-member? hash* ?hash ?hash* } ;
 135
 136 HELP: ?hash
 137 { $values { "key" "an object to look up in the hashtable" } { "hash/f" "a hashtable or " { $link f } } { "value" "the value associated to the key, or " { $link f } " if the key is not present in the hashtable" } }
 138 { $description "A variant of " { $link hash } " overloaded to return " { $link f } " if the given mapping is " { $link f } "."  }
 139 { $see-also hash-member? hash hash* hash ?hash* } ;
 140
 141 HELP: remove-hash
 142 { $values { "key" "a key" } { "hash" "a hashtable" } }
 143 { $description "Removes an entry from the hashtable." }
 144 { $side-effects "hash" }
 145 { $see-also clear-hash } ;
 146
 147 HELP: remove-hash*
 148 { $values { "key" "a key" } { "hash" "a hashtable" } { "old" "the previous value or " { $link f } } }
 149 { $description "Stores an entry into the hashtable." }
 150 { $side-effects "hash" }
 151 { $see-also hash remove-hash } ;
 152
 153 HELP: set-hash
 154 { $values { "value" "a value" } { "key" "a key to add" } { "hash" "a hashtable" } }
 155 { $description "Stores the key/value pair into the hashtable." }
 156 { $side-effects "hash" } ;
 157
 158 HELP: hash-keys
 159 { $values { "hash" "a hashtable" } { "keys" "an array of keys" } }
 160 { $description "Outputs an array of all keys in the hashtable." }
 161 { $see-also hash-values hash>alist alist>hash } ;
 162
 163 HELP: hash-values
 164 { $values { "hash" "a hashtable" } { "values" "an array of values" } }
 165 { $description "Outputs an array of all values in the hashtable." }
 166 { $see-also hash-keys hash>alist alist>hash } ;
 167
 168 HELP: hash>alist
 169 { $values { "hash" "a hashtable" } { "alist" "an array of key/value pairs" } }
 170 { $description "Outputs an array of all key/value pairs in the hashtable. Each pair is itself a two-element array." }
 171 { $see-also hash-keys hash-values alist>hash } ;
 172
 173 HELP: alist>hash
 174 { $values { "alist" "a sequence of key/value pairs" } { "hash" "a hashtable" } }
 175 { $description "Constructs a hashtable from a sequence of key/value pairs, where each pair is a two-element sequence. In the case of duplicate keys, later pairs take precedence." }
 176 { $see-also hash-keys hash-values hash>alist } ;
 177
 178 HELP: hash-each
 179 { $values { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( key value -- )" } } }
 180 { $description "Applies a quotation to each key/value pair in the hashtable." } ;
 181
 182 HELP: hash-each-with
 183 { $values { "obj" "an object" } { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( obj key value -- )" } } }
 184 { $description "Variant of " { $link hash-each } " which pushes a retained object on each invocation of the quotation." } ;
 185
 186 HELP: hash-all?
 187 { $values { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( key value -- ? )" } } { "?" "a boolean" } }
 188 { $description "Applies a predicate quotation to each key/value pair in the hashtable. Outputs true if the hashtable is empty or the quotation yields true for each entry." } ;
 189
 190 HELP: hash-all-with?
 191 { $values { "obj" "an object" } { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( obj key value -- ? )" } } { "?" "a boolean" } }
 192 { $description "Variant of " { $link hash-all? } " which pushes a retained object on each invocation of the quotation." } ;
 193
 194 HELP: hash-subset
 195 { $values { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( key value -- ? )" } } { "subhash" "a new hashtable" } }
 196 { $description "Constructs a hashtable consisting of all key/value pairs for which the predicate quotation yields true." } ;
 197
 198 HELP: hash-subset-with
 199 { $values { "obj" "an object" } { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( obj key value -- ? )" } } { "subhash" "a new hashtable" } }
 200 { $description "Variant of " { $link hash-all? } " which pushes a retained object on each invocation of the quotation." } ;
 201
 202 HELP: subhash?
 203 { $values { "hash1" "a hashtable" } { "hash2" "a hashtable" } { "?" "a new hashtable" } }
 204 { $description "Tests if " { $snippet "hash2" } " contains all key/value pairs of " { $snippet "hash1" } "." } ;
 205
 206 HELP: hash-stack
 207 { $values { "key" "a key" } { "seq" "a sequence of hashtables" } { "value" "a value or " { $link f } } }
 208 { $description "Looks up the key in every hashtable in the sequence, search from back to front. If the key could not be found, outputs " { $link f } ". This word is used to implement abstractions such as nested scopes; if the sequence is a stack represented by a vector, then the most recently pushed hashtable -- the innermost scope -- will be searched first." } ;
 209
 210 HELP: hash-intersect
 211 { $values { "hash1" "a hashtable" } { "hash2" "a hashtable" } { "intersection" "a new hashtable" } }
 212 { $description "Constructs a hashstable consisting of all key/value pairs from " { $snippet "hash2" } " such that the key is also present in " { $snippet "hash1" } "." }
 213 { $notes "The values of the keys in " { $snippet "hash1" } " are disregarded, so this word is usually used for set-theoretic calculations where the hashtable in question either has dummy sentinels as values, or the values equal the keys." } ;
 214
 215 HELP: hash-diff
 216 { $values { "hash1" "a hashtable" } { "hash2" "a hashtable" } { "difference" "a new hashtable" } }
 217 { $description "Constructs a hashstable consisting of all key/value pairs from " { $snippet "hash2" } " such that the key is not present in " { $snippet "hash1" } "" }
 218 { $notes "The values of the keys in " { $snippet "hash1" } " are disregarded, so this word is usually used for set-theoretic calculations where the hashtable in question either has dummy sentinels as values, or the values equal the keys." } ;
 219
 220 HELP: hash-update
 221 { $values { "hash1" "a hashtable" } { "hash2" "a hashtable" } }
 222 { $description "Adds all key/value pairs from " { $snippet "hash2" } " to " { $snippet "hash1" } "." }
 223 { $side-effects "hash1" } ;
 224
 225 HELP: hash-union
 226 { $values { "hash1" "a hashtable" } { "hash2" "a hashtable" } { "union" "a new hashtable" } }
 227 { $description "Constructs a hashstable consisting of all key/value pairs from " { $snippet "hash1" } " and " { $snippet "hash2" } ", with entries from " { $snippet "hash2" } " taking precedence." }
 228 { $notes "The values of the keys in " { $snippet "hash1" } " are disregarded, so this word is usually used for set-theoretic calculations where the hashtable in question either has dummy sentinels as values, or the values equal the keys." } ;
 229
 230 HELP: remove-all
 231 { $values { "hash" "a hashtable" } { "seq" "a sequence" } { "subseq" "a new sequence" } }
 232 { $description "Constructs a sequence consisting of all elements from the sequence that appear as keys in the hashtable." }
 233 { $notes "The values of the keys in the hashtable are disregarded, so this word is usually used for set-theoretic calculations where the hashtable in question either has dummy sentinels as values, or the values equal the keys." } ;
 234
 235 HELP: cache
 236 { $values { "key" "a key" } { "hash" "a hashtable" } { "quot" "a quotation with stack effect " { $snippet "( key -- value )" } } { "value" "a previously-retained or freshly-computed value" } }
 237 { $description "If the key is present in the hashtable, outputs the associated value, otherwise calls the quotation to produce a value and stores the key/value pair into the hashtable." }
 238 { $side-effects "hash" } ;
 239
 240 HELP: map>hash
 241 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( key -- value )" } } { "hash" "a hashtable" } { "value" "a previously-retained or freshly-computed value" } }
 242 { $description "Applies the quotation to each element of the sequence to produce a value corresponding to each key, and constructs a new hashtable from these key/value pairs." } ;