//////////////////////////////////////////////////////////////////////
// RootVector.java                                                  //
// --Root Node maintenance data structure used to maintain SPON--   //
//                                                                  //
// Supervised Peer-to-peer Overlay Network (SPON) Simulator         //
//                                                                  //
// Computer Science Independent Study                               //
// Modified by: Peter Keeler, Spring 2004                           //
//                                                                  //
// 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 String myKey;
    private int maxHeight;
    private int numberOfNodes;
    private boolean root;
    
    /**
       Create a new RootVector of size 0 on node <blank>.
    */
    public RootVector() {
	myVector = new Vector();
	maxHeight = 1;
	numberOfNodes = 0;
	root = false;
	myKey = "0.0.0.0";
    }
    
    /**
       Create a new Root Vector of size 0 for the system supervisor
       @param src - String representation of the supervisor IP
    */
    public RootVector( String src ) {
	myVector = new Vector();
	maxHeight = -1; 
	numberOfNodes = 0;
	myKey = src;
	root = false;
    }
    
    public RootVector( String src, boolean b ) {
	myVector = new Vector();
	maxHeight = -1; 
	numberOfNodes = 0;
	myKey = src;
	root = b;
    }

    public RootVector(int i) {
	myVector = new Vector();
	maxHeight = i;
	numberOfNodes = 0;
	root = false;
    }

    public RootVector(String src, int i) {
	myVector = new Vector();
	maxHeight = i;
	numberOfNodes = 0;
	root = false;
	myKey = src;
    }

    public int getHeight() { return maxHeight; }

    public Node getNode(int i) {
	// search for the i'th real node, ignoring empties.
	int k;
	int j;
	Node aNode = new Node();
	for (j = 0,k=0; k < i && j < myVector.size(); j++) {
	    aNode = (Node)myVector.elementAt(j);
	    if (!(aNode.isEmpty())) {
		k++;
	    }
	}
	return aNode;
	// aNode is either the ith real node, or is null.
    }

    public void removeNode(String key) {
	// search for the node with IP addr == key and remove it.
	String str;
	Node nullNode = new Node();
	for (int i = 0; i < myVector.size(); i++) {
	    str = ((Node) myVector.elementAt(i)).getKey();
	    if (key.compareToIgnoreCase(str)==0) {
		myVector.setElementAt(nullNode,i);
		numberOfNodes--;
		if (numberOfNodes < 0) numberOfNodes = 0;
	    }
	}
    }

    public boolean isChild(String str) {
	// search through vector, check if str is key to any node.
	for (int i = 0; i < myVector.size(); i++) {
	    if (((Node)myVector.elementAt(i)).getKey().compareToIgnoreCase(str)==0) return true;
	}
	return false;
    }

    public boolean isLeft(Node n) {
	for (int i = 0; i < myVector.size(); i++) {
	    if (((Node)myVector.elementAt(i)).getKey().compareToIgnoreCase(n.getKey())==0) {
		if (i%2==0) return true;
		return false;
	    }
	}
	return false;
    }

    public String getPos(Node n) {
	for (int i = 0; i < myVector.size(); i++) {
	    if (((Node)myVector.elementAt(i)).getKey().compareToIgnoreCase(n.getKey())==0) return Integer.toString(i+4);
	}
	return "-1";
    }

    /**
       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, add3, add4;
	add1 = myVector.add( new Node() );
	add2 = myVector.add( new Node() );
	add3 = myVector.add( new Node() );
	add4 = myVector.add( new Node() );
	return (add1 && add2 && add3 && add4);
    }
    
    /**
       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 >= 4 ) {
	    Node last1 = (Node)myVector.elementAt( vSize - 1 );
	    Node last2 = (Node)myVector.elementAt( vSize - 2 );
	    Node last3 = (Node)myVector.elementAt( vSize - 3 );
	    Node last4 = (Node)myVector.elementAt( vSize - 4 );
	    if( last1.isEmpty() && last2.isEmpty() && last3.isEmpty() && last4.isEmpty()) {
		myVector.removeElementAt( vSize - 1 );
		myVector.removeElementAt( vSize - 2 );
		myVector.removeElementAt( vSize - 3 );
		myVector.removeElementAt( vSize - 4 );
		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())) {
		// Found this node already in the network:
		// return its parent and the permissible height.
		Node foundNode = (Node)myVector.elementAt(i);
		comStack = foundNode.getMParent();
		return comStack + ";" + ((myVector.size()/4)-(i/4)+1);
	    }
	    if(((Node)myVector.elementAt(i)).getKey().compareToIgnoreCase("0.0.0.0")==0) {
		// Found an empty space to fill.
		emptySlot = i;
	    }
	}
	
	// Vector full. If space is available for growth, grow.
	if( emptySlot == -1 ) {
	    if (root || (myVector.size()/4)<maxHeight) {
		emptySlot = myVector.size();
		grow();
	    }
	    else {
		// no space available; tell the host to pass this node up to its parent.
		return "0.0.0.0";
	    }
	}
	// Put node into place.
	Node newNode = (Node)myVector.elementAt(emptySlot);
	newNode.setKey(ipKey);
	myVector.setElementAt(newNode,emptySlot);
	numberOfNodes++;
	// initially, node is only recorded as being in the tree.
	// If it swings, another message will be sent to indicate it.
	comStack += ipKey + ";" + (emptySlot/4) + ";own;-1;own;own;";
	comStack += "0.0.0.0;0.0.0.0;0.0.0.0;0.0.0.0";
	boolean toSwing = false;
	int rank = 0;
	int pos = 0;
	while (((rank+1)*4) < myVector.size()) {
	    Node addr1 = (Node)myVector.elementAt(4*rank+pos++);
	    Node addr2 = (Node)myVector.elementAt(4*rank+pos++);
	    Node addr3 = (Node)myVector.elementAt(4*rank+pos++);
	    Node addr4 = (Node)myVector.elementAt(4*rank+pos++);
	    Node par1 = (Node)myVector.elementAt(4*rank+pos++);
	    Node par2 = (Node)myVector.elementAt(4*rank+pos++);
	    Node par3 = (Node)myVector.elementAt(4*rank+pos++);
	    Node par4 = (Node)myVector.elementAt(4*rank+pos++);
	    pos = 0;
	    if (!(addr1.isEmpty())
		&& !(addr2.isEmpty())
		&& !(addr3.isEmpty())
		&& !(addr4.isEmpty())) {
		// nodes may need to be swung.
		if (par1.isEmpty() || 
		    par2.isEmpty() || 
		    par3.isEmpty() ||
		    par4.isEmpty()) {
		    // no more nodes need to be swung; 
		    // now comStack can be returned.
		    return comStack;
		}
		else {
		    // parents are all in place and at least some are not
		    // swung. Swing current nodes to their new parents.
		    if (par1.getLeftChild().compareToIgnoreCase("0.0.0.0")==0 &&
			par1.getRightChild().compareToIgnoreCase("0.0.0.0")==0 &&
			par1.getSLeftChild().compareToIgnoreCase("0.0.0.0")==0 &&
			par1.getSRightChild().compareToIgnoreCase("0.0.0.0")==0) {
			par1.setLeftChild(addr1.getKey());
			par1.setRightChild(addr2.getKey());
			par1.setSLeftChild(addr3.getKey());
			par1.setSRightChild(addr4.getKey());
			par2.setLeftChild(addr3.getKey());
			par2.setRightChild(addr4.getKey());
			par2.setSLeftChild(addr1.getKey());
			par2.setSRightChild(addr2.getKey());
			myVector.setElementAt(par1,4*rank+4);
			myVector.setElementAt(par2,4*rank+5);
			// add to return string
			comStack += "|" + addr1.getKey() + ";" + 
			    (rank+1) + ";" + par1.getKey() + ";" + "0" + "|" +
			    addr2.getKey() + ";" +
			    (rank+1) + ";" + par1.getKey() + ";" + "1" + "|" +
			    addr3.getKey() + ";" +
			    (rank+1) + ";" + par2.getKey() + ";" + "0" + "|" +
			    addr4.getKey() + ";" +
			    (rank+1) + ";" + par2.getKey() + ";" + "1";
			// remove children from own awareness
			Node nNode = new Node();
			myVector.setElementAt(nNode, 4*rank+0);
			myVector.setElementAt(nNode, 4*rank+1);
			myVector.setElementAt(nNode, 4*rank+2);
			myVector.setElementAt(nNode, 4*rank+3);
			numberOfNodes -= 4;
		    }
		    else {
			par3.setLeftChild(addr1.getKey());
			par3.setRightChild(addr2.getKey());
			par3.setSLeftChild(addr3.getKey());
			par3.setSRightChild(addr4.getKey());
			par4.setLeftChild(addr3.getKey());
			par4.setRightChild(addr4.getKey());
			par4.setSLeftChild(addr1.getKey());
			par4.setSRightChild(addr2.getKey());
			myVector.setElementAt(par3,4*rank+6);
			myVector.setElementAt(par4,4*rank+7);
			// Add to return string
			comStack += "|" + addr1.getKey() + ";" + 
			    (rank+1) + ";" + par3.getKey() + ";" + "0" + "|" +
			    addr2.getKey() + ";" +
			    (rank+1) + ";" + par3.getKey() + ";" + "1" + "|" +
			    addr3.getKey() + ";" +
			    (rank+1) + ";" + par4.getKey() + ";" + "0" + "|" +
			    addr4.getKey() + ";" +
			    (rank+1) + ";" + par4.getKey() + ";" + "1";

			// remove children from own awareness
			Node nNode = new Node();
			myVector.setElementAt(nNode, 4*rank+0);
			myVector.setElementAt(nNode, 4*rank+1);
			myVector.setElementAt(nNode, 4*rank+2);
			myVector.setElementAt(nNode, 4*rank+3);
			// on next pass through, parents will swing, too.
			numberOfNodes -= 4;
		    }
		}
	    }
	    rank++;
	} // end of while loop
	// went all the way through the nodes and didn't return;
	// This should never happen unless everything is full.
	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 myKey + " Vector Size: " + myVector.size() +
	    " content " + myVector.toString() + 
	    " consisting of " + numberOfNodes + " nodes";
    }
    
    public String sendTo(boolean coPar) {
	String comStack = "0.0.0.0";
	for (int i = 0; i < myVector.size(); i++) {
	    Node n = (Node)myVector.elementAt(i);
	    if ((i%4)<2 && !(n.isEmpty())) {
		// a primary child
		comStack += ";" + n.getKey();
	    } else if (coPar && !(n.isEmpty())) {
		// a secondary child and responsibility for it
		comStack += ";" + n.getKey();
	    } 
	}
	return comStack;
    }

    public String getAll() {
	String comStack = Integer.toString(myVector.size()) + ";";
	for (int i = 0; i < myVector.size();) {
	    Node n = (Node)myVector.elementAt(i);
	    comStack += n.getKey();
	    ++i;
	    if (i < myVector.size()) comStack += ";";
	}
	return comStack;
    }

    /**
       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;
    }

    public String getLowest() {
	for (int i = 0; i <  myVector.size(); i++) {
	    Node n = (Node)myVector.elementAt(i);
	    if (!(n.isEmpty())) {
		return n.getKey();
	    }
	}
	return "0.0.0.0";
    }
    
    /**
       Designates a Node as having intentions of leaving.
       @param leaveNode - the IP representation of the host wishing to leave
       @return String - a delimited string of messages to be sent to the other network members as a result of the leave
    */
    public String replace( String leaveNode) {
	// Find the node that's leaving.
	// If a node is available to replace it (a node in the lowest level
	// is available), use that. Otherwise, return 0.0.0.0.
	String comStack = "";
	int i = 0;
	boolean foundIt = false;
	Node n = new Node();
	for (i=0; i<myVector.size() && !foundIt; i++) {
	    n = (Node)myVector.elementAt(i);
	    if (n.getKey().compareToIgnoreCase(leaveNode)==0) {
		numberOfNodes--;
		foundIt = true;
	    }
	}
	if (!foundIt) {
	    return "0.0.0.0";
	}
	Node n0 = (Node)myVector.elementAt(0);
	Node n1 = (Node)myVector.elementAt(1);
	Node n2 = (Node)myVector.elementAt(2);
	Node n3 = (Node)myVector.elementAt(3);
	if (n0.getKey().compareToIgnoreCase("0.0.0.0")!=0) {
	    n.setKey(n0.getKey());
	    myVector.setElementAt(n,i);
	    n0.setKey("0.0.0.0");
	    myVector.setElementAt(n0,0);
	    comStack = n0.toString();
	} else if (n1.getKey().compareToIgnoreCase("0.0.0.0")!=0) {
	    n.setKey(n1.getKey());
	    myVector.setElementAt(n,i);
	    n1.setKey("0.0.0.0");
	    myVector.setElementAt(n1,1);
	    comStack = n1.toString();
	} else if (n2.getKey().compareToIgnoreCase("0.0.0.0")!=0) {
	    n.setKey(n2.getKey());
	    myVector.setElementAt(n,i);
	    n2.setKey("0.0.0.0");
	    myVector.setElementAt(n2,2);
	    comStack = n2.toString();
	} else if (n3.getKey().compareToIgnoreCase("0.0.0.0")!=0) {
	    n.setKey(n3.getKey());
	    myVector.setElementAt(n,i);
	    n3.setKey("0.0.0.0");
	    myVector.setElementAt(n3,3);
	    comStack = n3.toString();
	} else {
	    n.setKey("0.0.0.0");
	    myVector.setElementAt(n,i);
	    comStack = n.toString();
	}
	collapse();
	
	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;
    }


    public Node reposition(String str, int i) {
	Node n = (Node) myVector.elementAt(i);
	n.setKey(str);
	myVector.setElementAt(n,i);
	return(n);
    }
}