package brn.swans.route.metric;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import jist.runtime.JistAPI;

import org.apache.log4j.Logger;

import brn.swans.route.metric.LinkTable.HostData;
import brn.swans.route.metric.LinkTable.LinkData;
import brn.swans.route.metric.LinkTable.ObjectPair;
import brn.swans.route.metric.RouteMetricInterface.NoLinkExistsException;
import brn.swans.route.metric.RouteMetricInterface.NoRouteExistsException;

/**
 * Runs dijkstra's algorithm occasionally.
 *
 */
public class LinkTableQuerier {

  protected static class DijkstryHostEntry {
    protected Object ip;

    protected int metric = 0;
    protected Object prev = null;
    protected boolean marked = false;

    public DijkstryHostEntry(Object ip) {
      this.ip = ip;
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((ip == null) ? 0 : ip.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 DijkstryHostEntry other = (DijkstryHostEntry) obj;
      if (ip == null) {
        if (other.ip != null)
          return false;
      } else if (!ip.equals(other.ip))
        return false;
      return true;
    }

  }

  protected static class RouteCacheEntry {
    public long time;
    public List route;
    public int minLinkMetric;
    public Object addrSrc;
    public Object addrDst;

    public RouteCacheEntry(Object addrSrc, Object addrDst,
        int minLinkMetric, List route) {
      this.addrSrc = addrSrc;
      this.addrDst = addrDst;
      this.route = route;
      this.time = JistAPI.getTime();
      this.minLinkMetric = minLinkMetric;
    }
  }

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


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

  private Map routeCache;

  private long routeCacheTimeout;

  private LinkTable linkTable;


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

  public LinkTableQuerier(LinkTable linkTable, long routeCacheTimeout) {
    this.routeCache = new HashMap();
    this.routeCacheTimeout = routeCacheTimeout;
    this.linkTable = linkTable;
  }

  public int hashCode() {
    return 1;
  }

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

  /**
   * @return the routeCacheTimeout
   */
  public long getRouteCacheTimeout() {
    return routeCacheTimeout;
  }

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


  // ////////////////////////////////////////////////
  // operations
  //

  public int getLinkMetric(Object from, Object to) throws NoLinkExistsException {
    LinkData nfo = linkTable.getLinkInfo(from, to);
    if (nfo != null)
      return nfo.metric();

    throw new NoLinkExistsException("link not in link table");
  }

  public int getLinkMetric(Object from, Object to, int valueIfNotFound) {
    LinkData nfo = linkTable.getLinkInfo(from, to);
    if (nfo != null)
      return nfo.metric();

    return valueIfNotFound;
  }

  /**
   * Add a fixed route to the cache.
   * 
   * @param route the route to add
   * @param minLinkMetric the associated min link metric
   */
  public void addFixedRoute(List route, int minLinkMetric) {
    Object addrSrc = route.get(0);
    Object addrDst = route.get(route.size()-1);
    
    ObjectPair routeCacheKey = new ObjectPair(addrSrc, addrDst);
    RouteCacheEntry entry = new RouteCacheEntry(addrSrc, addrDst, minLinkMetric, route);
    entry.time = JistAPI.END;
    routeCache.put(routeCacheKey, entry);
  }

  /**
   * Returns the metric of the given route or <code>-1</code> if there is no route available
   *
   * @param route the route
   * @return the metric of the route
   */
  public int getRouteMetric(List /* Object */route, int maxLinkMetric,
      int maxLinkEtx) throws NoRouteExistsException, NoLinkExistsException {
    if (route.size() < 1)
      throw new NoRouteExistsException("invalid route given");

    // only one hop
    if (route.size() == 1)
      return 0; // src = dst; dst reached

    int routeMetric = 0;
    try {
      for (int i = 0; i < route.size() - 1; i++) {
        LinkData nfo = linkTable.getLinkInfo(route.get(i), route.get(i + 1));
        if (nfo.metric() >= maxLinkMetric)
          throw new NoRouteExistsException("min link metric exceeded");
        if (nfo.etx() >= maxLinkEtx)
          throw new NoRouteExistsException("min link etx exceeded");

        routeMetric += nfo.metric();
      }
    } catch (NullPointerException e) {
      throw new NoLinkExistsException("link not in link table");
    }

    return routeMetric;
  }

  public int getRouteMetric(List /* Object */route)
      throws NoRouteExistsException, NoLinkExistsException {
    return getRouteMetric(route, Integer.MAX_VALUE, Integer.MAX_VALUE);
  }

  protected List /* Object */ bestRoute(Object src, Object dst, boolean fromMe,
      int maxLinkMetric, int maxLinkEtx) throws NoRouteExistsException {
    if (dst == null)
      throw new NoRouteExistsException("invalid destination");

    // ip -> DijkstryHostEntry
    Hashtable ipAddrs = dijkstra(src, fromMe, maxLinkMetric, maxLinkEtx);

    List /* Object */reverseRoute = new ArrayList();
    List /* Object */route = null;

    DijkstryHostEntry nfo = (DijkstryHostEntry) ipAddrs.get(dst);

    while (nfo != null && nfo.metric != 0) {
      reverseRoute.add(nfo.ip);
      nfo = (DijkstryHostEntry) ipAddrs.get(nfo.prev);
    }
    if (nfo != null && nfo.metric == 0) {
      reverseRoute.add(nfo.ip);
    }

    if (reverseRoute.size() <= 1)
      throw new NoRouteExistsException("no route found");

    if (fromMe) {
      route = new ArrayList();
      /* why isn't there just push? */
      for (int i = reverseRoute.size() - 1; i >= 0; i--) {
        route.add(reverseRoute.get(i));
      }
      return route;
    }

    return reverseRoute;
  }

