алгоритм

Этот модуль реализует некоторые общие общие алгоритмы.

Основное использование

import algorithm

type People = tuple
  year: int
  name: string

var a: seq[People]

a.add((2000, "John"))
a.add((2005, "Marie"))
a.add((2010, "Jane"))

# Sorting with default system.cmp
a.sort()
assert a == @[(year: 2000, name: "John"), (year: 2005, name: "Marie"),
              (year: 2010, name: "Jane")]

proc myCmp(x, y: People): int =
  if x.name < y.name: -1
  elif x.name == y.name: 0
  else: 1

# Sorting with custom proc
a.sort(myCmp)
assert a == @[(year: 2010, name: "Jane"), (year: 2000, name: "John"),
              (year: 2005, name: "Marie")]

См. также

модуль sequtils для работы со встроенным типом seq
модуль tables для сортировки таблиц

Типы

SortOrder = enum Descending, Ascending: Исходный код Изменить

Процедуры

proc `*`(x: int; order: SortOrder): int {...}{.inline, raises: [], tags: [].}

Переворачивает x если order == Descending. Если order == Ascending, то возвращается x.

x должен быть результатом компаратора, т.е.

< 0 для меньше,
== 0 для равно,
> 0 для больше.

Пример:

assert `*`(-123, Descending) == 123
assert `*`(123, Descending) == -123
assert `*`(-123, Ascending) == -123
assert `*`(123, Ascending) == 123

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

proc fill[T](a: var openArray[T]; first, last: Natural; value: T)

Заполняет срез a[first..last] значением value.

Если передан некорректный диапазон, выбрасывается исключение IndexDefect.

Пример:

var a: array[6, int]
a.fill(1, 3, 9)
assert a == [0, 9, 9, 9, 0, 0]
a.fill(3, 5, 7)
assert a == [0, 9, 9, 7, 7, 7]
doAssertRaises(IndexDefect, a.fill(1, 7, 9))

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

proc fill[T](a: var openArray[T]; value: T)

Заполняет контейнер a значением value.

Пример:

var a: array[6, int]
a.fill(9)
assert a == [9, 9, 9, 9, 9, 9]
a.fill(4)
assert a == [4, 4, 4, 4, 4, 4]

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

proc reverse[T](a: var openArray[T]; first, last: Natural)

Обращает срез a[first..last].

Если передан некорректный диапазон, выбрасывается исключение IndexDefect.

См. также:

процедура reversed обращает срез и возвращает seq[T]
процедура reversed обращает и возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5, 6]
a.reverse(1, 3)
assert a == [1, 4, 3, 2, 5, 6]
a.reverse(1, 3)
assert a == [1, 2, 3, 4, 5, 6]
doAssertRaises(IndexDefect, a.reverse(1, 7))

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

proc reverse[T](a: var openArray[T])

Обращает содержимое контейнера a.

См. также:

процедура reversed обращает срез и возвращает seq[T]
процедура reversed обращает и возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5, 6]
a.reverse()
assert a == [6, 5, 4, 3, 2, 1]
a.reverse()
assert a == [1, 2, 3, 4, 5, 6]

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

proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]

Возвращает обратный срез a[first..last].

Если передан некорректный диапазон, выбрасывается исключение IndexDefect.

См. также:

процедура reverse обращает срез
процедура reverse

Пример:

let
  a = [1, 2, 3, 4, 5, 6]
  b = a.reversed(1, 3)
assert b == @[4, 3, 2]

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

proc reversed[T](a: openArray[T]): seq[T]

Возвращает обратный контейнер a.

См. также:

процедура reverse обращает срез
процедура reverse

Пример:

let
  a = [1, 2, 3, 4, 5, 6]
  b = reversed(a)
assert b == @[6, 5, 4, 3, 2, 1]

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

proc binarySearch[T, K](a: openArray[T]; key: K; cmp: proc (x: T; y: K): int {...}{.closure.}): int

Бинарный поиск key в a. Возвращает -1, если не найдено.

cmp — функция компаратора, ожидаемые значения возврата такие же, как у system.cmp.

Пример:

assert binarySearch(["a", "b", "c", "d"], "d", system.cmp[string]) == 3
assert binarySearch(["a", "b", "d", "c"], "d", system.cmp[string]) == 2

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

proc binarySearch[T](a: openArray[T]; key: T): int

Бинарный поиск key в a. Возвращает -1, если не найдено.

Пример:

assert binarySearch([0, 1, 2, 3, 4], 4) == 4
assert binarySearch([0, 1, 4, 2, 3], 4) == 2

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

proc lowerBound[T, K](a: openArray[T]; key: K; cmp: proc (x: T; k: K): int {...}{.closure.}): int

Возвращает позицию первого элемента в a больше key, или последнего, если такого элемента нет. Другими словами, если у вас отсортированная последовательность и вы вызываете insert(thing, elm, lowerBound(thing, elm)), последовательность останется отсортированной.

Если передан некорректный диапазон, выбрасывается исключение IndexDefect.

Версия использует cmp для сравнения элементов. Ожидаемые значения возврата такие же, как у system.cmp.

См. также:

процедура upperBound отсортировано по cmp в указанном порядке
процедура upperBound

Пример:

var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
assert arr.lowerBound(3, system.cmp[int]) == 2
assert arr.lowerBound(4, system.cmp[int]) == 3
assert arr.lowerBound(5, system.cmp[int]) == 3
arr.insert(4, arr.lowerBound(4, system.cmp[int]))
assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

proc lowerBound[T](a: openArray[T]; key: T): int

Версия использует функцию сравнения по умолчанию cmp.

См. также:

процедура upperBound отсортировано по cmp в указанном порядке
процедура upperBound

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

proc upperBound[T, K](a: openArray[T]; key: K; cmp: proc (x: T; k: K): int {...}{.closure.}): int

Возвращает позицию первого элемента в a не меньше (т.е. больше или равно) key, или последнего, если такого элемента нет. Другими словами, если у вас отсортированная последовательность и вы вызываете insert(thing, elm, upperBound(thing, elm)), последовательность останется отсортированной.

Если передан некорректный диапазон, выбрасывается исключение IndexDefect.

Версия использует cmp для сравнения элементов. Ожидаемые значения возврата такие же, как у system.cmp.

См. также:

процедура lowerBound отсортировано по cmp в указанном порядке
процедура lowerBound

Пример:

var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
assert arr.upperBound(2, system.cmp[int]) == 2
assert arr.upperBound(3, system.cmp[int]) == 3
assert arr.upperBound(4, system.cmp[int]) == 3
arr.insert(4, arr.upperBound(3, system.cmp[int]))
assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

proc upperBound[T](a: openArray[T]; key: T): int

Сокращенная версия sort, использующая system.cmp[T] в качестве функции сравнения.

См. также:

функция sort
процедура sorted отсортировано по cmp в указанном порядке
процедура sorted
шаблон sortedByIt

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

proc sorted[T](a: openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending): seq[T]

Возвращает a отсортированную по cmp в указанном order.

См. также:

функция sort
процедура sort
шаблон sortedByIt

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = sorted(a, system.cmp[int])
  c = sorted(a, system.cmp[int], Descending)
  d = sorted(["adam", "dande", "brian", "cat"], system.cmp[string])
assert b == @[1, 2, 3, 4, 5]
assert c == @[5, 4, 3, 2, 1]
assert d == @["adam", "brian", "cat", "dande"]

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

proc sorted[T](a: openArray[T]; order = SortOrder.Ascending): seq[T]

Сокращенная версия sorted, использующая system.cmp[T] в качестве функции сравнения.

См. также:

функция sort
процедура sort
шаблон sortedByIt

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = sorted(a)
  c = sorted(a, Descending)
  d = sorted(["adam", "dande", "brian", "cat"])
assert b == @[1, 2, 3, 4, 5]
assert c == @[5, 4, 3, 2, 1]
assert d == @["adam", "brian", "cat", "dande"]

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

proc isSorted[T](a: openArray[T]; order = SortOrder.Ascending): bool

Сокращённая версия isSorted, которая использует system.cmp[T] в качестве функции сравнения.

См. также:

Функция isSorted

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = [1, 2, 3, 4, 5]
  c = [5, 4, 3, 2, 1]
  d = ["adam", "brian", "cat", "dande"]
  e = ["adam", "dande", "brian", "cat"]
assert isSorted(a) == false
assert isSorted(b) == true
assert isSorted(c) == false
assert isSorted(c, Descending) == true
assert isSorted(d) == true
assert isSorted(e) == false

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

