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 = '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: 3y: 3 x: 5y: 2 x: 2y: 7 x: 4y: 4listsplice'x'00entries...listgetElements # => [{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. listtotalTo8'x' # => { x: 8, y: 5 } listtotalTo10'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. listtotalTo11'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. listsplice'x'31x: 7y: 1 # => [{x: 5, y: 2}] listgetElements # => [{x: 3, y: 3}, {x: 7, y: 1}, {x: 2, y: 7}, {x: 4, y: 4}] # You can splice in any tracked dimension: listsplice'y'40x: 2y: 2listgetElements # => [{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: listtotalTo3'elements' # => {x: 12, y: 6} # And this splices at the given element index: listsplice'elements'21 # => [{x: 2, y: 2}] listgetElements # => [{x: 3, y: 3}, {x: 7, y: 1}, {x: 2, y: 7}, {x: 4, y: 4}]