package brn.swans.route.cs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

import jist.runtime.JistAPI;
import jist.runtime.Main;
import jist.runtime.Util;
import jist.swans.Constants;
import jist.swans.misc.MessageAnno;
import jist.swans.net.NetAddress;
import jist.swans.net.NetMessage;
import jist.swans.radio.RadioInterface;

import org.apache.log4j.Logger;

import brn.swans.route.metric.RouteMetricInterface;
import brn.swans.route.metric.RouteMetricInterface.NoLinkExistsException;
import brn.swans.route.metric.RouteMetricInterface.NoRouteExistsException;

public abstract class CandidateSelection {

  private static Logger log = Logger.getLogger(CandidateSelection.class.getName());

  /**
   * This class is used for the calculation of the candidate set.
   */
  public static class NetAddressWithMetric implements Comparable {
    public NetAddress ip;
    public int metric;
    public int metricToSrc;

    /**
     * Creates an net address with metric object.
     *
     * @param ip the address of the node
     * @param metric metric to the destination
     * @deprecated use {@link #NetAddressWithMetric(NetAddress, int, int)}
     */
    public NetAddressWithMetric(NetAddress ip, int metric) {
      this(ip, metric, -1);
    }

    /**
     * Creates an net address with metric object.
     *
     * @param ip the address of the node
     * @param metric metric to the destination
     * @param metricToSrc metric to the source
     */
    public NetAddressWithMetric(NetAddress ip, int metric, int metricToSrc) {
      this.ip = ip;
      this.metric = metric;
      this.metricToSrc = metricToSrc;
    }

    /**
     * CompareTo is implemented as follows:
     * compare their route metric to the destination.
     */
    public int compareTo(Object o) {
      NetAddressWithMetric other = (NetAddressWithMetric) o;
      if (null == other)
        return (-1);

      return this.metric - other.metric;
    }

    public String toString() {
      return "[" + ip.getId() + "," + metricToSrc + "," + metric + "]";
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    public int hashCode() {
      final int PRIME = 31;
      int result = 1;
      result = PRIME * result + ((ip == null) ? 0 : ip.hashCode());
      return result;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      final NetAddressWithMetric other = (NetAddressWithMetric) obj;
      if (ip == null) {
        if (other.ip != null)
          return false;
      } else if (!ip.equals(other.ip))
        return false;
      return true;
    }
  }

  public static class CandidateCacheEntry {
    private NetAddress src;
    private NetAddress dst;
    private long time;
    private List candidates;

    public CandidateCacheEntry(NetAddress src, NetAddress dst) {
      this.src = src;
      this.dst = dst;
      this.time = 0;
      this.candidates = null;
    }

    public List getCandidates() {
      return candidates;
    }

    public void setCandidates(List candidates) {
      this.time = JistAPI.getTime();
      this.candidates = candidates;
    }

    public long getTime() {
      return time;
    }

    public int hashCode() {
      final int PRIME = 31;
      int result = 1;
      result = PRIME * result + ((dst == null) ? 0 : dst.hashCode());
      result = PRIME * result + ((src == null) ? 0 : src.hashCode());
      return result;
    }

    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      final CandidateCacheEntry other = (CandidateCacheEntry) obj;
      if (dst == null) {
        if (other.dst != null)
          return false;
      } else if (!dst.equals(other.dst))
        return false;
      if (src == null) {
        if (other.src != null)
          return false;
      } else if (!src.equals(other.src))
        return false;
      return true;
    }
  }

  // ////////////////////////////////////////////////
  // constants
  //

  /**
   * We must have a metric of not bigger than this value to a safe neighbor.
   */
  private static final int CS_MAX_METRIC_FOR_SAFE_NB  = 115;

  /** constant for an non-existing link */
  private final static int INVALID_ROUTE_METRIC = -1;

  /**
   * Only neighbors with this maximum metric are considered to be potential candidates.
   */
  private static final int MAX_METRIC_FOR_NB          = 350; //TODO 700

  private static final int NB_METRIC_DELTA            = 100;


  // ////////////////////////////////////////////////
  // locals
  //

  /** address of this node */
  protected NetAddress localAddr;

  /** metric to use for routing */
  protected RouteMetricInterface routeMetric;

  /** the size of the candidate set initialized with the default value */
  protected int cSetSize;

  /**
   * Only neighbors with this maximum metric are considered to be potential candidates.
   */
  protected int maxMetricForNeighbor = MAX_METRIC_FOR_NB;

