package brn.swans.route.cs;

import brn.swans.route.RouteMcExOR;
import brn.swans.route.cs.CandidateSelection.NetAddressWithMetric;
import brn.swans.route.metric.RouteMetricInterface;
import brn.swans.route.metric.RouteMetricInterface.NoLinkExistsException;
import brn.swans.route.metric.RouteMetricInterface.NoRouteExistsException;
import brn.swans.route.RouteMcExORFlood;
import brn.util.AbstractFluxBox;
import brn.util.Graphviz;
import brn.util.Tuple;
import jist.runtime.JistAPI;
import jist.runtime.Util;
import jist.swans.net.NetAddress;
import org.apache.log4j.Logger;

import java.util.*;

/**
 * The global McExOR-CSet Selection Algorithm.
 * <p/>
 * This class is reponsible for the construction of the candidate set graph.
 * Required to find a promising candidate set.
 *
 * @author Zubow
 */
public class CandidateSetGraph {

  /* Construct the cs tree with a depth of at least MIN_TREE_DEPTH */
  private final static int MIN_TREE_DEPTH = 5;
  private final static int DEFAULT_EDGE_WEIGHT = 100;
  /** constant for an non-existing link */
  private final static int INVALID_ROUTE_METRIC = 9999;

  /* ExOR logger. */
  private static Logger log = Logger.getLogger(CandidateSetGraph.class.getName());

  public static String saveDir;

  private final static int STRICT = 1;
  private final static int LAX = 2;
  private final static int mode = STRICT;

  private NetAddress me;
  private RouteMcExORFlood flood;
  private int cSetSize;

  /* remember each newly created edge while constructing the cs graph */
  private AbstractFluxBox /* CandidateSetEdge */ visitedEdge;

  private Node root; // pseudo node
  private Node myself;
  private Node sink; // pseudo node

  /* Expand only node with a metric smaller than currBestMetric */
  private double currBestMetric;

  private List currBestRoute;

  // performance aspects

  /* Inform me each time the underlaying link table is updated*/
  private LinkTableEventListener ltEvtListener;

  private Hashtable cachedRoute;
  private Hashtable cSetCache;
  private RouteMetricInterface routeMetric;

  //
  // Inner classes
  //

  /**
   * Garantees that each edge in the cset graph is unique.
   */
  private static class CSetEdgeFluxBox extends AbstractFluxBox {
    protected Object /* Value */ createValue(Object /* Key */ key, Object /* Params */ params) {
      return new Edge((CandidateSetEdge) key);
    }
  }

  /**
   * A node in our candidate set graph.
   */
  private static class Node {
    protected CandidateSet candidateSet;
    protected List /* Node */ childNodes;
    protected Node parent;

    public Node(CandidateSet candidateSet) {
      this.candidateSet = candidateSet;
      this.childNodes = new ArrayList();
      this.parent = null;
    }

    public String toString() {
      StringBuffer str = new StringBuffer();
      str.append("Node: [").append(candidateSet.toString()).append("]");
      return str.toString();
    }

    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final Node node = (Node) o;

