Scala 中基于节点的 Iterable 实现

Question

继续我在 Sedgwick 和 Wayne 算法中的练习，我遇到了一个我必须实现 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 本身的开始：

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 应该覆盖 Iterable 特征的 def 大小。在测试 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.<init>(RandomBagSpec.scala:16)
[info]   at ca.vgorcinschi.algorithms1_5_19.RandomBagSpec.$anonfun$new(RandomBagSpec.scala:12)
[info]   at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
[info]   at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)

问题似乎来自调用 Iterator 的 next 方法，实际上容器 Vector 不包含任何元素：

但为什么 next 在 random 之前被调用？

Answer 1

val size should have overridden the def size from Iterable trait

一个val会有，但你没有；您只是在非 case class 中有一个构造函数参数。实际上它是一个 private val 并且不能覆盖任何东西。

but why is next being called before random?

不是；在 RandomIterator 的构造函数中，random 在初始化程序 container = Vector() 之前被调用（作为 first match ... 的一部分）。 next 仅在构造函数之后调用。

Scala 中基于节点的 Iterable 实现

Node based Iterable implementation in Scala

iterator

iterable

scala

nodes