1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
|
(* Copyright 1989 by AT&T Bell Laboratories *)
structure Intmap : INTMAP =
struct
open Array List
infix 9 sub
val wtoi = Word.toIntX
val itow = Word.fromInt
datatype 'a bucket = NIL | B of (int * 'a * 'a bucket)
datatype 'a intmap =
H of {table: 'a bucket array ref,elems: int ref,exn: exn,name: string option}
fun clear(H{table,elems,...}) =
if !elems > 0 then (table := array(32,NIL); elems := 0) else ()
fun bucketapp f =
let fun loop NIL = ()
| loop(B(i,j,r)) = (f(i,j); loop r)
in loop
end
fun roundsize size =
let fun f x = if x >= size then x else f (x*2)
in f 1
end
fun namednew(name, size, exn) =
H {table=ref(array(roundsize size,NIL)),elems=ref 0,exn=exn,name=SOME name}
fun new(size, exn) =
H {table=ref(array(roundsize size,NIL)),elems=ref 0,exn=exn,name=NONE}
val elems = fn (H{elems,...}) => !elems
fun index(a, i) = wtoi (Word.andb(itow i, itow(Array.length a - 1)))
fun map (H{table,exn,...}) =
(fn i => let fun find NIL = raise exn
| find(B(i',j,r)) = if i=i' then j else find r
val ref a = table
in find(a sub (index(a, i)))
end)
fun mapWithDefault (H{table,exn,...},default) =
(fn i => let fun find NIL = default
| find(B(i',j,r)) = if i=i' then j else find r
val ref a = table
in find(a sub (index(a, i)))
end)
fun mapInt (H{table,exn,...}) =
(fn i => let fun find NIL = i
| find(B(i',j,r)) = if i=i' then j else find r
val ref a = table
in find(a sub (index(a, i)))
end)
fun rmv (H{table=ref a,elems,...}) i =
let fun f(B(i',j,r)) = if i=i' then (elems := !elems-1; r) else B(i',j,f r)
| f x = x
val indx = index(a, i)
in update(a, indx, f(a sub indx))
end
fun app f (H{table=ref a,...}) =
let fun zap 0 = ()
| zap n = let val m = n-1 in bucketapp f (a sub m); zap m end
in zap(Array.length a)
end
fun add (m as H{table as ref a, elems, name, ...}) (v as (i,j)) =
let val size = Array.length a
in if !elems <> size
then let val index = wtoi (Word.andb(itow i, itow(size-1)))
fun f(B(i',j',r)) = if i=i' then B(i,j,r) else B(i',j',f r)
| f x = (elems := !elems+1; B(i,j,x))
in update(a,index,f(a sub index))
end
else let val newsize = size+size
val newsize1 = newsize-1
val new = array(newsize,NIL)
fun bucket n =
let fun add'(a,b,B(i,j,r)) =
if wtoi (Word.andb(itow i, itow newsize1)) = n
then add'(B(i,j,a),b,r)
else add'(a,B(i,j,b),r)
| add'(a,b,NIL) =
(update(new,n,a);
update(new,n+size,b);
bucket(n+1))
in add'(NIL,NIL,a sub n)
end
in
bucket 0 handle Subscript => ();
table := new;
add m v
end
end
fun intMapToList(H{table,...})=
let val a = !table;
val last = Array.length a - 1
fun loop (0, NIL, acc) = acc
| loop (n, B(i,j,r), acc) = loop(n, r, (i,j)::acc)
| loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
in loop(last,a sub last,[])
end
fun values(H{table,...})=
let val a = !table;
val last = Array.length a - 1
fun loop (0, NIL, acc) = acc
| loop (n, B(i,j,r), acc) = loop(n, r, j::acc)
| loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
in loop(last,a sub last,[])
end
fun keys(H{table,...})=
let val a = !table;
val last = Array.length a - 1
fun loop (0, NIL, acc) = acc
| loop (n, B(i,j,r), acc) = loop(n, r, i::acc)
| loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
in loop(last,a sub last,[])
end
fun copy(H{table=ref a,elems,exn,name}) =
let val a' = Array.array(Array.length a,NIL)
in Array.copy{di=0, dst=a', len=NONE, si=0, src=a};
H{table=ref a', elems=ref(!elems), exn=exn, name=name}
end
end
|