f with X at M
f with Y at N
f with Y at N

h in B2, g in B1, f in A
h in B1, g in B2, f in A

g in A, f in C
h in B, f in A
k in A, h in B, f in A

def fibonacci(): Iter[BigInt] = {
  var previous = BigInt(1)
  val step: BigInt => BigInt = { current =>
    val following = previous + current
    previous = current
    following
  }
  new FunIter[BigInt](BigInt(0), step)
}

import scala.collection.immutable.Stream

class FunIter[T] private (
    private var rest: Stream[T]) extends Iter[T] {

  def this(v: T, f: T => T) = this(Stream.iterate(v)(f))

  def hasNext: Boolean = true

  def next(): T = {
    val result = rest.head
    rest = rest.tail
    result
  }

  def copy(): Iter[T] = new FunIter[T](rest)
}

trait RichIter[T] extends Iter[T] {
  def foreach(f: T => Unit): Unit = {
    while (hasNext) f(next())
  }

  def exists(p: T => Boolean): Boolean = {
    while (hasNext) {
      if (p(next())) return true
    }
    false
  }

  def foldLeft[U](x: U)(f: (U,T) => U): U = {
    var result = x
    while (hasNext) result = f(result, next())
    result
  }
}

class DropUntil[T] private (
    p: T => Boolean,
    iter: Iter[T],
    private var cached: Option[T],
    private var seeking: Boolean) extends Iter[T] {

  def this(p: T => Boolean, iter: Iter[T]) =
    this(p, iter, None, true)

  private def prepare(): Unit = {
    if (seeking) {
      while (cached.isEmpty && iter.hasNext) {
        val x = iter.next()
        if (p(x)) cached = Some(x)
      }
      seeking = false
    }
  }

  def hasNext: Boolean = {
    prepare()
    cached.nonEmpty || iter.hasNext
  }

  def next(): T = {
    prepare()
    cached match {
      case Some(x) => cached = None; x
      case None =>
        if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
        iter.next()
    }
  }

  def copy(): Iter[T] = {
    prepare()
    new DropUntil[T](p, iter.copy(), cached, false)
  }
}

class Sports(account: CableTV) extends Packages(account) {
  override def cost: Double = super.cost + 5.0
  override def packages: String = super.packages + ", Sports"
}

object CableTVExample extends App {
  val basic: CableTV = new BasicPlan
  val movies: CableTV = new Movies(basic)
  val hd: CableTV = new HDChannels(movies)
  val sports: CableTV = new Sports(hd)
  Seq(basic, movies, hd, sports).foreach { account =>
    println(account.packages + " = £" + account.cost)
  }
}

Basic plan = £30.0
Basic plan, Movies = £40.0
Basic plan, Movies, HD channels = £47.0
Basic plan, Movies, HD channels, Sports = £52.0

procedure OutRat(m,n)
    Out.Int(m)
    Out.String("/")
    Out.Int(n)

procedure OutEgypt(e)
    if e.i = 0 then
        Out.String("0")
    else
        for j := 0 to e.i-1 do
            if j > 0 then Out.String("+")
            Out.String("1/")
            Out.Int(e.x[j])

procedure toRat(e; var m,n)
    require 0 <= e.i <= N and every stored denominator is positive
    m := 0
    n := 1
    j := 0
    while j < e.i do
        q := e.x[j]
        m := m*q+n
        n := n*q
        Reduce(m,n)
        j := j+1

procedure fromRat(m,n; var e)
    require 0 <= m < n
    e.i := 0
    while m > 0 do
        q := n div m
        if n mod m != 0 then q := q+1
        assert e.i < N
        e.x[e.i] := q
        e.i := e.i+1
        m := m*q-n
        n := n*q
        Reduce(m,n)

function GCD(m,n): integer
    a := m
    b := n
    while b != 0 do
        r := a mod b
        a := b
        b := r
    return a

procedure Reduce(var m,n)
    require m >= 0 and n > 0
    d := GCD(m,n)
    m := m div d
    n := n div d

function Sort(xs: List): List
    allocate dummy headers remaining and output
    remaining.next := xs
    output.next := nil
    tail := output
    while remaining.next != nil do
        p := DelMin(remaining)
        tail.next := p
        tail := p
    return output.next

function DelMin(hd: List): List
    require hd != nil and hd.next != nil
    bestPrev := hd
    p := hd.next
    while p.next != nil do
        if p.next.x < bestPrev.next.x then
            bestPrev := p
        p := p.next
    result := bestPrev.next
    bestPrev.next := result.next
    result.next := nil
    return result

procedure Remove(x: List; var xs: List)
    require x is a node reachable from xs
    if xs = x then
        xs := x.next
    else
        p := xs
        while p.next != x do
            p := p.next
        p.next := x.next
    x.next := nil