(* This file is part of our reusable OCaml BRICKS library
   Copyright (C) 2007  Jean-Vincent Loddo

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. *)


(** Very simple module implementing a polymorphic unbounded sets. An encapsulated ('a, unit) Hashtbl.t is used for quickly answering to the membership problem. *)


(** The default size of the hash used in the implementation *)

let default_size = 251;;


class ['a] hashset = fun ?(size=default_size) () ->

  object (self) 

  
  (** The state of the hashset. *)

  val current : ('a, unit) Hashtbl.t = (Hashtbl.create size)

  
  (** Answer (quickly!) to the question if x is a member of the set. *)

  method mem x = Hashtbl.mem current x

  
  (** Add the element to the set *)

  method add x = (Hashtbl.replace current x ()) 

  
  (** Remove the element from the set *)

  method remove x = (Hashtbl.remove current x) 

end;; (* class hashset *)


(* Functional interface. *)

(** The abstract type of an hashset. *)

type 'a t       = 'a hashset ;;
 
(** The hashset constructor. *)

let make ?(size=default_size) () : 'a t = new hashset ~size () ;;

(** The member predicate. *)

let mem (hs:'a t) (x:'a) = hs#mem x;;

(** Add a member to the hashset. *)

let add (hs:'a t) (x:'a) = hs#add x;;
 
(** Remove a member from the hashset. *)

let remove (hs:'a t) (x:'a) = hs#remove x;;
 
(** Make an hashset from a list. *)

let of_list (l:'a list) : 'a t = 
 let n = List.length l in 
 let size = if n<(default_size/2) then default_size else n*2 in
 let hs = make ~size () in 
 (List.iter (add hs) l); hs
;;

(* Support for uniq. *)
let rec uniq hs = function
 | []   -> []
 | x::l -> if (hs#mem x) then (uniq hs l) else ((hs#add x); (x::(uniq hs l)))   
;;

(** Exploit an hashset for implementing the uniq function over lists. *)

let uniq (l:'a list) : ('a list) =
 let n = List.length l in
 let hs = make ~size:(n*3) () in
 uniq hs l
;;