  // TODO set !
  protected int maxEtxForNeighbor = MAX_METRIC_FOR_NB;

  protected int metricDelta = NB_METRIC_DELTA;

  protected int maxMetricForSafeNB = CS_MAX_METRIC_FOR_SAFE_NB;

  private Map candidateCache;

  private long candidateCacheTimeout;

  protected NetMessage.Ip msg;

  protected MessageAnno anno;

  // ////////////////////////////////////////////////
  // initialization
  //

  public CandidateSelection(int csSize, NetAddress localAddr,
      RouteMetricInterface routeMetric) {
    this.localAddr = localAddr;
    this.routeMetric = routeMetric;
    this.cSetSize = csSize;
    this.candidateCache = new HashMap();
    this.candidateCacheTimeout = 500 * Constants.MILLI_SECOND;
  }


  // ////////////////////////////////////////////////
  // accessors
  //

  /**
   * @return the cSetSize
   */
  public int getCSetSize() {
    return cSetSize;
  }

  /**
   * @param setSize the cSetSize to set
   */
  public void setCSetSize(int setSize) {
    cSetSize = setSize;
  }

  public int getMaxMetricForNeighbor() {
    return maxMetricForNeighbor;
  }

  public void setMaxMetricForNeighbor(int maxMetricForNeighbor) {
    this.maxMetricForNeighbor = maxMetricForNeighbor;
  }

  /**
   * @return the candidateCacheTimeout
   */
  public long getCandidateCacheTimeout() {
    return candidateCacheTimeout;
  }


  /**
   * @param candidateCacheTimeout the candidateCacheTimeout to set
   */
  public void setCandidateCacheTimeout(long candidateCacheTimeout) {
    this.candidateCacheTimeout = candidateCacheTimeout;
  }

  /**
   * Converts a list of {@link NetAddressWithMetric} to a list of
   * {@link NetAddress}.
   *
   * @param cs the list to convert
   * @return the converted list.
   */
  protected final List convertToIpList(List cs) {
    List ret = new ArrayList(cs.size());
    for (int i = 0; i < cs.size(); i++) {
      NetAddressWithMetric nawm = (NetAddressWithMetric)cs.get(i);
      ret.add(nawm.ip);
    }
    return ret;
  }

  // ////////////////////////////////////////////////
  // methods
  //

  /**
   * This method calculates the candidate set for a packet with source address
   * src and destination dst.
   *
   * @param src
   *          the source address of the packet
   * @param dst
   *          the final destination of the packet
   * @param anno
   * @param msg
   * @return the list of candidates prioritized my their path metric towards the
   *         final destination as List<NetAddress>
   */
  public final List calculate(NetAddress src, NetAddress dst, NetMessage.Ip msg, MessageAnno anno) {
    this.msg = msg;
    this.anno = anno;

    CandidateCacheEntry key = new CandidateCacheEntry(src, dst);
    CandidateCacheEntry entry = (CandidateCacheEntry) candidateCache.get(key);
    if (null == entry) {
      candidateCache.put(key, key);
      entry = key;
    } else if (entry.getTime() + candidateCacheTimeout >= JistAPI.getTime()) {
      List cached = getCachedCandidates(entry);
      if (null != cached)
        return cached;
    }

    List ret = calculate(src, dst);

    if (log.isInfoEnabled())
      log.info(this + "(" + JistAPI.getTime() + "): using " + ret);

    entry.setCandidates(ret);
    return getCachedCandidates(entry);
  }

  /**
   * Extract current candidates from cache entry. Overwrite if you want to
   * use a custom implementation.
   *
   * @param entry current cache entry.
   * @return candidate set to use.
   */
  protected List getCachedCandidates(CandidateCacheEntry entry) {
    return entry.getCandidates();
  }


  /**
   * Skeleton for candidate selection algorithms. In most cases, you do not have
   * to overwrite this method. Instead, overwrite and implement
   * {@link #select(NetAddress, NetAddress, List)}.
   *
   *
   * @param src
   *          the source address of the packet
   * @param dst
   *          the final destination of the packet
   * @return the list of candidates prioritized my their path metric towards the
   *         final destination as List<NetAddress>
   */
  protected List calculate(NetAddress src, NetAddress dst) {
    // calculate my path metric to dst
    List route = null;
    int metric = -1;
    try {
      route = routeMetric.queryRoute(src, dst, maxMetricForNeighbor, maxEtxForNeighbor);
      metric = routeMetric.getRouteMetric(route, maxMetricForNeighbor, maxEtxForNeighbor);
    } catch (Exception e) {} 

    // the cache may have changed...
    if (route == null || metric < 0) {
      try {
        route = routeMetric.queryRoute(src, dst, maxMetricForNeighbor, maxEtxForNeighbor, false);
        metric = routeMetric.getRouteMetric(route, maxMetricForNeighbor, maxEtxForNeighbor);
      } catch (NoRouteExistsException e) {
        // no route available
        return null;
      } catch (NoLinkExistsException e) {
        // no route available
        return null;
      }
    }

    if (log.isInfoEnabled())
      log.info(this + "(" + JistAPI.getTime() + "): shortest path: " + route);

    // for each of my neighbors calculate the shortest path to the destination
    List candidates = calcShortestPathForEachNeighbor(
        getNeighbors(src), src, dst, route, metric);

    List used_cs = select(src, dst, candidates);

    return used_cs;
  }

  protected List getNeighbors(NetAddress src) {
    return routeMetric.getNeighbors(src);
  }

  /**
   * Helper method calculates for each neighbor node the shortest path to the
   * destination.
   *
   * @param neighbors List<NetAddress> of neighbors
   * @param src source of the route to find
   * @param dst destination of the route to find
   * @param route
   * @param metric routing metric of the route between src and dst
   *
   * @return List<NetAddressWithMetric> with candidates.
   */
  protected List calcShortestPathForEachNeighbor(final List neighbors,
      final NetAddress src, final NetAddress dst, List route, final int metric) {
    List candidates = new ArrayList();

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

      try {
        // calculate the metric to this neighbor
        int nbMetric = routeMetric.getLinkMetric(src, nb);

        if (Main.ASSERT)
          Util.assertion(nbMetric > 0);

        // skip too bad neighbors
        if (nbMetric > maxMetricForNeighbor)
          continue;

        List candRoute = routeMetric.queryRoute(nb, dst, maxMetricForNeighbor, maxEtxForNeighbor); // src, dst

        // calculate path metric
        int routeMetric = this.routeMetric.getRouteMetric(candRoute, maxMetricForNeighbor, maxEtxForNeighbor);

        // skip neighbors with worser route metric to destination
        if (routeMetric + metricDelta > metric)
          continue;

        // add potential neighbor node
        candidates.add(new NetAddressWithMetric(nb, routeMetric, nbMetric));
      } catch (NoRouteExistsException e) {
      } catch (NoLinkExistsException e) {
        continue;
      }

    }

