1(* ========================================================================= *)
2(* mlibPatricia: Maps over integers implemented as mlibPatricia trees.               *)
3(* Copyright (c) 2000 Jean-Christophe Filliatre, 2001 Michael Norrish        *)
4(*                                                                           *)
5(* This software is free software; you can redistribute it and/or            *)
6(* modify it under the terms of the GNU Library General Public               *)
7(* License version 2, as published by the Free Software Foundation.          *)
8(*                                                                           *)
9(* This software is distributed in the hope that it will be useful,          *)
10(* but WITHOUT ANY WARRANTY; without even the implied warranty of            *)
11(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                      *)
12(* ========================================================================= *)
13
14signature mlibPatricia =
15sig
16
17type 'a t
18
19type key = int
20exception NotFound
21
22val empty   : 'a t
23val add     : key -> 'a -> 'a t -> 'a t
24val addf    : ('a -> 'a) -> key -> 'a -> 'a t -> 'a t
25val find    : key -> 'a t -> 'a
26val remove  : key -> 'a t -> 'a t
27val mem     : key -> 'a t -> bool
28val app     : (key * 'a -> unit) -> 'a t -> unit
29val map     : ('a -> 'b) -> 'a t -> 'b t
30val mapi    : (key -> 'a -> 'b) -> 'a t -> 'b t
31val fold    : (key * 'a * 'b -> 'b) -> 'b -> 'a t -> 'b
32val getItem : 'a t -> ((key * 'a) * 'a t) option
33val size    : 'a t -> int
34
35end
36