basis/interval-maps/interval-maps-docs.factor

   1 ! Copyright (C) 2008, 2009 Daniel Ehrenberg.\r
   2 ! See http://factorcode.org/license.txt for BSD license.\r
   3 USING: assocs help.markup help.syntax kernel sequences ;\r
   4 IN: interval-maps\r
   5 \r
   6 HELP: interval-at*\r
   7 { $values { "key" object } { "map" interval-map } { "value" "the value for the key, or f" } { "?" "whether the key is present" } }\r
   8 { $description "Looks up a key in an interval map, returning the corresponding value if the item is in an interval in the map, and a boolean flag. The operation takes O(log n) time." } ;\r
   9 \r
  10 HELP: interval-at\r
  11 { $values { "key" object } { "map" interval-map } { "value" "the value for the key, or f" } }\r
  12 { $description "Looks up a key in an interval map, returning the value of the corresponding interval, or f if the interval is not present in the map." } ;\r
  13 \r
  14 HELP: interval-key?\r
  15 { $values { "key" object } { "map" interval-map } { "?" boolean } }\r
  16 { $description "Tests whether an object is in an interval in the interval map, returning t if the object is present." } ;\r
  17 \r
  18 HELP: <interval-map>\r
  19 { $values { "specification" assoc } { "map" interval-map } }\r
  20 { $description "From a specification, produce an interval tree. The specification is an assoc where the keys are intervals, or pairs of numbers to represent intervals, or individual numbers to represent singleton intervals. The values are the values int he interval map. Construction time is O(n log n)." } ;\r
  21 \r
  22 HELP: interval-values\r
  23 { $values { "map" interval-map } { "values" sequence } }\r
  24 { $description "Constructs a list of all of the values that interval map keys are associated with. This list may contain duplicates." } ;\r
  25 \r
  26 HELP: coalesce\r
  27 { $values { "alist" "an association list with integer keys" } { "specification" { "array of the format used by " { $link <interval-map> } } } }\r
  28 { $description "Finds ranges used in the given alist, coalescing them into a single range." } ;\r
  29 \r
  30 ARTICLE: "interval-maps" "Interval maps"\r
  31 "The " { $vocab-link "interval-maps" } " vocabulary implements a data structure, similar to assocs, where a set of closed intervals of keys are associated with values. As such, interval maps do not conform to the assoc protocol, because intervals of floats, for example, can be used, and it is impossible to get a list of keys in between."\r
  32 $nl\r
  33 "The following operations are used to query interval maps:"\r
  34 { $subsections\r
  35     interval-at*\r
  36     interval-at\r
  37     interval-key?\r
  38     interval-values\r
  39 }\r
  40 "Use the following to construct interval maps"\r
  41 { $subsections\r
  42     <interval-map>\r
  43     coalesce\r
  44 } ;\r
  45 \r
  46 ABOUT: "interval-maps"\r