Summary

This repository contains the implementation of a Trie data structure and a variation called a DataTrie. The DataTrie is a Trie where the nodes which mark the end a string also hold data. This is to provide an alternative to using std::unordered_map or std::map with string keys.

More Info:

• Wikipedia
• Visualization

Integration

Note that these data sctructures are designed for C++14

Trie

#include <Trie/Trie.h>

Instantiation examples:

Trie< char > charTrie;

Trie< char16_t > char16Trie;

Trie< char32_t > char32Trie;

Trie< wchar_t > wcharTrie;

DataTrie

#include <Trie/DataTrie.h>

Instantiation examples:

struct SomeData
{
  int someVariable;
  // ...
};

DataTrie< char, std::shared_ptr< SomeData > > charDataTrie;

DataTrie< char16_t, SomeData > char16DataTrie;

DataTrie< char32_t, std::function< bool(SomeData const&) > > char32DataTrie;

DataTrie< wchar_t, std::wstring > wcharDataTrie;

Custom

To create a Trie variation:

1. Create a DerivedTrieNode class which extends TrieNode or DataTrieNode
2. Create a DerivedTrie class which extends BasicTrie< DerivedTrieNode< ... >, CharTy >

#include <Trie/BasicTrie.h>

Running Tests

$ cmake .
$ cmake --build .
$ ctest -VV --output-on-failure