sparse-set
An implementation of Briggs and Torczon's Efficient Representation for Sparse Sets.
This package exports a single class, SparseSet
, with the following interface:
class SparseSet {
readonly bound: number;
readonly preserve_order: boolean;
length: number;
size: number;
constructor(bound: number, options?: SparseSetOpts);
has(k: number): boolean;
add(k: number): SparseSet;
clear(): SparseSet;
delete(k: number, preserve_order?: boolean): boolean;
forEach(cb: (k: number) => void): void;
copy(options?: SparseSetOpts & { bound?: number; }): SparseSet;
complement(options?: SparseSetOpts & { bound?: number; }): SparseSet;
union(s: SparseSet): SparseSet;
intersect(s: SparseSet, preserve_order?: boolean): SparseSet;
difference(s: SparseSet, preserve_order?: boolean): SparseSet;
xor(s: SparseSet, preserve_order?: boolean): SparseSet;
entries(): Generator<[number, number]>;
keys(): Generator<number>;
values(): Generator<number>;
[Symbol.iterator](): Generator<number>;
}
SparseSetOpts
looks like this:
export interface SparseSetOpts {
values?: Iterable<number>;
preserve_order?: boolean;
memory?: {
buffer: ArrayBuffer;
byteOffset?: number;
};
}
The SparseSet
constructor requires a bound
argument which specifies the maximum size of the set (and is one more than the largest value that can be stored in the set). This is used to pre-allocate memory for the entire set, and, by defining a finite universe of set elements, allows performing set complement operations. If memory
is not provided, a new ArrayBuffer
is automatically allocated. Note that one of the advantages of this sparse set data structure is that memory can be allocated quickly, because it does not need to be initialized--however, JavaScript does not allow allocating uninitialized memory (ArrayBuffer
s are always initialized to zero), which eliminates that advantage. However, should you already have a sufficiently large ArrayBuffer
on hand to re-use, you can pass it through the memory
object to avoid re-allocation and re-initialization costs. Also note that TypedArray
and DataView
objects conform to the necessary interface to be directly passed as memory
objects. Like the built-in Set
object, the SparseSet
constructor can take in an optional iterable of initial elements via the values
field of SparseSetOpts
. There is also an optional preserve_order
argument; by default, SparseSet
preserves insertion order of elements for iteration; however, delete
s, intersection
s, difference
s, and xor
s can scramble the insertion order. Setting preserve_order
to true
ensures that insertion order is preserved under all operations, at a slight performance penalty. Each of those four methods also takes an optional preserve_order
argument, which can be used to override the default set by the constructor.
Note that SparseSet
duplicates the interface of the built-in JavaScript Set
type, with following additional properties and methods and properties:
-
bound: number
: the maximum size of the set; 1 more than the maximum value that can be stored in the set. -
length: number
: an alias forsize
. In contrast to a built-inSet
, thelength
andsize
properties can be set to truncate the latest values added to aSparseSet
. Attempting to setlength
orsize
to something larger than their current values will throw an exception. -
copy(options?: SparseSetOpts & { bound?: number; }): SparseSet
: efficiently produces a newSparseSet
containing a copy of the data in the originalSparseSet
. Ifbound
orpreserve_order
options are omitted, they will be copied from the originalSparseSet
. Settingbound
to a smaller value than that of the original will truncate elements that exceed the new bound. Backing memory is not re-used; pre-allocated memory for the new set can be passed in through the options object, but otherwise new memory will be automatically allocated. -
complement(options?: SparseSetOpts & { bound?: number; })
: efficiently produces a newSparseSet
containing all elements belowbound
which are not in the originalSparseSet
. Ifbound
orpreserve_order
options are omitted, they will be copied from the originalSparseSet
. Settingbound
to a smaller value than that of the original will truncate elements that exceed the new bound. Backing memory is not re-used; pre-allocated memory for the new set can be passed in through the options object, but otherwise new memory will be automatically allocated. -
union(s: SparseSet): SparseSet
: updates the currentSparseSet
with the elements from the givenSparseSet
, dropping any elements which are outside the current bound. -
intersection(s: SparseSet, preserve_order?: boolean): SparseSet
: removes elements from the currentSparseSet
that do not occur in the givenSparseSet
. -
difference(s: SparseSet, preserve_order?: boolean): SparseSet
: removes elements from the currentSparseSet
which do occur in the givenSparseSet
. -
xor(s: SparseSet, preserve_order?: boolean): SparseSet
: removes elements from the currentSparseSet
which occur in the givenSparseSet
, and adds elements from the givenSparseSet
which were not previously in the currentSparseSet
, dropping any elements which are outside the current bound.