//////////////////////////////////////////////////
// JIST (Java In Simulation Time) Project
// Timestamp: <MessageQueue.java Tue 2004/04/06 11:32:34 barr pompom.cs.cornell.edu>
//

// Copyright (C) 2004 by Cornell University
// All rights reserved.
// Refer to LICENSE for terms and conditions of use.

package jist.swans.net;

import jist.swans.Constants;

import org.apache.log4j.Logger;

/**
 * Implements a prioritized queue of items. Items are dequeued in order of
 * their priority, where a lower value priority comes first in the queue.
 * Priority values should be in the range [0, priorities), where
 * <code>priorities</code> is the queue initialization parameter.
 *
 * @author Rimon Barr &lt;barr+jist@cs.cornell.edu&gt;
 * @version $Id: MessageQueue.java,v 1.8 2004/04/06 16:07:49 barr Exp $
 * @since SWANS1.0
 */

public interface MessageQueue
{
  /**
   * IP logger.
   */
  public static final Logger log = Logger.getLogger(MessageQueue.class
      .getName());


  /**
   * Return whether queue is empty.
   *
   * @return whether queue is empty
   */
  public boolean isEmpty();

  /**
   * Return whether the queue is filled to capacity.
   *
   * @return whether queue is filled to capacity
   */
  public boolean isFull();

  /**
   * Return number of items in the queue.
   *
   * @return number of items in the queue
   */
  public int size();

  /**
   * Insert message into queue at end (with lowest priority).
   *
   * @param msg message to insert
   */
  public void insert(QueuedMessage msg);

  /**
   * Return first message, but do not dequeue.
   *
   * @return first message (not dequeued)
   */
  public QueuedMessage get();

  /**
   * Return first message and dequeue.
   *
   * @return first message in queue
   */
  public QueuedMessage remove();

  //////////////////////////////////////////////////
  // priority
  //

  /**
   * Insert message into queue with given priority.
   *
   * @param msg message to insert
   * @param pri message priority
   */
  public void insert(QueuedMessage msg, int pri);

  /**
   * Return priority of first queued message.
   *
   * @return priority of first queued message
   */
  public int getPri();

  /**
   * Return first message of given priority, but do not dequeue.
   *
   * @param pri priority of message requested
   * @return message of given priority (not dequeued), or null if
   *   no such message exists
   */
  public QueuedMessage get(int pri);

  /**
   * Return first message with given priority and dequeue.
   *
   * @param pri priority of message requested
   * @return message of given priority
   */
  public QueuedMessage remove(int pri);

  //////////////////////////////////////////////////
  // IMPLEMENTATIONS
  //

  //////////////////////////////////////////////////
  // NoDropMessage
  //

  public class NoDropMessageQueue implements MessageQueue
  {
    /**
     * Heads of message queues for different priorities.
     */
    protected QueuedMessage[] heads;

    /**
     * Tails of message queues for different priorities.
     */
    protected QueuedMessage[] tails;

    /**
     * Index of highest priority.
     */
    protected byte topPri;

    /**
     * Length of list.
     */
    protected byte size;

    /**
     * List size limit.
     */
    protected byte capacity;

    /**
     * Initialize prioritized message queue.
     *
     * @param priorities number of priority levels
     * @param capacity maximum number of items allowed in list
     */
    public NoDropMessageQueue(byte priorities, byte capacity)
    {
      heads = new QueuedMessage[priorities];
      tails = new QueuedMessage[priorities];
      topPri = Constants.NET_PRIORITY_D_BESTEFFORT;
      size = 0;
      this.capacity = capacity;
    }

    /**
     * Return whether list is empty.
     *
     * @return whether list is empty
     */
    public boolean isEmpty()
    {
      return size==0;
    }

    /**
     * Return whether the list is filled to capacity.
     *
     * @return whether list is filled to capacity
     */
    public boolean isFull()
    {
      return size>=capacity;
    }

    /**
     * Return number of items in the list.
     *
     * @return number of items in the list
     */
    public int size()
    {
      return size;
    }

    /**
     * Insert message into queue with given priority.
     *
     * @param msg message to insert
     * @param pri message priority
     */
    public void insert(QueuedMessage msg, int pri)
    {
      if(size==capacity)
      {
        //throw new IndexOutOfBoundsException("list maximum exceeded");
        return;
      }
      size++;
      topPri = (byte)Math.max(pri, topPri);
      QueuedMessage tail = tails[pri];
      if(tail==null)
      {
        heads[pri] = msg;
        tails[pri] = msg;
      }
      else
      {
        tail.next = msg;
        tails[pri] = msg;
      }
    }

    /**
     * Insert message into queue at end (with lowest priority).
     *
     * @param msg message to insert
     */
    public void insert(QueuedMessage msg)
    {
      insert(msg, heads.length-1);
    }

    /**
     * Return priority of first queued message.
     *
     * @return priority of first queued message
     */
    public int getPri()
    {
      while(heads[topPri]==null) topPri--;
      return topPri;
    }

    /**
     * Return first message of given priority, but do not dequeue.
     *
     * @param pri priority of message requested
     * @return message of given priority (not dequeued), or null if
     *   no such message exists
     */
    public QueuedMessage get(int pri)
    {
      return heads[pri];
    }

    /**
     * Return first message, but do not dequeue.
     *
     * @return first message (not dequeued)
     */
    public QueuedMessage get()
    {
      return heads[getPri()];
    }

