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 /smlnj-lib/trunk/Util/uref.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/Util/uref.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (view) (download)
Original Path: sml/trunk/src/smlnj-lib/Util/uref.sml

1 : monnier 2 (* uref.sml
2 :     *
3 :     * UNIONFIND DATA STRUCTURE WITH PATH COMPRESSION AND RANKED UNION
4 :     *
5 :     * Author:
6 :     * Fritz Henglein
7 :     * DIKU, University of Copenhagen
8 :     * henglein@diku.dk
9 :     *)
10 :    
11 :     structure URef : UREF =
12 :     struct
13 :    
14 :     datatype 'a urefC
15 :     = ECR of 'a * int
16 :     | PTR of 'a uref
17 :     withtype 'a uref = 'a urefC ref
18 :    
19 :     fun find (p as ref (ECR _)) = p
20 :     | find (p as ref (PTR p')) = let
21 :     val p'' = find p'
22 :     in
23 :     p := PTR p''; p''
24 :     end
25 :    
26 :     fun uRef x = ref (ECR(x, 0))
27 :    
28 :     fun !! p = let val ECR(x, _) = !(find p) in x end
29 :    
30 :     fun equal (p, p') = (find p = find p')
31 :    
32 :     fun update (p, x) = let val (p' as ref(ECR(_, r))) = find p
33 :     in
34 :     p' := ECR(x, r)
35 :     end
36 :    
37 :     fun link (p, q) = let
38 :     val p' = find p
39 :     val q' = find q
40 :     in
41 :     if (p' = q') then () else p' := PTR q
42 :     end
43 :    
44 :     fun unify f (p, q) = let
45 :     val (p' as ref(ECR(pc, pr))) = find p
46 :     val (q' as ref(ECR(qc, qr))) = find q
47 :     val newC = f (pc, qc)
48 :     in
49 :     if p' = q'
50 :     then p' := ECR(newC, pr)
51 :     else if pr = qr
52 :     then (
53 :     q' := ECR(newC, qr+1);
54 :     p' := PTR q')
55 :     else if pr < qr
56 :     then (
57 :     q' := ECR(newC, qr);
58 :     p' := PTR q')
59 :     else ((* pr > qr *)
60 :     p' := ECR(newC, pr);
61 :     q':= PTR p')
62 :     end
63 :    
64 :     fun union (p, q) = let
65 :     val p' = find p
66 :     val q' = find q
67 :     in
68 :     if p' = q'
69 :     then ()
70 :     else let
71 :     val ECR(pc, pr) = !p' and ECR(qc, qr) = !q'
72 :     in
73 :     if pr = qr
74 :     then (
75 :     q' := ECR(qc, qr+1);
76 :     p' := PTR q')
77 :     else if pr < qr
78 :     then p' := PTR q'
79 :     else q':= PTR p'
80 :     end
81 :     end
82 :    
83 :     end

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