splaylist.js

Splay-tree container with order statistics for Javascript.

version 0.0.0 Author: David Bau Date: 2014 Dec 31

A SplayList is an array-like container that provides both fast array-index and fast list-insertion access. It is useful for situations such as tracking an array of thousands of lines of text when insertions and deletions must be instant, yet where indexing by line number or character must also be fast,

This array-or-list replacement provides:

• A linked-list interface with O(1) (nanosecond) next() and prev(), and O(log n) (microsecond) insert(), remove(), splice() operations. These operations are all fast regardless of the number of elements.
• An array-style interface for skipping to the nth(i) item, or getting or setting the value at the ith position.
• An order-statistic interface, for determining the integer position of a node in O(log n) (microsecond) time. Additional order statistics, tracking running sums of any nonnegative weights of each value, can be added by subclassing SplayList.

Internally a SplayList is an automatically balanced splay tree. In practice, splay trees perform better than O(log n) because they take advantage of the typical locality of access in real applications.

This library is packaged to be used as a plain script or a node.js module.

Script tag usage

Node.js usage

Order Statistics

By default, the list tracks an "n" statistic: the number of locations before any given location.

It is possible to extend SplayList to track other order statistics beyond n; just override the orderstats method. The SplayList class has an extend method for conveniently creating subclasses that override SplayList methods. The orderstats method is passed four arguments. It must fill in sum statistics in X to reflect the sum of the contribution of value V as well as subtrees L and R. Either or both of L and R may be null.

The example above defines stats "n", "k", and "m". If orderstats is overridden, the statistic "n" should count elements, as above.

See test/test.js for an example of overriding orderstats to generalize to more than one order statistic.

LICENSE (MIT)

Copyright 2015 David Bau.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.