<a id="nupp.bitset"></a>
# `nupp.bitset`

## Types

<a id="nupp.bitset.Bitset"></a>
### `Bitset` _record_

```nupp
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

<a id="nupp.bitset.Bitset.constructor"></a>
##### `constructor`

```nupp
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 |

<a id="nupp.bitset.Bitset.reserve"></a>
##### `reserve`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.set"></a>
##### `set`

```nupp
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

<a id="nupp.bitset.Bitset.clear"></a>
##### `clear`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.get"></a>
##### `get`

```nupp
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 |

<a id="nupp.bitset.Bitset.setRange"></a>
##### `setRange`

```nupp
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

<a id="nupp.bitset.Bitset.count"></a>
##### `count`

```nupp
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 |

<a id="nupp.bitset.Bitset.isEmpty"></a>
##### `isEmpty`

```nupp
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 |

<a id="nupp.bitset.Bitset.clearAll"></a>
##### `clearAll`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.setOnly"></a>
##### `setOnly`

```nupp
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

<a id="nupp.bitset.Bitset.wordCount"></a>
##### `wordCount`

```nupp
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 |

<a id="nupp.bitset.Bitset.wordAt"></a>
##### `wordAt`

```nupp
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 |

<a id="nupp.bitset.Bitset.nextSetBit"></a>
##### `nextSetBit`

```nupp
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 |

<a id="nupp.bitset.Bitset.positionsInto"></a>
##### `positionsInto`

```nupp
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

<a id="nupp.bitset.Bitset.containsAll"></a>
##### `containsAll`

```nupp
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. |

<a id="nupp.bitset.Bitset.overlaps"></a>
##### `overlaps`

```nupp
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 |

<a id="nupp.bitset.Bitset.disjoint"></a>
##### `disjoint`

```nupp
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` |

<a id="nupp.bitset.Bitset.copyFrom"></a>
##### `copyFrom`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.orWith"></a>
##### `orWith`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.andWith"></a>
##### `andWith`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.andNotWith"></a>
##### `andNotWith`

```nupp
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` |  |

<a id="nupp.bitset.Bitset.xorWith"></a>
##### `xorWith`

```nupp
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` |  |