//////////////////////////////////////////////////////////////////////
// RootVector.java                                                  //
// --Root Node maintenance data structure used to maintain SPON--   //
//                                                                  //
// Supervised Peer-to-peer Overlay Network (SPON) Simulator         //
//                                                                  //
//                                                                  //
// Computer Science M.S.E. Project                                  //
// Programmed by: Joey Chau                                         //
// Copyright: February, 2003                                        //
//                                                                  //
// Research Advisor: Christian Scheideler                           //
//                   Computer Science                               //
//                   Johns Hopkins University                       //
//////////////////////////////////////////////////////////////////////
import java.io.*;
import java.net.*;
import java.util.*;

/**
   The data structure maintaing the list of root vectors known to the SPON Supervisor and provides the communcation
   mechanims for various join and leave processes.
*/
class RootVector 
{
  private Vector myVector;
  private int numberOfNodes;
  private String srcKey;

  /**
     Create a new RootVector of size 0 on node <blank>.
  */
  public RootVector() {
    myVector = new Vector();
    numberOfNodes = 0;
    srcKey = "";
  }

  /**
     Create a new Root Vector of size 0 
     @param src - String representation of the supervisor IP
  */
  public RootVector( String src ) {
    myVector = new Vector();
    numberOfNodes = 0;
    srcKey = src;
  }

  /**
     In case the vector is not long enough we can grow the vector to produce more space
     @return boolean - true if the vector was extended
  */
  private boolean grow() {
    boolean add1, add2;
    add1 = myVector.add( new Node() );
    add2 = myVector.add( new Node() );
    return (add1 && add2);
  }

  /**
     In case the vector is too long, this will collapse the higher elements to save space
     @return boolean  - true if the vector was collapsed
  */
  private boolean collapse() {
    boolean workornot;
    int vSize;

    vSize = myVector.size();
    workornot = false;
    if( vSize >= 2 ) {
      Node last1 = (Node)myVector.elementAt( vSize - 1 );
      Node last2 = (Node)myVector.elementAt( vSize - 2 );
      if( last1.isEmpty() && last2.isEmpty() ) {
	myVector.removeElementAt( vSize - 1 );
	myVector.removeElementAt( vSize - 2 );
	workornot = true;
      }
      else {
	workornot = false;
      }
    }
    else {
      workornot = false;
    }
    return workornot;
  }

