Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/library/dynamic-bitset.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/dynamic-bitset.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/library/dynamic-bitset.sml

1 : monnier 245 structure DynamicBitSet :> BITSET =
2 :     struct
3 :    
4 :     structure A = Word8Array
5 :     structure W = Word8
6 :     open A
7 :    
8 :     infix << >> & ||
9 :     infix sub
10 :    
11 :     type bitset = array ref
12 :    
13 :     val word = Word.fromInt
14 :     val int = Word.toInt
15 :     val op & = Word.andb
16 :     val op >> = Word.>>
17 :     val op << = W.<<
18 :    
19 :     fun create n = ref(array((n+7)div 8, 0wx0))
20 :    
21 :     fun size a = length(! a) * 8
22 :    
23 :     fun grow (r as ref a, i) =
24 :     let val new_size = Int.max(length a * 2, i)
25 :     val new_array = array(new_size, 0wx0)
26 :     val _ = copy { src = a, si = 0, dst = new_array, di = 0,
27 :     len = NONE }
28 :     in r := new_array
29 :     end
30 :    
31 :     fun set (r as ref a, i) =
32 :     let val byte = int((word i) >> 0w3)
33 :     val mask = W.<< (0w1, (word i) & 0w7)
34 :     in update(a, byte, W.orb(a sub byte, mask)) end
35 :     handle Subscript => (grow (r, i+1); set(r,i))
36 :    
37 :     fun reset (r as ref a, i) =
38 :     let val byte = int((word i) >> 0w3)
39 :     val mask = W.notb(W.<< (0w1, (word i) & 0w7))
40 :     in update(a, byte, W.andb(a sub byte, mask)) end
41 :     handle Subscript => ()
42 :    
43 :     fun clear (ref a) = modify (fn _ => 0wx0) a
44 :    
45 :     fun negate (ref a) = ref(tabulate (length a, fn i => W.notb(a sub i)))
46 :    
47 :     fun union (ref a, ref b) =
48 :     let val m = Int.max(length a, length b)
49 :     val n = Int.min(length a, length b)
50 :     val c = array(m, 0wx0)
51 :     fun f ~1 = ()
52 :     | f i = update(c, i, W.orb(a sub i, b sub i))
53 :     in f n;
54 :     copy { src = if length a > length b then a else b,
55 :     si = n, dst = c, di = n, len = NONE };
56 :     ref c
57 :     end
58 :    
59 :     fun intersect (ref a, ref b) =
60 :     let val n = Int.min(length a, length b)
61 :     val c = array(n, 0wx0)
62 :     fun f ~1 = ()
63 :     | f i = update(c, i, W.andb(a sub i, b sub i))
64 :     in f n;
65 :     ref c
66 :     end
67 :    
68 :     fun diff (ref a, ref b) =
69 :     let val m = length a
70 :     val c = array(m, 0wx0)
71 :     fun f ~1 = ()
72 :     | f i = update(c, i, W.andb(a sub i, W.notb(b sub i)))
73 :     in f m; ref c
74 :     end
75 :    
76 :     fun unionWith (r as ref a, ref b) =
77 :     (if length b > length a then grow(r, length b) else ();
78 :     modifyi (fn (i,x) => W.orb(x,b sub i)) (a, 0, NONE))
79 :    
80 :     fun intersectWith (ref a, ref b) =
81 :     modifyi (fn (i,x) => W.andb(x,b sub i)) (a, 0, NONE)
82 :    
83 :     fun diffWith (ref a, ref b) =
84 :     modifyi (fn (i,x) => W.andb(x,W.notb(b sub i))) (a, 0, NONE)
85 :    
86 :     fun complement (ref a) = modify W.notb a
87 :    
88 :     fun copy (ref a) = ref(tabulate (length a, fn i => a sub i))
89 :    
90 :     fun toString (ref a) =
91 :     let fun f i = if i < length a then W.toString(a sub i)::f(i+1) else []
92 :     val s = String.concat(f 0)
93 :     in "[" ^ s ^ "]" end
94 :    
95 :     fun contains (r as ref a, i) =
96 :     let val byte = int((word i) >> 0w3)
97 :     val mask = W.<<(0w1, (word i) & 0w7)
98 :     in W.andb(A.sub(a, byte), mask) <> 0wx0 end
99 :     handle Subscript => false
100 :    
101 :     fun markAndTest (r as ref a, i) =
102 :     let val byte = int((word i) >> 0w3)
103 :     val mask = W.<<(0w1, (word i) & 0w7)
104 :     val word = A.sub(a,byte)
105 :     in if W.andb(word, mask) <> 0wx0 then
106 :     true
107 :     else
108 :     (A.update(a, byte, W.orb(word, mask)); false)
109 :     end handle Subscript => (grow (r, i+1); markAndTest(r,i))
110 :    
111 :     fun unmarkAndTest (r as ref a, i) =
112 :     let val byte = int(word i >> 0w3)
113 :     val mask = W.<<(0w1, (word i) & 0w7)
114 :     val word = A.sub(a,byte)
115 :     in if W.andb(word, mask) <> 0wx0 then
116 :     (A.update(a, byte, W.andb(word,W.notb mask)); true)
117 :     else
118 :     false
119 :     end handle Subscript => false
120 :    
121 :     end
122 :    
123 :     (*
124 :     * $Log$
125 :     *)

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0