Spec-Zone.ru › Nim 1

critbits

Этот модуль реализует дерево крит-битов, которое является эффективным контейнером для упорядоченного набора строк или для упорядоченного отображения строк. Основано на отличной статье Адама Лэнли. (Дерево крит-битов — это разновидность дерева префиксных совпадений или дерева Патриции.)

Пример:

static:
  block:
    var critbitAsSet: CritBitTree[void]
    doAssert critbitAsSet.len == 0
    incl critbitAsSet, "kitten"
    doAssert critbitAsSet.len == 1
    incl critbitAsSet, "puppy"
    doAssert critbitAsSet.len == 2
    incl critbitAsSet, "kitten"
    doAssert critbitAsSet.len == 2
    incl critbitAsSet, ""
    doAssert critbitAsSet.len == 3
block:
  var critbitAsDict: CritBitTree[int]
  critbitAsDict["key"] = 42
  doAssert critbitAsDict["key"] == 42
  critbitAsDict["key"] = 0
  doAssert critbitAsDict["key"] == 0
  critbitAsDict["key"] = -int.high
  doAssert critbitAsDict["key"] == -int.high
  critbitAsDict["key"] = int.high
  doAssert critbitAsDict["key"] == int.high

Импорты

since

Типы

CritBitTree[T] = object
  root: Node[T]
  count: int
Дерево крит-битов может использоваться как отображение из строк в какой-то тип T или как набор строк, если T является пустым. Исходный код Изменить

Процедуры

proc excl[T](c: var CritBitTree[T]; key: string)

Удаляет key (и его связанное значение) из набора c. Если key не существует, ничего не происходит.

См. также:

  • процедура incl
  • процедура incl

Пример:

var c: CritBitTree[void]
incl(c, "key")
excl(c, "key")
doAssert not c.contains("key")
Исходный код Изменить 
proc missingOrExcl[T](c: var CritBitTree[T]; key: string): bool

Возвращает true, если c не содержит заданный key. Если ключ существует, выполняется c.excl(ключ).

См. также:

  • процедура excl
  • процедура containsOrIncl
  • процедура containsOrIncl

Пример:

block:
  var c: CritBitTree[void]
  doAssert c.missingOrExcl("key")
block:
  var c: CritBitTree[void]
  incl(c, "key")
  doAssert not c.missingOrExcl("key")
  doAssert not c.contains("key")
Исходный код Изменить 
proc containsOrIncl[T](c: var CritBitTree[T]; key: string; val: T): bool

Возвращает true, если c содержит заданный key. Если ключ не существует, выполняется c[key] = val.

См. также:

  • процедура incl
  • процедура incl
  • процедура containsOrIncl
  • процедура missingOrExcl

Пример:

block:
  var c: CritBitTree[int]
  doAssert not c.containsOrIncl("key", 42)
  doAssert c.contains("key")
block:
  var c: CritBitTree[int]
  incl(c, "key", 21)
  doAssert c.containsOrIncl("key", 42)
  doAssert c["key"] == 21
Исходный код Изменить 
proc containsOrIncl(c: var CritBitTree[void]; key: string): bool {...}{.raises: [],
    tags: [].}

Возвращает true, если c содержит заданный key. Если ключ не существует, он вставляется в c.

См. также:

  • процедура incl
  • процедура incl
  • процедура containsOrIncl
  • процедура missingOrExcl

Пример:

block:
  var c: CritBitTree[void]
  doAssert not c.containsOrIncl("key")
  doAssert c.contains("key")
block:
  var c: CritBitTree[void]
  incl(c, "key")
  doAssert c.containsOrIncl("key")
Исходный код Изменить 
proc inc(c: var CritBitTree[int]; key: string; val: int = 1) {...}{.raises: [],
    tags: [].}
Увеличивает c[key] на val.

Пример:

var c: CritBitTree[int]
c["key"] = 1
inc(c, "key")
doAssert c["key"] == 2
Исходный код Изменить 
proc incl(c: var CritBitTree[void]; key: string) {...}{.raises: [], tags: [].}
Включает key в c.

См. также:

  • процедура excl
  • процедура incl

Пример:

var c: CritBitTree[void]
incl(c, "key")
doAssert c.hasKey("key")
Исходный код Изменить 
proc incl[T](c: var CritBitTree[T]; key: string; val: T)
Вставляет key со значением val в c.

См. также:

  • процедура excl
  • процедура incl

Пример:

var c: CritBitTree[int]
incl(c, "key", 42)
doAssert c["key"] == 42
Исходный код Изменить 
proc `[]=`[T](c: var CritBitTree[T]; key: string; val: T)
Размещает пару (ключ, значение) в t.

См. также:

  • процедура []
  • процедура []

Пример:

var c: CritBitTree[int]
c["key"] = 42
doAssert c["key"] == 42
Исходный код Изменить

Функции

func len[T](c: CritBitTree[T]): int {...}{.inline.}
Возвращает количество элементов в c за O(1).

Пример:

