Return to stringmap.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / examples / awk

Annotation of researchv10no/cmd/sml/doc/examples/awk/stringmap.sml, revision 1.1.1.1

1.1       root        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 rem : '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:   type 'a stringmap = (string * 'a) list array
                     16:   exception Stringmap
                     17:   val hashFactor = 5
                     18:   and tableSize = 211
                     19: 
                     20:   (* a string hashing function
                     21:      returns a number between 0 and tableSize-1 *)
                     22:   fun hash(str: string) : int =
                     23:       let val i = ref 0
                     24:          and n = ref 0
                     25:          and nchars = String.length str
                     26:        in while !i < nchars do
                     27:              (n := (hashFactor * !n + ordof(str, !i)) mod tableSize;
                     28:               i := !i + 1);
                     29:          !n
                     30:       end
                     31: 
                     32:   (* create a new stringmap *)
                     33:   fun new (): '1a stringmap = array(tableSize,nil)
                     34: 
                     35:   (* add a mapping pair s +-> x to the stringmap a *)
                     36:   fun add a (s,x) = 
                     37:     let val index = hash s
                     38:      in update(a,index,(s,x)::(a sub index))
                     39:     end
                     40: 
                     41:   (* apply the stringmap a to the index string s *)
                     42:   fun map a s = 
                     43:     let fun find ((s',x)::r) = if s=s' then x else find r
                     44:          | find nil = raise Stringmap
                     45:      in find (a sub (hash s))
                     46:     end
                     47: 
                     48:   (* remove all pairs mapping string s from stringmap a *)
                     49:   fun rem a s = let fun f ((b as (s',j))::r) = 
                     50:                                if s=s' then f r else b :: f r
                     51:                      | f nil = nil
                     52:                    val index = hash s
                     53:                 in update(a,index, f(a sub index))
                     54:                end
                     55: 
                     56:   (* apply a function f to all mapping pairs in stringmap a *)
                     57:   fun app (f: string * 'a -> unit) a =
                     58:       let fun zap 0 = ()
                     59:            | zap n = let val m = n-1 in List.app f (a sub m); zap m end
                     60:       in  zap tableSize
                     61:       end
                     62: 
                     63: end  (* Stringmap *)

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.