Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <stdlib.h> /* srand, rand */
- #include <string.h>
- #include <stdio.h>
- #include <vector>
- int Created = 0;
- int Deleted = 0;
- template <typename T>
- T create_empty()
- {
- return T();
- }
- template <>
- bool create_empty<bool>()
- {
- return false;
- }
- template <typename T>
- bool check_empty(T& a)
- {
- return a.is_empty();
- }
- template <>
- bool check_empty<bool>(bool& a)
- {
- return a == false;
- }
- template <typename T,typename C,int Base>
- class TrieNode
- {
- TrieNode* childs[Base];
- T n;
- unsigned int val;
- void init(unsigned int val)
- {
- Created++;
- this->val = val;
- memset(childs, 0 ,sizeof(TrieNode*) * Base);
- n = create_empty<T>();
- }
- TrieNode(int mult)
- {
- init(mult);
- }
- T& create(unsigned int number,int mult)
- {
- if(!number)
- {
- return n;
- }
- else
- {
- unsigned int digit = number % Base;
- number /= Base;
- TrieNode*& child = childs[digit];
- if(!child)
- child = new TrieNode(digit*mult);
- return child->create(number,mult*Base);
- }
- }
- C get_keys(int val)
- {
- C list;
- if(!check_empty(n))
- {
- list.push_back(val);
- }
- for(int i=0;i<Base;i++)
- {
- TrieNode<T,C,Base>*& child = childs[i];
- if(child)
- {
- C list_new = child->get_keys(child->val + val);
- for(int j=0;j<(int)list_new.size();j++)
- {
- list.push_back(list_new[j]);
- }
- }
- }
- return list;
- }
- TrieNode& move(TrieNode& other)
- {
- this->val = other.val;
- memcpy(this->childs,other.childs,sizeof(TrieNode*) * Base);
- this->n = other.n;
- other.val = 1;
- memset(other.childs,0,sizeof(TrieNode*) * Base);
- other.n = create_empty<T>();
- return *this;
- }
- public :
- ~TrieNode()
- {
- Deleted++;
- for(int i=0;i<Base;i++)
- delete childs[i];
- }
- TrieNode(){ init(1); }
- TrieNode (const TrieNode& other)
- {
- move( const_cast<TrieNode&>(other) );
- }
- TrieNode& operator= (TrieNode other)
- {
- return move(other);
- }
- T& operator[](unsigned int number)
- {
- return this->create(number,1);
- }
- bool is_empty()
- {
- if(!check_empty<T>(n))
- return false;
- for(int i=0;i<Base;i++)
- {
- TrieNode*& child = childs[i];
- if(child)
- {
- if(!check_empty< TrieNode<T,C,Base> >(*child))
- return false;
- }
- }
- return true;
- }
- C get_keys()
- {
- return this->get_keys(0);
- }
- };
- template<typename T,typename C>
- struct TrieNodeTen
- {
- typedef TrieNode<T,C,10> type;
- };
- template <typename T>
- struct TrieNodeTenVec
- {
- typedef typename TrieNodeTen< T,std::vector<int> >::type type;
- };
- template <typename T,typename C>
- class TrieNodeTen1 : public TrieNode<T,C,10> {};
- template <typename T>
- class TrieNodeTenVec1 : public TrieNodeTen1<T,std::vector<int> > {};
- int main(int argc, char* argv[])
- {
- {
- TrieNodeTenVec< TrieNodeTenVec<bool>::type >::type trie;
- for(int i=0;i<100;i++)
- trie[rand()][rand()] = true;
- }
- printf("Created %d\n",Created);
- printf("Deleted %d\n",Deleted);
- getchar();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement