4
\$\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?
Improve this question
\$\endgroup\$
0

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.