7
\$\begingroup\$

I recently tried a basic C++ implementation of a Trie, and was looking for some feedback on my code style/choices. In particular I was wondering if I'd made the right choice spitting the program up into header files and using classes instead of structs.

Inside the main.cpp there is a very basic string permutation function that checks, upon each permutation, whether or not the word-prefix is possible (i.e. The permutation "abx" would be terminated). This program looks for words with a minimum length of 4 characters.

Here is a dictionary file.

DictTrie.h

/**
 * File:   DictTrie.h
 * Author: freman
 */

#include <iostream>
#include <vector>
#include "TrieNode.h"

#ifndef DICTTRIE_H
#define DICTTRIE_H

class DictTrie {

public:
    DictTrie();
    virtual ~DictTrie();
    bool containsWord(std::string str);
    bool containsPrefix(std::string str);
    void insert(std::string str);

private:
    TrieNode* root;
};

#endif  /* DICTTRIE_H */

DictTrie.cpp

/**
 * File:   DictTree.cpp
 * Author: freman
 *
 * Created on 18 March 2015, 8:45 AM
 */

#include "DictTrie.h"

using std::string;

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

DictTrie::~DictTrie(){ }

bool DictTrie::containsPrefix(string str) {
    return root->containsPrefix(root, str);
}

bool DictTrie::containsWord(string str) {
    return root->containsWord(root, str);
}

void DictTrie::insert(string str) {
    root->put(root, str);
}

TrieNode.h

/*
 * File:   TrieNode.h
 * Author: freman
 */

#include <vector>
#include <string>

#ifndef TRIENODE_H
#define TRIENODE_H

class TrieNode {
public:
    TrieNode();
    virtual ~TrieNode();
    TrieNode(char letter);
    void put(TrieNode* root, std::string str);
    bool containsWord(TrieNode* root, std::string str);
    bool containsPrefix(TrieNode* root, std::string str);

private:
    char letter;
    bool isWord;
    std::vector<TrieNode*> children;
    void addChild(TrieNode* child);
    TrieNode* contains(TrieNode* root, std::string str);
};
#endif  /* TRIENODE_H */

TrieNode.cpp

/*
 * File:   TrieNode.cpp
 * Author: freman
 */

#include <iostream>
#include "TrieNode.h"

using std::string;
using std::cout;
using std::endl;

TrieNode::TrieNode() { }

TrieNode::~TrieNode() { }

TrieNode::TrieNode(char letter) {
    this->letter = letter;
    isWord = false;
}

bool TrieNode::containsPrefix(TrieNode* root, string str) {
    TrieNode* node = contains(root, str);
    return node != NULL;
}

bool TrieNode::containsWord(TrieNode* root, string str) {
    TrieNode* node = contains(root, str);
    if(node == NULL) {
        return false;
    }
    return node->isWord;
}

TrieNode* TrieNode::contains(TrieNode* root, string str) {
    TrieNode* node = root;
    for(unsigned int i = 0; i < str.length(); i++) {
        bool found = false;
        unsigned int charN = 0;
        while((charN < node->children.size()) && !found) {
            if(node->children.at(charN)->letter == str[i]) {
                found = true;
                node = node->children.at(charN);
            }
            charN++;
        }
        if(!found) {
            return NULL;
        }
    }
    return node;
}

void TrieNode::put(TrieNode* root, string str) {
    TrieNode* node = root;
    for(unsigned int i = 0; i < str.length(); ++i) {
        bool found = false;
        unsigned int charN = 0;
        while((charN < node->children.size()) && !found) {
            if(node->children.at(charN)->letter == str[i]) {
                node = node->children.at(charN);
                found = true;
            }
            charN++;
        }
        if(!found) {
            node->addChild(new TrieNode(str[i]));
            node = node->children.back();
        }
    }
    node->isWord = true;
}

void TrieNode::addChild(TrieNode* child) {
    children.push_back(child);
}

main.cpp

/**
 * File: Main.cpp
 * Author: freman
 */

#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <time.h>

#include "DictTrie.h"

using std::string;
using std::vector;
using std::ifstream;
using std::cout;
using std::endl;

int count;
int words;

void permute(string prefix, string str, DictTrie* trie) {
    if(!trie->containsPrefix(prefix)) {
        return;
    }
    ++count;
    unsigned int length = str.length();

    if(prefix.length() >= 4 && trie->containsWord(prefix)) {
        cout << "Found word: " << prefix << endl;
        ++words;
    }

    if( length != 0 ) {
        for(unsigned int i = 0; i < length; i++) {
            permute(prefix + str.at(i),
                    str.substr(0,i) + str.substr(i+1, length), trie);
        }
    }
}

void permuteStart(string str, DictTrie* trie) {
    permute("", str, trie);
}

DictTrie* readFile(char* filename) {
    DictTrie* trie = new DictTrie();
    string line = "";

    ifstream file(filename);

    if(file.is_open()) {
        while(getline(file, line)) {
            trie->insert(line);
        }
        file.close();
    }
    return trie;
}

int main(int argc, char* argv[]) {
    cout << "Test" << endl;
    count = 0;
    words = 0;

    if(argc != 3) {
        cout << "<progname> <string> <dict_file>" << endl;
        return 1;
    }

    DictTrie* trie = readFile(argv[2]);

    permuteStart(argv[1], trie);
    cout << "Permuted " << count << " times" << endl;
    cout << "Found " << words << " words" << endl;
    return 0;
}
\$\endgroup\$
5
\$\begingroup\$

First thing, memory leak if you delete DictTrie; use a std::unique_ptr to hold the root. Same for the children; use a std::vector<std::unique_ptr<TrieNode> >.

There is no need for the contains functions of TrieNode to take a root for it's first parameter instead use this.

The children vector could be sorted by the letter to allow you to do a binary search for O(log n) per child, or you can use the char value as index and pre-size the vector to 256 for a O(1) lookup per child.

\$\endgroup\$
  • \$\begingroup\$ Oooh nice! Considering the dictionary I input is in alphabetical order I think the children should already be in alphabetical order as well, can't believe I didn't think of a binary search then! Genuis mate :). Also thank you very much for the tips on memory leaks - that's the kind of stuff that I'm unfortunately quite bad at. \$\endgroup\$ – tmck-code Jun 28 '15 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.