// $Id: Node.java,v 1.30 2007/11/08 07:35:13 zahorjan Exp $

import java.util.*;

import org.jgrapht.Graphs;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;

/**
 * Abstract base class of DV and LS node types.
 * Implements common functionality -- most everything but timestep based routing table update.
 */

public abstract class Node {
    private static int nextUID = 0;

    /**
     * Each node has an integer UID.  (They're consecutive.)
     */
    protected int uid;
    /**
     * Each node has a routing table.
     */
    private RoutingTable routingTable;  // maps destination node id to next hop node id
    /**
     * Each node has two queues of incoming update packets:
     * <ol>
     * <li>The packets sent to it during the last time step.
     * <li>The packets being sent to it during this time step.
     * </ol>
     * Packets in the first queue "have arrived," and can be read during this time step.
     * Packets in the second queue (i.e., sent this time step) aren't available until the
     * next time step.
     */ 
    private LinkedList<UpdatePacket> currentInQueue;
    private LinkedList<UpdatePacket> futureInQueue;

    /**
     * Each node has a current list of neighbors
     */
    protected LinkedHashSet<Node> neighbor;
    /**
     * Each neighbor has a time since last heard from
     */
    protected HashMap<Node,Integer> lastHeardDelay;
    /**
     * Time slot in which we last ran
     */
    protected int lastUpdatedSlot;
    /**
     * Indicator of whether or not this node has failed
     */
    protected boolean failed;

    protected static MyRandom rand = null;

    private static final float FAILURE_PROB = 1.0F / ConstSysProperties.NODE_MTF;
    private static final float RECOVERY_PROB = 1.0F / ConstSysProperties.NODE_MTR;

    public int getUID() { return uid; }
    public RoutingTable getRoutingTable() { 
        return routingTable;
    }
    public boolean hasFailed() { return failed; }

    public Node() {
        uid = nextUID++;
        routingTable = new RoutingTable();
        routingTable.setEntry(this, this, 0);
        currentInQueue = new LinkedList<UpdatePacket>();
        futureInQueue = new LinkedList<UpdatePacket>();
        lastHeardDelay = new HashMap<Node,Integer>();
        lastUpdatedSlot = 0;
        failed = false;
        if ( rand == null ) rand = new MyRandom();
    }

    /**
     * Fills in the routing table using an oracle (i.e., reliable/correct)
     * view of network connectivity.
     */
    public void oracleComputeRoutingTable() {
        oracleFillTable( routingTable );
    }

    /**
     * Fills in the routing table using an oracle (i.e., reliable/correct)
     * view of network connectivity.
     */
    public void oracleFillTable(RoutingTable rt) {
        Network network = Network.getNetwork();
        ClosestFirstIterator<Node,DefaultEdge> iter =
            new ClosestFirstIterator<Node, DefaultEdge>(network, this);
        while (iter.hasNext()) {
            Node next = iter.next();
            if ( next == this ) continue;
            DefaultEdge e = iter.getSpanningTreeEdge(next);
            // the graph is undirected, so we're not sure at which end of an 'edge'
            // to look for the one 'next' is connected to
            Node predecessor = network.getEdgeSource(e);
            if ( predecessor == next ) predecessor = network.getEdgeTarget(e);
            if ( predecessor == this ) {
                rt.setEntry(next, next, 1);
            } else {
                rt.setEntry(next, rt.getHopTo(predecessor), rt.getDistTo(predecessor) + 1 );
            }
        }
    }

    /**
     * Called as an initialization step, once the network topology is finalized.
     * Node should do whatever it has to do to understand who it thinks its neighbors 
     * are.
     */
    public void setupNeighborInformation() {
        neighbor = new LinkedHashSet<Node>( Graphs.neighborListOf(Network.getNetwork(), this) );
        for ( Node n : neighbor ) {
            lastHeardDelay.put(n, new Integer(0) );
        }
    }

    /**
     * Send an update packet
     */
    protected void sendUpdatePacket(Node dest, UpdatePacket p) throws IllegalArgumentException {
        if ( !neighbor.contains(dest) ) 
            throw new IllegalArgumentException("Node " + this + 
                                               " attempting to send to a non-neighbor destination (" + 
                                               dest + ")");
        dest.futureInQueue.add(p);
        ScoreKeeper.getScoreKeeper().sentUpdate();
    }

    /**
     * Swaps the current and future in queues.  (Called by Network code each time it
     * is asked to take a step.)
     */
    public void swapInQueues() {
        LinkedList<UpdatePacket> temp = currentInQueue;
        currentInQueue = futureInQueue;
        futureInQueue = temp;
    }

