3
\$\begingroup\$

I'm just starting to use C++ so beginner feedback is fine here.

CPP code

(main.cpp, node.h, node.cpp, trie.h, trie.cpp, utils.h)

main.cpp

#define BOOST_PYTHON_STATIC_LIB
#include <string>
#include "boost/python.hpp"
#include "boost/python/module.hpp"

#include "trie.h"


BOOST_PYTHON_MODULE(ptrie)
{
    using namespace boost::python;
    class_<Trie>("Trie", init<>())
        .def("show", &Trie::show)
        .def("insert", &Trie::add_word)
        .def("words_after", &Trie::words_after)
        .def("get_words_after", &Trie::get_words_after)
        .def("string", &Trie::as_string)
        .def("contains", &Trie::contains);
}

node.h

#pragma once
#include <vector>
#include <memory>


// Node class. Stored within a trie

class Node
{
public:
    Node * parent;
    std::vector<std::unique_ptr<Node>> children;
    bool terminal;
    char character;
    unsigned int depth;

    Node();  // Assumes top node
    Node(Node * p, bool t, char c);  // Child node

    void show();
    void add_data_to_string(std::string * str);
    std::unique_ptr<Node>* trace(std::string str);
    std::string back_trace();
    void add_word(std::string str);
    long words_after();
    void add_words_after(std::vector<std::string> * w);

private:
    void words_after(long * count);
    void back_trace(std::string * str);
};

node.cpp

#include <string>
#include <iostream>

#include "node.h"


Node::Node()
{
    parent = nullptr;
    terminal = false;
    character = 0;
    depth = 0;
}

Node::Node(Node * p, bool t, char c)
{
    parent = p;
    terminal = t;
    character = c;
    depth = p->depth + 1;
}

void Node::show()
{
    for (unsigned int i = 0; i < depth; ++i)
    {
        printf("-");
    }
    if (!terminal) std::cout << character << std::endl;
    else std::cout << character << "* (" << back_trace() << ")" << std::endl;
    for (unsigned int n = 0; n < children.size(); ++n)
    {
        children[n]->show();
    }
}

void Node::add_data_to_string(std::string * str)
{
    for (unsigned int i = 0; i < depth; ++i)
    {
        *str += "-";
    }
    if (character != 0) 
    { 
        *str += character;
        if (!terminal) *str += "\n";
        else *str += "* (" + back_trace() + ")\n"; // a little inefficient right now, but it'll do
        // it's much slower than a better solution but it barely puts a dent on performance
    }
    for (unsigned int n = 0; n < children.size(); ++n)
    {
        children[n]->add_data_to_string(str);
    }
}

std::unique_ptr<Node> * Node::trace(std::string str)
{
    for (unsigned int n = 0; n < children.size(); ++n)
    {
        if (children[n]->character == str.at(0))
        {
            str.erase(str.begin());
            if (!str.length()) return &children[n];
            else return children[n]->trace(str);
        }
    }
    // No match
    return nullptr;
}

std::string Node::back_trace()
{
    std::string str("");
    back_trace(&str);
    std::reverse(str.begin(), str.end());
    return str;
}

void Node::add_word(std::string str)
{
    for (unsigned int n = 0; n < children.size(); ++n)
    {
        if (children[n]->character == str.at(0))
        {
            str.erase(str.begin());
            if (!str.length())
            {
                children[n]->terminal = true;
                return;
            }
            else return children[n]->add_word(str);
        }
    }
    // going down a new path if this point is reached
    children.push_back(std::make_unique<Node>(this, false, str.at(0)));
    str.erase(str.begin());
    if (!str.length())
    {
        children.back()->terminal = true;
        return;
    }
    else return children.back()->add_word(str);
}

long Node::words_after()
{
    // Returns the amount of words that can be found as children or children of children...
    // after this node. includes this node. if this node is a word it will be counted
    long count(0);
    words_after(&count);
    return count;
}

void Node::add_words_after(std::vector<std::string>* w)
{
    if (terminal) (w->push_back(back_trace()));
    for (unsigned int n = 0; n < children.size(); ++n) children[n]->add_words_after(w);
}

void Node::words_after(long * count)
{
    if (terminal) (*count)++;
    for (unsigned int n = 0; n < children.size(); ++n)
    {
        children[n]->words_after(count);
    }
}

void Node::back_trace(std::string * str)
{
    if (parent == nullptr) return;
    *str += character;
    parent->back_trace(str);
}

trie.h

#pragma once


#include "node.h"


class Trie
{
public:

    Trie();

    Trie(Trie const &_copy);

    void show();
    void add_word(std::string str);
    bool contains(std::string str);
    long words_after(std::string str = "");
    std::string as_string();
    boost::python::list get_words_after(std::string str = "");

private:
    std::vector<std::string> add_history;
    Node top_node;
    std::unique_ptr<Node> * current_node; // Not used for anything particular just yet
};

