New collection: SortedList

Mygod · January 10, 2017, 1:27pm

Yes. SortedList is just a name I borrowed (it’s not actually a list because you can’t insert elements at arbitrary position). Perhaps SortedIndexedSet or simply requiring all SortedSets to be indexable is more appropriate.

Ichoran · January 11, 2017, 4:40pm

I see the discussion has already gone the way my first thought went: a SortedList that is not a List is confusing. There’s also a question of whether to have both immutable and mutable implementations.

The best algorithm would likely be to take the red-black tree and include child element counts in each node so an index can be reasonably efficiently looked up, and everything stays sorted. In fact, the existing mutable RedBlackTree already does contain the size and it would be relatively straightforward to do the lookup. (Edit: so does immutable; I just missed it. So there isn’t much point to this paragraph except that it agrees with the current strategy.)

As for duplicate elements, one could either just stuff them into the same tree or, more efficiently, chain them onto the same node.

The current implementation is not suitable because it calls nth which traverses n items in the tree, making indexed operations O(n) instead of O(log n) or O(1). (Edit: this paragraph is wrong, since the immutable implementation already has a stored count.)

Mygod · January 11, 2017, 4:55pm

github.com

scala/scala/blob/2.11.x/src/library/scala/collection/immutable/RedBlackTree.scala#L118


  if (tree.left ne null) _foreachKey(tree.left, f)
  f((tree.key))
  if (tree.right ne null) _foreachKey(tree.right, f)
}


def iterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None): Iterator[(A, B)] = new EntriesIterator(tree, start)
def keysIterator[A: Ordering](tree: Tree[A, _], start: Option[A] = None): Iterator[A] = new KeysIterator(tree, start)
def valuesIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None): Iterator[B] = new ValuesIterator(tree, start)


@tailrec
def nth[A, B](tree: Tree[A, B], n: Int): Tree[A, B] = {
  val count = this.count(tree.left)
  if (n < count) nth(tree.left, n)
  else if (n > count) nth(tree.right, n - count - 1)
  else tree
}


def isBlack(tree: Tree[_, _]) = (tree eq null) || isBlackTree(tree)


private[this] def isRedTree(tree: Tree[_, _]) = tree.isInstanceOf[RedTree[_, _]]
private[this] def isBlackTree(tree: Tree[_, _]) = tree.isInstanceOf[BlackTree[_, _]]

Where did you get that idea? It’s obviously O(log n).

Ichoran · January 11, 2017, 5:04pm

Sorry, I missed the count field in the abstract tree class!