  /**
     Adds a node onto the SPON network.
     @param ipKey - String representation of the Node wishing to join the Network
     @return String - a delimited string of messages to be sent to the other network members as a result of the join
  */
  public String join( String ipKey ) {
    String comStack = new String();
    
    // Check for redundancy
    int emptySlot;
    emptySlot = -1;
    for( int i  = (myVector.size() - 1); i >= 0; i-- ) {
      if( ipKey.equals(( (Node)myVector.elementAt( i ) ).getKey()) ) {
	// Communique
	String buffer = new String();
	buffer = "NEW0>" + ((Node)myVector.elementAt(i)).toString();
	buffer = buffer + "," + ipKey;
	comStack = comStack + "|" +  buffer;
	//
	return comStack;
      }
      if( ( (Node)myVector.elementAt(i) ).isEmpty() ) {
	emptySlot = i;
      }
    }
    
    // Vector full and grow
    if( emptySlot == -1 ) {
      emptySlot = myVector.size();
      grow();
    }

    // Top Node Check
    if( (emptySlot+2) > myVector.size() ||
	( ((emptySlot+3) > myVector.size()) && 
	  ((Node)myVector.elementAt(emptySlot+1)).isEmpty() ) 
	) {
      // Communique
      String buffer = new String();
      buffer = "TOP0>" + ipKey;
      buffer = buffer + "," + srcKey;
      comStack =  comStack + "|" + buffer;
      //
    }

    // Join Process
    int height;
    String leftChild, rightChild, nextNode;
    Node joinNode = new Node( ipKey );

    height = emptySlot/2;
    joinNode.setHeight( height );

    // CHILDREN operations
    if( height > 0 ) {
      leftChild = ( (Node)myVector.elementAt( ((height-1)*2) + 0 ) ).getKey();
      joinNode.setLeftChild( leftChild );
      // Communique
      String buffer = new String();
      buffer = "NEXT>" + " ";
      buffer = buffer + "," + leftChild;
      comStack = comStack + "|" + buffer;
      //
      rightChild = ( (Node)myVector.elementAt( ((height-1)*2) + 1 ) ).getKey();
      joinNode.setRightChild( rightChild );
      // Communique
      buffer = "NEXT>" + " ";
      buffer = buffer + "," + rightChild;
      comStack = comStack + "|" + buffer;
      //
    }

    // NEXT NODE operations
    if( emptySlot%2 == 1 ) {
      joinNode.setNext( ((Node)myVector.elementAt( emptySlot-1 )).getKey() );
      if( height < 2 ) {
	((Node)myVector.elementAt( emptySlot-1 )).setNext(" ");
	// Communique
	String buffer = new String();
	buffer = "NEXT>" + " ";
	buffer = buffer + "," + ((Node)myVector.elementAt( emptySlot-1 )).getKey();
	comStack = comStack + "|" + buffer;
	//
      }
      else {
	((Node)myVector.elementAt( emptySlot-1 )).
	  setNext( ((Node)myVector.elementAt( 2*(height-2)+1 )).getKey() );
	// Communique
	String buffer = new String();
	buffer = "NEXT>" + ((Node)myVector.elementAt( 2*(height-2)+1 )).getKey();
	buffer = buffer + "," + ((Node)myVector.elementAt( emptySlot-1 )).getKey() ;
	comStack = comStack + "|" + buffer;
	//
      }
    }
    else if( height > 1 ) {
      joinNode.setNext( ((Node)myVector.elementAt( 2*(height-2) + 1 )).getKey() );
    }
    for( int i = emptySlot+1; i< myVector.size();i++ ) {
      if( !((Node)myVector.elementAt(i)).isEmpty() ) {
	((Node)myVector.elementAt(i)).setNext(ipKey);
	// Communique
	String buffer = new String();
	buffer = "NEXT>" + ipKey;
	buffer = buffer + "," + ((Node)myVector.elementAt(i)).getKey();
	comStack = comStack + "|" + buffer;
	//
	break;
      }
    }
    
    // Set New Node
    myVector.setElementAt( joinNode, emptySlot );
    if( height > 0 ) {
      // Remove LeftChild
      myVector.setElementAt( new Node(), ((height-1)*2) + 0 );
      // Remove RightChild
      myVector.setElementAt( new Node(), ((height-1)*2) + 1 );
    }
    // Communique
    String buffer = new String();
    buffer = "NEW0>" + joinNode.toString();
    buffer = buffer + "," + ipKey;
    comStack = comStack + "|" + buffer;
    //
    numberOfNodes++;
    return comStack;
  }

  /**
     A String representation of the current state of the Root Vectors
     @return String - the representation of the current state in a displayable string format
  */
  public String toString() {
    return srcKey + " Vector Size: " + myVector.size() +
      " content " + myVector.toString() + 
      " consisting of " + numberOfNodes + " nodes";
  }

  /**
     The Number of Nodes still present to this supervisor in the SPON Network
     return int - the Number of Nodes in the SPON Network
  */
  public int size() {
    return numberOfNodes;
  }

