def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
  def hasNext: Boolean = t.hasNext || u.hasNext
  def next(): T = {
    if (t.hasNext) t.next()
    else {
      require(u.hasNext, "empty iterator")
      u.next()
    }
  }
}

def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
  def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
  def current: T = {
    if (t.hasCurrent) t.current
    else {
      require(u.hasCurrent, "empty cursor")
      u.current
    }
  }
  def next(): Unit = {
    if (t.hasCurrent) t.next()
    else {
      require(u.hasCurrent, "empty cursor")
      u.next()
    }
  }
}

def unitIter[T](t: T): Iter[T] = new Iter[T] {
  private var available = true
  def hasNext: Boolean = available
  def next(): T = {
    require(available, "empty iterator")
    available = false
    t
  }
}

def unitCursor[T](t: T): Cursor[T] = new Cursor[T] {
  private var available = true
  def hasCurrent: Boolean = available
  def current: T = {
    require(available, "empty cursor")
    t
  }
  def next(): Unit = {
    require(available, "empty cursor")
    available = false
  }
}

def map[T, U](f: T => U, it: Iter[T]): Iter[U] = new Iter[U] {
  def hasNext: Boolean = it.hasNext
  def next(): U = {
    require(it.hasNext, "empty iterator")
    f(it.next())
  }
}

def map[T, U](f: T => U, cur: Cursor[T]): Cursor[U] =
  asCursor(map(f, asIter(cur)))

def asIter[T](cur: Cursor[T]): Iter[T] = new Iter[T] {
  def hasNext: Boolean = cur.hasCurrent
  def next(): T = {
    require(cur.hasCurrent, "empty iterator")
    val answer = cur.current
    cur.next()
    answer
  }
}

def asCursor[T](it: Iter[T]): Cursor[T] = new Cursor[T] {
  private var cached: Option[T] = None

  def hasCurrent: Boolean = cached.nonEmpty || it.hasNext

  def current: T = {
    if (cached.isEmpty) {
      require(it.hasNext, "empty cursor")
      cached = Some(it.next())
    }
    cached.get
  }

  def next(): Unit = {
    if (cached.nonEmpty) cached = None
    else {
      require(it.hasNext, "empty cursor")
      it.next()
      ()
    }
  }
}

val doc: DocImp with CharCountPlugin = new DocImp with CharCountPlugin

trait DigitCountPlugIn extends CharCountPlugin {
  override protected def firstCounted: Char = '0'
  override protected def numberCounted: Int = 10
}

trait CharCountPlugin extends Doc {
  protected def firstCounted: Char = 'a'
  protected def numberCounted: Int = 26
  protected def slot(ch: Char): Int = {
    val k = ch.toInt - firstCounted.toInt
    if (0 <= k && k < numberCounted) k else -1
  }
  private lazy val totals = Array.fill(numberCounted)(0)

  abstract override def insert(pos: Int, ch: Char): Unit = {
    val k = slot(ch)
    super.insert(pos, ch)
    if (k >= 0) totals(k) += 1
  }

  abstract override def delete(pos: Int): Char = {
    val removed = super.delete(pos)
    val k = slot(removed)
    if (k >= 0) totals(k) -= 1
    removed
  }

  def count(ch: Char): Int = {
    val k = slot(ch)
    require(k >= 0, "character is outside the counted alphabet")
    totals(k)
  }
}

class DocImp extends Doc {
  private val data = scala.collection.mutable.ArrayBuffer.empty[Char]

  def insert(pos: Int, ch: Char): Unit = {
    require(0 <= pos && pos <= data.length)
    require(data.length < Int.MaxValue)
    data.insert(pos, ch)
  }

  def delete(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data.remove(pos)
  }

  def apply(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data(pos)
  }

  def length: Int = data.length
}

class Node(var value: Double, val index: Int,
           var prev: Node, var next: Node)

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

def eaLinear(n: Int): Double = {
  require(n > 0)
  val base = 1.0 + 1.0 / n.toDouble
  var i = 0
  var result = 1.0
  while (i < n) {
    result *= base
    i += 1
  }
  result
}