package brn.swans.route.metric;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import brn.swans.route.metric.LinkTable.LinkData;

import jist.swans.misc.PriorityList;
import jist.swans.net.NetAddress;

/**
 *
 *
 * @author Kurth
 *
 * TODO adjust to other metrics
 * TODO implement cache aging
 */
@SuppressWarnings("unchecked")
public class EaxMetric {

  public static interface MetricBridge {
    List getNeighbors(NetAddress from);

    double getMetrics(NetAddress from, NetAddress to);

    double getPdr(NetAddress from, NetAddress ci);
  }

  protected static class LinkTableBridge implements MetricBridge {
    protected RouteMetricInterface metric;

    public LinkTableBridge(RouteMetricInterface metric) {
      this.metric = metric;
    }

    public List getNeighbors(NetAddress from) {
      return metric.getNeighbors(from);
    }

    public double getMetrics(NetAddress from, NetAddress to) {
      List route = null;
      double metric = Double.MAX_VALUE;
      try {
        int maxMetricForNeighbor = 500;
        int maxEtxForNeighbor = 500;
        route = this.metric.queryRoute(from, to, maxMetricForNeighbor, maxEtxForNeighbor);
        metric = this.metric.getRouteMetric(route, maxMetricForNeighbor, maxEtxForNeighbor);
        metric = metric / 100.;
      } catch (Exception e) {}
      return metric;
//      LinkData link = metric.getLink(from, to);
//      if (null != link)
//        return link.metric;
//      return Double.MAX_VALUE;
    }

    public double getPdr(NetAddress from, NetAddress to) {
      LinkData link = metric.getLink(from, to);
      if (null != link)
        return 100. / (double)link.etx;
      return 0;
    }

  }

  protected class EaxEntry {
    public NetAddress from;
    public NetAddress to;
    public List candidates;
    public double eax;

    public EaxEntry(NetAddress from, NetAddress to) {
      super();
      this.from = from;
      this.to = to;
    }

    public EaxEntry(NetAddress from, NetAddress to, List candidates, double eax) {
      super();
      this.from = from;
      this.to = to;
      this.candidates = candidates;
      this.eax = eax;
    }

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((from == null) ? 0 : from.hashCode());
      result = prime * result + ((to == null) ? 0 : to.hashCode());
      return result;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      final EaxEntry other = (EaxEntry) obj;
      if (from == null) {
        if (other.from != null)
          return false;
      } else if (!from.equals(other.from))
        return false;
      if (to == null) {
        if (other.to != null)
          return false;
      } else if (!to.equals(other.to))
        return false;
      return true;
    }

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append('"'+from.toString()+'"').append(" [label=\"")
        .append(from.toString()).append(" ").append(eax).append("\"]; ");
      builder.append('"'+from.toString()+'"');

      if (candidates.size() > 0 && !candidates.contains(to)) {
        builder.append(" -> {");
        for (int i = 0; i < candidates.size(); i++)
          builder.append('"'+candidates.get(i).toString()+'"').append(";");
        builder.append(" } ");
      }

