(******************************************************************************
 ** TABLE.sml
 ** sml
 **
 ** Guy Blelloch 
 ** The TABLE signature
 ******************************************************************************)

signature TABLE =
sig
    type index
    type 'a table

    exception NoEntry

    val empty  : 'a table
    val isEmpty : 'a table -> bool
    val size : 'a table -> int
    val elt    : 'a table -> index  -> 'a option
    val find   : index * 'a table  -> 'a option
    val insert : ((index * 'a) * 'a table) -> 'a table
    val delete : index * 'a table -> 'a table
    val deleteReturn : index * 'a table -> 'a table * 'a option
    val update : ('a option -> 'a option) -> index * 'a table -> 'a table
    val updateReturn : ('a option -> 'a option * 'b) -> 
	               index * 'a table -> 
                       'a table * 'b 

    val foldr    : ((    'a     * 'b) -> 'b) -> 'b -> 'a table -> 'b 
    val foldrIdx : (((index * 'a) * 'b) -> 'b) -> 'b -> 'a table -> 'b 
    val foldl    : ((    'a     * 'b) -> 'b) -> 'b -> 'a table -> 'b 
    val foldlIdx : (((index * 'a) * 'b) -> 'b) -> 'b -> 'a table -> 'b 
    val map      : (    'a     -> 'b) -> 'a table -> 'b table
    val mapIdx   : ((index * 'a) -> 'b) -> 'a table -> 'b table
    val filter   : (    'a     -> 'b option) -> 'a table -> 'b table
    val filterIdx: ((index * 'a) -> 'b option) -> 'a table -> 'b table

    val union        : ('a * 'a -> 'a option) -> 'a table * 'a table -> 'a table
    val unionIdx     : (index*'a*'a -> 'a option) -> 'a table * 'a table -> 'a table
    val intersect    : ('a * 'b -> 'c option) -> 'a table * 'b table -> 'c table
    val intersectIdx : (index*'a*'b -> 'c option) -> 'a table * 'b table -> 'c table
    val diff         : ('a * 'b -> 'a option) -> 'a table * 'b table -> 'a table
    val diffIdx      : (index*'a*'b -> 'a option) -> 'a table * 'b table -> 'a table

    val toList : 'a table -> (index*'a) list
    val fromList : (index*'a) list -> 'a table

end