disjsets.java

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

/*{*/ // /*}*/package DataStructures;

/*{*/ import edu.odu.cs.zeil.AlgAE.Direction;
/*{*/ import edu.odu.cs.zeil.AlgAE.Server.algae;
/*{*/ import edu.odu.cs.zeil.AlgAE.Server.Rendering;
/*{*/ import edu.odu.cs.zeil.AlgAE.Server.Visible;
/*{*/ import edu.odu.cs.zeil.AlgAE.Server.VisibleRendering;
/*{*/ import java.awt.Color;

// DisjSets class
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x )              --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed

/**
 * Disjoint set class, using union by rank
 * and path compression.
 * Elements in the set are numbered starting at 0.
 * @author Mark Allen Weiss
 */
public class DisjSets implements Visible
{
/*{*/     private VisibleRendering vr;
/*{*/ 
     class DJSArrayElement implements Visible
     {
         private VisibleRendering vr;
         private int position;
         
         DJSArrayElement (int i)
         {
             position = i;
             vr = new VisibleRendering (this, java.awt.Color.cyan, false);
         }
 
         public Rendering getRendering() {return vr;}
 
         public String getAlgAEText()
         {
             return "" + array[position];
         }
     
         public void touchAllPointers() {}
         
         public void touchAllComponents() {}
     }
 
     class DJSTreeElement implements Visible
     {
         private VisibleRendering vr;
         private int position;
         
         DJSTreeElement (int i)
         {
             position = i;
             vr = new VisibleRendering (this, java.awt.Color.green, false);
         }
 
         public Rendering getRendering() {return vr;}
 
         public String getAlgAEText()
         {
             return "" + position;
         }
     
         public void touchAllPointers()
	 {
	     if (array[position] >= 0)
		 vr.touch (visElements[array[position]].tElement, Direction.N, "");
	     else
		 vr.touch (visElements[position].aElement, Direction.N, "");
	 }
         
         public void touchAllComponents() {}
     }

     class DJSElement
     {
         public DJSTreeElement tElement;
         public DJSArrayElement aElement;

	 public DJSElement (int i)
         {
             tElement = new DJSTreeElement(i);
             aElement = new DJSArrayElement(i);
         }

	 public void highlight()
	 {
	     tElement.getRendering().highlight(java.awt.Color.yellow);
	     aElement.getRendering().highlight(java.awt.Color.yellow);
	 }

	 public void unHighlight()
	 {
	     tElement.getRendering().unHighlight();
	     aElement.getRendering().unHighlight();
	 }
	 
	 public void show()
	 {
	     tElement.getRendering().show();
	 }
	 
	 public void hide()
	 {
	     tElement.getRendering().hide();
	 }
     }
    



 
/*{*/     private DJSElement[] visElements;
    
        
    /**
     * Construct the disjoint sets object.
     * @param numElements the initial number of disjoint sets.
     */
    public DisjSets( int numElements )
    {
        array = new int [ numElements ];
/*{*/         visElements = new DJSElement [numElements];
        for( int i = 0; i < array.length; i++ )
            {
                array[ i ] = -1;
/*{*/           visElements[i] = new DJSElement(i);
            }
/*{*/   vr = new VisibleRendering (this, java.awt.Color.blue, false);
    }

    /**
     * Union two disjoint sets using the height heuristic.
     * For simplicity, we assume root1 and root2 are distinct
     * and represent set names.
     * @param root1 the root of set 1.
     * @param root2 the root of set 2.
     */
    public void union( int root1, int root2 )
    {
/*{*/   visElements[root1].highlight();
/*{*/   visElements[root2].highlight();
/*{*/   algae.FRAME ("start a union");
        if( array[ root2 ] < array[ root1 ] )  /* root2 is deeper */
            {
/*{*/           algae.FRAME ("make root2 new root");
                array[ root1 ] = root2;        /* Make root2 new root */
            }
        else
	    {
/*{*/ 		algae.FRAME ("make root1 new root");
		if( array[ root1 ] == array[ root2 ] )
		    array[ root1 ]--;        /* Update height if same */
		array[ root2 ] = root1;        /* Make root1 new root */
	    }
/*{*/   algae.FRAME ("done with union"); algae.unHighlightAll();  
    }

    /**
     * Perform a find with path compression.
     * Error checks omitted again for simplicity.
     * @param x the element being searched for.
     * @return the set containing x.
     */
    public int find( int x )
    {
/*{*/   visElements[x].highlight();
/*{*/   algae.FRAME ("start to find");
        if( array[ x ] < 0 )
            {
/*{*/           algae.FRAME ("found the root");
/*{*/           visElements[x].unHighlight();
                return x;
            }
        else
            {
/*{*/           algae.FRAME ("recurse to find");
                array[ x ] = find( array[ x ] );
/*{*/           algae.FRAME ("return from recursive find");
/*{*/           visElements[x].unHighlight();
                return array[ x ];
            }
    }

    private int [ ] array;


    // Test main; all finds on same output line should be identical
    public static void main( String [ ] args )
    {
        int NumElements = 128;
        int NumInSameSet = 16;

        DisjSets s = new DisjSets( NumElements );
        int set1, set2;

        for( int k = 1; k < NumInSameSet; k *= 2 )
        {
            for( int j = 0; j + k < NumElements; j += 2 * k )
            {
                set1 = s.find( j );
                set2 = s.find( j + k );
                s.union( set1, set2 );
            }
        }

        for( int i = 0; i < NumElements; i++ )
        {
            System.out.print( s.find( i )+ "*" );
            if( i % NumInSameSet == NumInSameSet - 1 )
                System.out.println( );
        }
        System.out.println( );
    }


    public void show()
    {
	vr.show();
        for (int i = 0; i < visElements.length; i++ )
            visElements[i].show();
    }

    public void hide()
    {
	vr.hide();
        for (int i = 0; i < visElements.length; i++ )
            visElements[i].hide();
    }
    
	
    
    public Rendering getRendering() {return vr;}

    public String getAlgAEText()
    {
        return "";
    }
    
    public void touchAllPointers() {}
    
    public void touchAllComponents()
    {
        for (int i = 0; i < visElements.length; i++ )
            vr.touch (visElements[i].aElement);
    }
    
}