  /**
     Designates a Node as having intentions of leaving.
     @param leaveNode - the Node representation of the host wishing to leave
     @param pNode - String representation of the parent of the leaving nodel; pNode is null for root nodes
     @return String - a delimited string of messages to be sent to the other network members as a result of the leave
  */
  public String replace( Node leaveNode, String pNode ) {
    Node lowNode = new Node(), predecessor = new Node(), 
      localLeave = new Node(), beforeLeave = new Node(), topNode = new Node();
    String comStack = new String(), buffer;
    int cnt = 0;
    // Get Low Info
    for( int i = 0; i < myVector.size(); i++ ) {
      //System.out.println("Count: " + cnt);
      if( ( !((Node)myVector.elementAt( i )).isEmpty() ) && cnt==0 ) {
	lowNode = (Node)myVector.elementAt(i);
	cnt++;
      }
      else if( ( !((Node)myVector.elementAt( i )).isEmpty() ) && cnt==1 ) {
	predecessor = (Node)myVector.elementAt(i);
	cnt++;
      }
      // Find local info on leaving node if it exists
      if( ((Node)myVector.elementAt( i )).getKey().
	  equals( leaveNode.getKey() ) ) {
	localLeave = ((Node)myVector.elementAt( i ));
      }
      else if( !localLeave.isEmpty() && 
	       beforeLeave.isEmpty() && 
	       !((Node)myVector.elementAt( i )).isEmpty() ) {
	beforeLeave = ((Node)myVector.elementAt( i ));
      }

      // Find the top Node
      if( !((Node)myVector.elementAt( i )).isEmpty() ) {
	topNode = new Node( (Node)myVector.elementAt( i ) );
      }

    }
    // Store Low information before it is deleted
    Node copyLow = new Node( lowNode );
    int lHeight = leaveNode.getHeight();

    // If leaveNode is in the minimum nonempty pair of root slots
    if( lowNode ==  localLeave ) {
      System.out.println( "Leaving Node is Low Node" );
      // Remove localLeave Node
      // New Leave
      //localLeave = new Node();
      if( ((Node)myVector.elementAt( lHeight*2+0 )).getKey().equals( leaveNode.getKey() ) ) {
	myVector.setElementAt( new Node(), lHeight*2+0 );
      }
      else {
	myVector.setElementAt( new Node(), lHeight*2+1 );
      }

      // if height != 0
      if( lHeight != 0 ) {
	// Place leaveNodes Children in lower slot pair
	Node lChild = new Node( leaveNode.getLeftChild() );
	Node rChild = new Node( leaveNode.getRightChild() );
	lChild.setHeight( lHeight-1 );
	rChild.setHeight( lHeight-1 );

	rChild.setNext( lChild.getKey() );
	// Communique
	buffer = new String();
	buffer = "LNXT>" + lChild.getKey();
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + lChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//

	myVector.setElementAt(
			      lChild, (lHeight-1)*2 );
	// Communique
	buffer = new String();
	buffer = "NEED>";
	buffer = buffer + "," + lChild.getKey();
	comStack = comStack + "|" + buffer;
	//

	myVector.setElementAt( 
			      rChild, (lHeight-1)*2+1 );
	// Communique
	buffer = new String();
	buffer = "NEED>";
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//
      }
      if( !beforeLeave.isEmpty() ) {
	beforeLeave.setNext( leaveNode.getRightChild() );
	// Communique
	buffer = new String();
	buffer = "LNXT>" + leaveNode.getRightChild();
	buffer = buffer + "," + beforeLeave.getKey();
	comStack = comStack + "|" + buffer;
	//
      }
    }
    // Special Case: Leaving node is the child of the lowest root node
    else if( pNode.equals( lowNode.getKey() ) ) {
      System.out.println( "Leaving Node is a Special Case" );
      // Remove the low Node
      if( ((Node)myVector.elementAt( lowNode.getHeight()*2+0 )) == lowNode ) {
	myVector.setElementAt( new Node(), lowNode.getHeight()*2+0 );
      }
      else {
	myVector.setElementAt( new Node(), lowNode.getHeight()*2+1 );
      }
      
      // Leaving Node is left Child
      if( leaveNode.getKey().equals( copyLow.getLeftChild() ) ) {
	// Right Child
	Node rChild = new Node( copyLow.getRightChild() );
	rChild.setNext( " " );
	rChild.setHeight( lHeight );
	myVector.setElementAt( rChild, lHeight*2+0 );
	// Communique
	buffer = new String();
	buffer = "LNXT>" + " ";
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "NEED>";
	buffer = buffer + "," + rChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	
	// change the Low Node to use the Leave Node
	copyLow.setLeftChild( leaveNode.getLeftChild() );
	copyLow.setRightChild( leaveNode.getRightChild() );
	copyLow.setNext( rChild.getKey() );
	copyLow.setHeight( leaveNode.getHeight() );
	myVector.setElementAt( copyLow, lHeight*2+1 );
	if( lHeight > 0 ) {
	  // Communique
	  buffer = new String();
	  buffer = "PARN>";
	  buffer = buffer + "," + leaveNode.getLeftChild();
	  comStack = comStack + "|" + buffer;
	  //
	  // Communique
	  buffer = new String();
	  buffer = "PARN>";
	  buffer = buffer + "," + leaveNode.getRightChild();
	  comStack = comStack + "|" + buffer;
	  //
	}
	// Communique
	buffer = new String();
	buffer = "NEWX>" + copyLow.toString();
	buffer = buffer + "," + copyLow.getKey();
	comStack = comStack + "|" + buffer;
	//
      }
      // Leaving Node is Right Child
      else {
	// Left Child
	Node lChild = new Node( copyLow.getLeftChild() );
	lChild.setNext( " " );
	lChild.setHeight( lHeight );
	myVector.setElementAt( lChild, lHeight*2+0 );
	// Communique
	buffer = new String();
	buffer = "LNXT>" + " ";
	buffer = buffer + "," + lChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + lChild.getKey();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "NEED>";
	buffer = buffer + "," + lChild.getKey();
	comStack = comStack + "|" + buffer;
	//

	// change the Low Node to use the Leave Node
	copyLow.setLeftChild( leaveNode.getLeftChild() );
	copyLow.setRightChild( leaveNode.getRightChild() );
	copyLow.setNext( lChild.getKey() );
	copyLow.setHeight( leaveNode.getHeight() );
	myVector.setElementAt( copyLow, lHeight*2+1 );
	if( lHeight > 0 ) {
	  // Communique
	  buffer = new String();
	  buffer = "PARN>";
	  buffer = buffer + "," + leaveNode.getLeftChild();
	  comStack = comStack + "|" + buffer;
	  //
	  // Communique
	  buffer = new String();
	  buffer = "PARN>";
	  buffer = buffer + "," + leaveNode.getRightChild();
	  comStack = comStack + "|" + buffer;
	  //
	}
	// Communique
	buffer = new String();
	buffer = "NEWX>" + copyLow.toString();
	buffer = buffer + "," + copyLow.getKey();
	comStack = comStack + "|" + buffer;
	//
      }
    }
    else {
      System.out.println( "Leaving node is a Standard Case" );
      comStack = comStack + extricate( lowNode );
      // leave node is a root node
      if( !localLeave.isEmpty() ) {
	System.out.println( "Leaving Node is a Root Node" );
	if( localLeave.getNext() == copyLow.getKey() ) {
	  copyLow.setNext( copyLow.getRightChild() );
	}
	else {
	  copyLow.setNext( leaveNode.getNext() );
	}
	if( !localLeave.getNext().equals( " " ) ) {
	  // Communique
	  buffer = new String();
	  buffer = "PARN>";
	  buffer = buffer + "," + localLeave.getNext();
	  comStack = comStack + "|" + buffer;
	  //
	}
	if( !beforeLeave.isEmpty() ) {
	  beforeLeave.setNext( copyLow.getKey() );
	  // Communique
	  buffer = new String();
	  buffer = "LNXT>" + copyLow.getKey();
	  buffer = buffer + "," + beforeLeave.getKey();
	  comStack = comStack + "|" + buffer;
	  //
	}
      }
      else{
	System.out.println( "Leaving Node is Child Node" );
	// Parent
	//System.out.println( "PNode" );
	if( pNode != " " ) {
	  // Communique
	  buffer = new String();
	  buffer = "CHLD>" + leaveNode.getKey() + "+" + copyLow.getKey();
	  buffer = buffer + "," + pNode;
	  comStack = comStack + "|" + buffer;
	  //
	}
      }
      if( !predecessor.isEmpty() && predecessor != localLeave ) {
	  predecessor.setNext( copyLow.getRightChild() );
	  // Communique
	  buffer = new String();
	  buffer = "LNXT>" + copyLow.getRightChild();
	  buffer = buffer + "," + predecessor.getKey();
	  comStack = comStack + "|" + buffer;
	  //
	}
      
      // change the Low Node to use the Leave Node
      copyLow.setLeftChild( leaveNode.getLeftChild() );
      copyLow.setRightChild( leaveNode.getRightChild() );
      copyLow.setHeight( leaveNode.getHeight() );
      // Communique
      buffer = new String();
      buffer = "NEWX>" + copyLow.toString();
      buffer = buffer + "," + copyLow.getKey();
      comStack = comStack + "|" + buffer;
      //
      localLeave.setKey( copyLow.getKey() );
      localLeave.setLeftChild( copyLow.getLeftChild() );
      localLeave.setRightChild( copyLow.getRightChild() );
      localLeave.setNext( copyLow.getNext() );
      localLeave.setHeight( copyLow.getHeight() );

      if( lHeight > 0 ) {
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + leaveNode.getLeftChild();
	comStack = comStack + "|" + buffer;
	//
	// Communique
	buffer = new String();
	buffer = "PARN>";
	buffer = buffer + "," + leaveNode.getRightChild();
	comStack = comStack + "|" + buffer;
	//
      }
      

    }

    numberOfNodes--;
    collapse();

    // Recalculate the top node
    if( myVector.size() <= 0 ) {
      // Communique
      buffer = new String();
      buffer = "TOP0>" + " ";
      buffer = buffer + "," + srcKey;
      comStack =  comStack + "|" + buffer;
      //
    }
    else {
      for( int i = myVector.size()-1; i > myVector.size()-3; i-- ) {
	if( !((Node)myVector.elementAt( i )).isEmpty() ) {
	  if( !((Node)myVector.elementAt( i )).getKey().equals( topNode.getKey() ) ) {
	    System.out.println( "OLD TOP:"+topNode.getKey() );
	    topNode = ((Node)myVector.elementAt( i ));
	    // Communique
	    buffer = new String();
	    buffer = "TOP0>" + topNode.getKey();
	    buffer = buffer + "," + srcKey;
	    comStack =  comStack + "|" + buffer;
	    //
	  }
	  break;
	}
      }
    }
    // Grant Permission to Leave
    // Communique
    buffer = new String();
    buffer = "EXIT>" + leaveNode.getKey();
    buffer = buffer + "," + leaveNode.getKey();
    comStack = comStack + "|" + buffer;
    //
    return comStack;
  }

