home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / awk / stringmap.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  1.7 KB  |  66 lines  |  [TEXT/R*ch]
  1. (* stringmap.sml *)
  2.  
  3. signature STRINGMAP =
  4.   sig type 'a stringmap
  5.       exception Stringmap
  6.       val new : unit -> '1a stringmap
  7.       val add : 'a stringmap -> string * 'a -> unit
  8.       val remove : 'a stringmap -> string -> unit
  9.       val map : 'a stringmap -> string -> 'a
  10.       val app : (string * 'a -> unit) -> 'a stringmap -> unit
  11.   end
  12.  
  13. structure Stringmap : STRINGMAP =
  14. struct
  15.   open Array infix 9 sub
  16.  
  17.   type 'a stringmap = (string * 'a) list array
  18.   exception Stringmap
  19.   val hashFactor = 5
  20.   and tableSize = 211
  21.  
  22.   (* a string hashing function
  23.      returns a number between 0 and tableSize-1 *)
  24.   fun hash(str: string) : int =
  25.       let val i = ref 0
  26.       and n = ref 0
  27.       and nchars = String.length str
  28.        in while !i < nchars do
  29.           (n := (hashFactor * !n + ordof(str, !i)) mod tableSize;
  30.            i := !i + 1);
  31.       !n
  32.       end
  33.  
  34.   (* create a new stringmap *)
  35.   fun new (): '1a stringmap = array(tableSize,nil)
  36.  
  37.   (* add a mapping pair s +-> x to the stringmap a *)
  38.   fun add a (s,x) = 
  39.     let val index = hash s
  40.      in update(a,index,(s,x)::(a sub index))
  41.     end
  42.  
  43.   (* apply the stringmap a to the index string s *)
  44.   fun map a s = 
  45.     let fun find ((s',x)::r) = if s=s' then x else find r
  46.       | find nil = raise Stringmap
  47.      in find (a sub (hash s))
  48.     end
  49.  
  50.   (* remove all pairs mapping string s from stringmap a *)
  51.   fun remove a s = let fun f ((b as (s',j))::r) = 
  52.                 if s=s' then f r else b :: f r
  53.                   | f nil = nil
  54.             val index = hash s
  55.          in update(a,index, f(a sub index))
  56.         end
  57.  
  58.   (* apply a function f to all mapping pairs in stringmap a *)
  59.   fun app (f: string * 'a -> unit) a =
  60.       let fun zap 0 = ()
  61.         | zap n = let val m = n-1 in List.app f (a sub m); zap m end
  62.       in  zap tableSize
  63.       end
  64.  
  65. end  (* Stringmap *)
  66.