std/packedsets

    Dark Mode
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

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:

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:

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:

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:

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:

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:

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:

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:

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

Made with Nim. Generated: 2021-10-19 01:13:16 UTC