import scala.collection.{mutable, _}

final class Alternating[Even, Odd] private(val first: Even, val rest: Seq[(Odd, Even)])
  extends immutable.Iterable[Either[Even, Odd]] {
  self =>

  def this(firstElement: Even) = this(firstElement, Seq())

  def appended[E >: Even, O >: Odd](elem: (O, E)): Alternating[E, O] =
    new Alternating[E, O](first, rest :+ elem)

  def prepended[E >: Even, O >: Odd](elem: (E, O)): Alternating[E, O] =
    new Alternating[E, O](elem._1, (elem._2, first) +: rest)

  @inline def :+[E >: Even, O >: Odd](elem: (O, E)): Alternating[E, O] = appended(elem)

  @inline def +:[E >: Even, O >: Odd](elem: (E, O)): Alternating[E, O] = prepended(elem)

  def apply(i: Int): Either[Even, Odd] = i match {
    case 0 => Left(first)
    case even if i % 2 == 0 => Left(rest(i / 2 - 1)._2)
    case odd => Right(rest(i / 2)._1)
  }

  def length = rest.length * 2 + 1

  override def iterator: Iterator[Either[Even, Odd]] = new AbstractIterator[Either[Even, Odd]] {
    private var current = 0
    override def hasNext = current < self.length
    override def next() = {
      val elem = self(current)
      current += 1
      elem
    }
  }

  def evens: Seq[Even] = first +: rest.map { case (o, e) => e }

  def odds: Seq[Odd] = rest.map { case (o, e) => o }

  def evenSlide: Seq[(Option[Odd], Even, Option[Odd])] = {
    val someOdds = odds.map(Some.apply)
    (None +: someOdds, evens, someOdds :+ None).zipped.toSeq
  }

  def oddSlide: Seq[(Even, Odd, Even)] = (evens.init, odds, evens.tail).zipped.toSeq

  def slideBoth: Iterable[Either[(Option[Odd], Even, Option[Odd]), (Even, Odd, Even)]] = evenSlide interscalate oddSlide
}

object CollectionUtil {
  implicit class IterableOps[A](val iterable: Iterable[A]) {
    def intersperse(other: Iterable[A]): Iterable[A] =
      iterable
        .map(List(_))
        .zipAll(
          other
            .map(List(_)),
          Nil,
          Nil
        )
        .flatMap(Function.tupled(_ ::: _))

    def interscalate[B](other: Iterable[B]): Iterable[Either[A, B]] =
      iterable
        .map(Left[A, B])
        .map(List(_))
        .zipAll(
          other
            .map(Right[A, B])
            .map(List(_)),
          Nil,
          Nil
        )
        .flatMap(Function.tupled(_ ::: _))
  }
}