main.cpp

//
//  main.cpp
//  TrieTree Test Driver
//
//  Created by Zac Holland on 3/8/16.
//  Copyright © 2016 Diericx. All rights reserved.
//

#include <iostream>

#include "Trie.hpp"

using namespace std;

int main(int argc, const char * argv[]) {
    Trie tree;

    tree.add("poop");
    tree.add("happy");
    tree.add("rap");
    tree.add("ra");
    tree.add("rapper");
    
    cout << tree << endl;

    return 0;
}

Trie.cpp

//
//  Trie.cpp
//  ZacTrie
//
//  Created by Zac Holland on 3/8/16.
//  Copyright © 2016 Diericx. All rights reserved.
//

#include "Trie.hpp"

#include <vector> // Only needed for operator <<

// -----------------------------------------------------------------------------

TrieNode::TrieNode() {
    count = 0;
    childTries = new TrieNode*[NCHARS];
    
    for (int i = 0; i < NCHARS; i++)  // Be safe against non-standard compilers!
        childTries[i] = NULL;
}

/* First destroy all the children :-( of this TrieNode - Note that this will
 * recursively call the destructor for their descendants. Then free up the
 * array of children.
 */
TrieNode::~TrieNode() {
    for (int c = 0; c < NCHARS; c++)
        if (childTries[c] != NULL) {
            // cout <<"Deleting node " << (char) c << ": " <<childTries[c]->count <<endl; ////
            delete childTries[c];
        }
    
    delete [] childTries;
}

TrieNode *TrieNode::getChild(unsigned char c) {
    return childTries[c];
}

TrieNode *TrieNode::setChild(unsigned char c, TrieNode *child) {
    if (childTries == NULL) // shouldn't happen
        childTries = new TrieNode*[NCHARS];
    childTries[c] = child;
    
    return child;
}

// -----------------------------------------------------------------------------

Trie::Trie() {
    root = new TrieNode;
}

Trie::~Trie() {
    delete root;
}

/* Descend into the trie starting at the root and traversing one char
 * per level starting at s[start]. Create child nodes as necessary along the
 * way. Return the node at which string s runs out or maxChars have been
 * descended - whichever is earlier.
 *
 * NOTE: start indexes into the string at position 0, not 1.
 */
TrieNode *Trie::descendInto(const string &s, int startNdx, int numChars) {
    TrieNode *currLocation = root;
    for (int i = startNdx; i < s.length() && i < startNdx+numChars; i++) {
        unsigned char c = (unsigned char) s[i];
        
        TrieNode *p = currLocation->getChild(c);
        if (p == NULL)
            currLocation->setChild(c, new TrieNode);
        currLocation = currLocation->getChild(c);
    }
    
    return currLocation;
}

TrieNode *Trie::descendIntoWithoutAdding(const string &s, int startNdx, int numChars) const {
    if (startNdx + numChars > s.length()) return NULL;

    TrieNode *currLocation = root;
    for (int i = startNdx; i < s.length() && i < startNdx+numChars; i++) {
        unsigned char c = (unsigned char) s[i];
        if ((currLocation = currLocation->getChild(c)) == NULL)
            return NULL;
    }
    
    return currLocation;
}

/* Add the entire word, regardless of length, into the Trie
 * Iterative implementation.

void Trie::add(const string& s) {
    descendInto(s)->incr();
}
 */

/* Add num chars of string s, starting at s[start] into the Trie. If the string 
 * runs out before len, simply insert the entire string.
 */
void Trie::add(const string& s, int start, int numChars) {
    TrieNode *p = descendInto(s, start, numChars);
    
    if (p != NULL) p->incr();
    return;
}

/* Return the entry of the given string in this Trie. If the string does not
 * exist in the Trie, its frequency is zero implicitly.
 */
int Trie::getCount(const string& s) const {
    TrieNode *p = descendIntoWithoutAdding(s);
    return p? p->getCount() : 0;
}

/* Return the entry in this Trie of the given substring starting at index
 * start of s, and spanning num chars. If the substring does not
 * exist in the Trie, its frequency is zero implicitly.
 */
int Trie::getCount(const string& s, int start, int num) const {
    TrieNode *p = descendIntoWithoutAdding(s, start, num);
    return p? p->getCount() : 0;
}

/* Add all of the strings below the given node into the given vector and return.
 * Static method - needs to be passed a TrieNode to descend.
 *
 * NOTE: You'll see the strings are built up as the recursion unwinds. Thus,
 * to keep the stringbuilding linear, we'll build them up in reverse as
 * we wind back up the trie. It's up to the caller to reverse all the strings
 * before output or downstream processing.
 */
void Trie::vectorize(TrieNode *subTree, vector<TrieEntry>& entries) {
    for (int c = 0; c < NCHARS; c++) {
        TrieNode *child = subTree->getChild(c);
        if (child == NULL) continue;
        
        if (child->getCount() > 0)
            entries.push_back(TrieEntry(string("") + (char) c, child->getCount()));
        
        vector<TrieEntry> subEntries;
        vectorize(child, subEntries);
        
        for (unsigned long i = 0; i < subEntries.size(); i++) {
            subEntries[i].str.push_back(c);
            entries.push_back(TrieEntry(subEntries[i].str, subEntries[i].frequency));
        }
    }
}

ostream& operator<<(ostream &os, const Trie& tree) {
    vector<TrieEntry> entries;
    
    Trie::vectorize(tree.root, entries);

    for (int i = 0; i < entries.size(); i++)
        os << entries[i].toString() << endl;
    
    return os;
}

// -----------------------------------------------------------------------------

Trie.hpp

//
//  Trie.hpp
//  ZacTrie
//
//  Created by Zac Holland on 3/8/16.
//  Copyright © 2016 Diericx. All rights reserved.
//

#ifndef Trie_hpp
#define Trie_hpp

#include <string>
#include <iostream>
#include <vector> // Needed only for output using addAllEntries()

using namespace std;

const int NCHARS = 256;

// -----------------------------------------------------------------------------

class TrieNode {
private:
    int count;
    TrieNode **childTries;
    
public:
    TrieNode();
    ~TrieNode();
    
    TrieNode *getChild(unsigned char c);
    TrieNode *setChild(unsigned char c, TrieNode *child);
    
    void incr() { count++; }
    void decr() { count--; }
    int getCount() const { return count; }
    void setCount(int n) { count = n; }
};

// -----------------------------------------------------------------------------

struct TrieEntry {
    string str;
    int frequency;
    
    TrieEntry(string s, int f): str(s), frequency(f) {}
    string toString() const {
        string s = str;
        reverse(s.begin(), s.end());
        return to_string(frequency) + " : " + s;
    }
};

class Trie {
private:
    TrieNode *root;
    
    TrieNode *descendInto(const string& s, int start = 0, int numChars = INT_MAX);
    TrieNode *descendIntoWithoutAdding(const string& s, int start = 0, int numChars = INT_MAX) const;
    
public:
    Trie();
    ~Trie();
    
    void add(const string& s, int start = 0, int numChars = INT_MAX);
    
    int getCount(const string& s) const;
    int getCount(const string& s, int start, int numChars = INT_MAX) const;
    
    static void vectorize(TrieNode *subTree, vector<TrieEntry>& entries);
    
    friend ostream& operator<<(ostream& os, const Trie& trie);
};

// -----------------------------------------------------------------------------

#endif /* Trie_hpp */