(*
 Oukseh Lee

 Copyright(c) 2000-2004 KAIST/SNU Research On Program Analysis System
 (National Creative Research Initiative Center 1998-2003)
 http://ropas.snu.ac.kr/n

 All rights reserved. This file is distributed under the terms of
 an Open Source License.
*)

signature OrderedType = sig
type t
val compare: t -> t -> int
end

signature HashedType = sig
    type t
    val equal: t -> t -> bool
    val hash: t -> int
  end

signature SET =
sig
    type elt
    type t
    val empty: t
    val is_empty: t -> bool
    val mem: elt -> t -> bool
    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 min_elt: t -> elt
    val max_elt: t -> elt
    val choose: t -> elt
  end

functor MakeSet(A:OrderedType): SET where type elt = A.t = struct
   type elt = A.t
   type t = A.t list
   val empty = []
   fun is_empty x = true
   fun mem x y = true
   fun add x y = y
   fun singleton x = []
   fun remove _ y = y
   fun union x _ = x 
   val inter = union
   val diff = union
   fun compare x y = 1
   fun equal x y = true
   val subset = equal
   fun iter f x = ()
   fun fold f x y = y
   fun for_all f x = true
   val exists = for_all
   fun filter f x = x
   fun partition f x = (x,x)
   fun cardinal x = 1
   fun elements x = x
   fun min_elt [x] = x 
   val max_elt = min_elt
   val choose = min_elt 
end

   
signature MAP =
  sig
    type key
    type 'a t
    val empty: 'a t
    val add: key -> 'a -> 'a t -> 'a t
    val find: key -> 'a t -> 'a
    val remove: key -> 'a t -> 'a t
    val mem:  key -> 'a t -> bool
    val iter: (key -> 'a -> unit) -> 'a t -> unit
    val map: ('a -> 'b) -> 'a t -> 'b t
    val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
    val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  end

functor MakeMap(A:OrderedType): MAP where type key = A.t = struct
  type key = A.t
  type 'a t = 'a list
  val empty = []
  fun add x y z = z
  fun find x [y] = y 
  fun remove x y = y
  fun mem x y = true
  fun iter f x = ()
  fun map f [x] = [f x] 
  fun mapi f [x] = [] 
  fun fold f x y = y
end

signature HASH =
  sig
    type key
    type 'a t
    val create: int -> 'a t
    val clear: 'a t -> unit
    val copy : 'a t -> 'a t
    val add: 'a t -> key -> 'a -> unit
    val remove: 'a t -> key -> unit
    val find: 'a t -> key -> 'a
    val find_all: 'a t -> key -> 'a list
    val replace : 'a t -> key -> 'a -> unit
    val mem: 'a t -> key -> bool
    val iter: (key -> 'a -> unit) -> 'a t -> unit
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  end

functor MakeHash(H : HashedType) : HASH where type key = H.t = struct
  type key = H.t
  type 'a t = 'a list
  fun create x = []
  fun clear x = ()
  fun copy x = x
  fun add x y z = ()
  val replace = add
  fun remove x y = ()
  fun find [x] _ = x 
  fun find_all x y = [find x y]
  fun mem x y = true
  fun iter f x = ()
  fun fold f x y = y
end