(* 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
;;