ord_map.sig

signature ORDERED_MAP =
  sig

    type ord_key 

    type 'a map

    val empty : 'a map
	(* The empty map *)

    val isEmpty : 'a map -> bool
	(* Return true if and only if the map is empty *)

    val singleton : (ord_key * 'a) -> 'a map
	(* return the specified singleton map *)

    val insert  : 'a map * ord_key * 'a -> 'a map
    
    val insert' : ((ord_key * 'a) * 'a map) -> 'a map
	(* Insert an item. *)

    val find : 'a map * ord_key -> 'a option
	(* Look for an item, return NONE if the item doesn't exist *)

    val inDomain : ('a map * ord_key) -> bool
	(* return true, if the key is in the domain of the map *)

    val remove : 'a map * ord_key -> 'a map * 'a
	(* Remove an item, returning new map and value removed.
         * Raises LibBase.NotFound if not found.
	 *)

    val first : 'a map -> 'a option
    val firsti : 'a map -> (ord_key * 'a) option
	(* return the first item in the map (or NONE if it is empty) *)

    val numItems : 'a map ->  int
	(* Return the number of items in the map *)

    val listItems  : 'a map -> 'a list
    val listItemsi : 'a map -> (ord_key * 'a) list
	(* Return an ordered list of the items (and their keys) in the map. *)

    val listKeys : 'a map -> ord_key list
	(* return an ordered list of the keys in the map. *)

    val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order
	(* given an ordering on the map's range, return an ordering
	 * on the map.
	 *)

    val unionWith  : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
    val unionWithi : (ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
	(* return a map whose domain is the union of the domains of the two input
	 * maps, using the supplied function to define the map on elements that
	 * are in both domains.
	 *)

    val intersectWith  : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
    val intersectWithi : (ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
	(* return a map whose domain is the intersection of the domains of the
	 * two input maps, using the supplied function to define the range.
	 *)

    val app  : ('a -> unit) -> 'a map -> unit
    val appi : ((ord_key * 'a) -> unit) -> 'a map -> unit
	(* Apply a function to the entries of the map in map order. *)

    val map  : ('a -> 'b) -> 'a map -> 'b map
    val mapi : (ord_key * 'a -> 'b) -> 'a map -> 'b map
	(* Create a new map by applying a map function to the
         * name/value pairs in the map.
         *)

    val foldl  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
    val foldli : (ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
	(* Apply a folding function to the entries of the map
         * in increasing map order.
         *)

    val foldr  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
    val foldri : (ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
	(* Apply a folding function to the entries of the map
         * in decreasing map order.
         *)

    val filter  : ('a -> bool) -> 'a map -> 'a map
    val filteri : (ord_key * 'a -> bool) -> 'a map -> 'a map
	(* Filter out those elements of the map that do not satisfy the
	 * predicate.  The filtering is done in increasing map order.
	 *)

    val mapPartial  : ('a -> 'b option) -> 'a map -> 'b map
    val mapPartiali : (ord_key * 'a -> 'b option) -> 'a map -> 'b map
	(* map a partial function over the elements of a map in increasing
	 * map order.
	 *)

  end (* ORD_MAP *)