Programmeerimiskeeled 2018/19 sügis

Scala kogumi implementeerimine

Selles praktikumis loome uue järjekorra kogumi. Implementeerime selle kahe listi (xs ja ys) abil.

Alustame andmestruktuuri konktreetsete meetodite implementeerimisest ja siis lisame selle Scala kogumite klassihierarhiasse.

Implementeerime andmestruktuuri põhioperatsioonid.

import scala.language.higherKinds

trait J2rjekordOps[+T,CC[_]] {
  def onTyhi: Boolean
  def lisaAlgusse[Q >: T](x:Q):CC[Q]
  def v6taL6pust[Q >: T]:(Q, CC[Q])
}

case class J2rjekord[+T]
    (protected val xs: List[T],
     protected val ys: List[T])
  extends J2rjekordOps[T,J2rjekord]
{
  override def toString = s"J2rjekord($xs, $ys)"

  override def onTyhi: Boolean = ???
  override def lisaAlgusse[Q >: T](x: Q): J2rjekord[Q] = ???
  override def v6taL6pust[Q >: T]: (Q, J2rjekord[Q]) = ???
}

object TestJ2rjekord1 {
  def main(args: Array[String]): Unit = {
    val a = J2rjekord[Int](List(),List())
    assert(a.onTyhi)
    assert(!a.lisaAlgusse(1).onTyhi)
    assert(a.lisaAlgusse(1) == J2rjekord(List(1), List()))
    assert(a.lisaAlgusse(2) == J2rjekord(List(2), List()))

    val b = J2rjekord(List(6,5,4),List(1,2,3))
    assert(b.lisaAlgusse(7) == J2rjekord(List(7,6,5,4), List(1,2,3)))

    val (x,c) = b.v6taL6pust
    assert(x == 1)
    assert(c == J2rjekord(List(6,5,4),List(2,3)))
    assert(c.v6taL6pust == (2, J2rjekord(List(6,5,4),List(3))))

    assert(a.lisaAlgusse(7).v6taL6pust == (7, J2rjekord(List(),List())))
  }
}

Kogumi loomine kompanjonobjektiga

Kogumi loomisel lisame elemendid järjekorraga vasakult paremale. S.t. J2rjekord(1,2) == J2rjekord().lisaAlgusse(1).lisaAlgusse(2)

object J2rjekord {
  def apply[T](xs: T*): J2rjekord[T] = ???
}

object TestJ2rjekord2 {
  def main(args: Array[String]): Unit = {
    val a = J2rjekord[Int](List(),List())
    val b = J2rjekord(List(6,5,4,3,2,1), List())
    assert(a == J2rjekord())
    assert(b == J2rjekord(1,2,3,4,5,6))
  }
}

Scala kogumina (osa 1)

Esmalt lisame kolm asja: pikkuse arvutamise, indekseerimise ja kogumile vastava kompanjonobjekti. Viimane tähendab vastavat tüüpi builderi lisamine kompanjonobjekti. (apply meetod genereeritakse nüüd automaatselt builderi abil.)

case class J2rjekord[+T]
    (protected val xs: List[T],
     protected val ys: List[T])
  extends AbstractSeq[T]
    with LinearSeq[T]
    with GenericTraversableTemplate[T, J2rjekord]
    with J2rjekordOps[T,J2rjekord]
{
  // meetodid eelmisest koodilõigust

  override def companion: GenericCompanion[J2rjekord] = J2rjekord

  override val length: Int = ???

  override def apply(idx: Int): T = ???
}

object J2rjekord extends GenericCompanion[J2rjekord] {
  class MyCBF[A, Coll] extends CanBuildFrom[Coll, A, J2rjekord[A]] {
    override def apply(from: Coll): mutable.Builder[A, J2rjekord[A]] = newBuilder
    override def apply(): mutable.Builder[A, J2rjekord[A]] = newBuilder
  }

  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, J2rjekord[A]] = 
      new MyCBF[A,Coll]

  override def newBuilder[A]: mutable.Builder[A, J2rjekord[A]] = 
    new mutable.Builder[A, J2rjekord[A]] {
      private var list = List[A]() // kasutage seda muutujat ehitamiseks

      override def +=(elem: A): this.type = ???
      override def clear(): Unit = ???
      override def result(): J2rjekord[A] = ???
    }
}

