Source file `idxset.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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
(**************************************************************************)
(*                                                                        *)
(*  SPDX-License-Identifier LGPL-2.1                                      *)
(*  Copyright (C)                                                         *)
(*  CEA (Commissariat à l'énergie atomique et aux énergies alternatives)  *)
(*                                                                        *)
(**************************************************************************)

module type S =
sig
  type elt
  type t
  val empty : t
  val is_empty : t -> bool
  val mem : elt -> t -> bool
  val find : elt -> t -> elt
  val add : elt -> t -> t
  val singleton : elt -> t
  val remove : elt -> t -> t
  val union : t -> t -> t
  val inter : t -> t -> t
  val diff : t -> t -> t
  val compare : t -> t -> int
  val equal : t -> t -> bool
  val subset : t -> t -> bool
  val iter : (elt -> unit) -> t -> unit
  val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  val for_all : (elt -> bool) -> t -> bool
  val exists : (elt -> bool) -> t -> bool
  val filter : (elt -> bool) -> t -> t
  val partition : (elt -> bool) -> t -> t * t
  val cardinal : t -> int
  val elements : t -> elt list
  val map : (elt -> elt) -> t -> t
  val mapf : (elt -> elt option) -> t -> t
  val intersect : t -> t -> bool
end

module type IndexedElements =
sig
  type t
  val id : t -> int (* unique per t *)
end

module Make(E : IndexedElements) =
struct
  type t = E.t Intmap.t
  type elt = E.t
  let empty = Intmap.empty
  let singleton x = Intmap.singleton (E.id x) x

  (* good sharing *)
  let add x = Intmap.add (E.id x) x

  (* good sharing *)
  let remove x = Intmap.remove (E.id x)
  let is_empty = Intmap.is_empty
  let mem x m = Intmap.mem (E.id x) m
  let find x m = Intmap.find (E.id x) m
  let cardinal = Intmap.size
  let compare m1 m2 = Intmap.compare (fun _ _ -> 0) m1 m2
  let equal m1 m2 = Intmap.equal (fun _ _ -> true) m1 m2

  let _keep _ x _ = x
  let _keepq _ x _ = Some x
  let _same _ _ _ = true

  (* good sharing *)
  let union m1 m2 = Intmap.union _keep m1 m2

  (* good sharing *)
  let inter m1 m2 = Intmap.interq _keepq m1 m2

  (* good sharing *)
  let diff m1 m2 = Intmap.diffq _keepq m1 m2
  let subset m1 m2 = Intmap.subset _same m1 m2
  let intersect m1 m2 = Intmap.intersectf _same m1 m2

  (* increasing order on id *)
  let iter f m = Intmap.iteri (fun _i x -> f x) m

  (* increasing order on id *)
  let fold f m i = Intmap.foldi (fun _i x e -> f x e) m i

  (* good sharing *)
  let filter f m = Intmap.filter (fun _i x -> f x) m

  (* good sharing *)
  let partition f m = Intmap.partition (fun _i x -> f x) m

  let for_all f m = Intmap.for_all (fun _i x -> f x) m
  let exists f m = Intmap.exists (fun _i x -> f x) m

  (* increasing order on id *)
  let elements m = Intmap.mapl (fun _i x -> x) m

  (* good sharing *)
  let mapf f m = Intmap.mapq (fun _i x -> f x) m

  (* good sharing *)
  let map f m = Intmap.mapq (fun _i x -> Some (f x)) m
end