diff options
author | 2010-07-21 09:48:05 +0200 | |
---|---|---|
committer | 2010-07-21 09:48:05 +0200 | |
commit | bbb5e6eb84a46c7e8041e05ab0059994fa0b1a25 (patch) | |
tree | 7d2930678b27e520c9431739c3d1af9d6475ccd1 /lib/segmenttree.mli | |
parent | 7a998985060742038ba6d2664d159ff2dbcdec3d (diff) | |
parent | 5b7eafd0f00a16d78f99a27f5c7d5a0de77dc7e6 (diff) |
Merge branch 'experimental/upstream' into experimental/master
Diffstat (limited to 'lib/segmenttree.mli')
-rw-r--r-- | lib/segmenttree.mli | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/lib/segmenttree.mli b/lib/segmenttree.mli new file mode 100644 index 00000000..4aea13e9 --- /dev/null +++ b/lib/segmenttree.mli @@ -0,0 +1,20 @@ +(** This module is a very simple implementation of "segment trees". + + A segment tree of type ['a t] represents a mapping from a union of + disjoint segments to some values of type 'a. +*) + +(** A mapping from a union of disjoint segments to some values of type ['a]. *) +type 'a t + +(** [make [(i1, j1), v1; (i2, j2), v2; ...] creates a mapping that + associates to every integer [x] the value [v1] if [i1 <= x <= j1], + [v2] if [i2 <= x <= j2], and so one. + Precondition: the segments must be sorted. *) +val make : ((int * int) * 'a) list -> 'a t + +(** [lookup k t] looks for an image for key [k] in the interval tree [t]. + Raise [Not_found] if it fails. *) +val lookup : int -> 'a t -> 'a + + |