diff options
author | Emilio Jesus Gallego Arias <e+git@x80.org> | 2017-12-15 18:51:45 +0100 |
---|---|---|
committer | Emilio Jesus Gallego Arias <e+git@x80.org> | 2017-12-23 19:20:30 +0100 |
commit | 5ffa147bd2fe548df3ac9053fe497d0871a5f6df (patch) | |
tree | cc62882184c34e33e2995a5a4ff4ebfcbd0defe0 /clib/segmenttree.mli | |
parent | dea75d74c222c25f6aa6c38506ac7a51b339e9c6 (diff) |
[lib] Split auxiliary libraries into Coq-specific and general.
Up to this point the `lib` directory contained two different library
archives, `clib.cma` and `lib.cma`, which a rough splitting between
Coq-specific libraries and general-purpose ones.
We know split the directory in two, as to make the distinction clear:
- `clib`: contains libraries that are not Coq specific and implement
common data structures and programming patterns. These libraries
could be eventually replace with external dependencies and the rest
of the code base wouldn't notice much.
- `lib`: contains Coq-specific common libraries in widespread use
along the codebase, but that are not considered part of other
components. Examples are printing, error handling, or flags.
In some cases we have coupling due to utility files depending on Coq
specific flags, however this commit doesn't modify any files, but only
moves them around, further cleanup is welcome, as indeed a few files
in `lib` should likely be placed in `clib`.
Also note that `Deque` is not used ATM.
Diffstat (limited to 'clib/segmenttree.mli')
-rw-r--r-- | clib/segmenttree.mli | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/clib/segmenttree.mli b/clib/segmenttree.mli new file mode 100644 index 000000000..e274a6fdc --- /dev/null +++ b/clib/segmenttree.mli @@ -0,0 +1,28 @@ +(************************************************************************) +(* v * The Coq Proof Assistant / The Coq Development Team *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2017 *) +(* \VV/ **************************************************************) +(* // * This file is distributed under the terms of the *) +(* * GNU Lesser General Public License Version 2.1 *) +(************************************************************************) + +(** 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 + + |