var c: CritBitTree[void]
incl(c, "key1")
incl(c, "key2")
doAssert c.len == 2
Исходный код Изменить 
func contains[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
Возвращает true, если c содержит заданный key.

Пример:

var c: CritBitTree[void]
incl(c, "key")
doAssert c.contains("key")
Исходный код Изменить 
func hasKey[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
Псевдоним для contains. Исходный код Изменить 
func `[]`[T](c: CritBitTree[T]; key: string): T {...}{.inline.}

Получает значение по c[key]. Если key не находится в t, генерируется исключение KeyError. Можно проверить существование ключа с помощью hasKey.

См. также:

  • процедура []
  • процедура []=
Исходный код Изменить 
func `[]`[T](c: var CritBitTree[T]; key: string): var T {...}{.inline.}

Получает значение по c[key]. Значение может быть изменено. Если key не находится в t, генерируется исключение KeyError.

См. также:

  • процедура []
  • процедура []=
Исходный код Изменить 
func `$`[T](c: CritBitTree[T]): string
Преобразует c в строковое представление. Примеры вывода: {keyA: value, keyB: value}, {:}. Если T является пустым, вывод выглядит как: {keyA, keyB}, {}. Исходный код Изменить 
func commonPrefixLen[T](c: CritBitTree[T]): int {...}{.inline.}
Возвращает длину наибольшего общего префикса всех ключей c. Если c пуста, возвращает 0.

Пример:

var c: CritBitTree[void]
doAssert c.commonPrefixLen == 0
incl(c, "key1")
doAssert c.commonPrefixLen == 4
incl(c, "key2")
doAssert c.commonPrefixLen == 3
Исходный код Изменить 
func toCritBitTree[A, B](pairs: openArray[(A, B)]): CritBitTree[A]
Создаёт новый CritBitTree, который содержит заданный pairs.

Пример:

doAssert {"a": "0", "b": "1", "c": "2"}.toCritBitTree is CritBitTree[string]
Исходный код Изменить 
func toCritBitTree[T](items: openArray[T]): CritBitTree[void]
Создаёт новый CritBitTree, который содержит заданный items.

Пример:

doAssert ["a", "b", "c"].toCritBitTree is CritBitTree[void]
Исходный код Изменить

Итераторы

iterator keys[T](c: CritBitTree[T]): string
Возвращает все ключи в лексикографическом порядке.

Пример:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var keys: seq[string]
for key in c.keys:
  keys.add(key)
doAssert keys == @["key1", "key2"]
Исходный код Редактировать 
iterator values[T](c: CritBitTree[T]): T
Возвращает все значения c в лексикографическом порядке соответствующих ключей.

Пример:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var vals: seq[int]
for val in c.values:
  vals.add(val)
doAssert vals == @[1, 2]
Исходный код Редактировать 
iterator mvalues[T](c: var CritBitTree[T]): var T

Возвращает все значения c в лексикографическом порядке соответствующих ключей. Значения могут быть изменены.

См. также:

  • итератор значений
Исходный код Редактировать 
iterator items[T](c: CritBitTree[T]): string
Возвращает все ключи в лексикографическом порядке.

Пример:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var keys: seq[string]
for key in c.items:
  keys.add(key)
doAssert keys == @["key1", "key2"]
Исходный код Редактировать 
iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]
Возвращает все пары (ключ, значение) для c.

Пример:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var ps: seq[tuple[key: string, val: int]]
for p in c.pairs:
  ps.add(p)
doAssert ps == @[(key: "key1", val: 1), (key: "key2", val: 2)]
Исходный код Редактировать 
iterator mpairs[T](c: var CritBitTree[T]): tuple[key: string, val: var T]

Возвращает все пары (ключ, значение) для c. Возвращаемые значения могут быть изменены.

См. также:

  • итератор пар
Исходный код Редактировать 
iterator itemsWithPrefix[T](c: CritBitTree[T]; prefix: string;
                            longestMatch = false): string
Возвращает все ключи, начинающиеся с prefix. Если longestMatch истинно, возвращается самое длинное совпадение, не обязательно полное.

Пример:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var keys: seq[string]
for key in c.itemsWithPrefix("key"):
  keys.add(key)
doAssert keys == @["key1", "key2"]
Исходный код Редактировать 
iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string;
                           longestMatch = false): string
Возвращает все ключи, начинающиеся с prefix.

Пример:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var keys: seq[string]
for key in c.keysWithPrefix("key"):
  keys.add(key)
doAssert keys == @["key1", "key2"]
Исходный код Редактировать 
iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string;
                             longestMatch = false): T
Возвращает все значения c, начинающиеся с prefix соответствующих ключей.

Пример:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var vals: seq[int]
for val in c.valuesWithPrefix("key"):
  vals.add(val)
doAssert vals == @[42, 43]
Исходный код Редактировать 
iterator mvaluesWithPrefix[T](c: var CritBitTree[T]; prefix: string;
                              longestMatch = false): var T

Возвращает все значения c, начинающиеся с prefix соответствующих ключей. Значения могут быть изменены.

См. также:

  • итератор значений с префиксом
Исходный код Редактировать 
iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string;
                            longestMatch = false): tuple[key: string, val: T]
Возвращает все пары (ключ, значение) для c, начинающиеся с prefix.

Пример:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var ps: seq[tuple[key: string, val: int]]
for p in c.pairsWithPrefix("key"):
  ps.add(p)
doAssert ps == @[(key: "key1", val: 42), (key: "key2", val: 43)]
Исходный код Редактировать 
iterator mpairsWithPrefix[T](c: var CritBitTree[T]; prefix: string;
                             longestMatch = false): tuple[key: string,
    val: var T]

Возвращает все пары (ключ, значение) для c, начинающиеся с prefix. Возвращаемые значения могут быть изменены.

См. также:

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

© 2006–2021 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/critbits.html

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API