Итерируемая реализация на основе узлов в Scala - PullRequest
Новая
       15

Итерируемая реализация на основе узлов в Scala

0 голосов
/ 21 мая 2018

Продолжая свое путешествие через упражнения из алгоритмов Седжвика и Уэйна, я наткнулся на один, в котором мне нужно реализовать RandomBag.Первоначально RandomBag должен реализовывать Iterable (в Java), и его Iterator должен был обслуживать элементы в случайном порядке.

Это объект-компаньон моего ImmutableRandomBag: 

object ImmutableRandomBag{
  case class Node[Item](item: Item, next: Option[Node[Item]])
  def apply[Item](maybeNode: Option[Node[Item]], size: Int): ImmutableRandomBag[Item] = new ImmutableRandomBag(maybeNode, size)
}

И это начинаетсясамого класса: 

class ImmutableRandomBag[Item](maybeNode: Option[Node[Item]], size: Int) extends Iterable[Item]{

      override def isEmpty: Boolean = size == 0

      def add(item: Item) = {
        ImmutableRandomBag(Some(Node(item, maybeNode)), size +1)
      }
   ...
   }

Насколько я понимаю, val size должен был переопределить размер def из черты Iterable.При тестировании метода add я получаю исключение IndexOutOfBounException: 

class RandomBagSpec extends BaseSpec {

  trait RandomBag{
    val begin = new ImmutableRandomBag[Connection](None, 0)
  }

  ...

  "Adding an item to empty RandomBag" should "return another bag with size 1" in new RandomBag {
    val bag = begin.add(Connection(0,1))
    bag.size should equal(1)
  }
}

Хотя размер отладки правильно оценивается в параметре конструктора, поэтому я не уверен, откуда исходит исключение IndexOutOfBoundException, но я получаю его всякий раз, когдавызовите метод add.Возможно, проблема проистекает из следующего.В ImmutableRandomBag есть также реализация Iterator: 

...
override def iterator: Iterator[Item] = new RandomIterator[Item](maybeNode)

  private class RandomIterator[Item](first: Option[Node[Item]]) extends Iterator[Item]{

    first match {
      case Some(node) => random(node)
      case None =>
    }

    var current: Int = 0
    var container: Vector[Item] = Vector()

    override def hasNext: Boolean = current < ImmutableRandomBag.this.size

    override def next(): Item = {
      val item = container(current)
      current += 1
      item
    }

    def random(first: Node[Item]) = {
      @tailrec
      def randomHelper(next: Option[Node[Item]], acc: List[Item]):List[Item]= next match {
        case None => acc
        case Some(node) => randomHelper(node.next, node.item::acc)
      }

      val items = randomHelper(Some(first), List[Item]())
      container = Random.shuffle(items).toVector
    }
  }
}

И у меня есть другой тест в той же спецификации для него: 

...
"Random Bag's iterator" should "contain all items passed to parent iterable" in new RandomBag{
    val connections = List(Connection(0,1), Connection(1,0), Connection(1,1))
    var localRB = begin
    for(c <- connections) localRB = localRB.add(c)
    assert(localRB.iterator.forall(conn=> connections.contains(conn)) == true)
  }
...

Я также получаю исключение IndexOutOfBoundException со следующим стеком: 

    [info] RandomBagSpec:
[info] Random Bag's iterator
[info] - should contain all items passed to parent iterable *** FAILED ***
[info]   java.lang.IndexOutOfBoundsException: 0
[info]   at scala.collection.immutable.Vector.checkRangeConvert(Vector.scala:123)
[info]   at scala.collection.immutable.Vector.apply(Vector.scala:114)
[info]   at ca.vgorcinschi.algorithms1_3_34.ImmutableRandomBag$RandomIterator.next(ImmutableRandomBag.scala:31)
[info]   at scala.collection.Iterator.forall(Iterator.scala:956)
[info]   at scala.collection.Iterator.forall$(Iterator.scala:954)
[info]   at ca.vgorcinschi.algorithms1_3_34.ImmutableRandomBag$RandomIterator.forall(ImmutableRandomBag.scala:18)
[info]   at ca.vgorcinschi.algorithms1_5_19.RandomBagSpec$$anon$1.<init>(RandomBagSpec.scala:16)
[info]   at ca.vgorcinschi.algorithms1_5_19.RandomBagSpec.$anonfun$new$1(RandomBagSpec.scala:12)
[info]   at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
[info]   at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)

Проблема возникает из-за вызова следующего метода Итератора, и действительно, контейнер Vector не содержит никаких элементов: enter image description here

но почему next вызывается раньше random?

1 Ответ

0 голосов
/ 21 мая 2018

val size должен был переопределить размер def из итерируемой черты

A val, но у вас его нет;у вас просто есть параметр конструктора в не case классе.Фактически это private val и ничего не может переопределить.

но почему следующий вызов вызывается раньше случайного?

Это не так;в конструкторе RandomIterator random вызывается (как часть first match ...) перед инициализатором container = Vector().next вызывается только после конструктора.

...