Programming Languages 2018/19 fall

Neljas kodutöö: Puu kogumi loomine

Kirjuta immutable kahendpuu Puu alam-klassid ja kompanjonobjekt.

Implementeerida tulevad meetodid: length, lisa, iterator, apply, reverse, +=, clear ja result.

Kui meetodi argument pole mõistlik, visata erind (näiteks NoSuchElementException)

Lisatingimused:

• reverse peab puud peegeldama: rekursiivselt ära vahetama puu parema ja vasema alampuu.
• length peab arvutama puus olevate elementide arvu
• kaasaantud testid ei tohi nurjuda

Kood ja testid:

import scala.collection.{AbstractSeq, SeqLike, mutable}
import scala.collection.generic.{GenericCompanion, GenericTraversableTemplate}
import scala.language.higherKinds

trait PuuOp[+A, +CC[_]] {
  def lisa[B >: A](b: B): CC[B]
}

sealed abstract class Puu[+T]
  extends AbstractSeq[T]
    with GenericTraversableTemplate[T, Puu]
    with SeqLike[T, Puu[T]]
    with PuuOp[T, Puu]
    with Equals
{
  override def companion: GenericCompanion[Puu] = Puu
}

case object Leht extends Puu[Nothing] {
  // ???
}
case class  Haru[A](vasak: Puu[A], v: A, parem: Puu[A]) extends Puu[A] {
  override def toString = s"Haru($vasak, $v, $parem)"
  // ???
}

object Puu extends GenericCompanion[Puu] {
  // ???
}



object PuuTest {
  def main(args: Array[String]): Unit = {
    val a = Puu(1,2,3)
    assert(a.length == 3)

    assert(a contains 1)
    assert(a contains 2)
    assert(a contains 3)
    assert(!(a contains 4))

    assert(a.lisa(4) contains 1)
    assert(a.lisa(4) contains 2)
    assert(a.lisa(4) contains 3)
    assert(a.lisa(4) contains 4)
    assert(!(a.lisa(4) contains 5))

    assert(a.map(_+10).length == 3)
    assert(a.max == 3)
    assert(a.sum == 6)

    val b = Haru(Haru(Leht, 1, Leht), 2, Haru(Leht, 3, Leht))
    val c = Haru(Haru(Leht, 3, Leht), 2, Haru(Leht, 1, Leht))

    assert(b.reverse == c)
  }
}