intsets

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

Примечание: В настоящее время оператор присваивания = для IntSet выполняет довольно бессмысленную поверхностную копию. Поскольку в Nim в настоящее время нельзя перегружать оператор присваивания, используйте процедуру assign для получения глубокой копии.

См. также:

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

Импорты

since, hashes, sequtils, algorithm

Типы

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

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

Процедуры

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

Возвращает пустой IntSet.

См. также:

• процедуру toIntSet

Пример:

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

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

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

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

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

Пример:

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: [].}

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

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

См. также:

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

Пример:

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

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

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

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

Это инлайсовая версия s + other.

См. также:

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

Пример:

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

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

proc toIntSet(x: openArray[int]): IntSet {...}{.raises: [], tags: [].}

Создаёт новый IntSet, содержащий элементы x.

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

См. также:

• процедуру initIntSet

Пример:

var
  a = toIntSet([5, 6, 7])
  b = toIntSet(@[1, 8, 8, 8])
assert len(a) == 3
assert len(b) == 2

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

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

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

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

См. также:

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

Пример:

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: [].}

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

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

См. также:

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

Пример:

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: [].}

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

Это инлайсовая версия s - other.

См. также:

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

Пример:

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: [].}

Возвращает количество элементов в s. Исходный код Редактировать

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

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

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

См. также:

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

Пример:

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

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

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

Очищает IntSet, возвращая его в пустое состояние.

Пример:

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: [].}

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

Пример:

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: [].}

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

То же, что и 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: [].}

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

То же, что и 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: [].}

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

То же, что и 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: [].}

Возвращает симметрическую разность множеств 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 symmetricDifference(a, b).len == 4
## {1, 2, 4, 5}

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

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

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

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

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

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

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

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

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

Пример:

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: [].}

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

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

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

Подмножество s1 содержит все свои элементы в s2, и s2 не обязательно содержит больше элементов, чем s1. То есть, s1 может быть равно 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: [].}

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

Строгое или собственное подмножество s1 содержит все свои элементы в s2, но s2 содержит больше элементов, чем 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: [].}

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

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

Оператор $ для множеств целых чисел.

Преобразует множество s в строку, в основном для целей протоколирования и вывода на экран.

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

Итераторы

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

Итерируется по любым включённым элементам s. Исходный код Редактировать