  public List /* Object */ getNeighbors(Object ip) {
    List neighbors = new ArrayList();

    Iterator iter = linkTable.getHosts().iterator();
    while (null != iter && iter.hasNext()) {
      HostData neighbor = (HostData) iter.next();

      if (!ip.equals(neighbor.ip)) {
        LinkData lnfo = linkTable.getLinkInfo(ip, neighbor.ip);
        if (lnfo != null)
          neighbors.add(neighbor.ip);
      }
    }

    return neighbors;
  }

  /**
   * Runs Dijkstra Algorithm for the shortest path.
   *
   * @param src    the source node
   * @param fromMe
   * @param maxLinkMetric
   * @return Hashtable < ip -> DijkstryHostEntry >
   */
  protected Hashtable dijkstra(Object src, boolean fromMe,
      int maxLinkMetric, int maxLinkEtx) throws NoRouteExistsException {

    if (linkTable.getHostInfo(src) == null)
      throw new NoRouteExistsException("invalid destination");

    Hashtable /* ip -> DijkstryHostEntry */ ipAddrs = new Hashtable();

    Iterator iter = linkTable.getHosts().iterator();
    while (iter != null && iter.hasNext()) {
      HostData hInfo = (HostData) iter.next();
      if (hInfo.active)
        ipAddrs.put(hInfo.ip, new DijkstryHostEntry(hInfo.ip));
      else
        log.warn("skip node " + hInfo.ip);
    }

    DijkstryHostEntry rootInfo = (DijkstryHostEntry) ipAddrs.get(src);
    rootInfo.prev = rootInfo.ip;
    rootInfo.metric = 0;

    Object currentMinIp = rootInfo.ip;

    while (currentMinIp != null) {
      DijkstryHostEntry currentMin = (DijkstryHostEntry) ipAddrs.get(currentMinIp);
      currentMin.marked = true;

      Iterator hosts = ipAddrs.values().iterator();
      while (hosts != null && hosts.hasNext()) {
        DijkstryHostEntry neighbor = (DijkstryHostEntry) hosts.next();
        if (neighbor.marked)
          continue;

        LinkData lnfo;
        if (fromMe)
          lnfo = linkTable.getLinkInfo(currentMinIp, neighbor.ip);
        else
          lnfo = linkTable.getLinkInfo(neighbor.ip, currentMinIp);

        // ignore links with a very high metric
        if (lnfo == null || lnfo.etx() > maxLinkEtx
            || lnfo.metric() == 0 || lnfo.metric() > maxLinkMetric)
          continue;

        int neighborMetric = neighbor.metric;
        int adjustedMetric = currentMin.metric + lnfo.metric();

        if (neighborMetric == 0 || adjustedMetric < neighborMetric) {
          neighbor.metric = adjustedMetric;
          neighbor.prev = currentMinIp;
        }
      }

      currentMinIp = null;
      int minMetric = Integer.MAX_VALUE;

      // Determine host with min metric which is not already marked yet
      hosts = ipAddrs.values().iterator();
      while (hosts != null && hosts.hasNext()) {
        DijkstryHostEntry nfo = (DijkstryHostEntry) hosts.next();

        // TODO minEtx??
        if (!nfo.marked && nfo.metric != 0 && nfo.metric < minMetric) {
          currentMinIp = nfo.ip;
          minMetric = nfo.metric;
        }
      }
    }

    return ipAddrs;
  }

  public List /* Object */queryRoute(Object addrSrc, Object addrDst,
      int maxLinkMetric, int maxLinkEtx, boolean fromCache) throws NoRouteExistsException {

    // TODO maxLinkEtx
    ObjectPair routeCacheKey = new ObjectPair(addrSrc, addrDst);
    if (fromCache) {
      RouteCacheEntry entry = (RouteCacheEntry) routeCache.get(routeCacheKey);
      if (null != entry) {
        if (maxLinkMetric != entry.minLinkMetric)
          log.warn("min link metric differ!");
        else if (entry.time == JistAPI.END 
            || entry.time + routeCacheTimeout >= JistAPI.getTime())
          return entry.route;
      }
    }

    // current node is not final destination of the packet,
    // so lookup route from dsr table and generate a dsr packet
//    dijkstra(addrSrc, true, maxLinkMetric, maxLinkEtx);

    List route = bestRoute(addrSrc, addrDst, true, maxLinkMetric, maxLinkEtx);
    routeCache.put(routeCacheKey,
        new RouteCacheEntry(addrSrc, addrDst, maxLinkMetric, route));

    return route;
  }

  public void invalidateRoute(Object addrSrc, Object addrDst) {
    ObjectPair routeCacheKey = new ObjectPair(addrSrc, addrDst);
    routeCache.remove(routeCacheKey);
  }
}