      if (candidateSet != null ? !candidateSet.equals(node.candidateSet) : node.candidateSet != null) return false;
      if (childNodes != null ? !childNodes.equals(node.childNodes) : node.childNodes != null) return false;
      if (parent != null ? !parent.equals(node.parent) : node.parent != null) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = (candidateSet != null ? candidateSet.hashCode() : 0);
      result = 29 * result + (childNodes != null ? childNodes.hashCode() : 0);
      result = 29 * result + (parent != null ? parent.hashCode() : 0);
      return result;
    }
  }

  /**
   * An edge between 2 nodes {@link Node} in our cset graph.
   */
  private static class Edge {
    protected CandidateSetEdge csetEdge;

    public Edge(CandidateSetEdge csetEdge) {
      this.csetEdge = csetEdge;
    }

    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final Edge edge = (Edge) o;

      if (csetEdge != null ? !csetEdge.equals(edge.csetEdge) : edge.csetEdge != null) return false;

      return true;
    }

    public int hashCode() {
      return (csetEdge != null ? csetEdge.hashCode() : 0);
    }
  }

  /**
   * The value of a node {@link Node} is represented by the candidate set.
   */
  private static class CandidateSet {
    /* keep each node unique; required since a node could be visited multiple times */
    private static int id_gen = 0;

    private int id;
    private Integer channel;
    private Set member;
    private double csCum;
    private boolean containsFinalNode;

    public CandidateSet() {
      this.id = id_gen++;
      member = new HashSet();
      containsFinalNode = false;
    }

    public CandidateSet(NetAddressWithMetric node, Integer channel) {
      this.id = id_gen++;
      member = new HashSet();
      addMember(node);
      csCum = node.metric;
      this.channel = channel;
      containsFinalNode = false;
    }

    public CandidateSet(List members, Integer channel) {
      this.id = id_gen++;
      member = new HashSet(members);
      this.channel = channel;
      containsFinalNode = false;

      csCum = 0;
      for (Iterator it = members.iterator(); it.hasNext();) {
        NetAddressWithMetric nbInfo = (NetAddressWithMetric) it.next();
        if (nbInfo.metric == 0)
          containsFinalNode = true;
        csCum += nbInfo.metric;
      }
      // normiere csCum
      csCum /= members.size();
    }

    public void addMember(NetAddressWithMetric node) {
      member.add(node);
    }

    public boolean containsFinalNode() {
      return containsFinalNode;
    }

    public double getCsCum() {
      return csCum;
    }

    public Set getMembers() {
      return member;
    }

    public static void reset() {
      id_gen = 0;
    }

    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final CandidateSet that = (CandidateSet) o;

      if (this.id != that.id) return false;

      return that.getMembers().equals(getMembers());
    }

    public boolean similiar(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final CandidateSet that = (CandidateSet) o;

      return that.getMembers().equals(getMembers());
    }

    public int hashCode() {
      return member.hashCode();
    }

    public int getSize() {
      return member.size();
    }

    public String toString() {
      StringBuffer str = new StringBuffer();

      str.append(channel).append(":(");
      Iterator it = member.iterator();
      while (it.hasNext()) {
        NetAddressWithMetric item = (NetAddressWithMetric) it.next();
        str.append(item.ip.getId());
        if (it.hasNext())
          str.append(",");
      }
      str.append(")");
      return str.toString();
    }
  }

  /**
   * Represents an edge in the candidate set graph
   */
  private static class CandidateSetEdge {
    protected CandidateSet vertexLeft;
    protected CandidateSet vertexRight;
    protected double p_cs;

    public CandidateSetEdge(CandidateSet vertexLeft, CandidateSet vertexRight) {
      this.vertexLeft = vertexLeft;
      this.vertexRight = vertexRight;
    }

    public CandidateSetEdge(CandidateSet vertexLeft, CandidateSet vertexRight, double p_cs) {
      this(vertexLeft, vertexRight);
      this.p_cs = p_cs;
    }

    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final CandidateSetEdge that = (CandidateSetEdge) o;

      if (!vertexLeft.equals(that.vertexLeft)) return false;
      if (!vertexRight.equals(that.vertexRight)) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = vertexLeft.hashCode();
      result = 29 * result + vertexRight.hashCode();
      return result;
    }
  }

  /* mark cache as dirty when a link becomes too bad or good */
  private final static int MAX_LINK_VARIATION_BEFORE_DIRTY_CACHE = 2;

  /**
   * Handles changes in the network topology represented by the real link table.
   * Used for caching.
   */
  private class LinkTableEventListener implements RouteMetricInterface.EventListener {

    public void onUpdate(Object from, Object to, int old_metric, int metric) {
      // mark the whole cache as dirty
      int delta = Math.max(old_metric, metric) / Math.min(old_metric, metric);
      if (delta >= MAX_LINK_VARIATION_BEFORE_DIRTY_CACHE) {
        if (log.isDebugEnabled())
        log.debug(me + "(" + JistAPI.getTime() + ") mark the whole cache as dirty.");
        cachedRoute.clear();
        cSetCache.clear();
        currBestRoute.clear();
      }
    }

    public int hashCode() {
      return 1;
    }
  }

  /**
   * Construct a new candidate set graph.
   *
   * @param me               the address of the node which makes use of this algorithm
   * @param ls               a {@link LinkStat}
   * @param flood            a {@link RouteMcExORFlood}
   * @param cSetSize         the size of the candidate set.
   * @param relayPreferences nodes with relay pref different from the default value are described here
   */
  public CandidateSetGraph(NetAddress me, RouteMetricInterface routeMetric,
      RouteMcExORFlood flood, int cSetSize) {
    this.me = me;
    this.cSetSize = cSetSize;
    this.routeMetric = routeMetric;
    this.flood = flood;
    this.ltEvtListener = new LinkTableEventListener();
    this.currBestRoute = new ArrayList();
    this.cachedRoute = new Hashtable();
    this.cSetCache = new Hashtable();
    reset();
  }

  private void reset() {
    this.root = null;
    this.myself = null;
    this.sink = null;
    this.visitedEdge = new CSetEdgeFluxBox();
    this.currBestMetric = Integer.MAX_VALUE;
    CandidateSet.reset();
  }

  public RouteMetricInterface.EventListener getLinkTableEventListener() {
    return ltEvtListener;
  }

  /**
   * This method returns the best channel to be used as well as the candidate set @param rvalue
   *
   * @param rvalue   the calculated best candidate set.
   * @param finalSrc the source of the packet (often it is equal to {@link #me})
   * @param finalDst the final destination of the packet
   * @param chArray  an array with all channel the packet has used up to this point.
   * @return the channel to be used.
   */
  public Integer getNextCandidateSet(List rvalue, NetAddress finalSrc,
                                     NetAddress finalDst, byte[] chArray) {


    Tuple id = new Tuple(finalSrc, finalDst);

    cSetCache.clear();
    if (cachedRoute.get(id) == null) {
      //
      // construct the full graph
      //
      long t_start = System.currentTimeMillis();
      log.info(me + " constructing cs graph ... " + t_start);
      constructCSGraph(finalSrc, finalDst, chArray);
      // write a graphviz file; for debug purposes
      printCSGraph();
      long t_end = System.currentTimeMillis() - t_start;
      log.info(me + " cs graph created ...duration " + t_end);

      // cache cSet link table
      cachedRoute.put(id, revertList(currBestRoute));
    }

    // restore cached values
    List routes = (List) cachedRoute.get(id);

    if ((routes != null) && (!routes.isEmpty())) {
      // debug
      printRoute(routes);

      if (routes.size() >= 2) {
        CandidateSet bestCs = (CandidateSet) routes.get(1);
        if ((bestCs.channel == null) || (bestCs.channel.intValue() == -1)) {
          String msg = me + ": Channel is null " + bestCs + " while searching from " + myself.candidateSet
                  + " " + sink.candidateSet;
          throw new RuntimeException(msg);
        }

        rvalue.addAll(bestCs.getMembers());
        Collections.sort(rvalue);
        reset();

        return bestCs.channel;
      } else if (routes.size() == 1) {
        CandidateSet bestCs = (CandidateSet) routes.get(0);
        if ((bestCs.channel == null) || (bestCs.channel.intValue() == -1)) {
          String msg = me + ": Channel is null " + bestCs + " while searching from " + myself.candidateSet
                  + " " + sink.candidateSet;
          throw new RuntimeException(msg);
        }

        rvalue.addAll(bestCs.getMembers());
        Collections.sort(rvalue);
        reset();

        return bestCs.channel;
      }
    }
    String errMsg = "could not find a route in csetgraph from " + myself.candidateSet + " to " + sink.candidateSet;
    log.error(errMsg);
    throw new RuntimeException(me + " Could cot calculate cset: " + errMsg);
  }

  /**
   * The core of this algorithm: the cset graph is constructed recursively.
   *
   * @param finalSrc start address
   * @param finalDst destination address
   * @param chArray  the channels the packet has already used on his way to this node.
   */
  private void constructCSGraph(NetAddress finalSrc, NetAddress finalDst, byte[] chArray) {

    List route;
    int myRouteMetric = -1;
    NetAddressWithMetric me;
    CandidateSet cset;
    Set usedChs = new HashSet();

    /* create pseudo node for final destination */
    sink = new Node(new CandidateSet(new NetAddressWithMetric(NetAddress.LOCAL, 0), new Integer(-1)));

    /* create a pseudo node for each already used channel */
    Node currNode, prevNode = null;

    if (chArray != null) {
      // construct a pseudo node for each already used channel
      for (int i = 0; i < chArray.length; i++) {
        int c = chArray[i];
        // address does not matter
        cset = new CandidateSet(new NetAddressWithMetric(NetAddress.ANY, 9999), new Integer(c));

        currNode = new Node(cset);
        usedChs.add(new Integer(c));

        // construct edges
        if (prevNode != null) { // pseudo node available; create an edge
          // add link to linktable
          int metric = DEFAULT_EDGE_WEIGHT;

          CandidateSetEdge edge = new CandidateSetEdge(prevNode.candidateSet, cset, metric);

          // add new edge
          visitedEdge.getObject(edge, null);

          // append new node
          if (!(prevNode.childNodes.contains(currNode))) {
            prevNode.childNodes.add(currNode);
          }
          currNode.parent = prevNode;
        }

        if (root == null)
          root = currNode;

        prevNode = currNode;
      }
    }

    /* create node containing only myself (a kind of this node) */
    try {
      route = routeMetric.queryRoute(finalSrc, finalDst,
          INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);
      // calculate my path metric to dst
      myRouteMetric = routeMetric.getRouteMetric(route,
          INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);
    } catch (NoRouteExistsException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    } // src, dst
    catch (NoLinkExistsException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }
    me = new NetAddressWithMetric(finalSrc, myRouteMetric);

    Util.assertion(flood.getNodeHomeChannel(finalSrc) != null);

    cset = new CandidateSet(me, new Integer(flood.getNodeHomeChannel(finalSrc).getChannel()));

    myself = new Node(cset);
    usedChs.add(flood.getNodeHomeChannel(finalSrc));

    int depth = Math.max(routeMetric.getChannels().length, MIN_TREE_DEPTH);

    if (prevNode != null) { // pseudo node available; create an edge
      // add link to linktable
      int metric = DEFAULT_EDGE_WEIGHT;

      CandidateSetEdge edge = new CandidateSetEdge(prevNode.candidateSet, cset, metric);

      // add new edge
      visitedEdge.getObject(edge, null);

      // append new node
      if (!(prevNode.childNodes.contains(myself))) {
        prevNode.childNodes.add(myself);
      }
      myself.parent = prevNode;

      // construct full tree
      constructCSGraphR(myself, usedChs, false, depth, finalDst, 0);
    } else { // not pseudo node; we are the root node
      root = myself;
      // construct full tree
      constructCSGraphR(root, usedChs, false, depth, finalDst, 0);
    }
    log.info(me + " cset graph ready...");
  }


  /**
   * Constructs the candidate set graph (recursive algorithm).
   *
   * @param predecessor        the predecessor of the newly created node
   * @param usedCh             set of already used channels
   * @param forceChannelSwitch indicates whether we need to enforce a channel switch
   * @param depth              max tree depth
   */
  private void constructCSGraphR(Node predecessor, Set usedCh,
                                 boolean forceChannelSwitch, int depth, NetAddress finalDst,
                                 double currMetric) {

    //
    // algorithm: for each node in the cset of the current node a child node is constructed.
    //

    // approximation; expand only the best candidate

    List cand = new ArrayList(predecessor.candidateSet.getMembers());
    Collections.sort(cand);

    NetAddressWithMetric nb = (NetAddressWithMetric) cand.get(0);

    Hashtable csetTable = getCS(nb.ip, finalDst);
    // construct list of nodes
    Enumeration channels = csetTable.keys();
    while (channels.hasMoreElements()) {
      Integer ch = (Integer) channels.nextElement();

      Util.assertion((ch != null) && (ch.intValue() != -1));

      CandidateSet cset = new CandidateSet((List) csetTable.get(ch), ch);
      //Node child = (Node) visitedNodes.getObject(cset, null);
      Node child = new Node(cset);

      if (!(isLoopFree(child))) {
        log.warn("loop detected");
        continue;
      }

      // calculate probability to successfully transmit packet into the given candidate set
      double p_cs = estimateCsMetric(nb.ip, (List) csetTable.get(ch));

      // bonus for channel switch
      p_cs = enforceChannelSwitch(predecessor, p_cs, ch.intValue());

      p_cs = (1 / p_cs) * DEFAULT_EDGE_WEIGHT;// (predecessor.candidateSet.getCsCum() - cset.getCsCum());

      CandidateSetEdge edge = new CandidateSetEdge(predecessor.candidateSet, cset, p_cs);

      boolean doRecCall = !visitedEdge.contains(edge);

      // add new edge
      visitedEdge.getObject(edge, null);

      // append new node
      if (!(predecessor.childNodes.contains(child))) {
        predecessor.childNodes.add(child);
      }
      child.parent = predecessor;

      // update length to source node
      double tmpCurrMetric = currMetric + edge.p_cs;

      // last hop to pseudo node
      if ((cset.getCsCum() == 0) || (cset.containsFinalNode())) { // sink cset node
        connectWithSinkNode(cset, child, 1);

        saveCurrPath(tmpCurrMetric, child);

        continue;
      }

      // skip nodes with a channel we already used
      if (usedCh.contains(ch) && (depth <= 0)) {
        double m = 1 / cset.getCsCum();
        // bonus for channel switch
        m = enforceChannelSwitch(child, m, ch.intValue());
        m = 1 / m;
        connectWithSinkNode(cset, child, Math.max((int) m, 100));

        saveCurrPath(tmpCurrMetric, child);

        continue;
      }

      // calc the cummulated metric of this node and decide, whether we need to expand this node
      if ((tmpCurrMetric + DEFAULT_EDGE_WEIGHT) >= currBestMetric) {
        if (log.isDebugEnabled())
        log.debug(me + " do not expand this node;" + cset + " we already have a better route.");
        doRecCall = false;
      }

      // recursive call for each child node
      if (doRecCall) {
        // remember this channel
        Set clonedUsedCh = new HashSet(usedCh);
        clonedUsedCh.add(ch);

        if (depth > 0) {
          constructCSGraphR(child, clonedUsedCh, true, depth - 1, finalDst, tmpCurrMetric);
        } else { // max depth reached; connect this node with the pseudo node

          double m = 1 / cset.getCsCum();
          // bonus for channel switch
          m = enforceChannelSwitch(child, m, ch.intValue());

          m = 1 / m;

          connectWithSinkNode(cset, child, (int) m);
        }
      }
    }
  }

  private void saveCurrPath(double tmpCurrMetric, Node child) {
    if (currBestMetric > tmpCurrMetric) {
      currBestMetric = tmpCurrMetric;

      currBestRoute.clear();
      Node pointer = child;
      while (pointer != null) {
        currBestRoute.add(pointer.candidateSet);
        if (pointer.candidateSet.equals(myself.candidateSet))
          break;
        pointer = pointer.parent;
      }
    }
  }

  private Hashtable getCS(NetAddress src, NetAddress dst) {

    Tuple id = new Tuple(src, dst);

    if (cSetCache.get(id) == null) {
      List route;
      int currRouteMetric = INVALID_ROUTE_METRIC;
      try {
        route = routeMetric.queryRoute(src, dst, INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);
        // calculate my path metric to dst
        currRouteMetric = routeMetric.getRouteMetric(route,
            INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);
      } catch (NoRouteExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      } // src, dst
      catch (NoLinkExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      }

      Hashtable csetTable
              = createCsPerChannel(src, dst, calcShortestPathForEachNeighbor(src, dst, currRouteMetric));

      // cache cSet link table
      cSetCache.put(id, csetTable);
    }

    return (Hashtable) cSetCache.get(id);
  }

  private void connectWithSinkNode(CandidateSet cset, Node child, int metric) {
    CandidateSetEdge lastEdge = new CandidateSetEdge(cset, sink.candidateSet, metric);
    // add new edge
    visitedEdge.getObject(lastEdge, null);

    // append new node
    if (!(child.childNodes.contains(sink))) {
      child.childNodes.add(sink);
    }
  }

  private double estimateCsMetric(NetAddress src, List cs) {
    double pdiff = 1;

    for (int i = 0; i < cs.size(); i++) {

      // calculate link metric to my neighbors
      NetAddressWithMetric nbInfo = (NetAddressWithMetric) cs.get(i);

      int nbMetric = INVALID_ROUTE_METRIC;
      try {
        nbMetric = routeMetric.getLinkMetric(src, nbInfo.ip);
      } catch (NoLinkExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      }

      pdiff *= 1 - (100.0 / (double) nbMetric);
    }

    return 1 - pdiff; // wahrscheinlichkeit, dass das paket den cset erreicht.
  }

  /**
   * Helper method groups the potential neighbor nodes according to their home channel.
   *
   * @return a hashtable where the channel is the key and the value the is the candidate set.
   */
  private Hashtable createCsPerChannel(NetAddress src, NetAddress finalDst, List candidates) {

    Hashtable /* int (channel) -> List of NetAddressWithMetric */ csSet = new Hashtable();

    //
    // group potential candidates according to their homechannels
    //
    for (int i = 0; i < candidates.size(); i++) {
      NetAddressWithMetric netAddressWithMetric
              = (NetAddressWithMetric) candidates.get(i);

      NetAddress nb = netAddressWithMetric.ip;
      Integer nbHomeChannel = new Integer(flood.getNodeHomeChannel(nb).getChannel());

      // this should not happen
      if (nbHomeChannel == null) {

        if (mode == STRICT) {
          // TODO
//          Hashtable knownNodes = flood.getNodeHomeChannels();
//          Enumeration knKeys = knownNodes.keys();
//
//          while (knKeys.hasMoreElements()) {
//            NetAddress nodeIp = (NetAddress) knKeys.nextElement();
//            Integer nodeChannel = (Integer) knownNodes.get(nodeIp);
//            log.error(nodeIp + ": " + nodeChannel);
//          }

          throw new RuntimeException(me + ": nb homechannel unknown " + nb);
        } else {
          log.error(me + ": nb homechannel unknown; skipping node " + nb);
        }
      }

      List csTmp;
      if (csSet.get(nbHomeChannel) == null) {
        csSet.put(nbHomeChannel, new ArrayList());
      }
      csTmp = (List) csSet.get(nbHomeChannel);
      csTmp.add(netAddressWithMetric);

    }

    //
    // find safe nb for each cs
    //
    appendSafeNB(csSet, src, finalDst);

    return csSet;
  }

  private void appendSafeNB(Hashtable csSet, NetAddress src, NetAddress finalDst) {

    int metricToBestNb = INVALID_ROUTE_METRIC;
    int routeMetricOfBestNB = Integer.MAX_VALUE;
    NetAddressWithMetric safeNb = null, safeNbBck = null;

    boolean lastHop = false; // indicates whether we only need a single-unicast last hop
    Integer lastHopChannel = null;

    Enumeration chKeys = csSet.keys();
    while (chKeys.hasMoreElements()) {
      Integer chKey = (Integer) chKeys.nextElement();
      List cs = (List) csSet.get(chKey);

      // calculate for each candidate set the safe neighbor
      for (int i = 0; i < cs.size(); i++) {
        NetAddressWithMetric netAddressWithMetric
                = (NetAddressWithMetric) cs.get(i);

        NetAddress nb = netAddressWithMetric.ip;
        int routeMetric = netAddressWithMetric.metric;

        // calculate the metric to this neighbor
        int nbMetric = INVALID_ROUTE_METRIC;
        try {
          nbMetric = this.routeMetric.getLinkMetric(src, nb);
        } catch (NoLinkExistsException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
        }

        // remember safe candidate per channel
        if ((routeMetric < routeMetricOfBestNB) && (nbMetric <= RouteMcExOR.CS_MIN_METRIC_FOR_SAFE_NB)) {
          routeMetricOfBestNB = routeMetric;
          safeNb = netAddressWithMetric;
        }

        if (nbMetric < metricToBestNb) {
          metricToBestNb = nbMetric;
          safeNbBck = netAddressWithMetric;
        }

        // backup algorithm
        if (safeNb == null) {
          safeNb = safeNbBck;
        }
      } // end

      Collections.sort(cs);

      // strip candidates count to CS_SIZE
      ArrayList ncs = new ArrayList();
      int min_size = Math.min(cs.size(), cSetSize/* - 1*/);

      StringBuffer str = new StringBuffer();
      str.append("CS (" + chKey + "): [");

      for (int j = 0; j < Math.min(cs.size(), min_size); j++) {

        NetAddressWithMetric item = (NetAddressWithMetric) cs.get(j);

        str.append(item).append(", ");
        ncs.add(item);

        // check whether we are close to the destination
        int nbMetric = INVALID_ROUTE_METRIC;
        try {
          nbMetric = routeMetric.getLinkMetric(src, item.ip);
        } catch (NoLinkExistsException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
        }
        if (item.ip.equals(finalDst) && (nbMetric < RouteMcExOR.CS_MIN_METRIC_FOR_SAFE_NB)) {
          if (log.isDebugEnabled())
          log.debug(" last hop reached.");
          lastHop = true;
          lastHopChannel = chKey;
          break;
        }
      }

      if (!lastHop) {
        // check whether the safe nb is in the list, otherwise add
        if ((safeNb != null) && !(ncs.contains(safeNb))) {
          if (log.isDebugEnabled())
          log.debug("safe nb added: " + safeNb.ip);
          str.append(safeNb);
          // place safe nb on the last position
          ncs.set(min_size - 1, safeNb);
        }
      }
      str.append("]");
      if (log.isDebugEnabled())
      log.debug("(" + JistAPI.getTime() + "): createCsPerChannel; ch = " + chKey + " cset = " + str);

      csSet.put(chKey, ncs);

      safeNb = safeNbBck = null;
      metricToBestNb = INVALID_ROUTE_METRIC;
      routeMetricOfBestNB = Integer.MAX_VALUE;
    }

    // if we reached the final hop; drop all other candidates
    if (lastHop) {
      chKeys = csSet.keys();
      while (chKeys.hasMoreElements()) {
        Integer chKey = (Integer) chKeys.nextElement();
        if (!(chKey.equals(lastHopChannel)))
          csSet.remove(chKey);
      }
    }
  }


  /**
   * Calculates potentially available nodes at node @link src towards the destination @link dst
   * which could be used as nodes in the candidate set. However a grouping according to their home channels
   * is further required.
   */
  private List calcShortestPathForEachNeighbor(NetAddress src, NetAddress dst, int myRouteMetric) {

    NetAddress nb;
    List route;
    List candidates = new ArrayList();
    List neighbors = routeMetric.getNeighbors(src);

    for (int i = 0; i < neighbors.size(); i++) {
      nb = (NetAddress) neighbors.get(i);

      // calculate the metric to this neighbor
      int nbMetric = INVALID_ROUTE_METRIC;
      try {
        nbMetric = routeMetric.getLinkMetric(src, nb);
      } catch (NoLinkExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      }

      // skip too bad neighbors
      if (nbMetric > RouteMcExOR.CS_MIN_METRIC) {
        continue;
      }

      try {
        route = routeMetric.queryRoute(nb, dst,
            INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);
        // calculate path metric
        int routeMetric = this.routeMetric.getRouteMetric(route,
            INVALID_ROUTE_METRIC, INVALID_ROUTE_METRIC);

        if ((routeMetric == -1) || (routeMetric > myRouteMetric)) { //TODO >=
          // skip neighbors with worser route metric to destination
          continue;
        }

        // add potential neighbor node
        candidates.add(new NetAddressWithMetric(nb, routeMetric));
      } catch (NoRouteExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      } // src, dst
      catch (NoLinkExistsException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
      }


    }
    return candidates;
  }


  /**
   * This method evaluates the whole candidate set graph to find the best candidate set for
   * the next hop.
   */
  private void printCSGraph() {

    String fName = saveDir + "/" + me + "-cset.graph";
    Graphviz.DiGraph diGraph = new Graphviz.DiGraph();

    List open = new ArrayList();
    List visited = new ArrayList();

    open.add(root);

    while (open.size() != 0) {
      Node node = (Node) open.remove(0);
      visited.add(node);

      for (int i = 0; i < node.childNodes.size(); i++) {
        Node child = (Node) node.childNodes.get(i);
        Edge edge = (Edge) visitedEdge.getObject(new CandidateSetEdge(node.candidateSet, child.candidateSet), null);

        int nodeCh = (node.candidateSet.channel != null) ? node.candidateSet.channel.intValue() : -1;
        diGraph.addNode(node.candidateSet.toString(), nodeCh);

        int childCh = (child.candidateSet.channel != null) ? child.candidateSet.channel.intValue() : -1;
        diGraph.addNode(child.candidateSet.toString(), childCh);
        diGraph.addLink(node.candidateSet.toString(), child.candidateSet.toString(), "" + (int) edge.csetEdge.p_cs);
      }

      for (int i = 0; i < node.childNodes.size(); i++) {
        Node n = (Node) node.childNodes.get(i);
        //if (!(visited.contains(n))) {
        open.add(n);
        visited.add(n);
        //}
      }
    }

    // TODO
//    diGraph.write(fName);
  }

  //
  // algorithm to enforce channel switching
  //
  private boolean isLoopFree(Node node) {

    Node currNode = node.parent;

    while (currNode != null) {
      if (currNode.candidateSet.similiar(node.candidateSet))
        return false;
      currNode = currNode.parent;
    }
    return true;
  }

  //
  // algorithm to enforce channel switching
  //
  private double enforceChannelSwitch(Node predecessor, double pcs, int nextChannel) {


    int preChannel = -1;
    Node currNode = predecessor;

    // try to use each channel only once
    //int depth = ls.getAllChannels().size();
    int depth = Math.max(routeMetric.getChannels().length, MIN_TREE_DEPTH);

    int chCount = 0;
    while ((currNode != null) && (depth > 0)) {
      preChannel = currNode.candidateSet.channel.intValue();

      if (preChannel == nextChannel) {
        chCount++;
      }
      depth--;
      currNode = currNode.parent;
    }

    // TODO think about this !!!!!!
    pcs = pcs / (chCount + 1);

    return pcs;
  }

  private List revertList(List l) {
    List rl = new ArrayList();

    for (int i = l.size() - 1; i >= 0; i--) {
      rl.add(l.get(i));
    }

    return rl;
  }

  private void printRoute(List routes) {
    StringBuffer str = new StringBuffer();
    str.append(me + " Using: [");
    for (int i = 0; i < routes.size(); i++) {
      CandidateSet item = (CandidateSet) routes.get(i);
      str.append(item).append(",");
    }
    str.append("]");
    log.info(str);
  }

  public int hashCode() {
    return 1;
  }
}
