BitVector
Defined in: packages/data/src/bit/bit-vector.ts:30
The growable counterpart of BitSet: a bit vector with no fixed universe.
BitSet throws on a member outside its size, which is what a caller wants
when the universe is known and a stray index is a bug. This one grows the
backing instead, doubling it, so add never rejects a non-negative integer.
The trade is that size is a moving target and a typo silently allocates
rather than failing loudly — prefer BitSet whenever the bound is known.
Growth never shrinks: delete and clear clear bits but keep the backing,
so a vector that once held a large member stays that large. size therefore
reports the current capacity in bits, not the largest member held.
Time complexity: O(1) amortised for add, O(1) for delete and has,
O(size / 32) for count, rank and the set operations.
BitSet for the fixed-size version, and for the operation semantics.
Implements
Section titled “Implements”ISet<number>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new BitVector(
iterable?):BitVector
Defined in: packages/data/src/bit/bit-vector.ts:34
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<number, any, any>
Returns
Section titled “Returns”BitVector
Accessors
Section titled “Accessors”Get Signature
Section titled “Get Signature”get size():
number
Defined in: packages/data/src/bit/bit-vector.ts:43
The current capacity in bits, which grows and never shrinks.
Returns
Section titled “Returns”number
Methods
Section titled “Methods”[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<number>
Defined in: packages/data/src/bit/bit-vector.ts:48
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-vector.ts:78
O(1) amortised — grows the backing when member is beyond it.
Parameters
Section titled “Parameters”member
Section titled “member”number
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If member is negative or not an integer. Unlike the
upper bound, that can never be a sizing question.
Implementation of
Section titled “Implementation of”addAll()
Section titled “addAll()”addAll(
members):void
Defined in: packages/data/src/bit/bit-vector.ts:92
O(m), growing at most once per distinct backing size.
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-vector.ts:67
Clears every bit. Does not release the backing.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/bit/bit-vector.ts:62
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-vector.ts:99
O(1). A member beyond the current capacity was never present.
Parameters
Section titled “Parameters”member
Section titled “member”number
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”difference()
Section titled “difference()”difference(
other):BitVector
Defined in: packages/data/src/bit/bit-vector.ts:148
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitVector
Implementation of
Section titled “Implementation of”has(
member):boolean
Defined in: packages/data/src/bit/bit-vector.ts:120
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):BitVector
Defined in: packages/data/src/bit/bit-vector.ts:143
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitVector
Implementation of
Section titled “Implementation of”isDisjointFrom()
Section titled “isDisjointFrom()”isDisjointFrom(
other):boolean
Defined in: packages/data/src/bit/bit-vector.ts:176
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-vector.ts:160
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-vector.ts:165
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-vector.ts:131
How many members are strictly below upperBound. O(size / 32).
Parameters
Section titled “Parameters”upperBound
Section titled “upperBound”number
Returns
Section titled “Returns”number
symmetricDifference()
Section titled “symmetricDifference()”symmetricDifference(
other):BitVector
Defined in: packages/data/src/bit/bit-vector.ts:153
O(size / 32).
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitVector
Implementation of
Section titled “Implementation of”union()
Section titled “union()”union(
other):BitVector
Defined in: packages/data/src/bit/bit-vector.ts:136
O(size / 32). Returns a BitVector, so the result grows too.
Parameters
Section titled “Parameters”Iterable<number>
Returns
Section titled “Returns”BitVector