BitSet
Defined in: packages/data/src/bit/bit-set.ts:38
A fixed-size set of small non-negative integers, one bit per member.
Where a Set<number> costs a hash entry per member, this costs one bit per
possible member — so it wins decisively when the universe is bounded and
the set is dense, and loses when a handful of members are drawn from a huge
range. The set operations are word-at-a-time, which is what makes them
roughly 32× cheaper than the element-at-a-time equivalents.
Time complexity: O(1) for add, delete and has. count, rank and
every set operation are O(size / 32). Space complexity: O(size / 8) bytes,
independent of how many members are present.
Members outside 0 .. size - 1 are a programming error, not a miss: add
and delete throw, so a caller cannot silently lose elements to a mis-sized
set.
Implements
Section titled “Implements”ISet<number>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new BitSet(
iterable?,options?):BitSet
Defined in: packages/data/src/bit/bit-set.ts:47
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<number, any, any>
options?
Section titled “options?”Returns
Section titled “Returns”BitSet
Properties
Section titled “Properties”
readonlysize:number
Defined in: packages/data/src/bit/bit-set.ts:45
The number of bits, i.e. one past the largest member this can hold.
Methods
Section titled “Methods”[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<number>
Defined in: packages/data/src/bit/bit-set.ts:75
Members in ascending order.
Returns
Section titled “Returns”Iterator<number>
Implementation of
Section titled “Implementation of”add(
member):void
Defined in: packages/data/src/bit/bit-set.ts:105
O(1).
Parameters
Section titled “Parameters”member
Section titled “member”number
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If member is outside 0 .. size - 1.
Implementation of
Section titled “Implementation of”addAll()
Section titled “addAll()”addAll(
members):void
Defined in: packages/data/src/bit/bit-set.ts:118
O(m) in the number of members added.
Parameters
Section titled “Parameters”members
Section titled “members”Iterable<number>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/bit/bit-set.ts:95
Removes all elements from the collection.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/bit/bit-set.ts:91
The number of members. O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”delete()
Section titled “delete()”delete(
member):boolean
Defined in: packages/data/src/bit/bit-set.ts:129
O(1).
Parameters
Section titled “Parameters”member
Section titled “member”number
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”If member is outside 0 .. size - 1.
Implementation of
Section titled “Implementation of”difference()
Section titled “difference()”difference(
other):BitSet
Defined in: packages/data/src/bit/bit-set.ts:190
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitSet
Implementation of
Section titled “Implementation of”has(
member):boolean
Defined in: packages/data/src/bit/bit-set.ts:146
O(1). Out-of-range is a miss, not an error — a query never throws.
Parameters
Section titled “Parameters”member
Section titled “member”number
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”intersection()
Section titled “intersection()”intersection(
other):BitSet
Defined in: packages/data/src/bit/bit-set.ts:185
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitSet
Implementation of
Section titled “Implementation of”isDisjointFrom()
Section titled “isDisjointFrom()”isDisjointFrom(
other):boolean
Defined in: packages/data/src/bit/bit-set.ts:220
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”isSubsetOf()
Section titled “isSubsetOf()”isSubsetOf(
other):boolean
Defined in: packages/data/src/bit/bit-set.ts:200
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”isSupersetOf()
Section titled “isSupersetOf()”isSupersetOf(
other):boolean
Defined in: packages/data/src/bit/bit-set.ts:215
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”rank()
Section titled “rank()”rank(
upperBound):number
Defined in: packages/data/src/bit/bit-set.ts:162
How many members are strictly below upperBound. O(size / 32).
The companion of count(): rank(size) is count(). Together with has,
this is what makes a bit set usable as a succinct index.
Parameters
Section titled “Parameters”upperBound
Section titled “upperBound”number
Returns
Section titled “Returns”number
symmetricDifference()
Section titled “symmetricDifference()”symmetricDifference(
other):BitSet
Defined in: packages/data/src/bit/bit-set.ts:195
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitSet
Implementation of
Section titled “Implementation of”union()
Section titled “union()”union(
other):BitSet
Defined in: packages/data/src/bit/bit-set.ts:180
O(size / 32). The result is sized to hold both operands’ universes.
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitSet