std/packedsets

Модуль packedsets реализует эффективный Ordinal набор, реализованный как разреженный битовый набор.

Поддерживает любой тип Ordinal.

См. также

• модуль sets для более общих наборов хеширования

Импорты

since, hashes

Типы

PackedSet[A] = object

Эффективный набор типов Ordinal, реализованный как разреженный битовый набор. Исходный код Редактировать

Процедуры

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

Преобразует s в строку.

Пример:

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

Исходный код Редактировать

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

Псевдоним для intersection(s1, s2). Исходный код Редактировать

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

Псевдоним для union(s1, s2). Исходный код Редактировать

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

Псевдоним для difference(s1, s2). Исходный код Редактировать

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

Возвращает true, если s1 является собственным подмножеством s2.

Строгое или собственное подмножество s1 содержит все свои элементы в s2, но s2 содержит больше элементов, чем s1.

Пример:

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

Исходный код Редактировать

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

Возвращает true, если s1 является подмножеством s2.

Подмножество s1 содержит все свои элементы в s2, но s2 не обязательно содержит больше элементов, чем s1. То есть, s1 может быть равно s2.

Пример:

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

Исходный код Редактировать

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

Возвращает true, если s1 и s2 имеют одинаковые элементы и размер набора.

Пример:

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

Исходный код Редактировать

proc `=copy`[A](dest: var PackedSet[A]; src: PackedSet[A])

Копирует src в dest. dest не нужно инициализировать процедурой initPackedSet. Исходный код Редактировать

proc assign[A](dest: var PackedSet[A]; src: PackedSet[A]) {.inline, ...deprecated.}

Устарело

Копирует src в dest. dest не нужно инициализировать процедурой initPackedSet.

Пример:

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

Исходный код Редактировать

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

Псевдоним для len().

Card означает мощность множества.

Исходный код Редактировать

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

Очищает PackedSet[A] до пустого состояния.

Пример:

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

Исходный код Редактировать

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

Возвращает true, если key содержится в s.

Это позволяет использовать оператор in.

Пример:

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

Исходный код Редактировать

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

Включает key в множество s и указывает, был ли key уже в s.

Разница по сравнению с процедурой incl заключается в том, что эта процедура возвращает true, если s уже содержал key. Процедура вернет false, если key был добавлен в s как новое значение во время этого вызова.

См. также:

• процедура incl для включения элемента
• процедура missingOrExcl

Пример:

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

Исходный код Редактировать

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

Возвращает разность множеств s1 и s2.

То же самое, что s1 - s2.

Пример:

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

Исходный код Редактировать

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

Возвращает true, если множества s1 и s2 не имеют общих элементов.

Пример:

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

Исходный код Редактировать

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

Исключает key из множества s.

Ничего не делает, если key не найден в s.

См. также:

• процедура incl для включения элемента
• процедура excl для исключения множества
• процедура missingOrExcl

Пример:

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

Исходный код Редактировать

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

Исключает все элементы из other из s.

Это ин-место версия s - other.

См. также:

• процедура incl для включения множества
• процедура excl для исключения элемента
• процедура missingOrExcl

Пример:

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

Исходный код Редактировать

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

Включает элемент key в s.

Это ничего не делает, если key уже содержится в s.

См. также:

• исключающую процедуру для исключения элемента
• процедуру incl для включения множества
• процедуру containsOrIncl

Пример:

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

Исходный код Изменить

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

Включает все элементы из other в s.

Это версия для работы "на месте" процедуры s + other.

См. также:

• процедуру excl для исключения множества
• процедуру incl для включения элемента
• процедуру containsOrIncl

Пример:

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

Исходный код Изменить

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

Возвращает пустое PackedSet[A]. A должен быть Ordinal.

См. также:

• процедуру toPackedSet

Пример:

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

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

Исходный код Изменить

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

Возвращает пересечение множеств s1 и s2.

То же самое, что и s1 * s2.

Пример:

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

Исходный код Изменить

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

Возвращает true, если x пусто, иначе false.

Пример:

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

Исходный код Изменить

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

Возвращает количество элементов в s.

Пример:

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

Исходный код Изменить

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

Исключает key из множества s и сообщает, был ли key отсутствовал в s.

Различие с процедурой excl заключается в том, что эта процедура возвращает true, если key отсутствовал в s . Процедура вернёт false, если key был в s и был удалён в ходе этого вызова.

См. также:

• процедуру excl для исключения элемента
• процедуру excl для исключения множества
• процедуру containsOrIncl

Пример:

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

Исходный код Изменить

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

Возвращает симметрическую разность множеств s1 и s2.

Пример:

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

Исходный код Изменить

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

Создаёт новое PackedSet[A] содержащее элементы x.

Дубликаты удаляются.

См. также:

• процедуру initPackedSet

Пример:

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

Исходный код Изменить

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

Возвращает объединение множеств s1 и s2.

То же самое, что и s1 + s2.

Пример:

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

Исходный код Изменить

Итераторы

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

Перебирает все включенные элементы s . Исходный код Изменить