Return to intmap.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / src / util

Annotation of researchv10no/cmd/sml/src/util/intmap.sml, revision 1.1.1.1

1.1       root        1: (* Copyright 1989 by AT&T Bell Laboratories *)
                      2: structure Intmap : INTMAP =
                      3: struct
                      4:   datatype 'a bucket = NIL | B of (int * 'a * 'a bucket)
                      5:   datatype 'a intmap =
                      6:     H of {table: 'a bucket array ref,elems: int ref,exn: exn,name: string option}
                      7:   fun bucketapp f =
                      8:       let fun loop NIL = ()
                      9:            | loop(B(i,j,r)) = (f(i,j); loop r)
                     10:       in loop
                     11:       end
                     12:   fun namednew(name, size, exn) =
                     13:       H {table=ref(array(size,NIL)),elems=ref 0,exn=exn,name=SOME name}
                     14:   fun new(size, exn) =
                     15:       H {table=ref(array(size,NIL)),elems=ref 0,exn=exn,name=NONE}
                     16:   fun map (H{table,exn,...}) =
                     17:       (fn i => let fun find NIL = raise exn
                     18:                     | find(B(i',j,r)) = if i=i' then j else find r
                     19:                   val ref a = table
                     20:               in find(a sub Bits.andb(i,(Array.length a)-1))
                     21:               end)
                     22:   fun rem (H{table=ref a,elems,...}) i =
                     23:       let fun f(B(i',j,r)) = if i=i' then (dec elems; r) else B(i',j,f r)
                     24:            | f x = x
                     25:          val index = Bits.andb(i,(Array.length a)-1)
                     26:       in update(a, index, f(a sub index))
                     27:       end
                     28:   fun app f (H{table=ref a,...}) =
                     29:       let fun zap 0 = ()
                     30:            | zap n = let val m = n-1 in bucketapp f (a sub m); zap m end
                     31:       in  zap(Array.length a)
                     32:       end
                     33:   fun add (m as H{table as ref a, elems, name, ...}) (v as (i,j)) =
                     34:     let val size = Array.length a
                     35:     in if !elems <> size
                     36:        then let val index = Bits.andb(i, size-1)
                     37:                fun f(B(i',j',r)) = if i=i' then B(i,j,r) else B(i',j',f r)
                     38:                  | f x = (inc elems; B(i,j,x))
                     39:            in update(a,index,f(a sub index))
                     40:            end
                     41:        else let val newsize = size+size
                     42:                val newsize1 = newsize-1
                     43:                val new = array(newsize,NIL)
                     44:                fun bucket n =
                     45:                    let fun add'(a,b,B(i,j,r)) =
                     46:                            if Bits.andb(i,newsize1) = n
                     47:                            then add'(B(i,j,a),b,r)
                     48:                            else add'(a,B(i,j,b),r)
                     49:                          | add'(a,b,NIL) = 
                     50:                            (update(new,n,a);
                     51:                             update(new,n+size,b);
                     52:                             bucket(n+1))
                     53:                    in add'(NIL,NIL,a sub n)
                     54:                    end
                     55:            in (case name of
                     56:                  NONE => ()
                     57:                | SOME name =>
                     58:                  (print("\nIncreasing size of intmap " ^ name ^ " to: ");
                     59:                   print newsize; print "\n"));
                     60:               bucket 0 handle Subscript => ();
                     61:               table := new;
                     62:               add m v
                     63:            end
                     64:     end
                     65:   fun intMapToList(H{table,...})=
                     66:      let val a = !table;
                     67:         val last = Array.length a - 1
                     68:          fun loop (0, NIL, acc) = acc
                     69:          |   loop (n, B(i,j,r), acc) = loop(n, r, (i,j)::acc)
                     70:          |   loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
                     71:       in loop(last,a sub last,[])
                     72:      end
                     73: end

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