diff options
author | Benjamin Barenblat <bbaren@debian.org> | 2018-12-29 14:31:32 -0500 |
---|---|---|
committer | Benjamin Barenblat <bbaren@debian.org> | 2018-12-29 14:31:32 -0500 |
commit | 2708a015fcf65f72328be4296a00dd32b1f1c17a (patch) | |
tree | 696f9b5fb84817e1a5c8d9271976a92e25aef18a /clib/segmenttree.mli | |
parent | d7d80c5bea564b7cb0eadc33e9ee38c9d9de1cd8 (diff) | |
parent | 9043add656177eeac1491a73d2f3ab92bec0013c (diff) |
Updated version 8.8.2 from 'upstream/8.8.2'
with Debian dir a16bcf46abacaf1a684eda04f02555c984bf540d
Diffstat (limited to 'clib/segmenttree.mli')
-rw-r--r-- | clib/segmenttree.mli | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/clib/segmenttree.mli b/clib/segmenttree.mli new file mode 100644 index 00000000..63c968f5 --- /dev/null +++ b/clib/segmenttree.mli @@ -0,0 +1,30 @@ +(************************************************************************) +(* * The Coq Proof Assistant / The Coq Development Team *) +(* v * INRIA, CNRS and contributors - Copyright 1999-2018 *) +(* <O___,, * (see CREDITS file for the list of authors) *) +(* \VV/ **************************************************************) +(* // * This file is distributed under the terms of the *) +(* * GNU Lesser General Public License Version 2.1 *) +(* * (see LICENSE file for the text of the license) *) +(************************************************************************) + +(** 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 + + |