fast hashset for character arrays.

Trie.cpp

//
//  Trie.cpp
//  CPPTest
//
//  Created by Eric Fruchter on 12/26/15.
//  Copyright © 2015 Eric Fruchter. All rights reserved.
//

#include "Trie.hpp"

TrieNode::TrieNode() {
    count = 0;
}

void TrieNode::count_word(const char* word, const long start_index, const long length) {
    if (start_index + 1 == length) {
        count++;
        return;
    }
    
    int index_next = char_to_index(word[start_index + 1]);
    
    if (children[index_next] == nullptr) {
        children[index_next] = std::unique_ptr<TrieNode>(new TrieNode());
    }
    
    children[index_next]->count_word(word, start_index + 1, length);
}

int TrieNode::get_count(const char* word, const long start_index, const long length) const {
    if (start_index + 1 == length) {
        return count;
    }
    
    int index_next = char_to_index(word[start_index + 1]);
    
    if (children[index_next] == nullptr) {
        return 0;
    }
    
    return children[index_next]->get_count(word, start_index + 1, length);
}


Trie::Trie() {
    root = std::unique_ptr<TrieNode>(new TrieNode());
}

void Trie::add_word(const char* word) {
    add_word(word, 0, strlen(word));
}

void Trie::add_word(const char* word, const long start_index, const long length) {
    root->count_word(word, start_index - 1, length);
}

int Trie::get_count(const char* word) const {
    return get_count(word, 0, strlen(word));
}

int Trie::get_count(const char* word, const long start_index, const long length) const {
    return root->get_count(word, start_index - 1, length);
}

Trie.hpp

//
//  Trie.hpp
//  CPPTest
//
//  Created by Eric Fruchter on 12/26/15.
//  Copyright © 2015 Eric Fruchter. All rights reserved.
//

#ifndef Trie_hpp
#define Trie_hpp

#include <stdio.h>
#include <memory>

#define TRIE_A_INT ((int) 'a')
#define TRIE_Z_INT ((int) 'z')
#define TRIE_ALPHABET_SIZE (TRIE_Z_INT - TRIE_A_INT)

inline int char_to_index(char c) {
    return (((int) c) - TRIE_A_INT);
}

struct TrieNode {
    std::unique_ptr<TrieNode[]> children[TRIE_ALPHABET_SIZE];
    int count;
    
    TrieNode();
    void count_word(const char* word, const long start_index, const long length);
    int get_count(const char* word, const long start_index, const long length) const;
};

class Trie {
public:
    Trie();
    void add_word(const char* word);
    void add_word(const char* word, const long start_index, const long length);
    
    int get_count(const char* word) const;
    int get_count(const char* word, const long start_index, const long length) const;
private:
    std::unique_ptr<TrieNode> root;
};


#endif /* Trie_hpp */