# intsets

- Manual
- Standard library
- Index

Search:
Group by:

The `intsets` module implements an efficient `int` set implemented as a sparse bit set.

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

See also:

- sets module for more general hash sets

# Imports

hashes, math, sequtils, algorithm

# Types

    IntSet = object
      elems: int
      counter, max: int
      head: PTrunk
      data: TrunkSeq
      a: array[0 .. 33, int]

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

# Procs

    proc initIntSet(): IntSet {...}{.raises: [], tags: [].}

  Returns an empty IntSet.

  Examples:

      var a = initIntSet()
      assert len(a) == 0

  Source Edit

    proc contains(s: IntSet; key: int): bool {...}{.raises: [], tags: [].}

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

  This allows the usage of `in` operator.

  Examples:

      var a = initIntSet()
      for x in [1, 3, 5]:
        a.incl(x)
      assert a.contains(3)
      assert 3 in a
      assert(not a.contains(8))
      assert 8 notin a

  Source Edit

    proc incl(s: var IntSet; key: int) {...}{.raises: [], tags: [].}

  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 other set
  - containsOrIncl proc

  Examples:

      var a = initIntSet()
      a.incl(3)
      a.incl(3)
      assert len(a) == 1

  Source Edit

    proc incl(s: var IntSet; other: IntSet) {...}{.raises: [], tags: [].}

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

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

  See also:

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      b.incl(5)
      a.incl(b)
      assert len(a) == 2
      assert 5 in a

  Source Edit

    proc containsOrIncl(s: var IntSet; key: int): bool {...}{.raises: [], tags: [].}

  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

  Examples:

      var a = initIntSet()
      assert a.containsOrIncl(3) == false
      assert a.containsOrIncl(3) == true
      assert a.containsOrIncl(4) == false

  Source Edit

    proc excl(s: var IntSet; key: int) {...}{.raises: [], tags: [].}

  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 other set
  - missingOrExcl proc

  Examples:

      var a = initIntSet()
      a.incl(3)
      a.excl(3)
      a.excl(3)
      a.excl(99)
      assert len(a) == 0

  Source Edit

    proc excl(s: var IntSet; other: IntSet) {...}{.raises: [], tags: [].}

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

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

  See also:

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(5)
      b.incl(5)
      a.excl(b)
      assert len(a) == 1
      assert 5 notin a

  Source Edit

    proc missingOrExcl(s: var IntSet; key: int): bool {...}{.raises: [], tags: [].}

  Excludes `key` in 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 other set
  - containsOrIncl proc

  Examples:

      var a = initIntSet()
      a.incl(5)
      assert a.missingOrExcl(5) == false
      assert a.missingOrExcl(5) == true

  Source Edit

    proc clear(result: var IntSet) {...}{.raises: [], tags: [].}

  Clears the IntSet back to an empty state.

  Examples:

      var a = initIntSet()
      a.incl(5)
      a.incl(7)
      clear(a)
      assert len(a) == 0

  Source Edit

    proc isNil(x: IntSet): bool {...}{.inline, raises: [], tags: [].}

  Source Edit

    proc assign(dest: var IntSet; src: IntSet) {...}{.raises: [], tags: [].}

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      b.incl(5)
      b.incl(7)
      a.assign(b)
      assert len(a) == 2

  Source Edit

    proc union(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

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

  The same as s1 + s2.

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(2)
      a.incl(3)
      b.incl(3)
      b.incl(4)
      b.incl(5)
      assert union(a, b).len == 5
      ## {1, 2, 3, 4, 5}

  Source Edit

    proc intersection(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

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

  The same as s1 * s2.

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(2)
      a.incl(3)
      b.incl(3)
      b.incl(4)
      b.incl(5)
      assert intersection(a, b).len == 1
      ## {3}

  Source Edit

    proc difference(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

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

  The same as s1 - s2.

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(2)
      a.incl(3)
      b.incl(3)
      b.incl(4)
      b.incl(5)
      assert difference(a, b).len == 2
      ## {1, 2}

  Source Edit

    proc symmetricDifference(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(2)
      a.incl(3)
      b.incl(3)
      b.incl(4)
      b.incl(5)
      assert symmetricDifference(a, b).len == 4
      ## {1, 2, 4, 5}

  Source Edit

    proc `+`(s1, s2: IntSet): IntSet {...}{.inline, raises: [], tags: [].}

  Alias for union(s1, s2). Source Edit

    proc `*`(s1, s2: IntSet): IntSet {...}{.inline, raises: [], tags: [].}

  Alias for intersection(s1, s2). Source Edit

    proc `-`(s1, s2: IntSet): IntSet {...}{.inline, raises: [], tags: [].}

  Alias for difference(s1, s2). Source Edit

    proc disjoint(s1, s2: IntSet): bool {...}{.raises: [], tags: [].}

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      a.incl(2)
      b.incl(2)
      b.incl(3)
      assert disjoint(a, b) == false
      b.excl(2)
      assert disjoint(a, b) == true

  Source Edit

    proc len(s: IntSet): int {...}{.inline, raises: [], tags: [].}

  Returns the number of elements in `s`. Source Edit

    proc card(s: IntSet): int {...}{.inline, raises: [], tags: [].}

  Alias for len(). Source Edit

    proc `<=`(s1, s2: IntSet): bool {...}{.raises: [], tags: [].}

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

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      b.incl(1)
      b.incl(2)
      assert a <= b
      a.incl(2)
      assert a <= b
      a.incl(3)
      assert(not (a <= b))

  Source Edit

    proc `<`(s1, s2: IntSet): bool {...}{.raises: [], tags: [].}

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

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

  Examples:

      var
        a = initIntSet()
        b = initIntSet()
      a.incl(1)
      b.incl(1)
      b.incl(2)
      assert a < b
      a.incl(2)
      assert(not (a < b))

  Source Edit

    proc `==`(s1, s2: IntSet): bool {...}{.raises: [], tags: [].}

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

    proc `$`(s: IntSet): string {...}{.raises: [], tags: [].}

  The `$` operator for int sets.

  Converts the set `s` to a string, mostly for logging and printing purposes.

  Source Edit

# Iterators

    iterator items(s: IntSet): int {...}{.inline, raises: [], tags: [].}

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