    /**
     * Return first message with given priority and dequeue.
     *
     * @param pri priority of message requested
     * @return message of given priority
     */
    public QueuedMessage remove(int pri)
    {
      QueuedMessage msg = heads[pri];
      heads[pri] = msg.next;
      if(msg.next==null)
      {
        tails[pri] = null;
      }
      else
      {
        msg.next = null;
      }
      size--;
      return msg;
    }

    /**
     * Return first message and dequeue.
     *
     * @return first message in queue
     */
    public QueuedMessage remove()
    {
      return remove(getPri());
    }

  }

  /**
   * MessageQueue with a fixed capacity. All incoming packets exceeding the capacity
   * are dropped.
   *
   * @author kurth
   *
   */
  public class DropTailMessageQueue implements MessageQueue {

    /**
     * Heads of message queues for different priorities.
     */
    protected QueuedMessage[] heads;

    /**
     * Tails of message queues for different priorities.
     */
    protected QueuedMessage[] tails;

    /**
     * Index of highest priority.
     */
    protected byte topPri;

    /**
     * Length of list.
     */
    protected int size;

    /**
     * List size limit.
     */
    protected int capacity;

    /**
     * Initialize prioritized message queue.
     *
     * @param priorities number of priority levels
     * @param capacity maximum number of items allowed in list
     */
    public DropTailMessageQueue(int priorities, int capacity)
    {
      heads = new QueuedMessage[priorities];
      tails = new QueuedMessage[priorities];
      topPri = (byte) Constants.NET_PRIORITY_D_BESTEFFORT;
      size = 0;
      this.capacity = capacity;
    }

    /**
     * Return whether list is empty.
     *
     * @return whether list is empty
     */
    public boolean isEmpty()
    {
      return size==0;
    }

    /**
     * Return whether the list is filled to capacity.
     *
     * @return whether list is filled to capacity
     */
    public boolean isFull()
    {
      return size==capacity;
    }

    /**
     * Return number of items in the list.
     *
     * @return number of items in the list
     */
    public int size()
    {
      return size;
    }

    /**
     * Insert message into queue with given priority.
     *
     * @param msg message to insert
     * @param pri message priority
     */
    public void insert(QueuedMessage msg, int pri)
    {
      if(size==capacity){
        // simply drop the packet.
        if (log.isDebugEnabled())
          log.debug(this + " Maximum list size "
              + capacity + " reached, dropping packet" +
              msg.toString());
        return;
      }

      size++;
      topPri = (byte)Math.max(pri, topPri);
      QueuedMessage tail = tails[pri];
      if(tail==null)
      {
        heads[pri] = msg;
        tails[pri] = msg;
      }
      else
      {
        tail.next = msg;
        tails[pri] = msg;
      }
    }

    /**
     * Insert message into queue at end (with lowest priority).
     *
     * @param msg message to insert
     */
    public void insert(QueuedMessage msg)
    {
      insert(msg, heads.length-1);
    }

    /**
     * Return priority of first queued message.
     *
     * @return priority of first queued message
     */
    public int getPri()
    {
      while(heads[topPri]==null) topPri--;
      return topPri;
    }

    /**
     * Return first message of given priority, but do not dequeue.
     *
     * @param pri priority of message requested
     * @return message of given priority (not dequeued), or null if
     *   no such message exists
     */
    public QueuedMessage get(int pri)
    {
      return heads[pri];
    }

    /**
     * Return first message, but do not dequeue.
     *
     * @return first message (not dequeued)
     */
    public QueuedMessage get()
    {
      return heads[getPri()];
    }

    /**
     * Return first message with given priority and dequeue.
     *
     * @param pri priority of message requested
     * @return message of given priority
     */
    public QueuedMessage remove(int pri)
    {
      QueuedMessage msg = heads[pri];
      heads[pri] = msg.next;
      if(msg.next==null)
      {
        tails[pri] = null;
      }
      else
      {
        msg.next = null;
      }
      size--;
      return msg;
    }

    /**
     * Return first message and dequeue.
     *
     * @return first message in queue
     */
    public QueuedMessage remove()
    {
      return remove(getPri());
    }
  }

//  //////////////////////////////////////////////////
//  // FullAccessNoDropMessage
//  //
//
//  /**
//   * Queue thats enables user to examine more than only the first QueuedMessage.
//   */
//  public class FullAccessNoDropMessageQueue extends NoDropMessageQueue {
//
//    /** Internal state to access the next Message. */
//    int accessCounter, accessedPri;
//
//    public FullAccessNoDropMessageQueue(byte priorities, byte capacity) {
//      super(priorities, capacity);
//    }
//
//    /**
//     * Return first message of given priority, but do not dequeue.
//     *
//     * @param pri priority of message requested
//     * @return message of given priority (not dequeued), or null if
//     *   no such message exists
//     */
//    public QueuedMessage get(int pri)
//    {
//      accessCounter = -1;
//      accessedPri = pri;
//      return super.get(pri);
//    }
//
//    /**
//     * Return next message of given priority, but do not dequeue.
//     * consecutive calls work their way throug to queue.
//     * reset with normal get(Pri) call
//     *
//     * @param pri priority of message requested
//     * @return message of given priority (not dequeued), or null if
//     *   no such message exists
//     */
//    public QueuedMessage getNext(int pri)
//    {
//      accessedPri = pri;
//      ++accessCounter;
//
//      return heads[pri].next;
//    }
//  }

} // class: MessageQueue
