xspans
A container that allows to store and manipulate arrays of spans (or intervals).
Introduction
The library allows to store and manipulate arrays of spans (or intervals). It provides a data structure that can store an array of spans in a normalized form (sorted, non-intersecting, and coalesced) and static/member functions that can manipulate it. The library allows to perform a boolean algebra (and, or, xor, and subtraction) and various other operations like testing if a value or a span is in a span-array, and basic manipulation like offseting and scaling.
The library was designed to be friendly for JavaScript engines, especially V8, which powers node.js. The span-array is stored as an array of numbers giving JS engine a chance to store the whole data in an unboxed array. Utility functions to convert to or from internal representation are provided.
Documentation
The library provides member-function based functionality and static-function based functionality. Member functions can be called on objects created by xspans
and static functions are available through xspans
itself, which acts as a namespace in such case. The design follows a rule that member functions generally modify the xspans
container itself whereas static functions always return a new xspans
instance.
Creating an xspans (span-array) object
To create a span-array representation of a span-array use xspans()
or xspans.wrap()
functions.
// Create `xspans` object from an array of packed spans.var a = ; // Create `xspans` object from an array of arrays.var a = ; // Create `xspans` object from an array of objects having from/to.var a = ; // Create `xspans` object from an array of objects having start/end.var a = ; // Create `xspans` object from an array of objects having a/b.var a = ; // Create `xspans` object from an array of objects having custom properties.var a = ;
To wrap an existing data into the xspans
object, consider using xspans.fromData()
:
// Create `xspans` object based on a packed data. The engine will try to// reuse the array if it's well-formed. This can be dangerous in cases that// the input is modified while still being used by `xspans` object.var a = xspans;
NOTE: The library is designed in a way that all arguments always accept xspans
object or plain JavaScript array that is implicitly converted to xspans
for the given operation. You don't need to wrap all data you are using by xspans
, however, it's much faster to wrap each array that is used more than once as the library will normalize it only once and can omit normalization checks during later processing.
Data conversion
If you are done with xspans
it's possible to convert the data back to a preferred data format:
; // [1, 2, 5, 6] (weak).; // [1, 2, 5, 6] (copy).; // [[1, 2], [5, 6]].; // [{ from: 1, to: 2 }, { from: 5, to: 6 }].; // [{ a : 1, b : 2 }, { a : 5, b : 6 }].
Algebraic Operations
The following algebraic operations are provided:
- AND - Use
xspans.and
orxspans.intersect
. - OR - Use
xspans.or
orxspans.union
. - XOR - Use
xspans.xor
. - SUB - Use
xspans.sub
orxspans.subtract
.
Examples:
// Union (OR) two span arrays.var a = xspans; // [1, 2, 5, 6].var a = ; // [1, 2, 5, 6]. // Intersect (AND) two span arrays.var a = xspans; // [4, 6].var a = ; // [4, 6]. // XOR two span arrays.var a = xspans; // [1, 4, 6, 8].var a = ; // [1, 4, 6, 8]. // Subtract one span-array from another.var a = xspans; // [1, 4].var a = ; // [1, 4].
The number of spans in a span-array is not limited:
var a = ;var b = ; xspans; // [1, 2, 5, 6, 10, 200, 1000, 9999].xspans; // [15, 100, 4000, 5000].xspans; // [1, 2, 5, 6, 10, 15, 100, 200, 1000, 4000, 5000, 9999].xspans; // [1, 2, 10, 15, 1000, 4000].
Other Operations
Shifting allows to shift a span-array by a scalar value:
var a = ;a; // [-4, -3, 0, 1, 6, 7].a; // [ 6, 7, 10, 11, 16, 17].
Scaling allows to scale by a scalar value (only positive scale is allowed):
var a = ;a; // [2, 4, 10, 12, 22, 24].
Testing Operations
Testing enables to check whether a scalar value, an array, or a span-array is contained in xspans
object. There are 3 possible results defined:
xspans.kTestNone
- No match - the tested value, array, orxspans
are not part of thexspans
object.xspans.kTestFull
- Full match - the tested value, array, orxspans
are fully contained inxspans
object.xspans.kTestPart
- Partial match - part of an span orxspans
are contained inxspans
object.
var a = ;var b = ; // Scalar.a; // kTestFull.a; // kTestFull.a; // kTestNone (right side is not part of the span). // Interval.a; // kTestFull.a; // kTestPart (only partial match). // Span-array or `xspans` instance.a; // kTestFull.a; // kTestFull.a; // kTestPart.a; // kTestNone (empty array always causes kTestNone).