Skip to content

Instantly share code, notes, and snippets.

@PanagiotisPtr
Created January 10, 2019 15:27
Show Gist options
  • Save PanagiotisPtr/19ba04a5280394534f419a2c55a52369 to your computer and use it in GitHub Desktop.
Save PanagiotisPtr/19ba04a5280394534f419a2c55a52369 to your computer and use it in GitHub Desktop.
Simple Trie implementation in C++
#ifndef TRIE_H
#define TRIE_H
#include <unordered_map>
#include <exception>
#include <memory>
#include <string>
#include <list>
#include <stack>
#define DEBUG
#ifdef DEBUG
#include<iostream>
using namespace std;
#define log(str) cout << str << endl;
#else
#define log(str)
#endif
class invalid_node : public std::exception {
virtual const char* what() const throw (){
return "Node doesn't exist";
}
};
class Trie {
public:
Trie() : root(std::make_unique<Node>(0)) {}
template<typename Iterator>
void insert(Iterator first, Iterator last) { insert_impl(first, last, root); }
void insert(const std::string& str) { insert(std::begin(str), std::end(str)); }
template<typename Iterator>
bool find(Iterator first, Iterator last) {
try{
get_node(first, last, root);
return true;
}catch(const invalid_node& e){
return false;
}
}
bool find(const std::string& str) {
return find(std::begin(str), std::end(str));
}
template<typename Iterator>
void erase(Iterator first, Iterator last) {
if(!find(first, last))
return;
erase_impl(first, last, root);
}
void erase(const std::string& str) { erase(std::begin(str), std::end(str)); }
template<
typename Container = std::list<std::string>,
typename Iterator
>
Container get_items(Iterator first, Iterator last) {
Container c;
std::string start;
for(Iterator it = first; it != last; it++)
start += *it;
try {
const node_ptr& node = get_node(first, last, root);
for(std::pair<char, const node_ptr&> child : node->children)
get_items_impl(child.second, c, start + child.first);
}catch(const invalid_node& e){
return c;
}
return c;
}
template<typename Container = std::list<std::string> >
Container get_items(const std::string& str) {
return get_items(std::begin(str), std::end(str));
}
private:
struct Node;
using node_ptr = std::unique_ptr<Node>;
node_ptr root;
struct Node {
Node(char c) : val(c) {}
char val;
std::unordered_map<char, node_ptr> children;
};
bool is_child(const node_ptr& node, char c){
return node->children.find(c) != node->children.end();
}
node_ptr make_node(char c){ return std::make_unique<Node>(c); }
template<typename Iterator>
void insert_impl(Iterator first, Iterator last, const node_ptr& node){
Iterator next = first;
next++;
if(first == last){
node->children.insert(std::make_pair(0, make_node(0)));
}else if(is_child(node, *first)){
insert_impl(next, last, node->children[*first]);
}else{
node->children.insert(std::make_pair(*first, make_node(*first)));
insert_impl(next, last, node->children[*first]);
}
}
template<typename Iterator>
const node_ptr& get_node(Iterator first, Iterator last, const node_ptr& node) {
Iterator next = first;
next++;
if(first == last)
return node;
if(!is_child(node, *first))
throw invalid_node();
return get_node(next, last, node->children[*first]);
}
/* true if next node was deleted */
template<typename Iterator>
bool erase_impl(Iterator first, Iterator last, const node_ptr& node){
if(first == last && !is_child(node, 0)){
if(node == root) // edge case of string "" <- design choice
return false;
else
throw invalid_node();
}else if(first == last){
node->children.erase(node->children.find(0));
// if it isn't zero other nodes are still here
return node->children.size() == 0;
}
if(!is_child(node, *first)){
throw invalid_node();
}
Iterator next = first;
next++;
int qq = node->children.size();
bool res = erase_impl(next, last, node->children[*first]);
if(res && node->children.size()){
node->children.erase(node->children.find(*first));
return (node->children.size() == 0);
}
return false;
}
template<typename Container>
void get_items_impl(const node_ptr& node, Container& c, string str) {
if(node->val == 0){
c.insert(std::begin(c), str);
return;
}
// Depth First Search
for(std::pair<char, const node_ptr&> child : node->children)
get_items_impl(child.second, c, str + child.first);
}
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment