| 1 | template <class T> |
| 2 | struct trie { |
| 3 | struct node { |
| 4 | map<T, node*> children; |
| 5 | int prefixes, words; |
| 6 | node() { prefixes = words = 0; } }; |
| 7 | node* root; |
| 8 | trie() : root(new node()) { } |
| 9 | template <class I> |
| 10 | void insert(I begin, I end) { |
| 11 | node* cur = root; |
| 12 | while (true) { |
| 13 | cur->prefixes++; |
| 14 | if (begin == end) { cur->words++; break; } |
| 15 | else { |
| 16 | T head = *begin; |
| 17 | typename map<T, node*>::const_iterator it; |
| 18 | it = cur->children.find(head); |
| 19 | if (it == cur->children.end()) { |
| 20 | pair<T, node*> nw(head, new node()); |
| 21 | it = cur->children.insert(nw).first; |
| 22 | } begin++, cur = it->second; } } } |
| 23 | template<class I> |
| 24 | int countMatches(I begin, I end) { |
| 25 | node* cur = root; |
| 26 | while (true) { |
| 27 | if (begin == end) return cur->words; |
| 28 | else { |
| 29 | T head = *begin; |
| 30 | typename map<T, node*>::const_iterator it; |
| 31 | it = cur->children.find(head); |
| 32 | if (it == cur->children.end()) return 0; |
| 33 | begin++, cur = it->second; } } } |
| 34 | template<class I> |
| 35 | int countPrefixes(I begin, I end) { |
| 36 | node* cur = root; |
| 37 | while (true) { |
| 38 | if (begin == end) return cur->prefixes; |
| 39 | else { |
| 40 | T head = *begin; |
| 41 | typename map<T, node*>::const_iterator it; |
| 42 | it = cur->children.find(head); |
| 43 | if (it == cur->children.end()) return 0; |
| 44 | begin++, cur = it->second; } } } }; |
| 45 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected