basis/interval-sets/interval-sets-docs.factor

   1 ! Copyright (C) 2009 Daniel Ehrenberg.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: help.syntax help.markup math ;
   4 IN: interval-sets
   5
   6 ABOUT: "interval-sets"
   7
   8 ARTICLE: "interval-sets" "Interval sets"
   9 "The " { $vocab-link "interval-sets" } " vocabulary implements an efficient data structure for sets of positive, machine word-sized integers, specified by ranges. The space taken by the data structure is proportional to the number of intervals contained. Membership testing is O(log n), and creation is O(n log n), where n is the number of ranges. Boolean operations are O(n). Interval sets are immutable."
  10 { $subsection interval-set }
  11 { $subsection <interval-set> }
  12 { $subsection interval-in? }
  13 { $subsection <interval-not> }
  14 { $subsection <interval-and> }
  15 { $subsection <interval-or> } ;
  16
  17 HELP: interval-set
  18 { $class-description "The class of interval sets." }
  19 { $see-also "interval-sets" } ;
  20
  21 HELP: <interval-set>
  22 { $values { "specification" "a sequence of numbers and pairs of numbers" } { "interval-set" interval-set } }
  23 { $description "Creates an interval set based on the specification. Pairs of numbers are interpreted as intervals which include their endpoints, and individual numbers are interpreted to be in the set, in a singleton range." } ;
  24
  25 HELP: interval-in?
  26 { $values { "key" integer } { "set" interval-set } { "?" { { $link t } " or " { $link f } } } }
  27 { $description "Tests whether an integer is in an interval set. This takes O(log n) time for an interval map composed of n intervals." } ;
  28
  29 HELP: <interval-and>
  30 { $values { "set1" interval-set } { "set2" interval-set } { "set" interval-set } }
  31 { $description "Calculates the intersection of two interval sets. This takes O(n+m) time, where the input interval maps have n and m intervals in them." } ;
  32
  33 HELP: <interval-or>
  34 { $values { "set1" interval-set } { "set2" interval-set } { "set" interval-set } }
  35 { $description "Calculates the union of two interval sets. This takes O(n+m) time, where the input interval maps have n and m intervals in them." } ;
  36
  37 HELP: <interval-not>
  38 { $values { "set" interval-set } { "maximum" integer } { "set'" interval-set } }
  39 { $description "Calculates the complement of an interval set. Because interval sets are finite, this takes an argument for the maximum integer in the domain considered. This takes time proportional to the size of the input." } ;