scala - 将节点子节点存储在可变 R 树中 - Scala

Question

什么是用于将节点的子节点存储在可变 R 树中的最佳集合。

由于我的树是可变的，我的猜测可能是 ListBuffer、List、ArrayBuffer。但我不确定该选哪一个。我需要一个在删除和插入方面都具有相当复杂性的集合。

标签： scalanodeschildrenr-tree

Answer 1

它可以通过组合来实现ArrayBuffer, PriorityQueue

一个简单的非详尽示例

object RTree {

  /**
   * Construct an empty RTree.
   */
  def empty[A]: RTree[A] = new RTree(Node.empty[A], 0)

  /**
   * Construct an RTree from a sequence of entries.
   */
  def apply[A](entries: Entry[A]*): RTree[A] =
    entries.foldLeft(RTree.empty[A])(_ insert _)
}


case class RTree[A](root: Node[A], size: Int) {

  /**
   * To be considered equal, two trees must have the same
   * number of entries, and each entry found in one should be found in
   * the other.
   */
  def ===(that: RTree[A]): Boolean =
    size == that.size && entries.forall(that.contains)

  /**
   * Trees can only be equal to other trees. Unlike some other
   * containers.
   *
   * This means comparing an RTree[Int] and an RTree[Long] will
   * always return false.
   */
  override def equals(that: Any): Boolean =
    that match {
      case rt: RTree[_] =>
        Try(this === rt.asInstanceOf[RTree[A]]).getOrElse(false)
      case _ =>
        false
    }


  /**
   * Insert a value into the tree at (x, y), returning a new tree.
   */
  def insert(x: Float, y: Float, value: A): RTree[A] =
    insert(Entry(Point(x, y), value))

  /**
   * Insert an entry into the tree, returning a new tree.
   */
  def insert(entry: Entry[A]): RTree[A] = {
    val r = root.insert(entry) match {
      case Left(rs) => Branch(rs, rs.foldLeft(Box.empty)(_ expand _.box))
      case Right(r) => r
    }
    RTree(r, size + 1)
  }

  /**
   * Remove an entry from the tree, returning a new tree.
   *
   * If the entry was not present, the tree is simply returned.
   */
  def remove(entry: Entry[A]): RTree[A] =
    root.remove(entry) match {
      case None =>
        this
      case Some((es, None)) =>
        e.foldLeft(RTree.empty[A])(_ insert _)
      case Some((e, Some(node))) =>
        e.foldLeft(RTree(node, size - e.size - 1))(_ insert _)
    }

  /**
   * Return a sequence of all entries found in the given search space.
   */
  def search(space: Box): Seq[Entry[A]] =
    root.search(space, _ => true)

  /**
   * Return a sequence of all entries found in the given search space.
   */
  def search(space: Box, f: Entry[A] => Boolean): Seq[Entry[A]] =
    root.search(space, f)