import java.util.NoSuchElementException

import scala.collection.generic._
import scala.collection.immutable.LinearSeq
import scala.collection.{SeqLike, mutable}
import scala.{specialized ⇒ sp}

sealed trait CherryTree[+T]
  extends LinearSeq[T]
    with SeqLike[T, CherryTree[T]]
    with GenericTraversableTemplate[T, CherryTree] {
  override def stringPrefix: String = "CherryTree"

  def :+[A >: T](x: A): CherryTree[A]

  def +:[A >: T](x: A): CherryTree[A]

  override def companion = CherryTree

  protected def sizeList: List[Int]

  protected def get(idx: Int, sl: List[Int]): T
}


object CherryTree extends TraversableFactory[CherryTree] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, CherryTree[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  override def newBuilder[A] = new mutable.Builder[A, CherryTree[A]] {
    override def +=(elem: A): this.type = {result :+= elem; this}
    override def clear(): Unit = result = Empty
    var result: CherryTree[A] = Empty
  }

  private trait Tail[@sp +T] {
    def foreach[U](f: T ⇒ U): Unit

    def size: Int

    def head: T

    def last: T
  }

  private case class Tail1[@sp +T](x: T) extends Tail[T] {
    override def foreach[U](f: (T) ⇒ U): Unit = f(x)
    override def size: Int = 1
    override def head = x
    override def last = x
  }

  private case class Tail2[@sp +T](x: T, y: T) extends Tail[T] {
    override def foreach[U](f: (T) ⇒ U): Unit = {f(x); f(y)}
    override def size: Int = 2
    override def head: T = x
    override def last: T = y
  }

  private case object Empty extends CherryTree[Nothing] {
    override def :+[A](x: A) = Single(x)
    override def +:[A](x: A) = Single(x)
    override def length = 0
    override def isEmpty = true
    override def apply(idx: Int) = throw new NoSuchElementException
    override def sizeList: List[Int] = List(0)
    override protected def get(idx: Int, sl: List[Int]) = throw new NoSuchElementException
    override def foreach[U](f: (Nothing) ⇒ U) = ()
    override def head = throw new NoSuchElementException
    override def tail = throw new NoSuchElementException
    override def last = throw new NoSuchElementException
    override def init = throw new NoSuchElementException
  }

  private case class Single[+T](value: T) extends CherryTree[T] {
    override def :+[A >: T](x: A): CherryTree[A] = Cons(Tail1(value), Empty, Tail1(x))
    override def +:[A >: T](x: A): CherryTree[A] = Cons(Tail1(x), Empty, Tail1(value))
    override def length: Int = 1
    override def apply(idx: Int) = if (idx == 0) value else throw new NoSuchElementException
    override def isEmpty: Boolean = false
    override def sizeList: List[Int] = List(1)
    override protected def get(idx: Int, sl: List[Int]): T = value
    override def foreach[U](f: (T) ⇒ U): Unit = f(value)
    override def head = value
    override def tail = Empty
    override def last = value
    override def init = Empty
  }

  private case class Cons[+T](left: Tail[T], sub: CherryTree[Tail2[T]], right: Tail[T]) extends CherryTree[T] {
    override def :+[A >: T](x: A): CherryTree[A] = right match {
      case Tail1(y) ⇒ copy(right = Tail2(y, x))
      case Tail2(y, z) ⇒ copy(right = Tail1(x), sub = sub :+ Tail2(y, z))
    }
    override def +:[A >: T](x: A): CherryTree[A] = left match {
      case Tail1(y) ⇒ copy(left = Tail2(x, y))
      case Tail2(y, z) ⇒ copy(left = Tail1(x), sub = Tail2(y, z) +: sub)
    }
    override def length: Int = left.size + 2 * sub.length + right.size
    override def isEmpty: Boolean = false
    override def sizeList: List[Int] = {
      val subList = sub.sizeList
      (left.size + subList.head * 2 + right.size) :: subList
    }

    override def apply(idx: Int) = left match {
      case Tail1(x) if idx == 0 ⇒ x
      case Tail2(x, y) if idx < 2 ⇒ if (idx == 0) x else y
      case _ ⇒ get(idx, sizeList)
    }

    override protected def get(idx: Int, sl: List[Int]): T =
      if (idx < left.size) left match {
        case Tail1(x) ⇒ x
        case Tail2(x, y) ⇒ if (idx == 0) x else y
      } else if (idx >= sl.head - right.size) right match {
        case Tail1(x) ⇒ x
        case Tail2(x, y) ⇒ if (idx == sl.head - 1) y else x
      } else {
        val idxFixed = idx - left.size
        val s = sub.get(idxFixed / 2, sl.tail)
        if (idxFixed % 2 == 0) s.x else s.y
      }

    override def foreach[U](f: (T) ⇒ U): Unit = {
      left.foreach(f)
      sub.foreach {_.foreach(f)}
      right.foreach(f)
    }

    override def head = left.head

    override def tail = left match {
      case Tail2(_, x) ⇒ Cons(Tail1(x), sub, right)
      case _ if sub.nonEmpty ⇒ Cons(sub.head, sub.tail, right)
      case _ ⇒ right match {
        case Tail1(x) ⇒ Single(x)
        case Tail2(x, y) ⇒ Cons(Tail1(x), Empty, Tail1(y))
      }
    }

    override def last = right.last

    override def init = right match {
      case Tail2(x, _) ⇒ Cons(left, sub, Tail1(x))
      case _ if sub.nonEmpty ⇒ Cons(left, sub.init, sub.last)
      case _ ⇒ left match {
        case Tail1(x) ⇒ Single(x)
        case Tail2(x, y) ⇒ Cons(Tail1(x), Empty, Tail1(y))
      }
    }
  }
}