/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2005-2009, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

// $Id: MessageQueue.scala 16893 2009-01-13 13:09:22Z cunei $

package scala.actors

import scala.reflect.Manifest

trait MessageQueue[MsgType <: Message[_]] {
  def isEmpty: Boolean
  def size: Int
  def append(message: MsgType): Unit
  def foldLeft[B](z: B )(f: (B, Any) => B): B
  /**
   * get the nth message matching p from the queue
   * The matching message is NOT removed from the queue
   * @param n the number of matching messages to skip before returning a result
   * @param p predicate used to match a message
   * @return Some(msg) if a matching message is found, otherwise None
   */
  def get(n: Int)(p: MsgType => Boolean): Option[MsgType]
  /**
   * remove the nth message matching p from the queue and return it
   * @param n the number of matching messages to skip before returning a result
   * @param p the predicate used to match a message
   * @return Some(msg) if a matching message is found, otherwise None
   */
  def remove(n: Int)(p: MsgType => Boolean): Option[MsgType]
  /**
   * remove and return the first message matching p
   * equivalent to get(0)(p)
   * @param p the predicate used to match a message
   * @return Some(msg) is a matching message is found, otherwise None
   */
  def extractFirst(p: MsgType => Boolean): Option[MsgType]
}


/**
 * The class <code>MessageQueue</code> provides an efficient
 * implementation of a message queue specialized for this actor
 * library.
 *
 * @version 0.9.9
 * @author Philipp Haller
 */
@serializable
class BasicMessageQueue[MsgType <: Message[_]] extends MessageQueue[MsgType] {

  @serializable
  protected class Element(val message: MsgType, var next: Element) {
    def this(message: MsgType) = this(message, null)
  }

  private var first: Element = null
  /**
   * The last element in the queue
   * This is used so that the append operation can be constant time.
   * last == null iff queue is empty
   */
  private var last: Element = null

  def isEmpty = null eq last

  private var _size = 0
  def size = _size

  protected def changeSize(diff: Int) = {
    _size += diff
  }

  def append(message: MsgType): Unit = {
    changeSize(1) // size always increases by 1

    if (null eq last) { // list empty
      val el = new Element(message)
      first = el
      last = el
    } else {
      val el = new Element(message)
      last.next = el
      last = el
    }
  }

  def foldLeft[B](z: B)(f: (B, Any) => B): B = {
    var acc = z
    var curr = first
    while (curr != null) {
      acc = f(acc, curr.message)
      curr = curr.next
    }
    acc
  }

  /** Returns the n-th msg that satisfies the predicate
   *  without removing it.
   */
  def get(n: Int)(p: MsgType => Boolean) = findMessage(n, p, false)

  /** Removes the n-th msg that satisfies the predicate.
   */
  def remove(n: Int)(p: MsgType => Boolean) = findMessage(n, p, true)

  /**
   * Find the nth element with a mssage matching p and return it
   * @param n the number of matching messages to skip before returning
   * @param p predicate used to test messages
   * @param remove set to true if the message should be removed from the queue before
   *               being returned, false if it should be left in the queue
   * @return Some(msg) if a matching message is found, otherwise None
   */
  def findMessage(n: Int, p: MsgType => Boolean, remove: Boolean) = {
    def f(n: Int, prev: Element, cur: Element): Option[MsgType] = {
      if (cur eq null) None
      else if (p(cur.message)) {
        if (n > 0) f(n - 1, cur, cur.next)
        else {
          if (remove) removeElement(prev, cur)
          Some(cur.message)
        }
      } else f(n, cur, cur.next)
    }
    f(n, null, first)
  }

  protected def removeElement(prev: Element, cur: Element): Unit = {
    if (prev eq null) {
      first = cur.next     // removing the first element
    } else {
      prev.next = cur.next
    }
    if (cur eq last) {
      last = prev    // removing the last element
      if (last eq null) first = null  // queue is now empty
    }
    changeSize(-1)
  }


  def extractFirst(p: MsgType => Boolean) = findMessage(0, p, true)
}