Skip to content

Instantly share code, notes, and snippets.

@datlife datlife/trie.h
Created Dec 3, 2018

Embed
What would you like to do?
Trie Implementation in Modern C++ (Kind of, I am learning)
/**
* MIT License
*
* Copyright (c) 2018 Dat Nguyen
* Trie (aka Prefix Tree) is a type of Tree Data Structure. A node contains a
* list of child Nodes.
*
* Applications:
* ============
* * Word completion: quickly validate if a word is correctly type.
* * Word Prediction (Auto-completion)
*/
#ifndef TRIE_H_
#define TRIE_H_
#include <vector>
#include <string>
#include <unordered_map>
class Trie {
public:
// Trie Constructor
Trie();
explicit Trie(std::vector<std::string>);
// Trie Operations
void Insert(const std::string& word);
bool StartsWithPrefix(const std::string& prefix);
bool IsACompleteWord(const std::string& word);
private:
struct Node {
bool end_of_word;
std::unordered_map<char, std::unique_ptr<Node>> children;
Node(): end_of_word(false) {}
};
std::unique_ptr<Node> root;
};
/// ===========================
/// Tries Implementation
/// ===========================
Trie::Trie() {
root = std::unique_ptr<Node>(new Node());
}
Trie::Trie(std::vector<std::string> words) {
root = std::unique_ptr<Node>(new Node());
for (auto w : words)
Insert(w);
}
// Insert a word in to Trie if needed
void Trie::Insert(const std::string& word) {
if (word.empty()) return;
auto it = root.get();
for (const char & key : word) {
int found = it->children.count(key);
if (!found)
it->children.emplace(key, std::unique_ptr<Node>(new Node()));
it = it->children[key].get();
}
it->end_of_word = true;
}
// Returns True if prefix is matched in Trie
// Example:
// t.Insert("Hello")
// t.StartsWithPrefix("Hell") // is True
bool Trie::StartsWithPrefix(const std::string& prefix) {
auto it = root.get();
for (const char & key : prefix) {
auto found = it->children.count(key);
if (!found)
return false;
it = it->children[key].get();
}
return true;
}
// Returns True if input is a complete word
// Example:
// t.Insert("Hello")
// t.IsACompleteWord("Hello") // is True
bool Trie::IsACompleteWord(const std::string& word) {
auto it = root.get();
for (const char & key : word) {
auto found = it->children.count(key);
if (!found)
return false;
it = it->children[key].get();
}
return (it->end_of_word) ? true : false;
}
#endif // TRIE_H_
/* Copyright 2018 - Dat Nguyen
Trie test
*/
#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"
#include "trie.h"
SCENARIO("Trie operations", "[trie]") {
GIVEN("A Trie Data Structure") {
std::vector<std::string> words {"hello", "test"};
Trie trie(words);
REQUIRE(trie.StartsWithPrefix("hell") == true);
REQUIRE(trie.StartsWithPrefix("helli") == false);
REQUIRE(trie.StartsWithPrefix("test") == true);
REQUIRE(trie.StartsWithPrefix("ab") == false);
trie.Insert("ab");
REQUIRE(trie.StartsWithPrefix("ab") == true);
REQUIRE(trie.IsACompleteWord("ab") == true);
REQUIRE(trie.IsACompleteWord("hell") == false);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.