Data Structures - A Persistent Queue

BankersQueue.scala

/**
 * A simple implementation of a Banker's Queue http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf 3.4.2.
 * 
 * Note that this implementation differs slightly from the one described in the original
 * paper in that the reverse operation is performed only when the out/front list is empty.
 * This is done purely to simplify this example implementation. 
 */
sealed trait BankersQueue[+A] {
  /** The head element of the queue, or an exception if empty. */
  def head: A

  /** Some(head) element of the queue, or None. */
  def headOption: Option[A]

  /** The rest of the queue minus the head, an empty queue returns an empty tail. */
  def tail: BankersQueue[A]

  def isEmpty: Boolean

  def size: Int

  /** Returns a new queue with the supplied element at the end. */
  def add[B >: A](a: B): BankersQueue[B]
}

object BankersQueue {
  private val seed = 23
  private val prime = 17

  def apply[A](as: A*): BankersQueue[A] = apply(Nil, as.toList)

  def apply[A](i: List[A], o: List[A]): BankersQueue[A] = (i, o) match {
    case (Nil, Nil)      => Empty
    case (in, Nil)       => apply(Nil, in.reverse)
    case (Nil, a :: Nil) => Singleton(a)
    case (in, out)       => new Multi(in, out)
  }

  private case object Empty extends BankersQueue[Nothing] {
    def add[B](a: B) = BankersQueue(a)
    def head = throw new UnsupportedOperationException("undefined for an Empty BankersQueue")
    def headOption = None
    def tail = Empty
    def isEmpty = true
    def size = 0
  }

  private case class Singleton[A](a: A) extends BankersQueue[A] {
    def add[B >: A](b: B) = BankersQueue(a, b)
    def head = a
    def headOption = Some(a)
    def tail = Empty
    def isEmpty = false
    def size = 1
  }

  private final class Multi[A](in: List[A], out: List[A]) extends BankersQueue[A] {
    def add[B >: A](b: B) = BankersQueue(b :: in, out)
    def head = out.head
    def headOption = out.headOption
    def isEmpty = false
    lazy val tail = apply(in, out.tail)
    lazy val size = in.size + out.size

    override def equals(that: Any) = that match {
      case b: BankersQueue[_] => BankersQueue.equal(this, b)
      case _                  => false
    }

    override lazy val hashCode = {
      @annotation.tailrec
      def loop(q: BankersQueue[A])(i: Int): Int = q.headOption match {
        case Some(h) => loop(q.tail)(h.hashCode * (i + prime))
        case _       => i
      }
      loop(this)(seed)
    }

    override def toString = {
      @annotation.tailrec
      def loop(q: BankersQueue[A])(sb: StringBuilder): String = q.headOption match {
        case Some(h) => loop(q.tail)(sb.append(", ").append(h))
        case _       => sb.append(")").toString
      }
      loop(tail)(new StringBuilder("BankersQueue(").append(head))
    }
  }

  @annotation.tailrec
  private def equal(q1: BankersQueue[_], q2: BankersQueue[_]): Boolean = (q1, q2) match {
    case (Empty, Empty)               => true
    case (Empty, _)                   => false
    case (_, Empty)                   => false
    case (Singleton(a), Singleton(b)) => a.equals(b)
    case _ if q1.head == q2.head      => equal(q1.tail, q2.tail)
    case _                            => false
  }
}