trie.cpp

#define BOOST_PYTHON_STATIC_LIB
#include <memory>
#include "boost/python.hpp"
#include "boost/python/list.hpp"

#include "trie.h"
#include "utils.h"


Trie::Trie()
{
    top_node = Node();
    current_node = nullptr;
}

Trie::Trie(Trie const & _copy)
{
    top_node = Node();
    current_node = nullptr;
    for (unsigned int i = 0; i < _copy.add_history.size(); ++i)
    {
        add_word(add_history[i]);
    }
}

void Trie::show()
{
    top_node.show();
}

void Trie::add_word(std::string str)
{
    top_node.add_word(str);
    add_history.push_back(str);
}

bool Trie::contains(std::string str)
{
    // We can do this the lazy way (std::vector<string> add_history) or the proper way.
    std::unique_ptr<Node> * n = top_node.trace(str);
    if (n == nullptr) return false;
    else return (*n)->terminal;
}

long Trie::words_after(std::string str)
{
    // Find the node that the current str refers to
    if (!str.length()) return top_node.words_after();
    std::unique_ptr<Node> * cn = top_node.trace(str);
    if (cn == nullptr) return 0;
    else return (*cn)->words_after();
}

std::string Trie::as_string()
{
    std::string str("");
    top_node.add_data_to_string(&str);
    return str;
}

boost::python::list Trie::get_words_after(std::string str)
{
    std::vector<std::string> words;
    if (!str.length())
    {
        top_node.add_words_after(&words);
        return toPythonList(words);
    }
    std::unique_ptr<Node> * cn = top_node.trace(str);
    if (cn == nullptr) return boost::python::list(); // nothing
    (*cn)->add_words_after(&words);
    return toPythonList(words);
}

utils.h

#define BOOST_PYTHON_STATIC_LIB
#pragma once
#include "boost/python.hpp"
#include "boost/python/list.hpp"


template <class T>
boost::python::list toPythonList(std::vector<T> vec)
{
    typename std::vector<T>::iterator iter;
    boost::python::list ret;
    for (iter = vec.begin(); iter != vec.end(); ++iter)
    {
        ret.append(*iter);
    }
    return ret;
}

Python code (not that important)

PyTrie.py

from typing import List

from loader import Trie as Trie_


class Trie:

    def __init__(self) -> None:
        self.trie = Trie_()

    def insert(self, word: str) -> None:
        if not word.lower().strip():
            raise ValueError("Bad word.")
        self.trie.insert(word.lower().strip())

    def show(self) -> None:
        self.trie.show()

    def words_after(self, substr: str) -> int:
        return self.trie.words_after(substr)

    def get_words_after(self, substr: str) -> List[str]:
        return self.trie.get_words_after(substr)

    def __contains__(self, val: str) -> bool:
        return self.trie.contains(val)

    def __str__(self) -> str:
        return self.trie.string()

C++

Design choices

  • Abstraction from Node to Trie because it provides more flexibility (Analogy: It's easier to get information about a tree data structure when view the tree from afar than when climbing the tree.) Would you have done things differently here?
  • See long Trie::as_string there is definition std::string str(""); and then I pass the pointer to void Node::add_data_to_string(std::string * str); via top_node.add_data_to_string(&str). Inside Node::add_data_to_string it derefences str and appends relevant information to it and calls its children recursively, all of which add their information. This seemed the obvious design choice but it seems a little 'awkward'. Maybe it's because I'm not used to this. I do similar things in other methods such as long Node::words_after(); and void Node::words_after(long * count);. What is the best way?

Challenges

  • For my copy constructor for Trie I cheated a little and stored appended words in a std::vector<std::string> add_history; (private member of Trie). In retrospect, making a copy constructor for Node and recursively adding to the new Trie seems to make more sense. Advice?

C++ best practices

  • I don't know of something like a PEP8 or strict guidelines for C++ like there is for Python. Prior advice I have received is to not do ClassName * var due to that leading to ambiguity. VS 2017 seems to enforce that and I'm not sure how to turn it off. Any other little things I should be aware of?

Program bugs

  • I'm not sure of any problems in the program. Could there be a memory leak or something? I'm not sure. You tell me :)

Python

Design choices

  • Since I'm not skilled at C++ I opted to make simple class methods for C++ without input checking, etc. All that should be done by the Python wrapper.
  • loader.py I haven't included because I don't think it's important here. It just automatically imports the module ptrie.pyd depending on your detected python version (32 vs 64) bit. What do you think?

Python best practices

  • I'm unsure about how sound import Trie as Trie_ is. Seems to be fine on the surface. Is it?
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.