Programmeerimiskeeled 2020/21 sügis

4. Scala kodutöö

Moodle'ist leiad ka lahendusfaili malli Kt4.scala.

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 IndexOutOfBoundsException-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().