# std/packedsets

Dark Mode

- Manual
- Standard library
- Index
- Compiler docs
- Fusion docs
- devel, stable

Search:
Source Edit

The `packedsets` module implements an efficient `Ordinal` set implemented as a sparse bit set.

Supports any Ordinal type.

Note: Currently the assignment operator `=` for `PackedSet[A]` performs some rather meaningless shallow copy. Since Nim currently does not allow the assignment operator to be overloaded, use the assign proc to get a deep copy.

# See also

- sets module for more general hash sets

# Imports

since, hashes

# Types

    PackedSet[A] = object
      elems: int
      counter, max: int
      head: Trunk
      data: TrunkSeq
      a: array[0 .. 33, int]

  An efficient set of `Ordinal` types implemented as a sparse bit set. Source Edit

# Procs

    proc `$`[A](s: PackedSet[A]): string

  Converts `s` to a string.

  Example:

      let a = [1, 2, 3].toPackedSet
      assert $a == "{1, 2, 3}"

  Source Edit

    proc `*`[A](s1, s2: PackedSet[A]): PackedSet[A] {.inline.}

  Alias for intersection(s1, s2). Source Edit

    proc `+`[A](s1, s2: PackedSet[A]): PackedSet[A] {.inline.}

  Alias for union(s1, s2). Source Edit

    proc `-`[A](s1, s2: PackedSet[A]): PackedSet[A] {.inline.}

  Alias for difference(s1, s2). Source Edit

    proc `<=`[A](s1, s2: PackedSet[A]): bool

  Returns true if `s1` is a subset of `s2`.

  A subset `s1` has all of its elements in `s2`, but `s2` doesn't necessarily have more elements than `s1`. That is, `s1` can be equal to `s2`.

  Example:

      let
        a = [1].toPackedSet
        b = [1, 2].toPackedSet
        c = [1, 3].toPackedSet
      assert a <= b
      assert b <= b
      assert not (c <= b)

  Source Edit

    proc `<`[A](s1, s2: PackedSet[A]): bool

  Returns true if `s1` is a proper subset of `s2`.

  A strict or proper subset `s1` has all of its elements in `s2`, but `s2` has more elements than `s1`.

  Example:

      let
        a = [1].toPackedSet
        b = [1, 2].toPackedSet
        c = [1, 3].toPackedSet
      assert a < b
      assert not (b < b)
      assert not (c < b)

  Source Edit

    proc `==`[A](s1, s2: PackedSet[A]): bool

  Returns true if both `s1` and `s2` have the same elements and set size.

  Example:

      assert [1, 2].toPackedSet == [2, 1].toPackedSet
      assert [1, 2].toPackedSet == [2, 1, 2].toPackedSet

  Source Edit

    proc assign[A](dest: var PackedSet[A]; src: PackedSet[A])

  Copies `src` to `dest`. `dest` does not need to be initialized by the initPackedSet proc.

  Example:

      var
        a = initPackedSet[int]()
        b = initPackedSet[int]()
      b.incl(5)
      b.incl(7)
      a.assign(b)
      assert len(a) == 2

  Source Edit

    proc card[A](s: PackedSet[A]): int {.inline.}

  Alias for len().

  Card stands for the cardinality of a set.

  Source Edit

    proc clear[A](result: var PackedSet[A])

  Clears the `PackedSet[A]` back to an empty state.

  Example:

      var a = [5, 7].toPackedSet
      clear(a)
      assert len(a) == 0

  Source Edit

    proc contains[A](s: PackedSet[A]; key: A): bool

  Returns true if `key` is in `s`.

  This allows the usage of the `in` operator.

  Example:

      type ABCD = enum A, B, C, D

      let a = [1, 3, 5].toPackedSet
      assert a.contains(3)
      assert 3 in a
      assert not a.contains(8)
      assert 8 notin a

      let letters = [A, C].toPackedSet
      assert A in letters
      assert C in letters
      assert B notin letters

  Source Edit

    proc containsOrIncl[A](s: var PackedSet[A]; key: A): bool

  Includes `key` in the set `s` and tells if `key` was already in `s`.

  The difference with regards to the incl proc is that this proc returns true if `s` already contained `key`. The proc will return false if `key` was added as a new value to `s` during this call.

  See also:

  - incl proc for including an element
  - missingOrExcl proc

  Example:

      var a = initPackedSet[int]()
      assert a.containsOrIncl(3) == false
      assert a.containsOrIncl(3) == true
      assert a.containsOrIncl(4) == false

  Source Edit

    proc difference[A](s1, s2: PackedSet[A]): PackedSet[A]

  Returns the difference of the sets `s1` and `s2`.

  The same as s1 - s2.

  Example:

      let
        a = [1, 2, 3].toPackedSet
        b = [3, 4, 5].toPackedSet
        c = difference(a, b)
      assert c.len == 2
      assert c == [1, 2].toPackedSet

  Source Edit

    proc disjoint[A](s1, s2: PackedSet[A]): bool

  Returns true if the sets `s1` and `s2` have no items in common.

  Example:

      let
        a = [1, 2].toPackedSet
        b = [2, 3].toPackedSet
        c = [3, 4].toPackedSet
      assert disjoint(a, b) == false
      assert disjoint(a, c) == true

  Source Edit

    proc excl[A](s: var PackedSet[A]; key: A)

  Excludes `key` from the set `s`.

  This doesn't do anything if `key` is not found in `s`.

  See also:

  - incl proc for including an element
  - excl proc for excluding a set
  - missingOrExcl proc

  Example:

      var a = [3].toPackedSet
      a.excl(3)
      a.excl(3)
      a.excl(99)
      assert len(a) == 0

  Source Edit

    proc excl[A](s: var PackedSet[A]; other: PackedSet[A])

  Excludes all elements from `other` from `s`.

  This is the in-place version of s - other.

  See also:

  - incl proc for including a set
  - excl proc for excluding an element
  - missingOrExcl proc

  Example:

      var a = [1, 5].toPackedSet
      a.excl([5].toPackedSet)
      assert len(a) == 1
      assert 5 notin a

  Source Edit

    proc incl[A](s: var PackedSet[A]; key: A)

  Includes an element `key` in `s`.

  This doesn't do anything if `key` is already in `s`.

  See also:

  - excl proc for excluding an element
  - incl proc for including a set
  - containsOrIncl proc

  Example:

      var a = initPackedSet[int]()
      a.incl(3)
      a.incl(3)
      assert len(a) == 1

  Source Edit

    proc incl[A](s: var PackedSet[A]; other: PackedSet[A])

  Includes all elements from `other` into `s`.

  This is the in-place version of s + other.

  See also:

  - excl proc for excluding a set
  - incl proc for including an element
  - containsOrIncl proc

  Example:

      var a = [1].toPackedSet
      a.incl([5].toPackedSet)
      assert len(a) == 2
      assert 5 in a

  Source Edit

    proc initPackedSet[A](): PackedSet[A]

  Returns an empty `PackedSet[A]`. `A` must be `Ordinal`.

  See also:

  - toPackedSet proc

  Example:

      let a = initPackedSet[int]()
      assert len(a) == 0

      type Id = distinct int
      var ids = initPackedSet[Id]()
      ids.incl(3.Id)

  Source Edit

    proc intersection[A](s1, s2: PackedSet[A]): PackedSet[A]

  Returns the intersection of the sets `s1` and `s2`.

  The same as s1 * s2.

  Example:

      let
        a = [1, 2, 3].toPackedSet
        b = [3, 4, 5].toPackedSet
        c = intersection(a, b)
      assert c.len == 1
      assert c == [3].toPackedSet

  Source Edit

    proc isNil[A](x: PackedSet[A]): bool {.inline.}

  Returns true if `x` is empty, false otherwise.

  Example:

      var a = initPackedSet[int]()
      assert a.isNil
      a.incl(2)
      assert not a.isNil
      a.excl(2)
      assert a.isNil

  Source Edit

    proc len[A](s: PackedSet[A]): int {.inline.}

  Returns the number of elements in `s`.

  Example:

      let a = [1, 3, 5].toPackedSet
      assert len(a) == 3

  Source Edit

    proc missingOrExcl[A](s: var PackedSet[A]; key: A): bool

  Excludes `key` from the set `s` and tells if `key` was already missing from `s`.

  The difference with regards to the excl proc is that this proc returns true if `key` was missing from `s`. The proc will return false if `key` was in `s` and it was removed during this call.

  See also:

  - excl proc for excluding an element
  - excl proc for excluding a set
  - containsOrIncl proc

  Example:

      var a = [5].toPackedSet
      assert a.missingOrExcl(5) == false
      assert a.missingOrExcl(5) == true

  Source Edit

    proc symmetricDifference[A](s1, s2: PackedSet[A]): PackedSet[A]

  Returns the symmetric difference of the sets `s1` and `s2`.

  Example:

      let
        a = [1, 2, 3].toPackedSet
        b = [3, 4, 5].toPackedSet
        c = symmetricDifference(a, b)
      assert c.len == 4
      assert c == [1, 2, 4, 5].toPackedSet

  Source Edit

    proc toPackedSet[A](x: openArray[A]): PackedSet[A]

  Creates a new `PackedSet[A]` that contains the elements of `x`.

  Duplicates are removed.

  See also:

  - initPackedSet proc

  Example:

      let a = [5, 6, 7, 8, 8].toPackedSet
      assert len(a) == 4
      assert $a == "{5, 6, 7, 8}"

  Source Edit

    proc union[A](s1, s2: PackedSet[A]): PackedSet[A]

  Returns the union of the sets `s1` and `s2`.

  The same as s1 + s2.

  Example:

      let
        a = [1, 2, 3].toPackedSet
        b = [3, 4, 5].toPackedSet
        c = union(a, b)
      assert c.len == 5
      assert c == [1, 2, 3, 4, 5].toPackedSet

  Source Edit

# Iterators

    iterator items[A](s: PackedSet[A]): A {.inline.}

  Iterates over any included element of `s`. Source Edit