`nupp.bitset`

Module contents

Types

Type	Kind	Description
`Bitset`	record	A growable set of bit positions counting from 0.

Types#

`Bitset`record#

record data.Bitset
    constructor(self, capacityBits: integer?) end

    function reserve(self, bits: integer): nil end

    function set(self, index: integer): nil end

    function clear(self, index: integer): nil end

    function get(self, index: integer): boolean end

    function setRange(self, low: integer, high: integer): nil end

    function count(self): integer end

    function isEmpty(self): boolean end

    function clearAll(self): nil end

    function setOnly(self, index: integer): nil end

    function wordCount(self): integer end

    function wordAt(self, index: integer): integer end

    function nextSetBit(self, from: integer): integer end

    function positionsInto(self, target: int32[?], capacity: integer, from: integer): (integer, integer) end

    function containsAll(self, other: Bitset): boolean end

    function overlaps(self, other: Bitset): boolean end

    function disjoint(self, other: Bitset): boolean end

    function copyFrom(self, other: Bitset): nil end

    function orWith(self, other: Bitset): nil end

    function andWith(self, other: Bitset): nil end

    function andNotWith(self, other: Bitset): nil end

    function xorWith(self, other: Bitset): nil end
end

A growable set of bit positions counting from 0.

Reading, clearing and testing a position past the end are defined and cheap. Setting one grows, which reallocates private storage; nothing observable survives that, because the storage is never handed out.

Methods

`constructor`#

constructor: function constructor(self, capacityBits: integer?)

Creates an empty set.

Arguments

Name	Type	Description
`self`	`any`	the set being initialized
`capacityBits`	`integer?`	how many bits to allocate initially; setting a later position grows the set

`reserve`#

reserve: function reserve(self, bits: integer): nil

Grows storage so at least bits bits fit. Only grows, and never returns storage. A growth at least doubles, so repeated small growths stay amortised.

Arguments

Name	Type	Description
`self`	`any`
`bits`	`integer`	how many bits must fit

Returns

Type	Description
`nil`

`set`#

set: function set(self, index: integer): nil

Adds a bit, growing when it is past the end.

Arguments

Name	Type	Description
`self`	`any`
`index`	`integer`	the bit position, counting from 0

Returns

Type	Description
`nil`

Raises

when index is negative

`clear`#

clear: function clear(self, index: integer): nil

Removes a bit. Never allocates, and never narrows the used-word bound, so it stays constant-time whichever bit it was.

Arguments

Name	Type	Description
`self`	`any`
`index`	`integer`	the bit position, counting from 0. One past the end, a negative one included, does nothing.

Returns

Type	Description
`nil`

`get`#

get: function get(self, index: integer): boolean

Whether a bit is set.

Arguments

Name	Type	Description
`self`	`any`
`index`	`integer`	the bit position, counting from 0

Returns

Type	Description
`boolean`	false for any position past the end, so no bound check is needed at the call site

`setRange`#

setRange: function setRange(self, low: integer, high: integer): nil

Adds every bit in the inclusive range, one word-mask write per word rather than one operation per bit.

Arguments

Name	Type	Description
`self`	`any`
`low`	`integer`	the first position added, counting from 0
`high`	`integer`	the last position added. Below `low` adds nothing, so an empty range needs no guard at the call site.

Returns

Type	Description
`nil`

Raises

when low is negative

`count`#

count: function count(self): integer

How many bits are set. Resolves a pending recount, so a caller that reads it every frame pays for the set algebra it skipped; one that never reads it never pays.

Arguments

Name	Type	Description
`self`	`any`

Returns

Type	Description
`integer`	the number of set bits

`isEmpty`#

isEmpty: function isEmpty(self): boolean

Whether nothing is set. Says nothing about capacity.

Arguments

Name	Type	Description
`self`	`any`

Returns

Type	Description
`boolean`	true when no bit is set

`clearAll`#

clearAll: function clearAll(self): nil

Removes every bit, keeping capacity so a set reused each frame stops allocating once it has reached its peak.

Arguments

Name	Type	Description
`self`	`any`

Returns

Type	Description
`nil`

`setOnly`#

setOnly: function setOnly(self, index: integer): nil

Removes every bit, then adds exactly one.

Arguments

Name	Type	Description
`self`	`any`
`index`	`integer`	the one position left set, counting from 0

Returns

Type	Description
`nil`

Raises

when index is negative

`wordCount`#

wordCount: function wordCount(self): integer

An upper bound on the words that may hold a set bit. Every word at or above it is zero, and it is not narrowed by clear or by intersection, so it may exceed the exact high-water mark.

Arguments

Name	Type	Description
`self`	`any`

Returns

Type	Description
`integer`	the number of words a word-at-a-time walk must visit

`wordAt`#

wordAt: function wordAt(self, index: integer): integer

One stored word. Word w holds positions w * WORD_BITS through w * WORD_BITS + WORD_BITS - 1, lowest position first.

