What is the best collection to use for storing the children of a Node in a mutable R-tree.
Since my tree is mutable my guess would be something like ListBuffer, List, ArrayBuffer. But I am not sure which one to pick. I need a collection that has decent complexities both in removal and insertion.
It can be implemented with a combination of ArrayBuffer, PriorityQueue
A simple non-exhaustive example
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)
