Package Exports

span-skip-list

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (span-skip-list) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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}]