Source file binary_searchable_intf.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
(** Module types for a [binary_search] function for a sequence, and functors for building
    [binary_search] functions. *)

open! Import

(** An [Indexable] type is a finite sequence of elements indexed by consecutive integers
    [0] ... [length t - 1].  [get] and [length] must be O(1) for the resulting
    [binary_search] to be lg(n). *)
module type Indexable = sig
  type elt
  type t

  val get : t -> int -> elt
  val length : t -> int
end

module type Indexable1 = sig
  type 'a t

  val get    : 'a t -> int -> 'a
  val length : _ t -> int
end

type ('t, 'elt, 'key) binary_search =
  ?pos:int
  -> ?len:int
  -> 't
  -> compare:('elt -> 'key -> int)
  -> [ `Last_strictly_less_than         (** {v | < elt X |                       v} *)
     | `Last_less_than_or_equal_to      (** {v |      <= elt       X |           v} *)
     | `Last_equal_to                   (** {v           |   = elt X |           v} *)
     | `First_equal_to                  (** {v           | X = elt   |           v} *)
     | `First_greater_than_or_equal_to  (** {v           | X       >= elt      | v} *)
     | `First_strictly_greater_than     (** {v                       | X > elt | v} *)
     ]
  -> 'key
  -> int option

type ('t, 'elt) binary_search_segmented =
  ?pos:int
  -> ?len:int
  -> 't
  -> segment_of:('elt -> [ `Left | `Right ])
  -> [ `Last_on_left | `First_on_right ]
  -> int option

module type S = sig
  type elt
  type t

  (** See [Binary_search.binary_search] in binary_search.ml *)
  val binary_search : (t, elt, 'key) binary_search

  (** See [Binary_search.binary_search_segmented] in binary_search.ml *)
  val binary_search_segmented : (t, elt) binary_search_segmented
end

module type S1 = sig
  type 'a t

  val binary_search           : ('a t, 'a, 'key) binary_search
  val binary_search_segmented : ('a t, 'a) binary_search_segmented
end

module type Binary_searchable = sig
  module type S          = S
  module type S1         = S1
  module type Indexable  = Indexable
  module type Indexable1 = Indexable1

  type nonrec ('t, 'elt, 'key) binary_search = ('t, 'elt, 'key) binary_search
  type nonrec ('t, 'elt) binary_search_segmented = ('t, 'elt) binary_search_segmented

  module Make  (T : Indexable)  : S  with type    t :=    T.t with type elt := T.elt
  module Make1 (T : Indexable1) : S1 with type 'a t := 'a T.t
end