ソースを表示

[[メインページ]] [[Category:オープンソース|でいむ]]
----

== 何ですかこれは？ ==
効率的なTrieの実装方法であるDouble-ArrayのC++ライブラリ。

割合 http://citeseer.ist.psu.edu/aoe92efficient.html に忠実に作っています。

ヘッダライブラリなので、includeするだけで使えます。多分プラットフォーム非依存。
なお、以下の拡張を実装しています。
* TAIL
* G-link

== できること ==
* std::set<std::string> 的動作 (完全互換ではありません）
* Common prefix search
* Longest prefix match

== 使い方 ==
<code cpp>
#include <iostream>
#include "dame.h"

dame::DoubleArrayTrie trie;
trie.insert("bachelor");
trie.insert("jar");
trie.insert("badge");
trie.insert("baby");

// babyを検索
dame::DoubleArrayTrie::iterator it = trie.find("baby");
if (it != trie.end()) {
  std::cout << "baby found!" << std::endl;
}

// "ba"で始まる全てのキーを探索
dame::DoubleArrayTrie::iterator endit;
it = trie.findPrefixedBy("ba", endit);
while (it != endit) {
  std::cout << *it << std::endl;
  ++it;
}

// "bachelorism"の最長prefixを探索
it = trie.findLongestPrefixOf("bachelorism");
if (it != trie.end()) {
  std::cout << *it << std::endl;
}
</code>

== バグ ==
バグ？あー、うん、有るんじゃないかな。多分。

== ライセンス ==
Public Domain

== ダウンロード ==
* [http://www.void.in/files/dame/dame-1.3.1.tar.gz dame-1.3.1.tar.gz]

== 履歴 ==
* 2006/5/30 ver. 1.3
** iteratorが、キー以外を指さないようにした。DoubleArrayTrieElementからvalueメンバを削除。代わりにTAILの先頭に詰めるようにした。
* 2006/5/29 ver. 1.2
** iteratorを引数にとるinsert(), erase()を追加。
** charとarray_index_tのマッピングを行うクラスを切り出し、テンプレート引数で与えるようにした。
* 2006/5/28 ver. 1.1
** 空文字列も挿入できるように仕様を変更。
** reserve()追加。
** find(), insert(), erase()がconst std::string&を引数にとることができるようにした。
** std::setとの整合性のため、insert()がstd::pair<iterator,bool>を返すよう変更。
* 2006/5/27 ver. 1.0
** iterator実装。プレフィックスサーチ実装。
* 2006/5/26 ver. 0.1
** G-link実装。衝突解決のバグを修正。
* 2006/5/24 Public Release