      builder.append(" -> ").append('"'+to.toString()+'"').append(";");
      return builder.toString();
    }
  }

  static interface SelectionStrategy {
    double select(NetAddress from, NetAddress to);
  }

  /**
   * Selection heuristics according to Zhang. Start with empty candidate set and
   * find the currently best candidate. Add to cs, if it improves the metric and
   * find the best candidate out of the neighbors excluding the recently added
   * node. Repeat until all neighbors are candidates or no improvement anymore.
   */
  protected class EaxHeuristicsSelect implements SelectionStrategy {
    public double select(NetAddress from, NetAddress to) {
      List g = new LinkedList();
      double metricsFromTo = bridge.getMetrics(from, to);
      EaxComparator comparator = new EaxComparator(to);

      // generate candidate pool G
      List neighbors = bridge.getNeighbors(from);
      for (int i = 0; i < neighbors.size(); i++) {
        NetAddress neighbor = (NetAddress) neighbors.get(i);
        if (bridge.getMetrics(neighbor,to) < metricsFromTo)
          g.add(neighbor);
      }

      double mp = Double.MAX_VALUE;
      double mc = Double.MAX_VALUE;
      PriorityList c = new PriorityList(comparator);

      // pick contributing candidates C from G
      while(true) {
        NetAddress v = null;
        // find the next best candidate v
        for (int i = 0; i < g.size(); i++) {
          NetAddress vj = (NetAddress) g.get(i);
          c.add(vj);
          double mvj = getEax(c,from,to);
          c.remove(vj);
          if (mc > mvj) {
            v = vj;
            mc = mvj;
          }
        }

        // update the candidate list
        if (mc < mp) {
          c.add(v);
          g.remove(v);
          mp = mc;
        }
        else {
          // no more qualified candidates
          break;
        }
      }

      // in the case of a direct link, put in the destination only
      if (c.isEmpty() || metricsFromTo < mp) {
        c.clear();
        c.add(to);
        mp = metricsFromTo;
      }

      // remember mp and c
      EaxEntry entry = new EaxEntry(from,to,new LinkedList(c),mp);
      mapEaxCache.put(entry, entry);

      return mp;
    }
  }

  protected class CompleteEnumeration implements SelectionStrategy {
    private double minPdr = .05;

    public double select(NetAddress from, NetAddress to) {
      List g = new LinkedList();
      double metricsFromTo = bridge.getMetrics(from, to);
      EaxComparator comparator = new EaxComparator(to);

      // generate candidate pool G
      List neighbors = bridge.getNeighbors(from);
      for (int i = 0; i < neighbors.size(); i++) {
        NetAddress neighbor = (NetAddress) neighbors.get(i);
        if (bridge.getMetrics(neighbor,to) < metricsFromTo
            && minPdr  <= bridge.getPdr(from,neighbor))
          g.add(neighbor);
      }

      double mp = Double.MAX_VALUE;
      List c = null;
      PriorityList cj = new PriorityList(comparator);

      double max = Math.pow(2., g.size());
      for (int i = 1; i < max; i++) {
        cj.clear();
        for (int counter = 0, x = i; x > 0; x = x / 2, counter++) {
          if (0 != x % 2)
            cj.add(g.get(counter));
        }

        double mvj = getEax(cj,from,to);
        if (mp > mvj) {
          c = new LinkedList(cj);
          mp = mvj;
        }
      }

      // in the case of a direct link, put in the destination only
      if (c == null || metricsFromTo < mp) {
        c = new LinkedList();
        c.add(to);
        mp = metricsFromTo;
      }

      // remember mp and c
      EaxEntry entry = new EaxEntry(from,to,c,mp);
      mapEaxCache.put(entry, entry);

      return mp;
    }
  }

  protected Map mapEaxCache;

  protected MetricBridge bridge;

  protected SelectionStrategy selector;

  public EaxMetric(RouteMetricInterface metric) {
    this.mapEaxCache = new HashMap();
    this.bridge = new LinkTableBridge(metric);
    this.selector =
      //new EaxHeuristicsSelect();
      new CompleteEnumeration();
  }

  public double getEax(NetAddress from, NetAddress to) {
    EaxEntry entry = (EaxEntry) mapEaxCache.get(new EaxEntry(from,to));
    if (null == entry) {
      selector.select(from, to);
      entry = (EaxEntry) mapEaxCache.get(new EaxEntry(from,to));
    }
    return entry.eax;
  }

  public List getCandidates(NetAddress from, NetAddress to) {
    EaxEntry entry = (EaxEntry) mapEaxCache.get(new EaxEntry(from,to));
    if (null == entry) {
      selector.select(from, to);
      entry = (EaxEntry) mapEaxCache.get(new EaxEntry(from,to));
    }
    return entry.candidates;
  }

  private class EaxComparator implements Comparator {
    private NetAddress to;
    public EaxComparator(NetAddress to) {
      this.to = to;
    }
    public int compare(Object o1, Object o2) {
      NetAddress c1 = (NetAddress) o1;
      NetAddress c2 = (NetAddress) o2;

      double diff = getEax(c1, to) - getEax(c2, to);
      if (.0 == diff)
        return 0;
      else if (diff < 0)
        return -1;
      else
        return 1;
    }
  };

  private double getEax(PriorityList c, NetAddress from, final NetAddress to) {
    double z = 1; // prob none of the candidates receives the packet
    double r = 0; // remaining path costs

    // calculate remaining path costs
    Iterator iter = c.iterator();
    while (null != iter && iter.hasNext()) {
      NetAddress ci = (NetAddress) iter.next();
      double fi = bridge.getPdr(from,ci);
      r = r + getEax(ci,to) * fi * z;
      z = z * (1. - fi);
    }
    r = r / (1. - z);

    // calculate first hop
    double d = 1. / (1. - z); // TODO adjust to other metrics

    return d + r;
  }

}
