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/int-set.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/int-set.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/library/int-set.sml

1 : monnier 411 (*
2 :     * A fixed capacity integer set datatype
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 245 signature INTSET =
8 :     sig
9 :    
10 :     type intset
11 :    
12 :     val intset : int -> intset
13 :     val contains : intset * int -> bool
14 :     val add : intset * int -> unit
15 :     val remove : intset * int -> unit
16 :     val clear : intset -> unit
17 :     val size : intset -> int
18 :     val capacity : intset -> int
19 :     val is_empty : intset -> bool
20 :     val app : (int -> unit) -> intset -> unit
21 :     val fold : (int * 'a -> 'a) -> 'a -> intset -> 'a
22 :     val toList : intset -> int list
23 :     val toString : intset -> string
24 :     val copy : intset -> intset
25 :     val + : intset * intset -> intset
26 :     val - : intset * intset -> intset
27 :     val * : intset * intset -> intset
28 :     val union : intset * intset -> unit
29 :     val diff : intset * intset -> unit
30 :    
31 :     end
32 :    
33 :     structure IntSet :> INTSET =
34 :     struct
35 :    
36 :     structure A = Array
37 :     datatype intset = SET of {stack : int A.array,
38 :     pos : int A.array,
39 :     count : int ref
40 :     }
41 :     fun intset n = SET{stack=A.array(n,0),pos=A.array(n,0),count=ref 0}
42 :     fun contains(SET{stack,pos,count},i) =
43 :     let val j = A.sub(pos,i)
44 :     in j < !count andalso A.sub(stack,j) = i end
45 :    
46 :     fun add(SET{stack,pos,count},i) =
47 :     let val j = A.sub(pos,i)
48 :     val n = !count
49 :     in if j < n andalso A.sub(stack,j) = i then ()
50 :     else (A.update(stack,n,i); A.update(pos,i,n); count := n + 1)
51 :     end
52 :     fun remove(SET{stack,pos,count},i) =
53 :     let val j = A.sub(pos,i)
54 :     val n = !count
55 :     val k = A.sub(stack,j)
56 :     in if j < n andalso i = k then
57 :     let val k' = A.sub(stack,n-1)
58 :     in A.update(stack,j,k');
59 :     A.update(pos,k',j);
60 :     count := n - 1
61 :     end
62 :     else ()
63 :     end
64 :    
65 :     fun clear(SET{count,...}) = count := 0
66 :     fun size(SET{count,...}) = !count
67 :     fun capacity(SET{stack,...}) = A.length stack
68 :     fun is_empty(SET{count,...}) = !count = 0
69 :     fun app f (SET{count,stack,...}) =
70 :     let fun g ~1 = ()
71 :     | g i = (f(A.sub(stack,i)); g(i-1))
72 :     in g(!count - 1) end
73 :     fun fold f x (SET{count,stack,...}) =
74 :     let fun g(~1,x) = x
75 :     | g(i,x) = g(i-1,f(A.sub(stack,i),x))
76 :     in g(!count - 1,x) end
77 :     fun toList set = fold op:: [] set
78 :     fun toString set =
79 :     String.concat(
80 :     "{"::fold (fn (i,[x]) => [Int.toString i,x]
81 :     | (i,s) => Int.toString i::","::s) ["}"] set)
82 :    
83 :     fun copy (SET{stack,pos,count}) =
84 :     let val N = A.length stack
85 :     val stack' = A.array(N,0)
86 :     val pos' = A.array(N,0)
87 :     val n = !count
88 :     fun f(i,x) = (A.update(stack',i,x);A.update(pos',x,i))
89 :     in A.appi f (stack,0,SOME n);
90 :     SET{stack=stack',
91 :     pos =pos',
92 :     count=ref n
93 :     }
94 :     end
95 :    
96 :     fun union(s1,s2) = app (fn x => add(s2,x)) s1
97 :     fun diff(s1,s2) = app (fn x => remove(s2,x)) s1
98 :     fun s1 + s2 = let val s3 = copy s1
99 :     in union(s2,s3); s3 end
100 :     fun s1 - s2 = let val s3 = copy s1
101 :     in diff(s2,s3); s3 end
102 :     fun s1 * s2 = let val s3 = intset(capacity s1)
103 :     in app (fn x => if contains(s2,x) then add(s3,x) else ())
104 :     s1;
105 :     s3
106 :     end
107 :    
108 :    
109 :    
110 :     end
111 :    

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