package gsd.protocols.cycle.xbot;

import gsd.interfaces.PartialViewLivelinessVerifiable;
import gsd.protocols.interfaces.MessageCostObservable;

import java.util.ArrayList;

import peersim.cdsim.CDProtocol;
import peersim.config.Configuration;
import peersim.core.CommonState;
import peersim.core.Linkable;
import peersim.core.Node;
import peersim.util.IndexIterator;
import peersim.util.RandPermutation;
import dialnp.protocols.Failable;
import dialnp.protocols.MembershipProtocol;
import dialnp.protocols.OptimizationObservable;
import dialnp.protocols.OverlayAwareProtocol;
import dialnp.protocols.ShuffleObservable;
import dialnp.protocols.broadcast.hypartree.UnderlyingProtocol;
import dialnp.protocols.hybrid.HybridControlInterface;
import dialnp.protocols.selfImprovingHybrid.SelfImprovable;
import dialnp.support.oracle.Oracle;
import dialnp.utils.NCStatus;

public class XBot implements Linkable, CDProtocol,
		MembershipProtocol, SelfImprovable, Failable, ShuffleObservable, 
		OptimizationObservable, HybridControlInterface, UnderlyingProtocol,
		MessageCostObservable, PartialViewLivelinessVerifiable {

	/***************************************
	 * Parameters for configuration
	 ***************************************/
	public final static String PAR_ACTIVE_VIEW_SIZE = "AViewSize";
	public final static String PAR_PASSIVE_VIEW_SIZE = "PViewSize";
	public final static String PAR_PASSIVE_SHUFFLE_LENGHT = "PassiveShuffleL";
	public final static String PAR_ACTIVE_SHUFFLE_LENGHT = "ActiveShuffleL";
	public final static String PAR_PASSIVE_RANDOM_LENGHT = "PassiveRandomL";
	public final static String PAR_RANDOM_LENGHT = "RandomL";
	
	/**** SELF-ADAPTIVE OVERLAY ****/
	public final static String PAR_ADAPT_INTERVAL = "AdaptationInterval";
	public final static String PAR_NOOPTIMIZE_SIZE = "UnoptimizedNeighbours";
	public final static String PAR_SCAN_LENGHT = "ScanLenght";
	public final static String PAR_OPT_THRESHOLD = "OptimizationThreshold";
	
	
	//This will control the overlay that is tested in simulation
	public final static String PAR_MONITORIZATION = "monitor";
	//This are the possibilities to use in the monitor parameter
	public final static String MON_ACTIVE = "active";
	public final static String MON_PASSIVE = "passive";
	//This are the values to the variable that controls this process
	public final static int MON_ACTIVE_VAL = 0;
	public final static int MON_PASSIVE_VAL = 1;
	
	/***************************************
	 * Variables for parameters configuration
	 ***************************************/
	private static String name;
	private static int protocolID;
	
	private static int activeViewSize;
	private static int passiveViewSize;
	private static int passiveShuffleLenght;
	private static int activeShuffleLenght;
	private static int randomLenght;
	private static int passiveRandomLenght;
	
	/**** SELF-ADAPTIVE OVERLAY ****/
	private static int adaptationInterval;
	private static int unoptimizedPeers;
	private static int scanLenght;
	private static long optThreshold;
	
	//For selecting witch overlay to monitor
	private int overlayMonitor;
	
	/***************************************
	 * Internal State of the node protocol
	 ***************************************/
	private Node[] activeMembership;
	private Long[] utilityValues; //Added for the Self-Improving implementation
	private Node[] passiveMembership; //Update 24-10-2006: Changed from AgeableNode to Node
	
	private int activeDegree;
	private int passiveDegree;
	
	private int internalClock; //Added for Self-Improving implementation [25-10-2007]
	
	/*******************************************************
	 * Variables for supporting the MembershipProtocol Interface
	 *******************************************************/
	protected Node myNode;
	protected int msgSent;
	
	/*******************************************************
	 * Other variables
	 *******************************************************/
	private IndexIterator peerIterator;
	ArrayList<Node> sentList;
	
	/*******************************************************
	 * ShuffleObservable variables
	 *******************************************************/
	int shuffleStarted;
	int shuffleEnded;
	int shuffleForwarded;
	
	//for UnderlyingProtocol interface
	private OverlayAwareProtocol aboveProto;
	
	/**********************************************************
	 * OptimizationObservable variables
	 **********************************************************/
	int optimizationsSucceded;
	int optimizationsFailed;
	int optimizationsExecuted;
	int disconnectionsReceived;
	
	/**
	 * Constructor
	 * @param name
	 */
	public XBot(String name) {
		//Read configuration
		XBot.name = name;
		XBot.protocolID = Configuration.lookupPid(name.replaceFirst("protocol.",""));
		XBot.activeViewSize = Configuration.getInt(XBot.name+"."+PAR_ACTIVE_VIEW_SIZE);
		XBot.passiveViewSize = Configuration.getInt(XBot.name+"."+PAR_PASSIVE_VIEW_SIZE);
		XBot.passiveShuffleLenght = Configuration.getInt(XBot.name+"."+PAR_PASSIVE_SHUFFLE_LENGHT);
		XBot.activeShuffleLenght = Configuration.getInt(XBot.name+"."+PAR_ACTIVE_SHUFFLE_LENGHT);
		XBot.randomLenght = Configuration.getInt(XBot.name+"."+PAR_RANDOM_LENGHT);
		XBot.passiveRandomLenght = Configuration.getInt(XBot.name+"."+PAR_PASSIVE_RANDOM_LENGHT);
		
		//Read configuration for the Self Improving mechanisms
		XBot.adaptationInterval = Configuration.getInt(XBot.name+"."+PAR_ADAPT_INTERVAL);
		XBot.unoptimizedPeers = Configuration.getInt(XBot.name+"."+PAR_NOOPTIMIZE_SIZE);
		XBot.scanLenght = Configuration.getInt(XBot.name+"."+PAR_SCAN_LENGHT);
		XBot.optThreshold = Configuration.getLong(XBot.name+"."+PAR_OPT_THRESHOLD);
		
		String monitorizationTarget = Configuration.getString(XBot.name+"."+PAR_MONITORIZATION);
		if(monitorizationTarget.compareTo(MON_ACTIVE) == 0)
			this.overlayMonitor = MON_ACTIVE_VAL;
		else if(monitorizationTarget.compareTo(MON_PASSIVE) == 0)
			this.overlayMonitor = MON_PASSIVE_VAL;
		else {
			System.err.println("Invalid value for the Monitorization parameter.");
			System.exit(1);
		}
		
		//Initialization protocol configuration
		this.activeMembership = new Node[XBot.activeViewSize];
		this.utilityValues = new Long[XBot.activeViewSize];
		for(int i = 0; i < XBot.activeViewSize; i++) {
			this.activeMembership[i] = null;
			this.utilityValues[i] = null;
		}
		
		this.passiveMembership = new Node[XBot.passiveViewSize];
		for(int i = 0; i < XBot.passiveViewSize; i++)
			this.passiveMembership[i] = null;
		
		this.activeDegree = 0;
		this.passiveDegree = 0;
		
		this.internalClock = 0;
		
		//Start other protocol information with default values
		this.myNode = null;
		this.msgSent = 0;
		this.peerIterator = new RandPermutation(CommonState.r);
		this.sentList = null;
		
		//ShuffleObservable
		this.shuffleStarted = 0;
		this.shuffleEnded = 0;
		this.shuffleForwarded = 0;
	
		this.aboveProto = null;
		
		//OptimizationObservable
		this.optimizationsSucceded = 0;
		this.optimizationsFailed = 0;
		this.optimizationsExecuted = 0;
		this.disconnectionsReceived = 0;
	}
	
	/****************************************
	 * Protocol Specific Methods
	 ****************************************/
	
	/**
	 * This is used to generate fixed lenght random walks in the overlay when adding nodes
	 * this assumes no null in between nodes at active view
	 */
	public boolean randomWalk(Node newMember, int ttl, Node originator, int protocolID) {
		boolean status = this.myNode.isUp(); //check if node is up
		
		if(status) {
			//This node is up -> he can (and will) execute protocol
			if(ttl <= 0 || this.activeDegree <= 1) {
				//We first check if we can add the new neighbour to the view and only if we can we do it
				if(this.canAddNeighbour2ActiveMembership(newMember)) {
					//we can and should try to connect to new member
					this.msgSent++; //send a Join Connect
					if(((XBot)newMember.getProtocol(XBot.protocolID)).joinConnect(this.myNode)) {
						
						//If active view is full make a disconnect from someone random
						if(this.activeDegree == XBot.activeViewSize) {
							this.activeRemove();
							this.compressAndOrderArray(this.activeMembership,this.utilityValues);
						}
									
						//Add node to ones current view
						if(!this.activeMembershipAddNeighbour(newMember)) {
							System.err.println("Warning: A random walked stoped here but i could not add the new node: random walk droped!");
						}
					} else {
						//This should not happen
						System.err.println("Warning: A peer i received in a random walk refused my connect atempt");
					}
				}
			} else {
				//Check if this is the middle point of the random walk: if so add this node to the passive membership
				if(ttl == XBot.passiveRandomLenght) {
					if(this.canAddNeighbour2PassiveMembership(newMember)) {					
						this.passiveMembershipAddNeighbour(newMember);
					}
				}
				//Select a valid target to forward this request
				Node destino = null;
				this.peerIterator.reset(this.activeDegree);
				while(destino == null || destino.equals(originator))
					destino = this.activeMembership[this.peerIterator.next()];
			
				this.msgSent++;
				((XBot)destino.getProtocol(protocolID)).randomWalk(newMember, ttl - 1, this.myNode, protocolID);
			}
		} 
		
		return status;
	}
	
	private ArrayList<Node> getLocalPeerList() {
		ArrayList<Node> reply = new ArrayList<Node>();
		
		//Include self identifier in the message
		if(XBot.activeShuffleLenght > 0) {
			reply.add(this.myNode);
		}
		
		if(XBot.activeShuffleLenght > 1) {
			this.compressAndOrderArray(this.activeMembership,this.utilityValues);
			this.peerIterator.reset(this.activeDegree);
			
			for(int i = 0; i < XBot.activeShuffleLenght - 1 && i < this.activeDegree; i++)
				reply.add(this.activeMembership[this.peerIterator.next()]);
		}
		
		if(XBot.passiveShuffleLenght > 0) {
			this.compressArray(this.passiveMembership); //Just to ensure that the nodes are "compressed" in the begining of the view...
			this.peerIterator.reset(this.passiveDegree);
		
			for(int i = 0; i < XBot.passiveShuffleLenght && i < this.passiveDegree; i++)
				reply.add(this.passiveMembership[this.peerIterator.next()]);
		}
		return reply;
	}
	
	private ArrayList<Node> getLocalPeerList(int maxSize) {
		ArrayList<Node> reply = new ArrayList<Node>();
		
		this.compressArray(this.passiveMembership); //Just to ensure that the nodes are "compressed".
		this.peerIterator.reset(this.passiveDegree);
		
		for(int i = 0; i < maxSize && i < this.passiveDegree; i++)
			reply.add(this.passiveMembership[this.peerIterator.next()]);
		
		return reply;
	}
	
	private void filterList(ArrayList<Node> peerList) {
		for(int i = 0; i < peerList.size(); i++) {
			if(this.myNode.equals(peerList.get(i)) || this.activeContains(peerList.get(i)) || this.passiveContains(peerList.get(i))) {
				peerList.remove(i);
				i--;
			}
		}
	}
	
	private void mergeView(ArrayList<Node> myList, ArrayList<Node> peerList) {
		//Preparation: Create a copy (local) of my passiveView
		ArrayList<Node> passiveMembershipLocalCopy = new ArrayList<Node>();
		for(int i = 0; i < XBot.passiveViewSize; i++)
			if(this.passiveMembership[i] != null)
				passiveMembershipLocalCopy.add(this.passiveMembership[i]);
		
		
		//Clean myList of elements not present in my passive view (myself or members of my active view)
		for(int i = 0; i < myList.size(); i++)
			if(!this.passiveContains(myList.get(i))) {
				myList.remove(i);
				i--;
			}
		
		while(this.passiveDegree < XBot.passiveViewSize && peerList.size() > 0) {
			this.passiveMembershipAddNeighbour(peerList.remove(0));
		}
				
		Node toRemove = null;
		while(peerList.size() > 0) {
			if(myList.size() > 0) {
				toRemove = myList.remove(0);
				this.passiveRemove(toRemove);
				passiveMembershipLocalCopy.remove(toRemove);
			} else {
				//Select a random element that was present in the passive view at the start of this operation
				this.peerIterator.reset(passiveMembershipLocalCopy.size());
				this.passiveRemove(passiveMembershipLocalCopy.remove(this.peerIterator.next()));
			}
			this.passiveMembershipAddNeighbour(peerList.remove(0));
		}
	}
	
	/**
	 * This is to be called by a peer that wishes to add this node to his active view
	 * this should be called when this operation is done in the context of a Join Request 
	 * (A node is joining to the overlay)
	 */
	public Boolean joinConnect(Node peer) {
		Boolean status = null;
		
		if(this.myNode.isUp()) {
			if(this.activeDegree == XBot.activeViewSize) {
				//Drop someone so that we can add this new node
				this.activeRemove();
				this.compressAndOrderArray(this.activeMembership,this.utilityValues);
			}
			
			status = new Boolean(this.activeMembershipAddNeighbour(peer));
		
			this.msgSent++; //Sent a reply to peer
		}
		
		return status;
	}
	
	/**
	 * This is to be called by a peer that wishes to add this node to his active view
	 * this should be called when this operation is done in the context of a Join Request 
	 * (A node is joining to the overlay)
	 */
	public Boolean neighbourConnect(Node peer) {
		Boolean reply = null;
				
		if(this.myNode.isUp()) {
			if(this.activeDegree < XBot.activeViewSize) {
				reply = new Boolean(this.activeMembershipAddNeighbour(peer));
			} else {
				reply = new Boolean(false);
			}
			
			this.msgSent++; //sent a reply to peer
		}
		
		return reply;
	}
	
	/**
	 * 
	 */
	public boolean shuffleReply(ArrayList<Node> peerReply) {
		boolean reply = this.myNode.isUp();
		
		if(reply) {
			this.filterList(peerReply);
			this.mergeView(this.sentList, peerReply);
		}
		
		return reply;
	}
	
	/**
	 * This is to be called by a peer that wishes to close a connection in the active membership
	 */
	public void disconnect(Node peer) {
		if(this.myNode.isUp()) {
			//Counting for metrics
			this.disconnectionsReceived++;	
		} else 	
			return;
		
		int position = -1;
		
		for(int i = 0; position == -1 && i < XBot.activeViewSize && i < activeMembership.length; i++ )
			if(this.activeMembership[i] != null && this.activeMembership[i].equals(peer))
				position = i;
	
		if(position != -1) {
			Node temp = this.activeMembership[position];
			this.activeMembership[position] = null;
			this.utilityValues[position] = null;
			this.activeDegree--;
			this.compressAndOrderArray(this.activeMembership,this.utilityValues);
			this.passiveMembershipAddNeighbour(temp); //22-November-2006
			this.nodeDownNotification(temp);
		} else {
			System.err.println("Warning: Received a disconnect notification from someone i am not neighbour");
		}
	}
	
	/**
	 * This method is used to run the optimization procedure associated with the
	 * self improving interface
	 * 
	 */
	
	private void runOptimizationProcedure() {
		//Generate a temporary list of passive neighbours.
		ArrayList<Node> candidates = new ArrayList<Node>();
		this.peerIterator.reset(this.passiveDegree);
		for(int i = 0; i < this.passiveDegree; i++) {
			candidates.add(this.passiveMembership[this.peerIterator.next()]);
		}
		
		int startPoint = XBot.unoptimizedPeers;
		
		for(int i = 0; i < this.passiveDegree && i < XBot.scanLenght && startPoint < XBot.activeViewSize; i++) {
			Node c = candidates.remove(0);
			long utilityFunction = Oracle.utility(this.myNode, c);
		
			if(this.utilityValues[startPoint].longValue() > (utilityFunction + XBot.optThreshold)) {
				//This is an indication that we should trigger the optimization procedure between these nodes
				this.optimizationsExecuted++;
				
				//The node we will trade in our active view.
				Node toTrade = this.activeMembership[startPoint];
				
				//We start by making space in the passive view...				
				this.passiveRemove(c);				
				
				//We check if this peer wants to become our active neighbour, to that end we state which node we will disconnect.
				NCStatus status = ((SelfImprovable)c.getProtocol(XBot.protocolID)).neighbourConnect(this.myNode, toTrade);
				this.msgSent++; //Sent a request for optimization...
				
				if(status == null) {
					//The peer have failed, therefore we don't need to do anything.
					this.optimizationsFailed++;
				} else if( status.booleanValue() && status.getReplacementNode() == null ) {
					//The peer accepted to become our active neighbour and did not drop any node
					
					//First we disconnect our former active neighbor
					((XBot)toTrade.getProtocol(XBot.protocolID)).disconnect(this.myNode);
					this.msgSent++; //Increase message sent because of the disconnect message
					this.activeMembership[startPoint] = null;
					this.utilityValues[startPoint] = null;
					this.activeDegree--;
					
					//Replace it with our new neighbour
					this.activeMembershipAddNeighbour(c);

					//Sucess in the operation
					startPoint++;
					this.optimizationsSucceded++;
				} else if( status.booleanValue() && status.getReplacementNode() != null) {
					//The peer accepted to become our active neighbour and he did disconnect a node to become our neighbor
					
					//we require to disconnect the old active neighbour we do so, but we should not have to.)
					if(this.activeContains(toTrade)) {
						System.err.println("Warning: Had to make an explicit disconnect for a trade neighbour in an optimization step.");
						((XBot)toTrade.getProtocol(XBot.protocolID)).disconnect(this.myNode);
						this.msgSent++; //Increase message sent because of the disconnect message
						this.activeMembership[startPoint] = null;
						this.utilityValues[startPoint] = null;
						this.activeDegree--;
					}
					
					this.activeMembershipAddNeighbour(c);
					//Sucess
					startPoint++;
					this.optimizationsSucceded++;
				} else {
					//The peer refused to become our active neighbour -> do nothing
					this.optimizationsFailed++;
				}
			}
		}
		this.compressAndOrderArray(this.activeMembership, this.utilityValues);
	}
	
	/**
	 * This function is used by the node to transfer (if possible) nodes from his passive view to his active view)
	 *
	 */
	private void refillActiveView() {
		ArrayList<Node> candidates = new ArrayList<Node>();
		this.peerIterator.reset(this.passiveDegree);
		for(int i = 0; i < this.passiveDegree; i++) {
			candidates.add(this.passiveMembership[this.peerIterator.next()]);
		}
		
		while(this.activeDegree < XBot.activeViewSize && candidates.size() > 0) {
			Node c = candidates.remove(0);
			Boolean cReply = null;
			
			if(this.activeDegree == 0)
				cReply = ((XBot)c.getProtocol(XBot.protocolID)).joinConnect(this.myNode);
			else
				cReply = ((XBot)c.getProtocol(XBot.protocolID)).neighbourConnect(this.myNode);
		
			this.msgSent++; //Sent a neighboring request.
			
			if(cReply == null) {
				//The peer is down...
				this.passiveRemove(c);
			} else if(cReply.booleanValue()) {
				//The peer has accepted me in his membership
				this.passiveRemove(c);
				if(!this.activeMembershipAddNeighbour(c)) {
					//This should not happen... anyway... let's do the correct action in this case...
					System.err.println("Warning: I could not add a node to my active view that has acepted me in his active view [operation: refillActiveView]");
					this.passiveMembershipAddNeighbour(c);
					
					this.msgSent++; //Sent a Disconnect request.
					((XBot)c.getProtocol(XBot.protocolID)).disconnect(this.myNode);
				}
			} else {
				//The peer has refused to accept me to the membership
			}
		}
	}
	
	/**
	 * This function verifies witch members of my active view are now in TCP timeout
	 *
	 */
	public void verifyLiveliness(int protocolID) {
		if(!this.myNode.isUp())
			return;
		
		for(int i = 0; i < XBot.activeViewSize; i++) {
			if(this.activeMembership[i] != null && !this.activeMembership[i].isUp()) {
				this.nodeDownNotification(this.activeMembership[i]);
				this.activeMembership[i] = null;
				this.utilityValues[i] = null;
				this.activeDegree--;
			}
		}
		
		this.compressAndOrderArray(this.activeMembership, this.utilityValues);
	}
	
	/**
	 * This function validates if a given node can be added to the current active membership
	 */
	private boolean canAddNeighbour2ActiveMembership(Node neighbour) {
		return !this.activeContains(neighbour) && !this.myNode.equals(neighbour);
	}
	
	/**
	 * This function validates if a given node can be added to the current passive memberhip
	 */
	private boolean canAddNeighbour2PassiveMembership(Node neighbour) {
		return !this.activeContains(neighbour) && !this.passiveContains(neighbour) && !this.myNode.equals(neighbour);
	}
	
	
	/**
	 * Add's this node to the active membership checking the associated constraints
	 */
	private boolean activeMembershipAddNeighbour(Node neighbour) {
		boolean sucess = false;
		
		if(this.canAddNeighbour2ActiveMembership(neighbour) && this.activeDegree < XBot.activeViewSize)
			for(int i = 0; !sucess && i < XBot.activeViewSize; i++) {
				if(this.activeMembership[i] == null) {
					this.activeMembership[i] = neighbour;
					this.utilityValues[i] = Oracle.utility(this.myNode,neighbour);
					this.activeDegree++;
					
					//Guarantee that the node is not in the passive membership
					this.passiveRemove(neighbour);
					
					sucess = true;
				}
			}
		
		if(sucess) {
			this.nodeUpNotification(neighbour);
		}
		
		return sucess;
	}
	
	/**
	 * Add's this node to the passive membership checking the associated constraints
	 */
	private boolean passiveMembershipAddNeighbour(Node neighbour){
		boolean sucess = false;
		
		if(this.canAddNeighbour2PassiveMembership(neighbour)) {
			if(this.passiveDegree < XBot.passiveViewSize) {
				//Insert member in a free slot
				int i = 0;
				while(this.passiveMembership[i] != null)
					i++;
				this.passiveMembership[i] = neighbour;
				this.passiveDegree++;
			} else {
				//Select random member to drop 
				this.peerIterator.reset(XBot.passiveViewSize);
				this.passiveMembership[this.peerIterator.next()] = neighbour;
				System.err.println("Warning: random member droped in passive view");
			}
			sucess = true;
		}
		
		return sucess;
	}
	
	/**
	 * Check's if a node is present in the active membership of this node
	 */
	private boolean activeContains(Node neighbour) {
		boolean found = false;
		
		for(int i = 0; !found && i < XBot.activeViewSize; i++)
			found = this.activeMembership[i] != null && this.activeMembership[i].equals(neighbour);
		
		return found;
	}

	/**
	 * Check's if a node is present in the passive membership of this node
	 */
	private boolean passiveContains(Node neighbour) {
		boolean found = false;
		
		for(int i = 0; !found && i < XBot.passiveViewSize; i++)
			found = this.passiveMembership[i] != null && this.passiveMembership[i].equals(neighbour);
		
		return found;
	}
	
	/**
	 * Remove the given node from the active view of this node if it's present
	 * We should be careful with this method, because there should always be 
	 * symmetric membership when we speak of active membership (after all it should be running TCP)
	 */
	private boolean activeRemove(Node neighbour) {
		boolean found = false;
		int i = 0;
		
		for(i = 0; !found && i < XBot.activeViewSize; i++) {
			found = this.activeMembership[i] != null && this.activeMembership[i].equals(neighbour);
		}
		
		//The for cycle will increment one extra unit during the final test of the found variable
		if(found) {
			((XBot)this.activeMembership[i-1].getProtocol(XBot.protocolID)).disconnect(this.myNode);
			this.msgSent++; //Increase message sent because of the disconnect message
			
			this.nodeDownNotification(this.activeMembership[i-i]);
			
			this.activeMembership[i-1] = null;
			this.utilityValues[i-1] = null;
			this.compressAndOrderArray(this.activeMembership, this.utilityValues);
			this.activeDegree--;
		}
			
		return found;
	}
	
	/**
	 * Remove a random node from the active membership
	 * it notifies the node with a disconnect message
	 * @return
	 */
	private boolean activeRemove() {
		this.peerIterator.reset(this.activeDegree);
		int target = this.peerIterator.next();
		this.compressAndOrderArray(this.activeMembership, this.utilityValues);
		((XBot)this.activeMembership[target].getProtocol(XBot.protocolID)).disconnect(this.myNode);
		this.msgSent++; //Increase message sent because of the disconnect message
		
// 		Remember who i removed...		
		Node removed = this.activeMembership[target];
//		Remove this node from the active view
		this.activeMembership[target] = null;
		this.utilityValues[target] = null;
		this.compressAndOrderArray(this.activeMembership, this.utilityValues);
		this.activeDegree--;

		this.nodeDownNotification(removed);

		//Pass this node to my passive view
		if(this.canAddNeighbour2PassiveMembership(removed)) {
			this.passiveMembershipAddNeighbour(removed);
		}		
		
		return true;
	}
	
	/**
	 * Remove the given node from the passive view of this node if it's present
	 */
	private boolean passiveRemove(Node neighbour) {
		boolean found = false;
		int i = 0;
		
		for(i = 0; !found && i < XBot.passiveViewSize; i++) {
			found = this.passiveMembership[i] != null && this.passiveMembership[i].equals(neighbour);
		}

		//The for cycle will increment one extra unit during the final test of the found variable	
		if(found) {
			this.passiveMembership[i-1] = null;
			this.passiveDegree--;
			this.compressArray(this.passiveMembership);
		}
			
		return found;
	}
	
	@SuppressWarnings("unused")
	private boolean passiveRemove() {
		this.peerIterator.reset(this.passiveDegree);
		int target = this.peerIterator.next();
		this.compressArray(this.passiveMembership);
		this.passiveMembership[target] = null;
		this.compressArray(this.passiveMembership);
		this.passiveDegree--;
		
		return true;
	}
	
	/****************************************
	 * Generic Java Methods
	 ****************************************/
	
	public Object clone() {
		XBot nhm = null;
		try {
			nhm = (XBot) super.clone();
//			Set the variables of the new instance, doing a deep cloning...
			nhm.activeMembership = new Node[XBot.activeViewSize];
			nhm.utilityValues = new Long[XBot.activeViewSize];
			for(int i = 0; i < XBot.activeViewSize; i++) {
				nhm.activeMembership[i] = null;
				nhm.utilityValues[i] = null;
			}
			nhm.passiveMembership = new Node[XBot.passiveViewSize];
			for(int i = 0; i < XBot.passiveViewSize; i++)
				nhm.passiveMembership[i] = null;
			nhm.activeDegree = 0;
			nhm.passiveDegree = 0;
			nhm.myNode = null;
			nhm.msgSent = 0;
			nhm.sentList = null;
			nhm.peerIterator = new RandPermutation(CommonState.r); //Change Log: 13-11-2006:Jleitao Notei que falhava esta coisa...
		
			nhm.internalClock = 0;
			
			nhm.shuffleStarted = 0;
			nhm.shuffleEnded = 0;
			nhm.shuffleForwarded = 0;
			
			nhm.aboveProto = null;
			
			nhm.optimizationsSucceded = 0;
			nhm.optimizationsFailed = 0;
			nhm.optimizationsExecuted = 0;
			nhm.disconnectionsReceived = 0;
			
		} catch (CloneNotSupportedException e) {
			//never happens
		}
		return nhm;
	}
	
	/****************************************
	 * Interface CDProtocol
	 ****************************************/
	
	@SuppressWarnings("unchecked")
	public void nextCycle(Node node, int protocolID) {
		if(this.myNode.isUp()) {
		
			//We assume that by now every node that failed during the last cycle time, has given a timeout
			this.verifyLiveliness(protocolID);
			
			//The Cycle based simulation might not be the best model to use in this algorithm
			if(this.activeDegree > 0) {
				this.sentList = this.getLocalPeerList();
				ArrayList<Node> myList2Send = (ArrayList<Node>) this.sentList.clone();
			
				this.peerIterator.reset(this.activeDegree);
				Node destino = this.activeMembership[this.peerIterator.next()];
		
				this.msgSent++; //Sent a Shuffle
				boolean peerReply = ((XBot)destino.getProtocol(XBot.protocolID)).shuffle(myList2Send, this.myNode, this.myNode, 0);
				if(!peerReply) {
					//Peer didn't reply
					this.activeRemove(destino);
					this.msgSent--; //We will count with a disconnet msg, but in this scenario it is not required.
				}
			
				//ShuffleObservable
				this.shuffleStarted++;
			
			}
		
			//This is the mechanism used to improve the overlay network.
			this.internalClock++;
			
			if(this.internalClock == XBot.adaptationInterval) {
				
				//Only try to optimize if you have a full view
				if(this.activeDegree == XBot.activeViewSize)
					this.runOptimizationProcedure();
				
				this.internalClock = 0;
			}
			
		
			//This method add members to the active view using nodes from the passive view
			if(this.activeDegree < XBot.activeViewSize && this.passiveDegree > 0)
				this.refillActiveView();
		}
	}

	/****************************************
	 * Interface Linkable
	 ****************************************/

	public int degree() {
		if(this.overlayMonitor == MON_ACTIVE_VAL)
			return this.activeDegree;
		else
			return this.passiveDegree;
	}

	public Node getNeighbor(int i) {
		if(this.overlayMonitor == MON_ACTIVE_VAL)
			return this.activeMembership[i];
		else {
			return this.passiveMembership[i];
		}
	}
	
	public boolean addNeighbor(Node neighbour) {
		if(this.overlayMonitor == MON_ACTIVE_VAL)
			return this.activeMembershipAddNeighbour(neighbour);
		else
			return this.passiveMembershipAddNeighbour(neighbour);
	}

	public boolean contains(Node neighbor) {
		if(this.overlayMonitor == MON_ACTIVE_VAL)
			return this.activeContains(neighbor);
		else
			return this.passiveContains(neighbor);
	}

	public void pack() {
		//nothing to do...
	}
	
	public void onKill() {
		this.activeMembership = new Node[0];
		this.passiveMembership = new Node[0];
		this.utilityValues = new Long[0];
		this.activeDegree = 0;
		this.passiveDegree = 0;
	}
	/****************************************
	 * MembershipProtocol
	 ****************************************/

	/**
	 * @deprecated
	 */
	public void setMyId(int myID) {
		return;
	}
	
	public Object shuffle(Object target, int protocolID, int round) {
		return null;
	}
	
	@SuppressWarnings("unchecked")
	public boolean shuffle(Object target, Node sender, Node peer, int round) {
		if(this.myNode.isUp()) {
		
			int minimumActiveDegreeRequired = 1;
			
			if(!sender.equals(peer) && this.activeContains(sender))
				minimumActiveDegreeRequired = 2;
			
			if(round >= XBot.passiveRandomLenght || this.activeDegree == minimumActiveDegreeRequired) {
				//The random walk will stop here... generate list to send, and do the merge
				ArrayList <Node> peerList = (ArrayList<Node>) target;
				this.sentList = this.getLocalPeerList(peerList.size());
				ArrayList <Node> myList2Send = (ArrayList<Node>) this.sentList.clone();
			
				this.filterList(peerList);
		
				this.mergeView(this.sentList, peerList);

				boolean peerReply = ((XBot)sender.getProtocol(XBot.protocolID)).shuffleReply(myList2Send);
				this.msgSent++; //sent shuffle reply
				
				if(!peerReply) {
					this.passiveRemove(sender);
					int found = -1;
					for(int i = 0; found == -1 && i < XBot.activeViewSize; i++)
						if(this.activeMembership[i] != null && this.activeMembership[i].equals(sender))
							found = i;
					
					if(found != -1) {
						this.nodeDownNotification(this.activeMembership[found]);
						
						this.activeMembership[found] = null;
						this.utilityValues[found] = null;
						this.activeDegree--;
						this.compressAndOrderArray(this.activeMembership, this.utilityValues);
					}
				}
				
				//ShuffleObservable
				this.shuffleEnded++;
				
			} else {
				//Forward randomly this shuffle to other node :D
				Node destino = null;
				this.peerIterator.reset(this.activeDegree);
				
				while(destino == null || destino.equals(sender) || destino.equals(peer))
					destino = this.activeMembership[this.peerIterator.next()];
				
				boolean peerReply = ((XBot)destino.getProtocol(XBot.protocolID)).shuffle(target, sender, this.myNode, round + 1);
				this.msgSent++; //forwarded shuffle
				
				if(!peerReply) {
					//Peer didn't reply
					int found = -1;
					for(int i = 0; found == -1 && i < XBot.activeViewSize; i++)
						if(this.activeMembership[i] != null && this.activeMembership[i].equals(destino))
							found = i;
					
					if(found != -1) {
						this.nodeDownNotification(this.activeMembership[found]);
						
						this.activeMembership[found] = null;
						this.utilityValues[found] = null;
						this.activeDegree--;
						this.compressAndOrderArray(this.activeMembership, this.utilityValues);
					}		
				}
				
//				ShuffleObservable
				this.shuffleForwarded++;
			}
			return true;
		} else {
			return false; //To notify that this node is down...
		} 
	}
	
	
	/**
	 * join method.
	 * This method is invoked by a controller that simulates the initialization of the overlay.
	 * The simulator will pass to the contact node (a node already present in the overlay) the information of
	 * the joining node. In this method the algorithm to be executed by the contact node should be implemented.
	 * 
	 * One interesting concept of the Hybrid Membership Protocol is that we must run to join protocols
	 * One for the active overlay and other in the passive overlay
	 */
	public void join(Node newMember, int protocolID) {
		int position = 0;
		
		//Number of forwarded joins should be the minimum of this two values
		int tosend = (this.activeDegree <= (XBot.activeViewSize - 1) ? this.activeDegree : (XBot.activeViewSize - 1));
		boolean status = false;
		
		//Because our local view can change (e.g. some neighbour drops a connection to us)
		ArrayList<Node> peersSelected = new ArrayList<Node>();
		
		this.peerIterator.reset(this.activeDegree);
		
		for(int i = 0; i < tosend; i++)
			peersSelected.add(this.activeMembership[this.peerIterator.next()]);
		
		while(peersSelected.size() > 0) {
			Node peer = peersSelected.remove(0);
			status = ((XBot)peer.getProtocol(protocolID)).randomWalk(newMember,XBot.randomLenght,myNode,protocolID);
			this.msgSent ++; //Increase the number of messages sent by this node
			
			if(!status) {
				this.activeRemove(peer);
			}
		}
		
		//Now try to connect to new member
		this.msgSent++; //Send a Join Connect
		if(((XBot)newMember.getProtocol(XBot.protocolID)).joinConnect(this.myNode).booleanValue()) {
			
			if(this.activeDegree == XBot.activeViewSize) {
				//We have to replace a member, and notify him to establish a new connection to new member :D
				peerIterator.reset(XBot.activeViewSize);
				position = peerIterator.next();
				((XBot) this.activeMembership[position].getProtocol(XBot.protocolID)).disconnect(this.myNode);
				this.nodeDownNotification(this.activeMembership[position]);
				this.msgSent++; //number of messages rise cause of disconnect message (maybe this should not happen)
			} else {
				while(this.activeMembership[position] != null)
					position ++;
				this.activeDegree++;
			}
		
			this.activeMembership[position] = newMember;
			this.utilityValues[position] = Oracle.utility(this.myNode, newMember);
		
			this.nodeUpNotification(newMember);
		} else  {
			System.err.println("Warning: Connection to new member failed");
		}
	}

	public Node[] neighbors() {
		Node[] answer;
		int i = 0, j = 0;
		
		if(this.overlayMonitor == MON_ACTIVE_VAL) {
			answer = new Node[this.activeDegree];
			while(i < this.activeDegree) {
				while(this.activeMembership[j] == null)
					j++;
				answer[i] = this.activeMembership[j];
				i++;
				j++;
			}
		} else {
			answer = new Node[this.passiveDegree];
			while(i < this.passiveDegree) {
				while(this.passiveMembership[j] == null)
					j++;
				answer[i] = this.passiveMembership[j];
				i++;
				j++;
			}
		}
	
		return answer;
	}
	
	public int getViewSize() {
		if(this.overlayMonitor == MON_ACTIVE_VAL)
			return XBot.activeViewSize;
		else
			return XBot.passiveViewSize;
	}
	
	public void setMyNode(Node me) {
		this.myNode = me;
	}
	
	public int getSentMsg() {
		int reply = this.msgSent;
		this.msgSent = 0;
		return reply;
	}
	
	public Node getGossipTarget(int i) {
		return this.getNeighbor(i);
	}
	
	/********************************************
	 * SelfImprovable methods
	 ********************************************/	
	
	/**
	 * This is to be called by a peer that wishes to close a connection in the active membership
	 * for purposes of an optimization. replacement is a node that has also been disconnected due to 
	 * this optimization step and therefore can be used to replace the lost link in the overlay.
	 */
	public Boolean disconnect(Node peer, Node replacement, Node mediator) {
		
		Boolean answer = null;
		
		if(this.myNode.isUp()) {
		
			//Counting for metrics
			this.disconnectionsReceived++;	
			answer = new Boolean(false);
			
			this.msgSent++; //Have to send a reply to peer
			
			if(!this.activeContains(peer) || !this.canAddNeighbour2ActiveMembership(replacement))
				return answer;
			
			if(! (Oracle.utility(this.myNode, peer) > (Oracle.utility(this.myNode, replacement) + XBot.optThreshold)) )
				return answer;
			
			this.msgSent++; //sent a special neighboring request.
			Boolean status = ((SelfImprovable)replacement.getProtocol(XBot.protocolID)).neighbourConnectReplace(this.myNode, mediator);
			
			if(status == null) {
				//Do Nothing and fail the operation
			} else {
				if(!status.booleanValue()) { 
					this.passiveMembershipAddNeighbour(replacement); //Should never happen
					System.err.println("Warning: incorrect state achieved in special disconnect method.");
				}  else {
					int position = -1;
					
					for(int i = 0; position == -1 && i < XBot.activeViewSize && i < activeMembership.length; i++ )
						if(this.activeMembership[i] != null && this.activeMembership[i].equals(peer))
							position = i;
				
					if(position != -1) {
						this.activeMembership[position] = null;
						this.utilityValues[position] = null;
						this.activeDegree--;
						this.passiveMembershipAddNeighbour(peer); //22-November-2006
						answer = new Boolean(this.activeMembershipAddNeighbour(replacement));
					} else {
						System.err.println("Warning: Could not add my new neighbor <FAILURE>");
						((XBot) replacement.getProtocol(XBot.protocolID)).disconnect(this.myNode);
						this.msgSent++; //Sent a disconnect request
						answer = new Boolean(false);
					}
				}	
			}
		
			this.compressAndOrderArray(this.activeMembership, this.utilityValues);
			
		}
		
		return answer;
	}
	
	/**
	 * This solver concurrent and cyclic invocations to the method disconnect, when
	 * trying to make an optimization of the overlay structure.
	 */
	public Boolean concurrentDisconnect(Node peer) {
		Boolean answer = null;
		
		if(this.myNode.isUp()) {
			answer = new Boolean(false);
			
			int position = -1;
			
			for(int i = 0; position == -1 && i < XBot.activeViewSize && i < activeMembership.length; i++ )
				if(this.activeMembership[i] != null && this.activeMembership[i].equals(peer))
					position = i;
		
			if(position != -1) {
				this.activeMembership[position] = null;
				this.utilityValues[position] = null;
				this.activeDegree--;
				this.passiveMembershipAddNeighbour(peer); //22-November-2006
				answer = new Boolean(true);
			} else {
				System.err.println("Warning: Received a concurrent disconnect notification from someone i am not neighbour");
			}
		}
		
		return answer;
	}
	
	public NCStatus neighbourConnect(Node peer, Node replace) {
		
		NCStatus reply = null;
		
		if(this.myNode.isUp()) {
			reply = new NCStatus(false,null);
			Node drop = null;
			Boolean status = null;
			
			if(this.activeDegree == XBot.activeViewSize) {
				//There is no space
				drop = this.activeMembership[XBot.unoptimizedPeers]; 
				
				status = ((XBot)drop.getProtocol(XBot.protocolID)).disconnect(this.myNode, replace, peer); 
				this.msgSent++; //sent a special disconnect request
				
				if(status != null && status.booleanValue()) {
					this.activeMembership[XBot.unoptimizedPeers] = null;
					this.utilityValues[XBot.unoptimizedPeers] = null;
					this.activeDegree--;
				} else {
					return reply;
				}
			}
			
			this.msgSent++; //Sent a answer to peer
			reply = new NCStatus(this.activeMembershipAddNeighbour(peer),drop);
				
			this.compressAndOrderArray(this.activeMembership, this.utilityValues); 
		}
		
		return reply;
	}
	
	
	public Boolean neighbourConnectReplace(Node peer, Node replace) {
		Boolean reply = null;
		
		if(this.myNode.isUp()) {
			
			this.msgSent++; //Have to send a reply to peer.
			
			if(this.activeContains(replace) && this.canAddNeighbour2ActiveMembership(peer)) {
			
				reply = new Boolean(true);
				
				boolean found = false;
				int i = 0;
				
				for(i = 0; !found && i < XBot.activeViewSize; i++) {
					found = this.activeMembership[i] != null && this.activeMembership[i].equals(replace);
				}
				
				//The for cycle will increment one extra unit during the final test of the found variable
				if(found) {
					reply = ((XBot)this.activeMembership[i-1].getProtocol(XBot.protocolID)).concurrentDisconnect(this.myNode);
					if(reply == null || reply.booleanValue()) {
						this.msgSent++; //Increase message sent because of the special disconnect message
						this.activeMembership[i-1] = null;
						this.utilityValues[i-1] = null;
						this.activeDegree--;
					} else {
						return reply;
					}
				} else {
					return new Boolean(false);
				}
									
				reply = new Boolean(this.activeMembershipAddNeighbour(peer));
				
				this.compressAndOrderArray(this.activeMembership, this.utilityValues);
			} else {
				System.err.println("Warning: Could not replace neighbor. Wither replace node not in active view or peer already in active view.");
				
				reply = new Boolean(false);
			}
		}
		
		return reply;
	}
	
	/********************************************
	 * Failable methods
	 ********************************************/
	
	public void fail() {
		this.activeMembership = new Node[XBot.activeViewSize];
		this.utilityValues = new Long[XBot.activeViewSize];
		this.passiveMembership = new Node[XBot.passiveViewSize];
		for(int i = 0; i < XBot.activeViewSize; i++) {
			this.activeMembership[i] = null;
			this.utilityValues[i] = null;
		}
		for(int i = 0; i < XBot.passiveViewSize; i++)
			this.passiveMembership[i] = null;
		this.activeDegree = 0;
		this.passiveDegree = 0;
		
		this.myNode.setFailState(Node.DEAD);
	}
	
	/********************************************
	 * Auxiliary methods
	 ********************************************/
	
	
	/**
	 * This method should clear a array of all null positions, in a way that all not null entrys should be
	 * in the start of the array, the logical order of the nodes is maintained
	 */
	protected void compressArray(Object[] array) {
		Object[] temp = new Object[array.length];
		int position = 0;
		
		for(int i = 0; i < array.length; i++) {
			if(array[i] != null) {
				temp[position] = array[i];
				position++;
			}
		}
		
		for(; position < temp.length; position++)
			temp[position] = null;
		
		System.arraycopy(temp, 0, array, 0, array.length);	
	}
	
	/**
	 * This method should clear 2 arrays of all null positions, in a way that all not null entrys should be
	 * in the start of the array, the logical order of the nodes is maintained in both arrays
	 */
	
	protected void compressAndOrderArray(Object[] array, Long values[]) {
		Object[] temp = new Object[array.length];
		Long[] temp2 = new Long[array.length];
		
		int position = 0;
		
		for(int i = 0; i < array.length; i++) {
			if(array[i] != null) {
				temp[position] = array[i];
				temp2[position] = values[i];
				position++;
			}
		}
		
		for(; position < temp.length; position++) {
			temp[position] = null;
			temp2[position] = null;
		}
		
		Object move1 = null;
		Long move2 = null;
		
		for(int i = 1; i < temp2.length && temp2[i] != null; i++) {
			if(temp2[i] > temp2[i-1]) {
				move1 = temp[i-1];
				move2 = temp2[i-1];
				temp[i-1] = temp[i];
				temp2[i-1] = temp2[i];
				temp[i] = move1;
				temp2[i] = move2;
				i = 0;
			}
		}
		
		System.arraycopy(temp, 0, array, 0, array.length);
		System.arraycopy(temp2, 0, values, 0, values.length);
	}
	
	public void setMonitorActive() {
		this.overlayMonitor = MON_ACTIVE_VAL;
	}
	
	public void setMonitorPassive() {
		this.overlayMonitor = MON_PASSIVE_VAL;
	}
	
	/********************************************
	 * ShuffleObservable methods
	 ********************************************/
	
	public int shufflesEnded() {
		int value = this.shuffleEnded;
		this.shuffleEnded = 0;
		return value;
	}

	public int shufflesForwarded() {
		int value = this.shuffleForwarded;
		this.shuffleForwarded = 0;
		return value;
	}

	public int shufflesStarted() {
		int value = this.shuffleStarted;
		this.shuffleStarted = 0;
		return value;
	}

	/**
	 * For interface UnderlyingProtocol
	 */
	
	public void registerProtocol(OverlayAwareProtocol proto) {
		this.aboveProto = proto;
	}

	private void nodeDownNotification(Node n) {
		if(this.aboveProto != null)
			this.aboveProto.neighborDownNotification(n);
	}
	
	private void nodeUpNotification(Node n) {
		if(this.aboveProto != null)
			this.aboveProto.newNeighborNotification(n);
	}
	
	/***************************************************
	 * OptimizationObservable
	 ***************************************************/
	
	public int disconnectionsReceived() {
		int value;
		value = this.disconnectionsReceived;
		this.disconnectionsReceived = 0;
		return value;
	}

	public long mediumCost() {
		long sum = 0;
		for(int i = 0; i < this.activeDegree; i++)
			if(this.activeMembership[i] != null)
				sum += Oracle.perfectUtility(this.myNode,this.activeMembership[i]);
		
		if(this.activeDegree == 0)
			return 0;
		else 
			return (long) sum / this.activeDegree;
	}

	public long mediumCostNonOptimized() {
		long sum = 0;
		for(int i = 0; i < XBot.unoptimizedPeers; i++)
			if(this.activeMembership[i] != null)
				sum += Oracle.perfectUtility(this.myNode,this.activeMembership[i]);
		
		if(this.activeDegree == 0 || XBot.unoptimizedPeers == 0)
			return 0;
		else 
			return (long) sum / XBot.unoptimizedPeers;
	}

	public long mediumCostOptimized() {
		long sum = 0;
		for(int i = XBot.unoptimizedPeers; i < this.activeDegree; i++)
			if(this.activeMembership[i] != null)
				sum += Oracle.perfectUtility(this.myNode,this.activeMembership[i]);
		
		if(this.activeDegree - XBot.unoptimizedPeers <= 0)
			return 0;
		else 
			return (long) sum / (this.activeDegree - XBot.unoptimizedPeers);
	}

	public int optimizationsExecuted() {
		int value;
		value = this.optimizationsExecuted;
		this.optimizationsExecuted = 0;
		return value;
	}

	public int optimizationsFailed() {
		int value;
		value = this.optimizationsFailed;
		this.optimizationsFailed = 0;
		return value;
	}

	public int optimizationsSucceded() {
		int value;
		value = this.optimizationsSucceded;
		this.optimizationsSucceded = 0;
		return value;
	}

	public long getOwnedLinksCost() {
		long costForNodesAbove = 0;
		
		for(Node n: this.activeMembership) {
			if(n != null && n.getID() > this.myNode.getID())
				costForNodesAbove += Oracle.perfectUtility(this.myNode, n).longValue();
		}
		
		return costForNodesAbove;
	}

	public long getOwnedLinksCount() {
		long count = 0;
		
		for(Node n: this.activeMembership) {
			if(n != null && n.getID() > this.myNode.getID())
				count++;
		}
		
		return count;
	}
	
	@SuppressWarnings("unused")
	private void debugActiveView() {
		System.out.print(this.myNode + " Active View is: ");
		for(int i = 0; i < XBot.activeViewSize; i++) {
			System.out.print(this.activeMembership[i] + (this.activeMembership[i] != null ? "," + this.utilityValues[i].longValue() : "") + " || ");
		}
		System.out.println("My degree is: " + this.activeDegree);
	}

	public int getSentMessages() {
		return this.msgSent;
	}

	public boolean isInitialized() {
		return this.myNode != null;
	}

	public void resetSentMessages() {
		this.msgSent = 0;
	}

}