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

SCM Repository

[smlnj] View of /sml/trunk/src/smlnj-lib/Util/uref.sml
ViewVC logotype

View of /sml/trunk/src/smlnj-lib/Util/uref.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 475 - (download) (annotate)
Wed Nov 10 22:59:58 1999 UTC (19 years, 11 months ago) by monnier
Original Path: sml/branches/SMLNJ/src/smlnj-lib/Util/uref.sml
File size: 1708 byte(s)
version 110.24
(* uref.sml
 *
 * UNIONFIND DATA STRUCTURE WITH PATH COMPRESSION AND RANKED UNION
 *
 * Author:
 *    Fritz Henglein
 *    DIKU, University of Copenhagen
 *    henglein@diku.dk
 *)

structure URef : UREF =
  struct

    datatype 'a urefC
      = ECR of 'a * int
      | PTR of 'a uref
    withtype 'a uref = 'a urefC ref

    fun find (p as ref (ECR _)) = p
      | find (p as ref (PTR p')) = let
	  val p'' = find p'
          in
	    p := PTR p''; p''
          end

    fun uRef x = ref (ECR(x, 0))

    fun !! p = let val ECR(x, _) = !(find p) in x end
      
    fun equal (p, p') = (find p = find p')

    fun update (p, x) = let val (p' as ref(ECR(_, r))) = find p
	  in
	    p' := ECR(x, r)
	  end

    fun link (p, q) = let
	  val p' = find p
          val q' = find q
	  in
	    if (p' = q') then false else (p' := PTR q; true)
	  end

    fun unify f (p, q) = let
	  val (p' as ref(ECR(pc, pr))) = find p
          val (q' as ref(ECR(qc, qr))) = find q
	  val newC = f (pc, qc)
          in
	    if p' = q'
	      then (p' := ECR(newC, pr); false)
	      else (
	        if pr = qr
		  then (
		    q' := ECR(newC, qr+1);
		    p' := PTR q')
		else if pr < qr
		  then (
		    q' := ECR(newC, qr);
		    p' := PTR q')
		  else ((* pr > qr *)
		    p' := ECR(newC, pr);
		    q':= PTR p');
		true)
          end

    fun union (p, q) = let
	  val p' = find p
          val q' = find q
          in
	    if p' = q' 
              then false
              else let
		val ECR(pc, pr) = !p' and ECR(qc, qr) = !q'
		in
		  if pr = qr 
		    then (
		      q' := ECR(qc, qr+1);
		      p' := PTR q')
		  else if pr < qr
		    then p' := PTR q'
		    else q':= PTR p';
		  true
		end
          end

  end

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