object TestJ2rjekord3 {
  def main(args: Array[String]): Unit = {
    val a = J2rjekord(6,7,8,9)
    // testimiseks kasutame toString-i kuna equals defineerime hiljem
    assert(a.toString == J2rjekord(List(9,8,7,6),List()).toString)

    val b = J2rjekord(List(6,5,4),List(1,2,3))
    assert(b.length == 6)
    assert(b(0) == 1)
    assert(b(1) == 2)
    assert(b(2) == 3)
    assert(b(3) == 4)
    assert(b(4) == 5)
    assert(b(5) == 6)
  }
}

J2rjekord Scala kogumina (osa 2)

Nüüd lisage iteraator. Võrduse kontrolli kood on etteantud.

case class J2rjekord[+T]
    (protected val xs: List[T],
     protected val ys: List[T])
  extends AbstractSeq[T]
    with LinearSeq[T]
    with GenericTraversableTemplate[T, J2rjekord]
    with LinearSeqLike[T, J2rjekord[T]]
    with Equals
    with J2rjekordOps[T,J2rjekord] 
{
  // meetodid eelmisest koodilõigust

  override def iterator: Iterator[T] = new Iterator[T] {
    private var cons = xs
    private var snoc = ys
    private var l = xs.length + ys.length

    // järgnevad meetodid peavad kasutama (ja muutma) eelnevaid muutujaid
    override def hasNext: Boolean = ???
    override def next(): T = ???
  }

  override def canEqual(other: Any): Boolean = other.isInstanceOf[J2rjekord[_]]

  override def equals(other: Any): Boolean = other match {
    case that: J2rjekord[_] =>
      super.equals(that) &&
        (that canEqual this) &&
        (this, that).zipped.forall(_ == _)
    case _ => false
  }

  override def hashCode(): Int = {
    this.map(_.hashCode()).foldLeft(0)((a, b) => 31 * a + b)
  }
}


object TestJ2rjekord4 {
  def main(args: Array[String]): Unit = {
    val a = J2rjekord(6,7,8,9)

    // prindib "6 7 8 9"
    for (x <- a)
      print(s"$x ")
    println()

    assert(a == J2rjekord(List(9,8,7,6),List()))
    assert(a == J2rjekord(List(),List(6,7,8,9)))

    assert(a.map(10+_) == J2rjekord(16,17,18,19))
  }
}

Optimeeritud implementatsioonid

Tänu iteraatori lisamisele on meil nüüd kasutatav suur hulk meetode, näiteks map, :+ ja +:. Nende vaikeimplementatsioon pole aga järjekorrale omane. Näiteks, algusse lisamine peaks olema konstantse ajaga tehtav aga vaikeimplementatsioon on lineaarne.

Katke järgnevad meetodid üle sobilikuma implementatsiooniga. (CanBuildFrom-i argumendina võtvad funktsioonid lahendage samamoodi nagu map.)

case class J2rjekord[+T]
    (protected val xs: List[T],
     protected val ys: List[T])
  extends AbstractSeq[T]
    with LinearSeq[T]
    with GenericTraversableTemplate[T, J2rjekord]
    with LinearSeqLike[T, J2rjekord[T]]
    with Equals
    with J2rjekordOps[T,J2rjekord]
{
  // meetodid eelmisest koodilõigust

  override def head: T = ???
  override def tail: J2rjekord[T] = ???
  override def forall(p: T => Boolean): Boolean = ???
  override def exists(p: T => Boolean): Boolean = ???

  override def +:[B >: T, That](elem: B)
         (implicit bf: CanBuildFrom[J2rjekord[T], B, That]): That = ???

  override def :+[B >: T, That](elem: B)
         (implicit bf: CanBuildFrom[J2rjekord[T], B, That]): That = ???

  override def reverse: J2rjekord[T] = ???

  // sama mustriga teha +:, :+
  override def map[B, That](f: T => B)
         (implicit bf: CanBuildFrom[J2rjekord[T], B, That]): That = 
    bf match {
      case _: J2rjekord.MyCBF[_, _] => 
         new J2rjekord(xs.map(f), ys.map(f)).asInstanceOf[That]
      case _ => super.map(f)(bf)
  }
}


object TestJ2rjekord5 {
  def main(args: Array[String]): Unit = {
    val a = J2rjekord(6,7,8,9)

    assert(a.head == 6)
    assert(a.tail == J2rjekord(7,8,9))
    assert(a.tail.tail == J2rjekord(8,9))

    assert(a.forall(_ < 10))
    assert(!a.forall(_ < 7))
    assert(a.exists(_ == 7))
    assert(!a.exists(_ == 5))

    assert(5 +: a  == J2rjekord(5,6,7,8,9))
    assert(a :+ 10  == J2rjekord(6,7,8,9,10))

    assert(a.map(10+_) == J2rjekord(16,17,18,19))
  }
}