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/branches/SMLNJ/src/MLRISC/library/int-set.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/library/int-set.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)

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

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