Nimony

The road to Nim 3

packedsets

nimony/lib/std/packedsets.nim

The packedsets module implements an efficient set of Ordinal values as a sparse bit set:idx:. Values that cluster -- symbol ids, file ids, node positions -- cost about one bit each, while values far apart cost one small block each.

Unlike HashSet no hash is required of the element type: the element's ordinal value is the bit index. That is exactly what Ordinal gives us -- int(x) to find the bit and A(i) to hand the element back out of items -- so Ordinal is the constraint, and it is enough to typecheck every body here up front. Routines needing more say so: $ also asks for Stringable.

See also ========

sets module for general hash sets
intsets module for the non-generic int case

```
type PackedSet = object
  t: Table
```
func initPackedSet(): PackedSet[A]
Returns an empty PackedSet[A].
func contains(s: PackedSet[A]; key: A): bool
True if key is in s. This allows the usage of the in operator.
func incl(s: var PackedSet[A]; key: A)
Includes key in s. Does nothing if it is already in there.
func excl(s: var PackedSet[A]; key: A)
Excludes key from s. Does nothing if it is not in there.
func containsOrIncl(s: var PackedSet[A]; key: A): bool
Includes key in s and tells whether it was already in there.
func missingOrExcl(s: var PackedSet[A]; key: A): bool
Excludes key from s and tells whether it was already missing.
iterator items(s: PackedSet[A]): A
Iterates over every element of s. Trunks come out in insertion order (nimony's Table is insertion-ordered) and ascending within a trunk, so the traversal is reproducible across runs.
func len(s: PackedSet[A]): int64
The number of elements in s.
func card(s: PackedSet[A]): int64
Alias for len: the cardinality of the set.
func clear(s: var PackedSet[A])
Resets s back to the empty set.
func toPackedSet(x: openArray[A]): PackedSet[A]
A new PackedSet[A] holding the elements of x; duplicates are removed.
func incl(s: var PackedSet[A]; other: PackedSet[A])
Includes every element of other in s -- the in-place s + other.
func excl(s: var PackedSet[A]; other: PackedSet[A])
Excludes every element of other from s -- the in-place s - other.
func union(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
The union of s1 and s2.
func intersection(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
The intersection of s1 and s2.
func difference(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
The difference of s1 and s2: everything in s1 that is not in s2.
func symmetricDifference(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
Everything that is in exactly one of s1 and s2.
func +(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
Alias for union.
func *(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
Alias for intersection.
func -(s1: PackedSet[A]; s2: PackedSet[A]): PackedSet[A]
Alias for difference.
func disjoint(s1: PackedSet[A]; s2: PackedSet[A]): bool
True if s1 and s2 have no element in common.
func <=(s1: PackedSet[A]; s2: PackedSet[A]): bool
True if s1 is a subset of s2 (s1 may equal s2).
func <(s1: PackedSet[A]; s2: PackedSet[A]): bool
True if s1 is a proper subset of s2.
func ==(s1: PackedSet[A]; s2: PackedSet[A]): bool
True if both sets hold the same elements.
func $(s: PackedSet[A]): string
Renders s as {a, b, c}. Needs $ of the element type on top of the Ordinal-ness the container itself requires.