Module intsets

The intsets module implements an efficient int set implemented as a sparse bit set. Note: Since Nim currently does not allow the assignment operator to be overloaded, = for int sets performs some rather meaningless shallow copy; use assign to get a deep copy.

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

Procs

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

returns true iff key is in s.

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

includes an element key in s.

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

Includes all elements from other into s.

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

excludes key from the set s.

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

Excludes all elements from other from s.

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

returns true if s does not contain key, otherwise key is removed from s and false is returned.

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

returns true if s contains key, otherwise key is included in s and false is returned.

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

creates a new int set that is empty.

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

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

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

copies src to dest. dest does not need to be initialized by initIntSet.

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

Returns the union of the sets s1 and s2.

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

Returns the intersection of the sets s1 and s2.

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

Returns the difference of the sets s1 and s2.

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

Returns the symmetric difference of the sets s1 and s2.

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

Alias for union(s1, s2).

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

Alias for intersection(s1, s2).

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

Alias for difference(s1, s2).

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

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

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

Returns the number of keys in s.

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

alias for len() <#len> _.

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

Returns true iff s1 is subset of s2.

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

Returns true iff s1 is proper subset of s2.

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

Returns true if both s and t have the same members and set size.

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

The $ operator for int sets.

proc empty(s: IntSet): bool {...}{.inline, deprecated, raises: [], tags: [].}

returns true if s is empty. This is safe to call even before the set has been initialized with initIntSet. Note this never worked reliably and so is deprecated.

Iterators

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

iterates over any included element of s.