    /**
     * Causes node to read currentInQueue of update packets and act on them.
     */
    public void takeStep() {

        // check for failure / recovery.  Note that you can't fail and recover
        // in the same step (which is good, as the future queue isn't cleared
        // until it becomes the current queue).
        if ( hasFailed() ) {
            currentInQueue.clear();
            if ( rand.nextFloat() < RECOVERY_PROB) setHasFailed(false);
        } else {
            if ( rand.nextFloat() < FAILURE_PROB) setHasFailed(true);
        }

        // now actually take a step, depending on the current state of node
        if ( rand.nextFloat() < ConstSysProperties.UPDATE_PROB && !hasFailed()) {
            // inform subclass that a step is starting
            startUpdate();

            // first increment time since we heard from each neighbor
            int tDelta = sim.getTime() - lastUpdatedSlot;
            lastUpdatedSlot = sim.getTime();

            for ( Node n : neighbor ) {
                // increment only if we currently think the node is up
                if ( routingTable.getDistTo(n) < ConstAlg.INFINITY ) 
                    lastHeardDelay.put(n, new Integer(lastHeardDelay.get(n) + tDelta));
            }

            // update state based on received update packets.

            UpdatePacket p;
            while (!currentInQueue.isEmpty()) {
                p = currentInQueue.remove();
                if ( ConstConfig.DEBUG && routingTable.getDistTo(p.fromNode) >= ConstAlg.INFINITY )
                    System.out.println( this + " sees " + p.fromNode + " is back at t=" + sim.getTime() );
                lastHeardDelay.put( p.fromNode, new Integer(0) );
                // allow subclass to process update
                processUpdate(p);
            }

            // look for neighbors that appear to be unreachable.
            // can't remove elements from collection we're iterating over,
            // so remember ones to remove and then remove them later.
            for ( Node n : neighbor ) {
                if ( lastHeardDelay.get(n) >= ConstAlg.FAILED_TIMEOUT ) {
                    // notify subclass of failure
                    neighborFailureEvent(n);
                    lastHeardDelay.put(n, new Integer(0));
                    if ( ConstConfig.DEBUG ) System.out.println(this + " sees " + n + " down at t=" + sim.getTime());
                }
            }
        }

        // indicate to the node's implementation that we're done with this time step.
        // it should send any update packets it feels are useful.
        stopUpdate();
    }

    /** 
     * Allows manipulation of failure/recovery of this node.
     */
    public boolean setHasFailed( boolean f ) { 
        boolean result = failed; 
        failed = f; 

        // if this node has failed, it can't route to anywhere
        if ( failed ) {
            if ( ConstConfig.DEBUG ) System.out.println(this + " failing at t=" + sim.getTime());
            // update Network graph
            Network.getNetwork().removeVertex(this);

            // throw away all routing table info (and turn off logging)
            routingTable.cleanTable();

            // notify subclass of failure
            failureEvent();
        }
        else if (result == true ) {
            // it was down; now it's up.  Put this node back
            // in the network graph.
            if ( ConstConfig.DEBUG ) System.out.println(this + " recovering at t=" + sim.getTime());
            Network.getNetwork().addVertex(this);
            for ( Node o : neighbor ) {
                lastHeardDelay.put( o, new Integer(0) );
                if ( !o.hasFailed() ) Network.getNetwork().addEdge(this, o);
            }

            // notify the subclass that the node has recovered
            recoveryEvent();

            // make sure the self link entry is correct
            routingTable.setEntry(this, this, 0);
        }
        return result;
    }

    /**
     * When this node is selected to run during a time step, the "driver"
     * code in Node.java:
     * <ol>
     * <li>first calls this routine (startUpdate())
     * <li>then with high, but not certain, probability calls processUpdate()
     *     for each update packet in the node's queue
     * <li then calls stopUpdate()
     * </ol>
     * (1) and (3) allow some flexibility in the implementation of 
     * different (sub)classes of node, without having to meddle with the
     * code in Node.java.
     */
    protected abstract void startUpdate();
    /**
     * Called for each update packet in this node's queue 
     * when it is selected to run during a time step.
     */
    protected abstract void processUpdate(UpdatePacket p);
    /**
     * See startUpdate().
     */
    protected abstract void stopUpdate();
    /**
     * Invoked when this node fails.
     */
    protected abstract void failureEvent();
    /**
     * Invoked when this node recovers from a failure.
     */
    protected abstract void recoveryEvent();
    /**
     * Invoked when a timeout indicates that a neighbor node 
     * has failed.
     */
    protected abstract void neighborFailureEvent(Node neighbor);

    public String toString() {
        return new Integer(uid).toString();
    }

}