search

montagejs / collections

This package contains JavaScript implementations of common data structures with idiomatic interfaces.
http://www.collectionsjs.com
Other
2.1k stars 183 forks source link

How to access the i-th element of SortedSet #123

Open lygstate opened 9 years ago

lygstate commented 9 years ago

At the current time, SortedSet are baked with Splay Tree, that doesn't support for directly access the i-th element of the tree, so the SortedSet doesn't act like a array and getting problems. So we need a way to do that.

Stuk commented 9 years ago

This does seem to be an oversight, @kriskowal?

As a workaround you could so sortedSet.slice(i, i+1);

kriskowal commented 9 years ago

Very much an oversight. We should implement get(index). Pull request welcome. The logic for traversing to the node at a given index already exists, using the subtree length to find the node at that position by walking to the node with a left subtree of the same length as your index.

lygstate commented 9 years ago

@kriskowal So does SortedArray? Does SortedArrray backed with SplayTree for o(logn) access time?

kriskowal commented 9 years ago

SortedArray is backed by an Array and uses binary search for O(log n) search, but O(n) insert and remove, which is much faster and produces less garbage collector churn than SortedSet’s splay tree for reasonable sizes of n.

On Thu, Apr 23, 2015 at 4:25 AM, Yonggang Luo notifications@github.com wrote:

@kriskowal https://github.com/kriskowal So does SortedArray? Does SortedArrray backed with SplayTree for o(logn) access time?

— Reply to this email directly or view it on GitHub https://github.com/montagejs/collections/issues/123#issuecomment-95547618 .