    return candidates;
  }

  protected NetAddressWithMetric getSafeNeighbor(NetAddress src, List candidates) {
    //
    // find safe nb for each cs
    //
    int metricToBestNb = INVALID_ROUTE_METRIC;
    int routeMetricOfBestNB = Integer.MAX_VALUE;
    NetAddressWithMetric safeNb = null, safeNbBck = null;

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

      int routeMetric = netAddrWithMetric.metric;
      int nbMetric = netAddrWithMetric.metricToSrc;

      // remember safe candidate per channel
      if (routeMetric < routeMetricOfBestNB
          && nbMetric <= maxMetricForSafeNB) {
        routeMetricOfBestNB = routeMetric;
        safeNb = netAddrWithMetric;
      }

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

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

    return safeNb;
  }

  /**
   * Helper method for choosing a candidate set. Basic operation is as follows:
   * the candidates list is trimmed down to the size of the candidate set and
   * a safe neighbor is added, if available.
   *
   * Overwrite this method if you want to implement your own candidate selection.
   *
   * @param src source node looking for a route and candidate set.
   * @param dst destination you are looking for
   * @param candidates list of possible candidates (e.g. must be on the same channel)
   * @return the candidate set as List<NetAddressWithMetric>
   */
  protected List select(NetAddress src, NetAddress dst, List candidates) {
    // get the safe neighbor
    NetAddressWithMetric safeNb = getSafeNeighbor(src, candidates);

    // sort all candidates according to their metrics
    Collections.sort(candidates);

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

    for (int j = 0; j < min_size; j++)
      cs.add(candidates.get(j));

    // check whether the safe nb is in the list, otherwise add
    if (safeNb != null && !cs.contains(safeNb))
      // place safe nb on the last position
      cs.set(min_size - 1, safeNb);

    return convertToIpList(cs);
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  public String toString() {
    return localAddr.toString();
  }

  /**
   * Abstract base class for all candidate selection algorithms with multiple
   * rf channels.
   *
   * @author kurth
   */
  public static abstract class MultiChannel extends CandidateSelection {

    protected boolean preferHomeChannel;
    private byte[] chArray;
    /** the RF channel of the previously calculated candidate set */
    private RadioInterface.RFChannel rFChannelForSelectedCandidateSet;

    public MultiChannel(int csSize, NetAddress localAddr, RouteMetricInterface routeMetric) {
      super(csSize, localAddr, routeMetric);
    }

    /**
     * This method calculates the candidate set for a packet with source address
     * src and destination dst in regard to the used channels.
     *
     * @param src
     *          the source address of the packet
     * @param dst
     *          the final destination of the packet
     * @param preferHomeChannel
     *          indicates whether we should prefer the use of our home channel
     * @return the list of candidates prioritized my their path metric towards the
     *         final destination as List<NetAddress>
     */
    public List calculate(NetAddress src, NetAddress dst,
                          boolean preferHomeChannel, byte[] chArray) {
      this.preferHomeChannel = preferHomeChannel;
      this.chArray = chArray;
      return super.calculate(src, dst, null, null);
    }

    /* (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#calculate(jist.swans.net.NetAddress, jist.swans.net.NetAddress)
     */
    public List calculate(NetAddress src, NetAddress dst, byte[] chArray) {
      this.preferHomeChannel = false;
      this.chArray = chArray;
      return super.calculate(src, dst, null, null);
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#calcShortestPathForEachNeighbor(java.util.List, jist.swans.net.NetAddress, jist.swans.net.NetAddress, int)
     */
    protected List calcShortestPathForEachNeighbor(List neighbors,
        NetAddress src, NetAddress dst, List route, int metric) {
      List candidates = new ArrayList();
      RadioInterface.RFChannel myHomeChannel = routeMetric.getHomeChannel(localAddr);

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

        try {
          // calculate the metric to this neighbor
          int nbMetric = routeMetric.getLinkMetric(src, nb);

          // skip too bad neighbors
          if (nbMetric > maxMetricForNeighbor)
            continue;

          List newRoute = routeMetric.queryRoute(nb, dst, maxMetricForNeighbor, maxEtxForNeighbor); // src, dst

          // calculate path metric
          int routeMetric = this.routeMetric.getRouteMetric(newRoute, maxMetricForNeighbor, maxEtxForNeighbor);

          RadioInterface.RFChannel nbHomeChannel = this.routeMetric.getHomeChannel(nb);

          // prefer always candidates with the same channel
          if (preferHomeChannel && (myHomeChannel.equals(nbHomeChannel))) {
            // candidates on the homechannel are always prefered
          } else if (routeMetric == -1 || routeMetric + metricDelta > metric) {
            // skip neighbors with worser route metric to destination
            continue;
          }

          // add potential neighbor node
          candidates.add(new NetAddressWithMetric(nb, routeMetric, nbMetric));
        } catch (NoLinkExistsException e) {
          continue;
        } catch (NoRouteExistsException e) {
          continue;
        }
      }

      return candidates;
    }

    /* (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#select(jist.swans.net.NetAddress, java.util.List)
     */
    protected List select(NetAddress src, NetAddress dst, List candidates) {
      try {
        // group candidates by their home channel
        Hashtable csSet = createCsPerChannel(src, dst, candidates);

        // choose the most promising candidate set
        rFChannelForSelectedCandidateSet = chooseMostPromisingChannel(csSet,
            src, preferHomeChannel, chArray);

        if (rFChannelForSelectedCandidateSet == null
            ||rFChannelForSelectedCandidateSet.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL))
          return null;

        return convertToIpList((List) csSet.get(rFChannelForSelectedCandidateSet));
      } catch (NoLinkExistsException e) {
        // TODO is this possible
        throw new RuntimeException(e);
      }
    }

    /**
     * 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.
     * @throws NoLinkExistsException
     */
    protected Hashtable createCsPerChannel(NetAddress src, NetAddress dst, List candidates) throws NoLinkExistsException {

      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;
        RadioInterface.RFChannel nbHomeChannel = routeMetric.getHomeChannel(nb);

        if (nbHomeChannel.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL)) {
          log.error(this + "(" + JistAPI.getTime() + "): home ch of nb unknown");
        }

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

      // select a candidate set per channel
      Enumeration chKeys = csSet.keys();
      while (chKeys.hasMoreElements()) {
        RadioInterface.RFChannel chKey = (RadioInterface.RFChannel) chKeys.nextElement();

        List cs = (List) csSet.get(chKey);
        List ncs = super.select(src, dst, cs);

        //
        // check whether the node in the candidate set are well connected to each
        // other according to their
        // priority; this algorithm tries to prevent duplicates in the network
        ncs = choose(cs, ncs);

        csSet.put(chKey, ncs);
      }

      return csSet;
    }

    protected abstract List choose(List cs, List ncs) throws NoLinkExistsException;

    /**
     * This method chooses the most promising cset among all available candidate
     * sets.
     *
     * @param csSet
     *          the hashtable of available csets per channel
     * @param src
     *          calculate the cset for this node
     * @param preferHomeChannel
     *          indicates whether we need to prefer the home channel
     * @throws NoLinkExistsException
     */
    protected RadioInterface.RFChannel chooseMostPromisingChannel(Hashtable csSet,
        NetAddress src, boolean preferHomeChannel, byte[] chArray) throws NoLinkExistsException {

      RadioInterface.RFChannel bestChannel = null;

      int currMinValue = Integer.MAX_VALUE;
      Enumeration chKeys = csSet.keys();
      RadioInterface.RFChannel myHomeChannel = routeMetric.getHomeChannel();
      Util.assertion(!myHomeChannel.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL));
      //
      // check the candidate set for each channel
      //
      while (chKeys.hasMoreElements()) {
        RadioInterface.RFChannel chKey = (RadioInterface.RFChannel) chKeys.nextElement();

        assert (!chKey.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL));

        List cs = (List) csSet.get(chKey);

        double pdiff = 1;
        double csCum = 0;

        boolean isSafeLastHop = false;
        for (int i = 0; i < cs.size(); i++) {
          // log.fatal(cs.get(i));
          // calculate link metric to my neighbors
          NetAddressWithMetric nbInfo = (NetAddressWithMetric) cs.get(i);

          csCum += nbInfo.metric;

          int nbMetric = routeMetric.getLinkMetric(src, nbInfo.ip);

          if ((nbInfo.metric == 0) && (nbMetric <= maxMetricForSafeNB))
            isSafeLastHop = true;

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

        // normiere csCum
        csCum /= cs.size();

        if (isSafeLastHop)
          csCum = 0;

        double pcs = 1 - pdiff; // wahrscheinlichkeit, dass das paket den cset erreicht.

        //
        // algorithm to enforce channel switching
        //
        pcs = enforceChannelSwitch(chKey, chArray, pcs,
            routeMetric.getChannels().length);

        csCum = (1 / pcs) * csCum;

        // prefer candidates with the same channel
        if (preferHomeChannel && (myHomeChannel.equals(chKey))) {
          if (pcs < 0.3)
            if (log.isInfoEnabled())
              log.info(this + "(" + JistAPI.getTime() + "): the prefered cs is quite bad; maybe the network is not dense");
          return chKey;
        }

        if (csCum < currMinValue) {
          currMinValue = (int) csCum;
          bestChannel = chKey;

          if (bestChannel.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL))
            log.error(this + "(" + JistAPI.getTime() + "): aa");
        }
      }
      return bestChannel;
    }

    protected double enforceChannelSwitch(RadioInterface.RFChannel chKey, byte[] chArray,
                                          double pcs, int maxAvChannels) {

      if ((chArray == null) || (chArray.length == 0))
        return pcs;

      int nwCh = chKey.getChannel();
      int chCount = 0;
      for (int i = chArray.length - 1; i >= 0
          && i > chArray.length - maxAvChannels; i--) {
        byte usedCh = chArray[i];

        if (nwCh == usedCh) {
          chCount++;
        }
      }

      if (chCount > 0)
        pcs /= (chCount + 1);
      return pcs;
    }

    public RadioInterface.RFChannel getRFChannelForSelectedCandidateSet() {
      RadioInterface.RFChannel rv = rFChannelForSelectedCandidateSet;
      rFChannelForSelectedCandidateSet = null;
      return rv;
    }
  }

  /**
   * Try to average between metric of highest and lowest candidate.
   *
   * @author kurth
   */
  public static class Averaging extends MultiChannel {

    public Averaging(int csSize, NetAddress localAddr, RouteMetricInterface routeMetric) {
      super(csSize, localAddr, routeMetric);
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection.MultiChannel#choose(java.util.List, java.util.List)
     */
    protected List choose(List cs, List ncs) throws NoLinkExistsException {
      if (null == ncs || ncs.size() < 2 || this.cSetSize < 3
          || cs.size() <= this.cSetSize)
        return (ncs);

      ArrayList nncs = new ArrayList();

      NetAddressWithMetric nb_highest = (NetAddressWithMetric) ncs.get(0);
      NetAddressWithMetric nb_lowest = (NetAddressWithMetric) ncs.get(ncs.size() - 1);
      nncs.add(nb_highest);
      nncs.add(nb_lowest);

      // initial replacement
      int replacements = this.cSetSize - 2;
      NetAddressWithMetric[] replacmentNodes = new NetAddressWithMetric[replacements];
      int minDistReplacement = java.lang.Integer.MAX_VALUE;

      NetAddressWithMetric[] nodes = new NetAddressWithMetric[replacements];
      int[] idx = new int[replacements];
      Arrays.fill(idx, 0);

      // iterate over candidate set
      boolean finished = false;
      while (!finished) {
        boolean cont = false;
        int distance = 0;

        for (int j = 0; j < replacements - 1; j++) {
          for (int k = j + 1; k < replacements; k++) {
            if (idx[j] == idx[k])
              cont = true;
            break;
          }
          if (cont == true)
            break;
        }

        for (int j = 0; false == cont && j < replacements; j++) {
          nodes[j] = (NetAddressWithMetric) cs.get(idx[j]);
          if (nncs.contains(nodes[j])) {
            cont = true;
            break;
          }
          if (0 == j)
            distance += routeMetric.getLinkMetric(nb_lowest.ip, nodes[j].ip);
          else
            distance += routeMetric.getLinkMetric(nodes[j - 1].ip, nodes[j].ip);
        }

        if (!cont) {
          distance += routeMetric.getLinkMetric(nodes[replacements - 1].ip,
              nb_highest.ip);
          if (distance < minDistReplacement) {
            minDistReplacement = distance;
            System.arraycopy(nodes, 0, replacmentNodes, 0, nodes.length);
          }
        }

        idx[0]++;
        for (int i = 0; i < idx.length; i++) {
          if (idx[i] >= cs.size()) {
            idx[i] = 0;
            if (i + 1 < idx.length)
              idx[i + 1]++;
            else
              finished = true;
          }
        }
      }

      if (null != replacmentNodes) {
        nncs.addAll(Arrays.asList(replacmentNodes));
      }

      Collections.sort(nncs);
      return (nncs);
    }
  }


  /**
   * Use the candidates along the best path from src to dst.
   *
   * @author kurth
   */
  public static class BestPaths extends MultiChannel {

    public BestPaths(int csSize, NetAddress localAddr, RouteMetricInterface routeMetric) {
      super(csSize, localAddr, routeMetric);
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection.MultiChannel#choose(java.util.List, java.util.List)
     */
    protected List choose(List cs, List ncs) throws NoLinkExistsException {
      if (null == ncs || this.cSetSize < 2 || cs.size() <= this.cSetSize)
        return (ncs);

      NetAddressWithMetric[] nbs = new NetAddressWithMetric[this.cSetSize];
      int[] nbs_metric = new int[this.cSetSize];
      Arrays.fill(nbs, null);
      Arrays.fill(nbs_metric, Integer.MAX_VALUE);

      // iterate over candidate set
      for (int i = 0; i < cs.size(); i++) {
        NetAddressWithMetric node = (NetAddressWithMetric) cs.get(i);

        // calculate the distance between two candidates
        int distance = routeMetric.getLinkMetric(localAddr, node.ip)
            + node.metric;

        for (int j = 0; j < nbs_metric.length; j++) {
          if (null == nbs[j]) {
            nbs[j] = node;
            nbs_metric[j] = distance;
            break;
          }
          if (nbs[j].equals(node)) {
            break;
          }
          if (distance < nbs_metric[j]) {
            for (int k = nbs_metric.length - 2; k >= j; k--) {
              nbs[k + 1] = nbs[k];
              nbs_metric[k + 1] = nbs_metric[k];
            }
            nbs[j] = node;
            nbs_metric[j] = distance;
            break;
          }
        }
      }

      ArrayList nncs = new ArrayList();

      for (int j = 0; j < nbs.length; j++) {
        if (null != nbs[j] && !nncs.contains(nbs[j]))
          nncs.add(nbs[j]);
      }

      Collections.sort(nncs);
      return (nncs);
    }
  }
}
