intsets

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.

関連:

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.   ソース 編集

プロシージャ

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

用例:

var a = initIntSet()
assert len(a) == 0
  ソース 編集
proc contains(s: IntSet; key: int): bool {...}{.raises: [], tags: [].}

Returns true if key is in s.

This allows the usage of in operator.

用例:

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
  ソース 編集
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.

関連:

用例:

var a = initIntSet()
a.incl(3)
a.incl(3)
assert len(a) == 1
  ソース 編集
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.

関連:

用例:

var
  a = initIntSet()
  b = initIntSet()
a.incl(1)
b.incl(5)
a.incl(b)
assert len(a) == 2
assert 5 in a
  ソース 編集
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.

関連:

用例:

var a = initIntSet()
assert a.containsOrIncl(3) == false
assert a.containsOrIncl(3) == true
assert a.containsOrIncl(4) == false
  ソース 編集
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.

関連:

用例:

var a = initIntSet()
a.incl(3)
a.excl(3)
a.excl(3)
a.excl(99)
assert len(a) == 0
  ソース 編集
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.

関連:

用例:

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
  ソース 編集
proc len(s: IntSet): int {...}{.inline, raises: [], tags: [].}
Returns the number of elements in s.   ソース 編集
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.

関連:

用例:

var a = initIntSet()
a.incl(5)
assert a.missingOrExcl(5) == false
assert a.missingOrExcl(5) == true
  ソース 編集
proc clear(result: var IntSet) {...}{.raises: [], tags: [].}
Clears the IntSet back to an empty state.

用例:

var a = initIntSet()
a.incl(5)
a.incl(7)
clear(a)
assert len(a) == 0
  ソース 編集
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.

用例:

var
  a = initIntSet()
  b = initIntSet()
b.incl(5)
b.incl(7)
a.assign(b)
assert len(a) == 2
  ソース 編集
proc union(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

Returns the union of the sets s1 and s2.

The same as s1 + s2.

用例:

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}
  ソース 編集
proc intersection(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

Returns the intersection of the sets s1 and s2.

The same as s1 * s2.

用例:

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}
  ソース 編集
proc difference(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}

Returns the difference of the sets s1 and s2.

The same as s1 - s2.

用例:

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}
  ソース 編集
proc symmetricDifference(s1, s2: IntSet): IntSet {...}{.raises: [], tags: [].}
Returns the symmetric difference of the sets s1 and s2.

用例:

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}
  ソース 編集
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 if the sets s1 and s2 have no items in common.

用例:

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
  ソース 編集
proc card(s: IntSet): int {...}{.inline, raises: [], tags: [].}
Alias for len().   ソース 編集
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.

用例:

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))
  ソース 編集
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.

用例:

var
  a = initIntSet()
  b = initIntSet()
a.incl(1)
b.incl(1)
b.incl(2)
assert a < b
a.incl(2)
assert(not (a < b))
  ソース 編集
proc `==`(s1, s2: IntSet): bool {...}{.raises: [], tags: [].}
Returns true if both s1 and s2 have the same elements and set size.   ソース 編集
proc `$`(s: IntSet): string {...}{.raises: [], tags: [].}

The $ operator for int sets.

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

  ソース 編集

イテレータ

iterator items(s: IntSet): int {...}{.inline, raises: [], tags: [].}
Iterates over any included element of s.   ソース 編集