critbits

このモジュールは文字列集合のソート、または文字列写像のソートで効率的なコンテナである crit ビットツリーの実装です。アダム・ラングリーによる素晴らしい論文をベースにしています (crit ビットツリーの方式は基数ツリー、またはパトリシア・トライです)。

用例:

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

CritBitTree[T] = object
  root: Node[T]
  count: int
crit ビットツリーは文字列から T 型に対する写像、または T が void のときは文字列集合として使えます。  ソース 編集

プロシージャ

proc len[T](c: CritBitTree[T]): int
O(1) により c の要素数を返します。  ソース 編集
proc contains[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
c に指定された key がある場合に限り true を返します。  ソース 編集
proc hasKey[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
contains のエイリアスです。  ソース 編集
proc excl[T](c: var CritBitTree[T]; key: string)
key (および関連値) を集合 c から削除します。key がなければ、何もしません。  ソース 編集
proc missingOrExcl[T](c: var CritBitTree[T]; key: string): bool
c に指定された key がない場合に限り true を返します。key があれば c.excl(key) を実行します。  ソース 編集
proc containsOrIncl[T](c: var CritBitTree[T]; key: string; val: T): bool
c に指定された key がある場合に限り true を返します。key がなければ c[key] = val を実行します。  ソース 編集
proc containsOrIncl(c: var CritBitTree[void]; key: string): bool {...}{.raises: [], tags: [].}
c に指定された key がある場合に限り true を返します。key がなければ c へ挿入します。  ソース 編集
proc inc(c: var CritBitTree[int]; key: string; val: int = 1) {...}{.raises: [], tags: [].}
valc[key] をインクリメント (増分) します。  ソース 編集
proc incl(c: var CritBitTree[void]; key: string) {...}{.raises: [], tags: [].}
ckey をインクルードします。  ソース 編集
proc incl[T](c: var CritBitTree[T]; key: string; val: T)
c にある値 valkey へ挿入します。  ソース 編集
proc `[]=`[T](c: var CritBitTree[T]; key: string; val: T)
(key, value) ペアを t に追加します。  ソース 編集
proc `[]`[T](c: CritBitTree[T]; key: string): T {...}{.inline.}
c[key] の値を取得します。tkey がないときは、 KeyError 例外が発生します。key の有無は hasKey で確認できます。  ソース 編集
proc `[]`[T](c: var CritBitTree[T]; key: string): var T {...}{.inline.}
c[key] の値を取得します。値は修正可能です。tkey がないときは、 KeyError 例外が発生します。  ソース 編集
proc `$`[T](c: CritBitTree[T]): string
c を文字列形式へ変換します。出力例: {keyA: value, keyB: value}, {:} T が void ならば出力は: {keyA, keyB}, {}.   ソース 編集

イテレータ

iterator keys[T](c: CritBitTree[T]): string
辞書式順序でキーをすべて生成します。  ソース 編集
iterator values[T](c: CritBitTree[T]): T
対応するキーによる辞書式順序で c 値をすべて生成します。  ソース 編集
iterator mvalues[T](c: var CritBitTree[T]): var T
対応するキーによる辞書式順序で c 値をすべて生成します。値は修正可能です。  ソース 編集
iterator items[T](c: CritBitTree[T]): string
辞書式順序でキーをすべて生成します。  ソース 編集
iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]
c にある (key, value) の全ペアを生成します。  ソース 編集
iterator mpairs[T](c: var CritBitTree[T]): tuple[key: string, val: var T]
c にある (key, value) の全ペアを生成します。生成値は修正可能です。  ソース 編集
iterator itemsWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string
prefix を始点としたキーをすべて生成します。longestMatch が true ならば、最長一致を返します。この場合は完全一致でなくても問題ありません。  ソース 編集
iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string
prefix を始点としたキーをすべて生成します。  ソース 編集
iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): T
対応するキーの prefix を始点として c にある (key, value) の全ペアを生成します。  ソース 編集
iterator mvaluesWithPrefix[T](c: var CritBitTree[T]; prefix: string;
                             longestMatch = false): var T
対応するキーの prefix を始点として c にある (key, value) の全ペアを生成します。値は修正可能です。  ソース 編集
iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): tuple[
    key: string, val: T]
prefix を始点として c にある (key, value) の全ペアを生成します。  ソース 編集
iterator mpairsWithPrefix[T](c: var CritBitTree[T]; prefix: string;
                            longestMatch = false): tuple[key: string, val: var T]
prefix を始点として c にある (key, value) の全ペアを生成します。生成値は修正可能です。  ソース 編集