proc product[T](x: openArray[seq[T]]): seq[seq[T]]

Создаёт декартово произведение массива. Внимание: сложность может взорваться.

Пример:

assert product(@[@[1], @[2]]) == @[@[1, 2]]
assert product(@[@["A", "K"], @["Q"]]) == @[@["K", "Q"], @["A", "Q"]]

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

proc nextPermutation[T](x: var openArray[T]): bool {...}{.discardable.}

Вычисляет следующую лексикографическую перестановку, напрямую изменяя x. Результат — произошло ли перестановки, или же мы достигли последней упорядоченной перестановки.

Если вы начинаете с неупорядоченного массива/последовательности, повторяющиеся перестановки не дадут вам все перестановки, а остановятся на последней.

См. также:

Функция prevPermutation

Пример:

var v = @[0, 1, 2, 3]
assert v.nextPermutation() == true
assert v == @[0, 1, 3, 2]
assert v.nextPermutation() == true
assert v == @[0, 2, 1, 3]
assert v.prevPermutation() == true
assert v == @[0, 1, 3, 2]
v = @[3, 2, 1, 0]
assert v.nextPermutation() == false
assert v == @[3, 2, 1, 0]

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

proc prevPermutation[T](x: var openArray[T]): bool {...}{.discardable.}

Вычисляет предыдущую лексикографическую перестановку, напрямую изменяя x. Результат — произошло ли перестановки, или же мы достигли первой упорядоченной перестановки.

См. также:

Функция nextPermutation

Пример:

var v = @[0, 1, 2, 3]
assert v.prevPermutation() == false
assert v == @[0, 1, 2, 3]
assert v.nextPermutation() == true
assert v == @[0, 1, 3, 2]
assert v.prevPermutation() == true
assert v == @[0, 1, 2, 3]

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

proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int {...}{. discardable.}

Выполняет циклический сдвиг влево на диапазон элементов. Если вы хотите сдвинуть вправо, используйте отрицательное значение dist. Конкретно, rotateLeft сдвигает элементы в slice на dist позиции.

Элемент с индексом slice.a + dist будет на индексе slice.a.
Элемент с индексом slice.b будет на индексе slice.a + dist -1.
Элемент с индексом slice.a будет на индексе slice.b + 1 - dist.
Элемент с индексом slice.a + dist - 1 будет на индексе slice.b.

Элементы за пределами slice останутся без изменений. Время выполнения пропорционально slice.b - slice.a + 1. Если передан неверный диапазон (HSlice), возникает исключение IndexDefect.

slice: Индексы диапазона элементов, которые необходимо сдвинуть.
dist: Расстояние в количестве элементов, на которое должны быть сдвинуты данные. Может быть отрицательным, может быть любым числом.

См. также:

Функция rotateLeft для версии, которая сдвигает весь контейнер
Функция rotatedLeft для версии, которая возвращает seq[T]

Пример:

var a = [0, 1, 2, 3, 4, 5]
a.rotateLeft(1 .. 4, 3)
assert a == [0, 4, 1, 2, 3, 5]
a.rotateLeft(1 .. 4, 3)
assert a == [0, 3, 4, 1, 2, 5]
a.rotateLeft(1 .. 4, -3)
assert a == [0, 4, 1, 2, 3, 5]
doAssertRaises(IndexDefect, a.rotateLeft(1 .. 7, 2))

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

proc rotateLeft[T](arg: var openArray[T]; dist: int): int {...}{.discardable.}

Значения по умолчанию для среза, чтобы эта процедура работала со всем arg, а не только с его частью.

См. также:

Функция rotateLeft для версии, которая сдвигает диапазон
Функция rotatedLeft для версии, которая возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5]
a.rotateLeft(2)
assert a == [3, 4, 5, 1, 2]
a.rotateLeft(4)
assert a == [2, 3, 4, 5, 1]
a.rotateLeft(-6)
assert a == [1, 2, 3, 4, 5]

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

proc rotatedLeft[T](arg: openArray[T]; slice: HSlice[int, int]; dist: int): seq[ T]

То же, что и rotateLeft, только с тем отличием, что не изменяет аргумент. Создаёт новый seq вместо этого.

Элементы за пределами slice останутся без изменений. Если передан неверный диапазон (HSlice), возникает исключение IndexDefect.

