OkasakiAppendableQueue.scala

// todo: these data structures expect lists to be non-empty but I've not bothered encoding this
// each non-empty list could be modelled by pulling the head directly into the case class, and having
// a possibly empty tail, but life is short

sealed trait OkasakiAppendableQueue[A] {
  def :+ (a: A): OkasakiAppendableQueue[A]
  def +: (a: A): OkasakiAppendableQueue[A]
  def headTail: Option[(A, OkasakiAppendableQueue[A])]
  def initsLast: Option[(OkasakiAppendableQueue[A], A)]
  def isEmpty: Boolean
  def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A]
}

// todo: Either cheat with a single instance of this that gets cast, or use variance +A and an object
case class OkasakiNil[A]() extends OkasakiAppendableQueue[A] {
  override def :+(a: A): OkasakiAppendableQueue[A] = OkasakiTails(a :: Nil) // could choose Heads

  override def +:(a: A): OkasakiAppendableQueue[A] = OkasakiHeads(a :: Nil) // could choose Tails

  override def headTail: Option[(A, OkasakiAppendableQueue[A])] = None

  override def initsLast: Option[(OkasakiAppendableQueue[A], A)] = None

  override def isEmpty: Boolean = true

  override def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A] = other
}

case class OkasakiHeads[A](heads: List[A]) extends OkasakiAppendableQueue[A] {
  override def :+(a: A): OkasakiAppendableQueue[A] = OkasakiQ[A](heads, a :: Nil)

  override def +:(a: A): OkasakiAppendableQueue[A] = OkasakiHeads(a :: heads)

  override def headTail: Option[(A, OkasakiAppendableQueue[A])] = heads match {
    case h :: Nil =>
      Some((h, OkasakiNil()))
    case h :: t =>
      Some((h, OkasakiHeads(t)))
  }

  override def initsLast: Option[(OkasakiAppendableQueue[A], A)] =
    OkasakiTails(heads.reverse).initsLast

  override def isEmpty: Boolean = false

  override def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A] = other match {
    case OkasakiTails(tails) =>
      OkasakiQ(heads, tails)
    case OkasakiAppend(OkasakiTails(tails), right) =>
      OkasakiAppend(OkasakiQ(heads, tails), right)
    case OkasakiNil() =>
      this
    case _ =>
      OkasakiAppend(this, other)
  }
}

case class OkasakiTails[A](tails: List[A]) extends OkasakiAppendableQueue[A] {
  override def :+(a: A): OkasakiAppendableQueue[A] = OkasakiTails(a :: tails)

  override def +:(a: A): OkasakiAppendableQueue[A] = OkasakiQ(a :: Nil, tails)

  override def headTail: Option[(A, OkasakiAppendableQueue[A])] = OkasakiHeads(tails.reverse).headTail

  override def initsLast: Option[(OkasakiAppendableQueue[A], A)] = tails match {
    case l :: Nil =>
      Some((OkasakiNil(), l))
    case l :: i =>
      Some((OkasakiTails(i), l))
  }

  override def isEmpty: Boolean = false

  override def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A] = other match {
    case OkasakiHeads(heads) =>
      OkasakiQ(heads, tails)
    case OkasakiNil() =>
      this
    case _ =>
      OkasakiAppend(this, other)
  }
}


case class OkasakiQ[A](heads: List[A], tails: List[A]) extends OkasakiAppendableQueue[A] {
  override def :+(a: A): OkasakiAppendableQueue[A] = OkasakiQ(heads, a :: tails)

  override def +:(a: A): OkasakiAppendableQueue[A] = OkasakiQ(a :: heads, tails)

  override def headTail: Option[(A, OkasakiAppendableQueue[A])] = heads match {
    case h :: Nil =>
      Some((h, OkasakiTails(tails)))
    case h :: t =>
      Some((h, OkasakiQ(t, tails)))
  }

  override def initsLast: Option[(OkasakiAppendableQueue[A], A)] = tails match {
    case l :: Nil =>
      Some((OkasakiHeads(heads), l))
    case l :: i =>
      Some((OkasakiQ(heads, i), l))
  }

  override def isEmpty: Boolean = false

  override def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A] = other match {
    case OkasakiNil() =>
      this
    case _ =>
      OkasakiAppend(this, other)
  }
}

case class OkasakiAppend[A](left: OkasakiAppendableQueue[A], right: OkasakiAppendableQueue[A]) extends
  OkasakiAppendableQueue[A] {
  override def :+(a: A): OkasakiAppendableQueue[A] = OkasakiAppend(left, right :+ a)

  override def +:(a: A): OkasakiAppendableQueue[A] = OkasakiAppend(a +: left, right)

  override def headTail: Option[(A, OkasakiAppendableQueue[A])] = left.headTail match {
    case Some((h, leftT)) if leftT.isEmpty =>
      Some((h, right))
    case Some((h, leftT)) =>
      Some(h, OkasakiAppend(leftT, right))
  }

  override def initsLast: Option[(OkasakiAppendableQueue[A], A)] = right.initsLast match {
    case Some((rightI, l)) if rightI.isEmpty =>
      Some((left, l))
    case Some((rightI, l)) =>
      Some((OkasakiAppend(left, rightI), l))
  }

  override def isEmpty: Boolean = false

  override def ++(other: OkasakiAppendableQueue[A]): OkasakiAppendableQueue[A] = (left, right, other) match {
    case (_, _, OkasakiNil()) =>
      this
    case (_, OkasakiHeads(heads), OkasakiTails(tails)) =>
      OkasakiAppend(left, OkasakiQ(heads, tails))
    case _ =>
      OkasakiAppend(this, other)
  }
}