Arguments

Name	Type	Description
`self`	`any`
`index`	`integer`	a word index counting from 0, bounded by `wordCount`

Returns

Type	Description
`integer`	the word as a signed value, so one with its top bit set reads negative, and 0 for any index outside the bound

`nextSetBit`#

nextSetBit: function nextSetBit(self, from: integer): integer

The lowest set position at or after from.

Stateless, so nested walks do not interfere and a mutation between calls cannot invalidate a walk in progress.

Arguments

Name	Type	Description
`self`	`any`
`from`	`integer`	the lowest position that may be returned, counting from 0

Returns

Type	Description
`integer`	that position, or -1 when there is none

`positionsInto`#

positionsInto: function positionsInto(self, target: int32[?], capacity: integer, from: integer): integer, integer

Writes every set position at or after from into target, lowest first.

One call rather than one per position. A walk pays a call and a word read for every position it returns, which for a few thousand positions is most of what it costs; this reads each word once and clears the position it just reported out of a register.

target is a pointer and a count because that is what a native kernel takes. Filling it here rather than allocating keeps a per-frame extraction allocation-free, and leaves the boundary where a native one would sit.

Arguments

Name	Type	Description
`self`	`any`
`target`	`int32[?]`	where positions are written, indexed from 0
`capacity`	`integer`	how many positions `target` holds
`from`	`integer`	the lowest position that may be written, counting from 0

Returns

Type	Description
`integer`	how many positions were written, and the position to resume from when `target` filled first, or -1 when the set is exhausted
`integer`

Raises

when capacity is negative

`containsAll`#

containsAll: function containsAll(self, other: Bitset): boolean

Whether every bit set in other is also set here.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified

Returns

Type	Description
`boolean`	true when `other` is a subset. An empty `other` is contained by anything.

`overlaps`#

overlaps: function overlaps(self, other: Bitset): boolean

Whether at least one bit is set in both. Early-exiting, and deliberately not an intersection followed by a count.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified, as is the receiver

Returns

Type	Description
`boolean`	true when the two share a set bit

`disjoint`#

disjoint: function disjoint(self, other: Bitset): boolean

Whether the two share no set bit.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified, as is the receiver

Returns

Type	Description
`boolean`	the negation of `overlaps`

`copyFrom`#

copyFrom: function copyFrom(self, other: Bitset): nil

Replaces these bits with a copy of other's. The two are independent afterwards, and this keeps its own capacity when that is the larger.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified

Returns

Type	Description
`nil`

`orWith`#

orWith: function orWith(self, other: Bitset): nil

Adds every bit set in other.

One bitwise operation per word: the population is marked for recount rather than tracked, and there is no per-word test for whether the word changed, because that branch costs more than the write it saves.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified

Returns

Type	Description
`nil`

`andWith`#

andWith: function andWith(self, other: Bitset): nil

Keeps only the bits also set in other.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified. Words beyond the ones it uses are cleared, so an empty `other` empties the receiver.

Returns

Type	Description
`nil`

`andNotWith`#

andNotWith: function andNotWith(self, other: Bitset): nil

Removes every bit set in other.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified. Words beyond the ones it uses keep their bits, so an empty `other` changes nothing.

Returns

Type	Description
`nil`

`xorWith`#

xorWith: function xorWith(self, other: Bitset): nil

Keeps only the bits set in exactly one of the two.

Arguments

Name	Type	Description
`self`	`any`
`other`	`Bitset`	read and not modified

Returns

Type	Description
`nil`

nupp.bitset

Module contents

Types

Types#

Bitsetrecord#

Methods

constructor#

Arguments

reserve#

Arguments

Returns

set#

Arguments

Returns

Raises

clear#

Arguments

Returns

get#

Arguments

Returns

setRange#

Arguments

Returns

Raises

count#

Arguments

Returns

isEmpty#

Arguments

Returns

clearAll#

Arguments

Returns

setOnly#

Arguments

Returns

Raises

wordCount#

Arguments

Returns

wordAt#

Arguments

Returns

nextSetBit#

Arguments

Returns

positionsInto#

Arguments

Returns

Raises

containsAll#

Arguments

Returns

overlaps#

Arguments

Returns

disjoint#

Arguments

Returns

copyFrom#

Arguments

Returns

orWith#

Arguments

Returns

andWith#

Arguments

Returns

andNotWith#

Arguments

Returns

xorWith#

Arguments

Returns

`nupp.bitset`

`Bitset`record#

`constructor`#

`reserve`#

`set`#

`clear`#

`get`#

`setRange`#

`count`#

`isEmpty`#

`clearAll`#

`setOnly`#

`wordCount`#

`wordAt`#

`nextSetBit`#

`positionsInto`#

`containsAll`#

`overlaps`#

`disjoint`#

`copyFrom`#

`orWith`#

`andWith`#

`andNotWith`#

`xorWith`#