slice: Индексы диапазона элементов, которые необходимо сдвинуть.
dist: Расстояние в количестве элементов, на которое должны быть сдвинуты данные. Может быть отрицательным, может быть любым числом.

См. также:

Функция rotateLeft для верси в месте этого вызова
Функция rotatedLeft для версии, которая сдвигает весь контейнер

Пример:

var a = @[1, 2, 3, 4, 5]
a = rotatedLeft(a, 1 .. 4, 3)
assert a == @[1, 5, 2, 3, 4]
a = rotatedLeft(a, 1 .. 3, 2)
assert a == @[1, 3, 5, 2, 4]
a = rotatedLeft(a, 1 .. 3, -2)
assert a == @[1, 5, 2, 3, 4]

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

proc rotatedLeft[T](arg: openArray[T]; dist: int): seq[T]

То же, что и rotateLeft, только с тем отличием, что не изменяет аргумент. Создаёт новый seq вместо этого.

См. также:

Функция rotateLeft для верси в месте этого вызова
Функция rotatedLeft для версии, которая сдвигает диапазон

Пример:

var a = @[1, 2, 3, 4, 5]
a = rotatedLeft(a, 2)
assert a == @[3, 4, 5, 1, 2]
a = rotatedLeft(a, 4)
assert a == @[2, 3, 4, 5, 1]
a = rotatedLeft(a, -6)
assert a == @[1, 2, 3, 4, 5]

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

Функции

func sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending)

Стандартная функция сортировки Nim (реализация слиянием). Сортировка гарантированно стабильна, худший случай гарантированно O(n log n).

Текущая реализация использует итеративную сортировку слиянием. Использует временную последовательность длиной a.len div 2. Если вы не хотите предоставлять свою собственную cmp, вы можете использовать system.cmp или вызвать перегруженную версию sort, которая использует system.cmp.

sort(myIntArray, system.cmp[int])
# do not use cmp[string] here as we want to use the specialized
# overload:
sort(myStrArray, system.cmp)

Вы можете встраивать функции сравнения adhoc с помощью нотации do. Пример:

people.sort do (x, y: Person) -> int:
  result = cmp(x.surname, y.surname)
  if result == 0:
    result = cmp(x.name, y.name)

См. также:

Функция sort
Функция sorted сортировка по cmp в указанном порядке
Функция sorted
Шаблон sortedByIt

Пример:

var d = ["boo", "fo", "barr", "qux"]
proc myCmp(x, y: string): int =
  if x.len() > y.len() or x.len() == y.len(): 1
  else: -1
sort(d, myCmp)
assert d == ["fo", "qux", "boo", "barr"]

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

func isSorted[T](a: openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending): bool

Проверяет, отсортирован ли a в order с использованием cmp для сравнения. Параметры идентичны sort. Требует O(n) времени.

См. также:

Функция isSorted

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = [1, 2, 3, 4, 5]
  c = [5, 4, 3, 2, 1]
  d = ["adam", "brian", "cat", "dande"]
  e = ["adam", "dande", "brian", "cat"]
assert isSorted(a) == false
assert isSorted(b) == true
assert isSorted(c) == false
assert isSorted(c, Descending) == true
assert isSorted(d) == true
assert isSorted(e) == false

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

Шаблоны

template sortedByIt(seq1, op: untyped): untyped

Удобный шаблон вокруг функции sorted для сокращения набора символов.

Шаблон вставляет переменную it, которую вы можете использовать непосредственно в выражении.

Поскольку базовый cmp() определён для кортежей, вы можете выполнить вложенную сортировку.

См. также:

Функция sort
Функция sort
Функция sorted сортировка по cmp в указанном порядке
Функция sorted

Пример:

type Person = tuple[name: string, age: int]
var
  p1: Person = (name: "p1", age: 60)
  p2: Person = (name: "p2", age: 20)
  p3: Person = (name: "p3", age: 30)
  p4: Person = (name: "p4", age: 30)
  people = @[p1, p2, p4, p3]

assert people.sortedByIt(it.name) == @[(name: "p1", age: 60), (name: "p2",
    age: 20), (name: "p3", age: 30), (name: "p4", age: 30)]
# Nested sort
assert people.sortedByIt((it.age, it.name)) == @[(name: "p2", age: 20),
   (name: "p3", age: 30), (name: "p4", age: 30), (name: "p1", age: 60)]

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