span-skip-list
A data structure for calculating running totals in multiple dimensions in O(ln(n)).
npm install span-skip-list
Want to see pretty graphs? Log in now!
17 | downloads in the last day |
48 | downloads in the last week |
138 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.1.1 last updated 8 months ago |
License | MIT |
Keywords | skip-list, data-structure, index |
Repository | https://github.com/atom/span-skip-list.git (git) |
Bugs | https://github.com/atom/span-skip-list/issues |
Dependencies | underscore |
Dependents | telepath, text-buffer |
Span Skip-List
This data structure stores arbitrary mappings between various dimensions and allows running totals to be calculated in O(ln(n)), where n is the number of table entries. Say you have a table entries like the following:
x | y |
---|---|
3 | 3 |
5 | 2 |
2 | 7 |
4 | 4 |
With this data structure, you can determine how many y's you have traversed when you've traversed up to a certain number of x's. For example, when you've traversed up to 8 in the x dimension your total in the y dimension is 5. Here's an example of how you'd use the span skip list to answer that query:
SpanSkipList = require 'span-skip-list'
# Construct with the dimensions you want to track
list = new SpanSkipList('x', 'y')
# Populate with entries. Splice takes the dimension in which to interpret the
# index as a first argument. More on that later.
entries = [
{x: 3, y: 3}
{x: 5, y: 2}
{x: 2, y: 7}
{x: 4, y: 4}
]
list.splice('x', 0, 0, entries...)
list.getElements() # => [{x: 3, y: 3} {x: 5, y: 2} {x: 2, y: 7} {x: 4, y: 4}]
# Call ::totalTo with a total in one dimension to get a total in all dimensions
# up to the element that exceeds the target value in that dimension.
list.totalTo(8, 'x') # => { x: 8, y: 5 }
list.totalTo(10, 'x') # => { x: 10, y: 12 }
# Note that you always get the total exclusive of the exceeding element. In this
# case, x = 11 returns the same total as x = 10 because including the next
# element ({x: 4, y: 4} would make x = 14, which exceeds x = 11.
list.totalTo(11, 'x') # => { x: 10, y: 12 }
# The splice occurs at the index of the first element that exceeds the given
# index in the given dimension. In this case, the splice at x = 3 replaces the
# element {x: 5, y: 2} with the given element. The ::splice method returns an
# array of removed elements, list like Array::splice.
list.splice('x', 3, 1, {x: 7, y: 1}) # => [{x: 5, y: 2}]
list.getElements() # => [{x: 3, y: 3}, {x: 7, y: 1}, {x: 2, y: 7}, {x: 4, y: 4}]
# You can splice in any tracked dimension:
list.splice('y', 4, 0, {x: 2, y: 2})
list.getElements() # => [{x: 3, y: 3}, {x: 7, y: 1}, {x: 2, y: 2}, {x: 2, y: 7}, {x: 4, y: 4}]
# You can also splice and run totals in the special 'elements' dimension, which
# counts each element as a unit. This returns the total of the first 3 elements:
list.totalTo(3, 'elements') # => {x: 12, y: 6}
# And this splices at the given element index:
list.splice('elements', 2, 1) # => [{x: 2, y: 2}]
list.getElements() # => [{x: 3, y: 3}, {x: 7, y: 1}, {x: 2, y: 7}, {x: 4, y: 4}]