package brn.swans.route.metric;

import java.util.ArrayList;
import java.util.Collection;
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 jist.runtime.Main;
import jist.swans.Constants;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.misc.Pickle;
import jist.swans.misc.Util;
import jist.swans.net.NetAddress;
import jist.swans.radio.RadioInterface;

import org.apache.log4j.Logger;

import brn.swans.route.metric.LinkProbe.LinkEntry;
import brn.swans.route.metric.LinkTable.LinkData;
import brn.util.ObjectPool;
import brn.util.PoolableObject;

/**
 * Measures Multi-channel Link Stat (used by ETX metric)
 *
 * TODO pooling of RateSizes ProbeTs
 *
 *
 * @author Tolja
 * @author kurth
 */
public class LinkStat {

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

  /** prune links with < 25% PDR */
  protected static final int MIN_PDR_LINKPROBE = 25;

  //////////////////////////////////////////////////
  //  helper classes
  //

  private static class NeighborInfo {
    private NetAddress addr;
    private RadioInterface.RFChannel homeChannel;

    public NeighborInfo(NetAddress addr, RadioInterface.RFChannel homeChannel) {
      this.addr = addr;
      this.homeChannel = homeChannel;
    }

    public NetAddress getAddress() {
      return addr;
    }

    public RadioInterface.RFChannel getHomeChannel() {
      return homeChannel;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    public int hashCode() {
      final int PRIME = 31;
      int result = 1;
      result = PRIME * result + ((addr == null) ? 0 : addr.hashCode());
      result = PRIME * result + ((homeChannel == null) ? 0 : homeChannel.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 NeighborInfo other = (NeighborInfo) obj;
      if (addr == null) {
        if (other.addr != null)
          return false;
      } else if (!addr.equals(other.addr))
        return false;
      if (homeChannel == null) {
        if (other.homeChannel != null)
          return false;
      } else if (!homeChannel.equals(other.homeChannel))
        return false;
      return true;
    }

  }

  public static class RateSize {
    public Integer rate;
    public int size;

    public RateSize(Integer rate, int size) {
      this.rate = rate;
      this.size = size;
    }

    public String toString() {
      return rate + "/" + size;
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((rate == null) ? 0 : rate.hashCode());
      result = prime * result + size;
      return result;
    }
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      final RateSize other = (RateSize) obj;
      if (rate == null) {
        if (other.rate != null)
          return false;
      } else if (!rate.equals(other.rate))
        return false;
      if (size != other.size)
        return false;
      return true;
    }

  }

  public static class RateSizeChannel extends RateSize {
    public RadioInterface.RFChannel ch;

    public RateSizeChannel(Integer rate, int size, RadioInterface.RFChannel ch) {
      super(rate, size);
      this.ch = ch;
    }

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

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

  public static class LinkInfo extends RateSize implements Message, Cloneable {
    protected final static int BASE_SIZE = 5;

    public int fwd;

    public int rev;

    public LinkInfo(Integer rate, int size, int fwd, int rev) {
      super(rate, size);
      this.fwd = fwd;
      this.rev = rev;
    }

    public LinkInfo(byte[] data, int offset) {
      super(Pickle.arrayToUShort(data, offset),
          Pickle.arrayToUByte(data, offset+2)*Constants.BANDWIDTH_1Mbps/2);
      this.fwd = Pickle.arrayToUByte(data, offset + 3);
      this.rev = Pickle.arrayToUByte(data, offset + 4);
    }

    /*
     * (non-Javadoc)
     * @see jist.swans.misc.Message#getBytes(byte[], int)
     */
    public void getBytes(byte[] msg, int offset) {
      Pickle.ushortToArray(size, msg, offset);
      Pickle.ubyteToArray(rate*2/Constants.BANDWIDTH_1Mbps, msg, offset + 2);
      Pickle.ubyteToArray(fwd, msg, offset + 3);
      Pickle.ubyteToArray(rev, msg, offset + 4);
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.metric.LinkStat.RateSize#toString()
     */
    public String toString() {
      StringBuffer str = new StringBuffer();
      str.append("size ").append(size);
      str.append(" rate ").append(rate);
      str.append(" fwd ").append(fwd);
      str.append(" rev ").append(rev);

      return str.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#clone()
     */
    public Object clone() {
      return new LinkInfo(this.rate, this.size, this.fwd, this.rev);
    }

    /*
     * (non-Javadoc)
     * @see jist.swans.misc.Message#getSize()
     */
    public int getSize() {
      return BASE_SIZE;
    }
  }

  /**
   * record probes received from other hosts
   */
  private static class ProbeT extends RateSize implements PoolableObject {
    protected long when;

    protected long seqNum;

    protected ProbeT() {
      super (null,0);
    }

    public void init(long when, long seqNum, Integer rate, int size) {
      this.rate = rate;
      this.size = size;
      this.when = when;
      this.seqNum = seqNum;
    }

    public void init() {
    }

    public void returned() {
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString() {
      return super.toString() + " ("+seqNum+"/"+when+") ";
    }
  }

  private static class ProbeListT {

    protected NetAddress ip;

    /** period of this node's probes, as reported by the node */
    protected long period;

    /** this node's stats averaging period, as reported by the node */
    protected long tau;

    protected int sent;

    protected int numProbes;

    protected long seqNum;

    protected long lastRx;

    protected Map /* RateSize x LinkInfo */ linkInfos;

    /**
     * TODO: Queue; most recently received probes
     */
    protected List /* ProbeT */ probes;

    private static ObjectPool probePool = new ObjectPool.Dynamic(5000) {
      protected PoolableObject newObject() {
        return new ProbeT();
      }
    };

    public ProbeListT(NetAddress ip, long period, long tau) {
      this.ip = ip;
      this.period = period;
      this.tau = tau;
      this.sent = 0;
      this.probes = new ArrayList();
      this.linkInfos = new HashMap();
      if (period == 0) {
        throw new Error("invalid value period=0");
      }
    }

    private final void addProbe(ProbeT probe, long start) {
      probes.add(probe);

      // A - B > C
      long delta  = Constants.SECOND + tau; // in seconds
      long expiry = Math.max(JistAPI.getTime() - delta, 0);

      // keep stats for at least the averaging period; kick old probes
      while (probes.size() > 0
          && expiry > ((ProbeT) probes.get(0)).when) { // TODO
        probePool.returnObject(probes.get(0));
        probes.remove(0);
      }

      // lookup link info
      LinkInfo linkInfo = (LinkInfo)
        linkInfos.get(new RateSize(probe.rate, probe.size));
      if (null == linkInfo) { // entry not found
        linkInfo = new LinkInfo(probe.rate, probe.size, 0, 0);
        linkInfos.put(new RateSize(probe.rate, probe.size),
            linkInfo);
      }

      // update the reverse rate according to the received probe
      linkInfo.rev = (int) revRate(start, probe.rate, probe.size);
    }

    private final long revRate(long start, Integer rate, int size) {
      long earliest = JistAPI.getTime() - tau;

      int num = 0;
      for (int i = probes.size() - 1; i >= 0; i--) {
        ProbeT probeT = (ProbeT) probes.get(i);
        if (earliest > probeT.when)
          break;
        if (probeT.size == size && probeT.rate.equals(rate))
          num++;
      }

      assert (linkInfos.size() != 0);

      long numExpected = tau / period;

      long rvalue = 100 * num / numExpected;

      if (100 < rvalue)
        return 100;

      return rvalue;
    }

    public void probeArrived(LinkProbe lp, long start, NetAddress localAddr,
        Metric metric) {
      if (Main.ASSERT)
        Util.assertion(lp.ip.equals(ip));

      if (period != lp.period*Constants.MILLI_SECOND) {
        log.warn("BRNLinkStat " + ip + " has changed its link probe period from "
            + period + " to " + lp.period*Constants.MILLI_SECOND + "; clearing probe info");
        for (int i = 0; i < probes.size(); i++)
          probePool.returnObject(probes.get(i));
        probes.clear();
      }
      if (tau != lp.tau*Constants.MILLI_SECOND) {
        log.warn("BRNLinkStat " + ip + " has changed its link tau from "
                + period + " to " + lp.tau*Constants.MILLI_SECOND + " clearing probe info");
        for (int i = 0; i < probes.size(); i++)
          probePool.returnObject(probes.get(i));
        probes.clear();
      }

      if (lp.sent < sent) {
        log.warn("BRNLinkStat " + ip + " has reset; clearing probe info");
        for (int i = 0; i < probes.size(); i++)
          probePool.returnObject(probes.get(i));
        probes.clear();
      }

      long timeNow = JistAPI.getTime();
      period    = lp.period*Constants.MILLI_SECOND;
      tau       = lp.tau*Constants.MILLI_SECOND;
      sent      = lp.sent;
      lastRx    = timeNow;
      numProbes = lp.numProbes;
      seqNum    = lp.seqNum;

      // add arrived probe to internal structures
      ProbeT probe = (ProbeT) probePool.getObject();
      probe.init(timeNow, lp.seqNum, lp.rate, lp.size);
      addProbe(probe, start);

      // fetch link entries
      RateSize tmpRateSize = new RateSize(probe.rate, probe.size);
      for (int linkNumber = 0; linkNumber < lp.linkEntries.size(); linkNumber++) {
        LinkEntry entry = (LinkEntry) lp.linkEntries.get(linkNumber);

        long seq = lp.seqNum;
        List /* LinkInfo */ recvLinkInfo = entry.linkinfo;

        // reverse delivery ratio is available -> use it.
        if (entry.ip.equals(localAddr)) {
          seq = (long) timeNow;
          recvLinkInfo = new ArrayList();
          for (int m = 0; m < entry.linkinfo.size(); m++) {
            // Note: do not change nfo since it is shared by all receivers !!
            LinkInfo nfo = (LinkInfo) entry.linkinfo.get(m);

            tmpRateSize.rate = nfo.rate;
            tmpRateSize.size = nfo.size;

            LinkInfo linkInfo = (LinkInfo) linkInfos.get(tmpRateSize);
            if (null == linkInfo) { // entry not found
              linkInfo = new LinkInfo(nfo.rate, nfo.size, 0, 0);
              linkInfos.put(tmpRateSize, linkInfo);
            }
            linkInfo.fwd = nfo.rev;
            recvLinkInfo.add(linkInfo);
          }
        }

        metric.updateLink(ip, entry.ip, seq, recvLinkInfo);
      }
    }

    /* (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());
      result = PRIME * result + (int) (period ^ (period >>> 32));
      result = PRIME * result + (int) (tau ^ (tau >>> 32));
      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 ProbeListT other = (ProbeListT) obj;
      if (ip == null) {
        if (other.ip != null)
          return false;
      } else if (!ip.equals(other.ip))
        return false;
      if (period != other.period)
        return false;
      if (tau != other.tau)
        return false;
      return true;
    }
  }

  public interface Metric {

    LinkTable getLinkTable();

    void updateLink(NetAddress ip, NetAddress ip2, long seq, List recvLinkInfo);

  }

  // ////////////////////////////////////////////////
  // member
  //
  public final static int CLEAN_UP_TIMEOUT = 6000;

  protected long tau; /* JiST-Time (ns) */

  protected long period; /* JiST-Time (ns) */

  protected int sent;

  protected int seqId;

  protected Metric metric;

  protected long start;

  /**
   * Per-sender map of received probes; map contains information about the
   * link quality to all my neighbors
   */
  private Hashtable /* NetAddress -> ProbeListT */bcastStats;

  private List /* NeighborInfo */neighbors;

  // sometimes it is not possible to put the complete information of all my
  // neighbors into the probe packets;
  // so we point to the next neighbor
  private int nextNeighborToAd;

  protected RateSizeChannel[] adsRs;

  protected RadioInterface.RFChannel[] adsChannels;

  private int adsRsIndex;

  protected NetAddress localAddr;

  private RadioInterface.RFChannel homeChannel = RadioInterface.RFChannel.DEFAULT_RF_CHANNEL;

//  private RateTable rtable;

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

  public LinkStat(NetAddress localAddr, long period, long tau, Metric etxMetric,
      int[] probes, int numberOfChannels, AvailableRates rates, long frequency) {
    this(localAddr, period, tau, probes, numberOfChannels, rates, frequency);
    this.metric = etxMetric;
  }

  public LinkStat(NetAddress localAddr, long period, long tau, int[] probes,
      int numberOfChannels, AvailableRates rates, long frequency) {
    this.sent = 0;
    this.nextNeighborToAd = 0;
    this.adsRsIndex = 0;
    this.neighbors = new ArrayList();
    this.bcastStats = new Hashtable();

    this.localAddr = localAddr;
    this.period = period;
    this.tau = tau;
    this.adsChannels = new RadioInterface.RFChannel[numberOfChannels];
    for (int i = 0; i < numberOfChannels; i++)
      adsChannels[i] = new RadioInterface.RFChannel(frequency, i + 1);

    if (null != rates)
      throw new Error("RateTable not available");
//      this.rtable = new RateTable(rates, rates.lookup(me));

    parseProbes(probes, adsChannels);
    reset();
  }

  public Metric getMetric() {
    return metric;
  }

  public int hashCode() {
    return 1;
  }

  public RadioInterface.RFChannel[] getAdsChannels() {
    return adsChannels;
  }

  /**
   * @param metric the metric to set
   */
  public void setMetric(Metric metric) {
    this.metric = metric;
  }

  private void parseProbes(int[] probe, RadioInterface.RFChannel[] adsChannels) {
    if (probe.length % 2 != 0) {
      String msg = "must provide even number of numbers.";
      //log.fatal(msg);
      throw new RuntimeException(msg);
    }

    adsRs = new RateSizeChannel[probe.length/2 * adsChannels.length];

    for (int i = 0; i < adsChannels.length; i++) {
      for (int x = 0; x < probe.length/2; x++) {
        Integer rate = Integer.valueOf(probe[2*x]);
        int size = probe[2*x + 1];
        adsRs[i*probe.length/2 + x] = new RateSizeChannel(rate, size, adsChannels[i]);
      }
    }

    if (adsRs.length == 0) {
      String msg = "no PROBES provided.";
      //log.fatal(msg);
      throw new RuntimeException(msg);
    }

    for (int i = 0; i < adsRs.length; i++) {
      RateSizeChannel rsc = (RateSizeChannel) adsRs[i];
      for (int j = i+1; j < adsRs.length; j++) {
        if (adsRs[j].equals(rsc))
          // duplicate probes lead to wrong link estimates!!!
          throw new Error("duplicate probe: " + rsc);
      }
    }
  }

  public void setHomeChannel(RadioInterface.RFChannel ch) {
    this.homeChannel = ch;
  }

  public RadioInterface.RFChannel getHomeChannel() {
    return homeChannel;
  }

  public LinkTable getLinkTable() {
    return metric.getLinkTable();
  }

  public RadioInterface.RFChannel getNeighborHomeChannel(NetAddress addr) {
    for (int i = 0; i < neighbors.size(); i++) {
      NeighborInfo nbInfo = (NeighborInfo) neighbors.get(i);
      if (nbInfo.getAddress().equals(addr)) {
        return nbInfo.getHomeChannel();
      }
    }
    return RadioInterface.RFChannel.INVALID_RF_CHANNEL;
  }

  public List getNeighborHomeChannels(int maxLinkMetric) {
    List nbCh = new ArrayList();
    for (int i = 0; i < neighbors.size(); i++) {
      NeighborInfo nbInfo = (NeighborInfo) neighbors.get(i);

      // only clear neighbors are considered
      LinkData ldata = getLinkTable().getLinkInfo(localAddr, nbInfo.addr);

      // skip too bad neighbors
      if (null == ldata || ldata.metric > maxLinkMetric) {
        continue;
      }

      if (!nbCh.contains(nbInfo.getHomeChannel()))
        nbCh.add(nbInfo.getHomeChannel());
    }

    RadioInterface.RFChannel my_home_ch = getHomeChannel();
    if (nbCh.contains(my_home_ch)) {
      nbCh.remove(my_home_ch);
      nbCh.add(0, my_home_ch);
    }

    return nbCh;
  }

  public long getPeriod() {
    return period;
  }

  public long getJitter(long maxJitter) {
    return Constants.random.nextLong() % (maxJitter + 1);
  }

  public long calcNextSendPacket() {
    long p = period / adsRs.length; // period (nanosecs)

    return p + getJitter(p / 10);
  }

  public void clearStale() {
    long time = JistAPI.getTime();

    Iterator iter = neighbors.iterator();
    while (iter.hasNext()) {
      NeighborInfo n = (NeighborInfo) iter.next();

      ProbeListT l = (ProbeListT) bcastStats.get(n.getAddress());
      long delta = 2 * l.tau; // in seconds
      long expiry = time - delta;

      if (l == null
          || time >= 0 && l.lastRx < expiry) {
        if (log.isDebugEnabled())
          log.debug("clearing stale neighbor " + n + " age " + (time - l.lastRx));
        bcastStats.remove(n.getAddress());
        iter.remove();
      }
    }
  }


  /*
  * This method is called periodically (_period / _ads_rs.size() +/- jitter
  * msecs) to inform neighbor nodes about his links.
  */
  public LinkProbe sendProbe() {

    if (adsRs.length == 0) {
      if (log.isDebugEnabled())
        log.debug("no probes to send");
      return null;
    }

    // size of the probe packet (e.g. 1000 byte)
    int size = adsRs[adsRsIndex].size;
    // probe packet's transmission rate (e.g. 22)
    Integer rate = adsRs[adsRsIndex].rate;

    RadioInterface.RFChannel nextChannel = adsRs[adsRsIndex].ch;

    if (log.isDebugEnabled())
      log.debug(localAddr + "(" + JistAPI.getTime() + "): sendProbe ... via ch " + nextChannel);

    // points to the next probe packet type
    adsRsIndex = (adsRsIndex + 1) % adsRs.length;

    // how many probes this node has sent
    sent++;

    seqId = (seqId+1) % Integer.MAX_VALUE;

    return constructAndSendProbe(seqId, rate, size, nextChannel);
  }

  private LinkProbe constructAndSendProbe(int seqId, Integer rate, int size,
      RadioInterface.RFChannel nextChannel) {
    // construct probe packet
    LinkProbe lp = new LinkProbe(localAddr, seqId, period, tau, sent, rate,
        size, adsRs.length, nextChannel, adsChannels.length, homeChannel);

//    // set available rates
//    if (this.rtable != null)
//      this.rtable.setRates(lp);

    // iterate over my neighbor list and append link information to packet
    // TODO check size !!
    while (lp.linkEntries.size() < neighbors.size()) {
      nextNeighborToAd = (nextNeighborToAd + 1) % neighbors.size();

      ProbeListT probeList = (ProbeListT) bcastStats.get(
          ((NeighborInfo) neighbors.get(nextNeighborToAd)).getAddress());

      if (probeList == null) {
        log.warn("lookup for " + ((NeighborInfo) neighbors.get(nextNeighborToAd)).getAddress()
            + " failed in ad " + nextNeighborToAd);
        continue;
      }

      // append link info
      Collection collLinkInfos = probeList.linkInfos.values();
      ArrayList clonedLinkInfos = new ArrayList(collLinkInfos.size());
      Iterator iter = collLinkInfos.iterator();
      while (iter.hasNext()) {
        LinkInfo linkInfo = (LinkInfo) iter.next();
        // prune links with < 25% PDR
        if (linkInfo.rev < MIN_PDR_LINKPROBE)
          continue;
        clonedLinkInfos.add(linkInfo.clone());
      }

      lp.linkEntries.add(new LinkEntry(probeList.ip, clonedLinkInfos));
    }

    if (log.isDebugEnabled())
      log.debug(localAddr + "(" + JistAPI.getTime() + ", ch=" + homeChannel + ") send: "
          + lp.toString());

    // given rate
    return lp;
  }

  /**
   * Handles an incoming probe packet.
   */
  public void handleMsg(Message msg, MessageAnno anno) {
    LinkProbe lp  = (LinkProbe) msg;
    NetAddress ip = lp.getIp();

    // sanity checks
    if (Main.ASSERT) {
      Integer rate = (Integer)anno.get(MessageAnno.ANNO_MAC_BITRATE);
      RadioInterface.RFChannel operatingChannel
        = (RadioInterface.RFChannel)anno.get(MessageAnno.ANNO_MAC_RF_CHANNEL);

      Util.assertion(!ip.equals(localAddr));

      // bit rate anno must be set!
      if (!lp.rate.equals(rate))
        log.error(this + "(" + JistAPI.getTime() + "): link probe rate is " +
            lp.rate + ", but found rate " + rate + "in annos; drop it.");

      Util.assertion(operatingChannel != null);
      Util.assertion(operatingChannel.equals(lp.nextChannel));
    }

    // fetch sender's probe list
    ProbeListT probeList = (ProbeListT) bcastStats.get(ip);
    if (probeList == null) { // new neighbor
      probeList = new ProbeListT(ip, lp.period * Constants.MILLI_SECOND,
          lp.tau * Constants.MILLI_SECOND);
      bcastStats.put(ip, probeList);
      neighbors.add(new NeighborInfo(ip, lp.homeChannel));
    }

    probeList.probeArrived(lp, start, localAddr, metric);

//  if (rtable != null && null != lp.availableRates) { // available
//  rtable.processRate(lp);
//}
  }

  private void reset() {
    neighbors.clear();
    bcastStats.clear();
    sent = 0;
    start = JistAPI.getTime();
  }

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

