It doesn't need to support eager re-computation, just lazily finding item at position N after splice has occurred (in O(log n) if possible).
-
-
Replying to @wycats
@wycats Skip list? http://en.wikipedia.org/wiki/Skip_list1 reply 1 retweet 1 like -
Replying to @seancribbs
@seancribbs so the idea is that each layer has a count of the elements below it, so splicing just updates the number of layers up?1 reply 0 retweets 0 likes -
Replying to @seancribbs
@seancribbs next: how to maintain a better-than-linear-time map of source->target positions when the target is a sorted version of source1 reply 0 retweets 0 likes
Replying to @seancribbs
@seancribbs no... this is for a single insert/delete/lookup. Insertion into a sorted list is easy to do better-than-linear.
2:06 PM - 26 Oct 2013
0 replies
0 retweets
0 likes
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.