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/mlrisc/sparseSet.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/mlrisc/sparseSet.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 93 - (view) (download)

1 : monnier 16 (* sparseSet.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     (* sparse-set.sml
8 :     *
9 :     * Sparse sets of integers; based on "An efficient representation for sparse sets,"
10 :     * by Briggs and Torczon, LOPLAS v. 2, #1-4, 1993.
11 :     *)
12 :    
13 :     signature SPARSESET = sig
14 :     type set
15 :     val set : int -> set
16 :     val clear : set -> unit
17 :     val insert : set -> int -> unit
18 :     val delete : set -> int -> unit
19 :     val member : set * int -> bool
20 :     val forall : set -> (int -> unit) -> unit
21 :     end
22 :    
23 :     structure SparseSet :> SPARSESET = struct
24 :    
25 :     datatype set = SET of {
26 :     max : int,
27 :     members : int ref,
28 :     sparse : int Array.array,
29 :     dense : int Array.array
30 :     }
31 :    
32 :     exception SparseSet
33 :    
34 :     fun set max = SET{
35 :     max = max,
36 :     members = ref 0,
37 :     sparse = Array.array(max, 0),
38 :     dense = Array.array(max, 0)
39 :     }
40 :    
41 :     fun error msg = (print ("SparseSet: "^ msg); raise SparseSet)
42 :    
43 :     val subscript = Array.sub
44 :     val update = Array.update
45 :     val unsafeSub = Unsafe.Array.sub
46 :     val unsafeUpdate = Unsafe.Array.update
47 :    
48 :     fun clear(SET{members, ...}) = (members := 0)
49 :    
50 :     fun member(SET{members = ref n, sparse, dense, ...}, x) = let
51 :     val i = Array.sub(sparse, x)
52 :     in
53 :     (i < n) andalso (unsafeSub(dense, i) = x)
54 :     end
55 :    
56 :     fun insert(SET{members, sparse, dense, ...}) x = let
57 :     val n = !members
58 :     val i = Array.sub(sparse, x)
59 :     in
60 :     if ((n <= i) orelse (unsafeSub(dense, i) <> x))
61 :     then (
62 :     unsafeUpdate(sparse, x, n);
63 :     Array.update(dense, n, x);
64 :     members := n+1)
65 :     else ()
66 :     end
67 :    
68 :     fun delete(SET{members,sparse,dense,...}) x = let
69 :    
70 :     val n = !members - 1
71 :     val i = Array.sub(sparse,x)
72 :     in
73 :     if (i <= n) andalso Array.sub(dense,i) = x then let
74 :     val e = Array.sub(dense,n)
75 :     in
76 :     members:=n;
77 :     unsafeUpdate(dense,i,e);
78 :     unsafeUpdate(sparse,e,i)
79 :     end
80 :     else ()
81 :     end
82 :    
83 :     fun forall(SET{members,dense,...}) f = let
84 :     val n = !members
85 :     fun doit i = (f (Array.sub(dense,i)); doit(i-1))
86 :     in
87 :     doit(n-1) handle _ => ()
88 :     end
89 :     end
90 :    
91 :    
92 :    
93 :     (*
94 :     * $Log: sparseSet.sml,v $
95 : monnier 93 * Revision 1.1.1.1 1998/04/08 18:39:02 george
96 :     * Version 110.5
97 : monnier 16 *
98 :     *)

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