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     ! 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.