辞書ツリーのC++実装
24310 ワード
今回のコードは、自動タイプ推定、テンプレート類など、新鮮なものがたくさん使われていて、本当に楽しかったですね.
自分で簡単なテストをしましたが、プログラムの丈夫さなどはまだ悪いので、このプログラムは後で機能補完を行います.
テスト:
自分で簡単なテストをしましたが、プログラムの丈夫さなどはまだ悪いので、このプログラムは後で機能補完を行います.
#pragma once
#include<cstddef>
#include<string>
using std::strlen;
using std::pair;
using std::make_pair;
//
template<int size>
class TrieNode
{
public:
TrieNode() :NodeSize(0), TerminableSize(0)
{
for (size_t i = 0; i < size; i++)
{
ChildNode[i] = NULL;
}
}
~TrieNode()
{
for (size_t i = 0; i < size; i++)
{
delete ChildNode[i];
ChildNode[i] = NULL;
}
}
public: // , ,
int NodeSize; //
int TerminableSize; //
TrieNode* ChildNode[size]; //
};
//
template < int Size, typename Type> class Trie
{
public:
typedef TrieNode<Size> Node;
typedef TrieNode<Size>* pNode;
public:
Trie() :root(new Node) {}
~Trie() { delete root; }
public:
template<typename itr>
void insert(itr beg, itr end);
void insert(const char* str);
template<typename itr>
pair<bool,int> find(itr beg, itr end);
pair<bool,int> find(const char* str);
template<typename itr>
bool DownNodeAlone(itr beg);
template<typename itr>
bool erase(itr beg, itr end);
bool erase(const char* str);
int sizeAll(pNode);
int sizeNodeRedundant(pNode);
public:
pNode root;
private:
Type index;
};
template < int Size, typename Type>
template<typename itr>
void Trie<Size, Type>::insert(itr beg, itr end)
{
pNode cur = root, pre = NULL;
for (; beg != end; ++beg)
{
if (!cur->ChildNode[index[*beg]])
{
cur->ChildNode[index[*beg]] = new(Node);
++cur->NodeSize;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre)
++pre->TerminableSize;
}
template < int Size, typename Type>
void Trie<Size, Type>::insert(const char* str)
{
return insert(str, str + strlen(str));
}
template <int Size, typename Type>
pair<bool, int> Trie<Size, Type>::find(const char* str)
{
return find(str, str + strlen(str));
}
template <int Size, typename Type>
template<typename itr>
pair<bool,int> Trie<Size, Type>::find(itr beg, itr end)
{
pNode cur = root, pre = NULL;
pair<bool, int> res(false, 0);
for (;beg != end;++beg)
{
if (!cur->ChildNode[index[*beg]])
{
return res;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre != NULL&&pre->TerminableSize > 0)
{
res.first = true;
res.second = pre->TerminableSize;
}
return res;
}
template <int Size, typename Type>
template<typename itr>
bool Trie<Size, Type>::DownNodeAlone(itr beg)
{
pNode cur = root;
int terminableSum = 0;
while (cur->NodeSize != 0)
{
terminableSum += cur->TerminableSize;
if (cur->NodeSize > 1)
return false;
else
{
for (size_t i = 0; i < Size; i++)
{
if (cur->ChildNode[i])
{
cur = cur->ChildNode[i];
}
}
}
}
if (terminableSum == 1)
return true;
else return false;
}
template <int Size, typename Type>
template<typename itr>
bool Trie<Size, Type>::erase(itr beg, itr end)
{
auto var = find(beg, end);
if (var.first)
{
pNode cur = root, pre = NULL;
for (; beg != end; ++beg)
{
if (DownNodeAlone(cur))
{
delete cur;
cur = NULL;
return true;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre->TerminableSize > 0)
--pre->TerminableSize;
return true;
}
return false;
}
template <int Size, typename Type>
bool Trie<Size, Type>::erase(const char* str)
{
auto var = find(str);
if (var.first)
{
erase(str, str + strlen(str));
return true;
}
return false;
}
template <int Size, typename Type>
int Trie<Size, Type>::sizeAll(pNode ptr)
{
if (ptr == NULL)
return 0;
int rev = ptr->TerminableSize;
for (size_t i = 0; i < Size; i++)
{
rev += sizeAll(ptr->ChildNode[i]);
}
return rev;
}
template <int Size, typename Type>
int Trie<Size, Type>::sizeNodeRedundant(pNode ptr)
{
if (NULL == ptr)
return 0;
int i, rev = 0;
if (ptr->TerminableSize > 0)
rev = 1;
if (ptr->NodeSize != 0)
{
for (i = 0; i < Size; ++i)
{
rev += sizeNodeRedundant(ptr->ChildNode[i]);
}
}
return rev;
}
template<int Size>
class Index
{
public:
Index() {}
~Index() {}
public:
int operator[](char vchar)
{
return (vchar - 'a') % Size;
}
};
テスト:
int main(void)
{
{
Trie<26, Index<26>> temp;
temp.insert("hello");
temp.insert("he");
temp.insert("he");
temp.insert("her");
temp.insert("him");
temp.insert("fuck");
temp.insert("fuckyou");
temp.insert("hupu");
temp.insert("lady");
temp.insert("hahah");
temp.insert("lady");
temp.insert("lady");
temp.insert("lady");
auto var = temp.find("lady");
cout << "lady:" << boolalpha <<var.first <<" "<<var.second<< endl;
var = temp.find("heihei");
cout << "heihei:" << boolalpha << var.first << " " << var.second << endl;
cout << "size:" << temp.sizeAll(temp.root) << endl;
cout << "size of NoneRedundant:" << temp.sizeNodeRedundant(temp.root) << endl;
var = temp.find("hupu");
cout << "hupu:" << boolalpha << var.first <<" "<<var.second<< endl;
temp.erase("hupu");
var = temp.find("hupu");
cout << "hupu:" << boolalpha << var.first << " " << var.second << endl;
cout << "size:" << temp.sizeAll(temp.root) << endl;
cout << "size of NoneRedundant:" << temp.sizeNodeRedundant(temp.root) << endl;
}
cin.get();
_CrtDumpMemoryLeaks();
return 0;
}