Trie.h Trie.cc LHashTrie.cc SArrayTrie.cc
文档作者：rickjin
创立时间：08.08.24
--------------
1、基本类
--------------
Trie.h Trie.cc 这两个文件主要以模板方式实现了一个常用Trie 结构, Trie DataT> 可以当作是 Map 的扩展, 把一个 KeyT 的序列 (KeyT *) 映射到数据.
该文件中同时提供了两个用于遍历 Trie 的 迭代器:
TrieIter 用于遍历当前Trie 结点下的直接子结点
TrieIter2 用于遍历当前Trie 结点下的所有可能路径中符合给定深度的子结点
SArrayTrie.cc 同 LHashTrie.cc 两个文件很简单, 只是加载 Trie 的定义,
但分别使用 SArray 和 LHash 存储内部数据. Trie.h 中提供了一个宏
USE_SARRAY_TRIE 作为选择开关 如果 USE_SARRAY_TRIE 被定义, 则选用 SArray
存储数据, 否则使用 LHash存储数据.
#ifdef USE_SARRAY_TRIE
# define TRIE_INDEX_T SArray
# define TRIE_ITER_T SArrayIter
#else /* ! USE_SARRAY_TRIE */
# define TRIE_INDEX_T LHash
# define TRIE_ITER_T LHashIter
#endif /* USE_SARRAY_TRIE *
----------------
2、类接口说明
----------------
2.1) Trie 类主要接口
template
class Trie
{
friend class TrieIter;
friend class TrieIter2;
public:
//查找操作
Trie *findTrie(const KeyT *keys, Boolean &foundP);
//插入操作
Trie *insertTrie(const KeyT *keys, Boolean &foundP);
//删除操作
Trie *removeTrie(const KeyT *keys, Boolean &foundP);
//返回当前结点数据
DataT &value();
//清空操作
void clear();
//数据大小
unsigned int numEntries();
private:
TRIE_INDEX_T< KeyT, Trie > sub
DataT data;
};
说明:
a. 私有成员 sub 可以是 SArray 或是 LHash, 是一种 Map 结构,
用于索引键值, 由此构造的 Trie 形成一个嵌套的链式结构, 可以通过 sub
找到所有的子结点. DataT 用于存储当前结点下的数据.
b. 类似于 C 语言中的字符串以 '\0' 结束, 键值序列 KeyT *keys 也以一个特殊键值
标志结束位置, 可以通过布尔函数 Map_noKeyP(key) 判定key 是否为结束标志.
c. 如果 keys == NULL 或是 keys 长度为0 (即 Map_noKeyP(Key[0]) == True), 则此
键值索引当前的 Trie 结点.
d. foundP 用于指示基于 keys 的检索是否成功, 如果成功则 foundP 被设置为 True.
2.2) TrieIter 类主要接口
template
class TrieIter
{
public:
//构造函数
TrieIter(const Trie &trie, int (*sort)(KeyT,KeyT) = 0);
//重新初始化函数
void init();
//迭代函数
Trie *next(KeyT &key);
private:
TRIE_ITER_T< KeyT, Trie > myIter;
};
说明：
a. TrieIter 用于遍历当前 Trie 结点下的直接子 Trie 结点, 对应于 Trie::TRIE_INDEX_T
为 SArray(或 LHash) 类型， TrieIter::TRIE_ITER_T 将为 SArrayIter (或
LHashIter) 类型， 所以直接使用 SAarrayIter (或 LHashIter) 完成遍历操作， 实
现很简单。
b. 构造函数中的 sort 函数用于键值排序。
c. 迭代函数 next(KeyT &key) 调用之后， 设置下一个 key 的值并返回和 key 值对应的
Trie 结点指针。
d. 当你使用了一个迭代器 TrierIter, 想再次是用它的时候， 可以调用 init() 对它重新
初始化
2.3) TrieIter2 类主要接口
template
class TrieIter2
{
public:
//构造函数
TrieIter2(const Trie &trie, KeyT *keys, unsigned int level, int (*sort)(KeyT,KeyT) = 0);
//重新初始化函数
void init();
//迭代函数
Trie *next();
private:
const Trie &myTrie; // 当前 Trie 结点
KeyT *keys; // 用于存储满足要求的结点的键值
int level; // 要求的结点深度
int (*sort)(KeyT,KeyT); // 键值比较函数
TRIE_ITER_T< KeyT, Trie > myIter; // 用于遍历当前 Trie 结点下的所有子结点
TrieIter2 *subIter; // 递归地遍历子结点的子结点
Boolean done; // level=0 的时候指示迭代是否结束
};
说明：
a. TrieIter2 用于遍历当前 Trie 结点下的所有可能路径中深度为 level 的子 Trie 结点
b. 构造函数中传入的 KeyT *keys, 是用于迭代中存储键值用的。 每次调用迭代函数
next(), 函数返回下一个深度为 level 的 Trie 结点的指针， *keys 将被设置为对应于
该结点的键值，
d. 当你使用了一个迭代器 TrierIter2, 想再次是用它的时候， 可以调用 init() 对它重新
初始化
-------------------
3、主要函数功能说明
-------------------
2.1) Trie 类主要接口
a) 析构函数
Trie::~Trie()
{
TrieIter iter(*this);
KeyT key;
Trie *node;
while (node = iter.next(key)) {
node->~Trie(); //显示调用子结点的析构函数!!
}
}
该析构函数通过递归显示调用当前 Trie 结点的子结点的析构函数销毁对象, 此处必须进
行显示递归调用, 否则会出现内存泄漏. 原因是 sub 属于 SArray/LHash 类型, 其中使用
placement new 对内部内存做初始化, 所以必须由用户自己显示调用析构函数, 否则析构
函数不会被执行。
b)查找操作
参数说明：
@param keys 要查找的键值
@param foundP 指示键值对应结点是否存在
@return 键值所对应的 Trie 结点
Trie*
Trie::findTrie(const KeyT *keys, Boolean &foundP)
{
// 键值为空, 指示当前结点,
// 设置 foundP 为 True, 返回当前的 Trie 结点
if (keys == 0 || Map_noKeyP(keys[0])) {
foundP = true;
return (Trie *)this;
} else {
//非空, 查找索引 sub
Trie *subtrie = sub.find(keys[0]);
if (subtrie == 0) { //查找失败, 设置foundP 为 false, 返回 NULL
foundP = false;
return 0;
} else { // 继续递归查找
return subtrie->findTrie(keys + 1, foundP);
}
}
}
查找函数使用递归函数调用实现， 如果修改为迭代算法能够提高一些性能。
c) 插入操作
插入和查找非常相似, 不再详细介绍
d) 删除操作
参数说明：
@param keys 要删除的结点的键值
@param foundP 指示键值对应结点是否存在
@return 被删除的 Trie 结点的指针
Trie *
Trie::removeTrie(const KeyT *keys, Boolean &foundP)
{
//删除操作必须提供长度 >0 的 key 值, 否则不做删除操作
if (keys == 0 || Map_noKeyP(keys[0]))
{
foundP = false;
return 0;
} else if (Map_noKeyP(keys[1])) //键长为 1, 查找到子结点并删除
{
Trie *subtrie = sub.remove(keys[0], foundP);
if (foundP)
{
subtrie->~Trie(); //删除结点，显示调用析构,
return subtrie;
} else {
return 0;
}
} else { // 键长 > 1, 递归调用删除操作
Trie *subtrie = sub.find(keys[0], foundP);
if (!foundP) {
return 0;
} else {
return subtrie->removeTrie(keys + 1, foundP);
}
}
}
2.1) Trie 类主要接口
a) 构造函数
template
TrieIter2::TrieIter2(const Trie &trie,
KeyT *keys, unsigned int level,
int (*sort)(KeyT,KeyT) )
: myTrie(trie),
keys(keys),
level(level),
sort(sort),
myIter(trie.sub, sort),
subIter(0),
done(false)
{
if (level == 0)
{
Map_noKey(keys[0]); // 设置键值为空
}
else if (level == 1)
{
Map_noKey(keys[1]); // 设置键值长度为 1
}
}
b) 迭代函数
参数说明：
@return 返回下一个满足深度要求的 Trie 结点， 同时把 keys 设置为该 Trie 结点对应
的键值
template
Trie* TrieIter2::next()
{
// level == 0 的时候, 直接返回当前 Trie 结点
// 使用 done 指示迭代是否结束
if (level == 0)
{
if (done)
return 0;
else
{
done = true;
return (Trie *)&myTrie;
}
}
else if (level == 1) //当前结点下面的所有子结点都满足 level == 1
{
return myIter.next(keys[0]);
}
else // 结点深度要求 level > 1
{
while (1) {
if (subIter == 0) {
//获取当前结点的下一个子结点
Trie *subTrie = myIter.next(keys[0]);
if (subTrie == 0) //当前结点已经没有其他子结点了
return 0;
else
// subTrie 为 Trie 结点的一个子结点
// 对 subTrie 子结点建立一个 迭代器 subIter, 用于遍历子结点的子结点
subIter = new TrieIter2(*subTrie, keys + 1, level - 1, sort);
}
//对结点 subTrie， 递归调用迭代函数 next()
Trie *next = subIter->next();
if (next == 0)
{
//subTrie 的所有子结点遍历结束
delete subIter;
subIter = 0;
} else
return next; //找到 subTrie 的一个子结点, 返回
}
}
}
/* vi: set ts=4 sw=4 et: */