  /**
     Special helper method used by the replace() method to assist in removing the lowest node of the root nodes
     @param lowNode - Node which happens to be the lowest in the root that needs to be removed
     @return String - a delimited string of messages to be sent to the other network members as a result of the low node removal
  */
  private String extricate( Node lowNode ) {
    String comStack = new String();
    int lHeight = lowNode.getHeight();
    Node copyLow = new Node( lowNode ); // store lowNode info
    // Remove the Node
    if( ((Node)myVector.elementAt( lHeight*2+0 )) == lowNode ) {
      myVector.setElementAt( new Node(), lHeight*2+0 );
    }
    else {
      myVector.setElementAt( new Node(), lHeight*2+1 );
    }

    // height != 0
    if( lHeight != 0 ) {
      Node lowLChd = new Node( copyLow.getLeftChild() );
      Node lowRChd = new Node( copyLow.getRightChild() );
      lowLChd.setHeight( lHeight-1 );
      lowRChd.setHeight( lHeight-1 );

      lowRChd.setNext( lowLChd.getKey() );
      // Communique
      String buffer = new String();
      buffer = "PARN>";
      buffer = buffer + "," + lowLChd.getKey();
      comStack = comStack + "|" + buffer;
      //
      // Communique
      buffer = new String();
      buffer = "LNXT>" + lowLChd.getKey();
      buffer = buffer + "," + lowRChd.getKey();
      comStack = comStack + "|" + buffer;
      //
      myVector.setElementAt(
			     lowLChd, (lHeight-1)*2+0 );
      // Communique
      buffer = new String();
      buffer = "NEED>";
      buffer = buffer + "," + lowLChd.getKey();
      comStack = comStack + "|" + buffer;
      //

      myVector.setElementAt( 
			     lowRChd, (lHeight-1)*2+1 );
      // Communique
      buffer = new String();
      buffer = "NEED>";
      buffer = buffer + "," + lowRChd.getKey();
      comStack = comStack + "|" + buffer;
      //
      
      // Communique
      buffer = new String();
      buffer = "PARN>";
      buffer = buffer + "," + lowRChd.getKey();
      comStack = comStack + "|" + buffer;
      //
    }
    return comStack;
  }

  /**
     Updates the children information for a node in the root vector
     @param newInfo - Node representation of the Node and it's children
     @return boolean - true if the node was found in the network and updated
  */
  public boolean update( Node newInfo ) {
    for( int i = 0; i< myVector.size(); i++ ) {
      if( ((Node)myVector.elementAt(i)).getKey().equals( newInfo.getKey() ) ) {
	((Node)myVector.elementAt(i)).setLeftChild( newInfo.getLeftChild() );
	((Node)myVector.elementAt(i)).setRightChild( newInfo.getRightChild() );
	return true;
      }
    }
    return false;
  }

}