Programming Languages 2019/20 fall

Neljas Scala kodutöö: Puu kogumi loomine

Kirjuta immutable kahendpuu Puu alamklassid ja companion objekt. Seda puud peab olema võimalik kasutada kui Scala järjendit, mille elementide järjestus vastab puu keskjärjestusele (vasak alampuu, juurelement, parem alampuu). Kuna tegemist on järjendiga (mitte hulgaga vms), siis elemendid peavad olema selles järjestuses nagu nad lisati, mitte sorteeritult (nagu tüüpiliselt on kahendotsingupuus). Lihtsuse mõttes pole vaja, et puu oleks ja hoitaks tasakaalus.

Puu alamklassides tuleb mõistlikult implementeerida järgmised meetodid, isegi kui neil on vaikimisi implementatsioonid olemas:

• kõrgus arvutab puu kõrguse, lehe kõrgus on 0.
• asendaLehed asendab iga lehe antud väärtusega.
• length arvutab puus olevate väärtuste koguarvu.
• apply indekseerib puus olevaid väärtusi keskjärjestuses; kui antud indeksile vastavat elementi puus pole peab viskama NoSuchElementException-i.
• iterator itereerib puus olevad väärtused keskjärjestuses.
• appended lisab puusse antud väärtuse nii, et see oleks kõige parempoolne.
• prepended lisab puusse antud väärtuse nii, et see oleks kõige vasakpoolne.
• reverse peegeldab puu (rekursiivselt), vahetades alampuud.

Puu companion objektis tuleb implementeerida järgmised meetodid:

• empty tagastab tühja puu.
• newBuilder tagastab builder-i millega puud elementhaaval konstrueerida.
• from implementatsioonina võib kasutada lihtsalt (newBuilder ++= source).result().

Lahenduse mall ja testid

import scala.collection.{IterableFactoryDefaults, SeqFactory, mutable}
import scala.collection.immutable.{AbstractSeq, SeqOps}
import scala.util.Try

trait PuuOp[+A, +CC[_], +C] {
  def kõrgus: Int
  def asendaLehed[B >: A](elem: B): CC[B]
}

sealed abstract class Puu[+A]
  extends AbstractSeq[A]
    with SeqOps[A, Puu, Puu[A]]
    with IterableFactoryDefaults[A, Puu]
    with PuuOp[A, Puu, Puu[A]] {

  override def iterableFactory: SeqFactory[Puu] = Puu
}

case object Leht extends Puu[Nothing] {
  override def toString: String = "Leht"

  // ???
}

case class Haru[A](vasak: Puu[A], juur: A, parem: Puu[A]) extends Puu[A] {
  override def toString: String = s"Haru($vasak,$juur,$parem)"

  // ???
}

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


object TestPuu {
  def main(args: Array[String]): Unit = {
    val a = Haru(Haru(Leht, 1, Leht), 2, Leht)
    val b = Haru(Haru(Haru(Leht, 1, Leht), 2, Haru(Leht, 3, Leht)), 4, Haru(Leht, 5, Leht))

    // meetod kõrgus
    assert(Leht.kõrgus == 0)
    assert(a.kõrgus == 2)
    assert(b.kõrgus == 3)

    // meetod asendaLehed
    val puu0 = Haru(Leht, 0, Leht)
    assert(Leht.asendaLehed(0) == puu0)
    assert(a.asendaLehed(0) == Haru(Haru(puu0, 1, puu0), 2, puu0))

    // meetod length
    assert(Leht.length == 0)
    assert(a.length == 2)
    assert(b.length == 5)

    // meetod apply (indekseerimine)
    Try(Leht(0)).isFailure // peaks viskama NoSuchElementException
    assert(a(0) == 1)
    assert(a(1) == 2)
    Try(a(-1)).isFailure // peaks viskama NoSuchElementException
    Try(a(2)).isFailure // peaks viskama NoSuchElementException
    assert(b(0) == 1)
    assert(b(1) == 2)
    assert(b(2) == 3)
    assert(b(3) == 4)
    assert(b(4) == 5)

    // meetod iterator (itereerimine)
    assert(a.iterator sameElements Iterator(1, 2))
    assert(b.iterator sameElements Iterator(1, 2, 3, 4, 5))

    // objekt Puu (companion)
    assert(Puu.empty == Leht)
    assert(Puu(1, 2) == a)
    assert(Puu(1, 2, 3, 4, 5) == b)

    // meetod appended (:+)
    assert(a :+ 3 == Puu(1, 2, 3))
    assert(b :+ 6 == Puu(1, 2, 3, 4, 5, 6))

    // meetod prepended (+:)
    assert(0 +: a == Puu(0, 1, 2))
    assert(0 +: b == Puu(0, 1, 2, 3, 4, 5))

    // meetod reverse
    assert(a.reverse == Puu(2, 1))
    assert(b.reverse == Puu(5, 4, 3, 2, 1))

    // tuletatud Seq meetodid (head, sum, max, contains, map)
    assert(a.head == 1)
    assert(a.sum == 3)
    assert(a.max == 2)
    assert(a.contains(2))
    assert(!a.contains(5))
    assert(a.map(_ + 10) == Puu(11, 12))

    assert(b.head == 1)
    assert(b.sum == 15)
    assert(b.max == 5)
    assert(b.contains(5))
    assert(!b.contains(8))
    assert(b.map(_ + 10) == Puu(11, 12, 13, 14, 15))
  }
}