interval-maps:interval-values word, and more docs for interval-maps

diff --git a/basis/interval-maps/interval-maps-docs.factor b/basis/interval-maps/interval-maps-docs.factor
index de184585462f553fcf8ce2be277a8dcf751d3ab5..0d5e471bffd8c48620a57b9115ca1f0ebd61807e 100644 (file)
--- a/basis/interval-maps/interval-maps-docs.factor
+++ b/basis/interval-maps/interval-maps-docs.factor
@@ -1,22 +1,32 @@
-USING: help.markup help.syntax ;\r
+! Copyright (C) 2008, 2009 Daniel Ehrenberg.\r
+! See http://factorcode.org/license.txt for BSD license.\r
+USING: help.markup help.syntax assocs kernel sequences ;\r
 IN: interval-maps\r
 \r
 HELP: interval-at*\r
-{ $values { "key" "an object" } { "map" "an interval map" } { "value" "the value for the key, or f" } { "?" "whether the key is present" } }\r
+{ $values { "key" object } { "map" interval-map } { "value" "the value for the key, or f" } { "?" "whether the key is present" } }\r
 { $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
 \r
 HELP: interval-at\r
-{ $values { "key" "an object" } { "map" "an interval map" } { "value" "the value for the key, or f" } }\r
+{ $values { "key" object } { "map" interval-map } { "value" "the value for the key, or f" } }\r
 { $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
 \r
 HELP: interval-key?\r
-{ $values { "key" "an object" } { "map" "an interval map" } { "?" "a boolean" } }\r
+{ $values { "key" object } { "map" interval-map } { "?" "a boolean" } }\r
 { $description "Tests whether an object is in an interval in the interval map, returning t if the object is present." } ;\r
 \r
 HELP: <interval-map>\r
-{ $values { "specification" "an assoc" } { "map" "an interval map" } }\r
+{ $values { "specification" assoc } { "map" interval-map } }\r
 { $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
 \r
+HELP: interval-values\r
+{ $values { "map" interval-map } { "values" sequence } }\r
+{ $description "Constructs a list of all of the values that interval map keys are associated with. This list may contain duplicates." } ;\r
+\r
+HELP: coalesce\r
+{ $values { "alist" "an association list with integer keys" } { "specification" { "array of the format used by " { $link <interval-map> } } } }\r
+{ $description "Finds ranges used in the given alist, coalescing them into a single range." } ;\r
+\r
 ARTICLE: "interval-maps" "Interval maps"\r
 "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
 $nl\r
@@ -24,7 +34,9 @@ $nl
 { $subsection interval-at* }\r
 { $subsection interval-at }\r
 { $subsection interval-key? }\r
+{ $subsection interval-values }\r
 "Use the following to construct interval maps"\r
-{ $subsection <interval-map> } ;\r
+{ $subsection <interval-map> }\r
+{ $subsection coalesce } ;\r
 \r
 ABOUT: "interval-maps"\r

diff --git a/basis/interval-maps/interval-maps.factor b/basis/interval-maps/interval-maps.factor
index 63a5740845ef03117df61006a834c27b2f26a40e..22283deecb5971a7c0a9caa3c2ac89c076f7def0 100644 (file)
--- a/basis/interval-maps/interval-maps.factor
+++ b/basis/interval-maps/interval-maps.factor
@@ -8,17 +8,21 @@ TUPLE: interval-map array ;
 \r
 <PRIVATE\r
 \r
+ALIAS: start first\r
+ALIAS: end second\r
+ALIAS: value third\r
+\r
 : find-interval ( key interval-map -- interval-node )\r
-    [ first <=> ] with search nip ;\r
+    array>> [ start <=> ] with search nip ;\r
 \r
 : interval-contains? ( key interval-node -- ? )\r
-    first2 between? ;\r
+    [ start ] [ end ] bi between? ;\r
 \r
 : all-intervals ( sequence -- intervals )\r
     [ [ dup number? [ dup 2array ] when ] dip ] { } assoc-map-as ;\r
 \r
 : disjoint? ( node1 node2 -- ? )\r
-    [ second ] [ first ] bi* < ;\r
+    [ end ] [ start ] bi* < ;\r
 \r
 : ensure-disjoint ( intervals -- intervals )\r
     dup [ disjoint? ] monotonic?\r
@@ -30,14 +34,17 @@ TUPLE: interval-map array ;
 PRIVATE>\r
 \r
 : interval-at* ( key map -- value ? )\r
-    [ drop ] [ array>> find-interval ] 2bi\r
+    [ drop ] [ find-interval ] 2bi\r
     [ nip ] [ interval-contains? ] 2bi\r
-    [ third t ] [ drop f f ] if ;\r
+    [ value t ] [ drop f f ] if ;\r
 \r
 : interval-at ( key map -- value ) interval-at* drop ;\r
 \r
 : interval-key? ( key map -- ? ) interval-at* nip ;\r
 \r
+: interval-values ( map -- values )\r
+    array>> [ value ] map ;\r
+\r
 : <interval-map> ( specification -- map )\r
     all-intervals [ [ first second ] compare ] sort\r
     >intervals ensure-disjoint interval-map boa ;\r