Spec-Zone.ru › Nim

std/critbits

SourceEdit

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

Пример:

import std/critbits
from std/sequtils import toSeq

var critbitAsSet: CritBitTree[void] = ["kitten", "puppy"].toCritBitTree
doAssert critbitAsSet.len == 2
critbitAsSet.incl("")
doAssert "" in critbitAsSet
critbitAsSet.excl("")
doAssert "" notin critbitAsSet
doAssert toSeq(critbitAsSet.items) == @["kitten", "puppy"]
let same = ["puppy", "kitten", "puppy"].toCritBitTree
doAssert toSeq(same.keys) == toSeq(critbitAsSet.keys)

var critbitAsDict: CritBitTree[int] = {"key1": 42}.toCritBitTree
doAssert critbitAsDict.len == 1
critbitAsDict["key2"] = 0
doAssert "key2" in critbitAsDict
doAssert critbitAsDict["key2"] == 0
critbitAsDict.excl("key1")
doAssert "key1" notin critbitAsDict
doAssert toSeq(critbitAsDict.pairs) == @[("key2", 0)]

Импорты

since

Типы

CritBitTree[T] = object
Дерево критических битов может использоваться либо как отображение строк на некоторый тип T , либо как набор строк, если T является void. Source Edit

Процедуры

func `$`[T](c: CritBitTree[T]): string
Преобразует c в строковое представление.

Пример:

doAssert $CritBitTree[int].default == "{:}"
doAssert $toCritBitTree({"key1": 1, "key2": 2}) == """{"key1": 1, "key2": 2}"""
doAssert $CritBitTree[void].default == "{}"
doAssert $toCritBitTree(["key1", "key2"]) == """{"key1", "key2"}"""
Исходный код Редактировать 
func `[]`[T](c: CritBitTree[T]; key: string): lent T {.inline.}

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

См. также:

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

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

См. также:

  • [] proc
  • []= proc
Исходный код Редактировать 
proc `[]=`[T](c: var CritBitTree[T]; key: string; val: sink T)

Псевдоним для incl.

См. также:

  • [] proc
  • [] proc
Исходный код Редактировать 
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 contains[T](c: CritBitTree[T]; key: string): bool {.inline.}
Возвращает true, если c содержит данный key.

Пример:

var c: CritBitTree[void]
incl(c, "key")
doAssert c.contains("key")
Исходный код Редактировать 
proc containsOrIncl(c: var CritBitTree[void]; key: string): bool {....raises: [],
    tags: [], forbids: [].}

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

См. также:

  • incl proc
  • incl proc
  • containsOrIncl proc
  • missingOrExcl proc

Пример:

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 containsOrIncl[T](c: var CritBitTree[T]; key: string; val: sink T): bool

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

См. также:

  • incl proc
  • incl proc
  • containsOrIncl proc
  • missingOrExcl proc

Пример:

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 excl[T](c: var CritBitTree[T]; key: string)

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

См. также:

  • incl proc
  • incl proc

Пример:

var c: CritBitTree[void]
incl(c, "key")
excl(c, "key")
doAssert not c.contains("key")
Исходный код Редактировать 
func hasKey[T](c: CritBitTree[T]; key: string): bool {.inline.}
Псевдоним для contains. Исходный код Редактировать 
proc inc(c: var CritBitTree[int]; key: string; val: int = 1) {....raises: [],
    tags: [], forbids: [].}
Увеличивает 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: [],
    forbids: [].}

Включает key в c.

См. также:

  • excl proc
  • incl proc

Пример:

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

Вставляет key со значением val в c.

См. также:

  • excl proc
  • incl proc

Пример:

var c: CritBitTree[int]
incl(c, "key", 42)
doAssert c["key"] == 42
Исходный код Редактировать 
func len[T](c: CritBitTree[T]): int {.inline.}
Возвращает количество элементов в c за O(1).

Пример:

let c = ["key1", "key2"].toCritBitTree
doAssert c.len == 2
Исходный код Редактировать 
proc missingOrExcl[T](c: var CritBitTree[T]; key: string): bool

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

См. также:

  • excl proc
  • containsOrIncl proc
  • containsOrIncl proc

Пример:

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 toCritBitTree(items: sink openArray[string]): CritBitTree[void] {.
    ...raises: [], tags: [], forbids: [].}
Создаёт новое CritBitTree, содержащее указанные items.

Пример:

doAssert ["a", "b", "c"].toCritBitTree is CritBitTree[void]
Исходный код Редактировать 
proc toCritBitTree[T](pairs: sink openArray[(string, T)]): CritBitTree[T]
Создаёт новое CritBitTree, содержащее указанные pairs.

Пример:

doAssert {"a": "0", "b": "1", "c": "2"}.toCritBitTree is CritBitTree[string]
doAssert {"a": 0, "b": 1, "c": 2}.toCritBitTree is CritBitTree[int]
Исходный код Редактировать

Итераторы

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

Пример:

from std/sequtils import toSeq

let c = {"key1": 1, "key2": 2}.toCritBitTree
doAssert toSeq(c.keys) == @["key1", "key2"]
Исходный код Изменить 
iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string): string
Возвращает все ключи, начинающиеся с prefix.

Пример:

from std/sequtils import toSeq

let c = {"key1": 42, "key2": 43}.toCritBitTree
doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"]
Исходный код Изменить 
iterator mpairs[T](c: var CritBitTree[T]): tuple[key: string, val: var T]

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

См. также:

  • итератор pairs
Исходный код Изменить 
iterator mpairsWithPrefix[T](c: var CritBitTree[T]; prefix: string): tuple[
    key: string, val: var T]

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

См. также:

  • итератор pairsWithPrefix
Исходный код Изменить 
iterator mvalues[T](c: var CritBitTree[T]): var T

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

См. также:

  • итератор values
Исходный код Изменить 
iterator mvaluesWithPrefix[T](c: var CritBitTree[T]; prefix: string): var T

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

См. также:

  • итератор valuesWithPrefix
Исходный код Изменить 
iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]

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

См. также:

  • итератор mpairs

Пример:

from std/sequtils import toSeq

let c = {"key1": 1, "key2": 2}.toCritBitTree
doAssert toSeq(c.pairs) == @[(key: "key1", val: 1), (key: "key2", val: 2)]
Исходный код Изменить 
iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string): tuple[
    key: string, val: T]

Возвращает все (ключ, значение)-пары c, начинающиеся с prefix.

См. также:

  • итератор mpairsWithPrefix

Пример:

from std/sequtils import toSeq

let c = {"key1": 42, "key2": 43}.toCritBitTree
doAssert toSeq(c.pairsWithPrefix("key")) == @[(key: "key1", val: 42), (key: "key2", val: 43)]
Исходный код Изменить 
iterator values[T](c: CritBitTree[T]): lent T

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

См. также:

  • итератор mvalues

Пример:

from std/sequtils import toSeq

let c = {"key1": 1, "key2": 2}.toCritBitTree
doAssert toSeq(c.values) == @[1, 2]
Исходный код Изменить 
iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string): lent T

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

См. также:

  • итератор mvaluesWithPrefix

Пример:

from std/sequtils import toSeq

let c = {"key1": 42, "key2": 43}.toCritBitTree
doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43]
Исходный код Изменить

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

Spec-Zone.ru

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