Ukkonen's algorithm in C++

Question

Here below is an implementation of the Ukkoken's algorithm in C++. Please review for correctness, robustness and performance.

#include "suffix_tree.h"
#include <cassert>
#include <iostream>
using namespace std;

class node
{
public:
    node();
    ~node();
    int m_begin;
    int m_end;
    node* m_parent;
    node* m_first_child;
    node* m_sibling;
    node* m_suffix_link;
};

class suffix_tree_impl
{
public:
    suffix_tree_impl(string s);
    ~suffix_tree_impl();
private:
    char first_char(node* node);
    int length(node* node, int implicit_end);
    string m_s;
    node* m_root;
};

node::node() : m_begin(0), m_end(0), m_parent(nullptr), m_first_child(nullptr), m_sibling(nullptr), m_suffix_link(nullptr)
{

}

node::~node()
{
    if (this->m_first_child != nullptr)
    {
        delete this->m_first_child;
    }
    if (this->m_sibling != nullptr)
    {
        delete this->m_sibling;
    }
}

suffix_tree_impl::suffix_tree_impl(string s) : m_s(s)
{
    node* node_cursor;
    int edge_cursor;
    node* next_node_cursor;
    int next_text_cursor;
    int implicit_end;
    node* last_internal_node;

    this->m_root = new node();
    node_cursor = nullptr;
    next_node_cursor = nullptr;
    last_internal_node = nullptr;
    int start = 0;
    for (int end = 1; end <= s.length(); end++)
    {
        next_node_cursor = this->m_root;
        next_text_cursor = start;
        implicit_end = end;
        for (; start < end; start++)
        {
            bool no_op_applied = false;

            node_cursor = next_node_cursor;
            start = next_text_cursor;
            edge_cursor = 0;

            int text_cursor = start;
            next_node_cursor = this->m_root;
            next_text_cursor = start + 1;
            while (text_cursor < end - 1)
            {
                int node_length = length(node_cursor, implicit_end);
                if (edge_cursor == node_length)
                {
                    if (node_cursor->m_suffix_link != nullptr)
                    {
                        next_node_cursor = node_cursor->m_suffix_link;
                        next_text_cursor = text_cursor - 1;
                    }

                    char next_char = this->m_s[text_cursor];
                    node* child_cursor = node_cursor->m_first_child;
                    while (true)
                    {
                        assert(child_cursor != nullptr);
                        if (this->first_char(child_cursor) == next_char)
                        {
                            node_cursor = child_cursor;
                            edge_cursor = 0;
                            break;
                        }
                        else
                        {
                            child_cursor = child_cursor->m_sibling;
                        }
                    }
                }
                else
                {
                    int text_move = end - 1 - text_cursor;
                    int edge_move = node_length - edge_cursor;
                    int move = text_move > edge_move ? edge_move : text_move;
                    edge_cursor += move;
                    text_cursor += move;
                }
            }

            char next_text_char = this->m_s[end - 1];
            node* search_end = nullptr;
            node* new_internal_node = nullptr;
            if (edge_cursor == length(node_cursor, implicit_end))
            {
                if (node_cursor != this->m_root && node_cursor->m_first_child == nullptr)
                {
                }
                else
                {
                    node* search = node_cursor->m_first_child;
                    bool found = false;
                    while (search != nullptr)
                    {
                        if (first_char(search) == next_text_char)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            search = search->m_sibling;
                        }
                    }
                    if (found)
                    {
                        no_op_applied = true;
                    }
                    else
                    {
                        node* new_leaf = new node();
                        new_leaf->m_begin = end - 1;
                        new_leaf->m_parent = node_cursor;
                        new_leaf->m_sibling = node_cursor->m_first_child;
                        node_cursor->m_first_child = new_leaf;
                    }
                }
                search_end = node_cursor;
            }
            else
            {
                char next_tree_char = this->m_s[node_cursor->m_begin + edge_cursor];
                if (next_text_char == next_tree_char)
                {
                    no_op_applied = true;
                }
                else
                {
                    node* new_node = new node();
                    node* new_leaf = new node();
                    new_leaf->m_begin = end - 1;
                    new_node->m_begin = node_cursor->m_begin;
                    new_node->m_end = node_cursor->m_begin + edge_cursor;
                    node_cursor->m_begin = node_cursor->m_begin + edge_cursor;

                    new_node->m_parent = node_cursor->m_parent;
                    new_leaf->m_parent = new_node;
                    node_cursor->m_parent = new_node;

                    new_node->m_sibling = new_node->m_parent->m_first_child;
                    new_node->m_parent->m_first_child = new_node;

                    node* search = new_node;
                    while (search != nullptr)
                    {
                        if (search->m_sibling == node_cursor)
                        {
                            search->m_sibling = search->m_sibling->m_sibling;
                            break;
                        }
                        search = search->m_sibling;
                    }

                    new_node->m_first_child = new_leaf;
                    new_leaf->m_sibling = node_cursor;
                    node_cursor->m_sibling = nullptr;

                    new_internal_node = search_end = new_node;
                }
            }

            if (last_internal_node != nullptr)
            {
                assert(last_internal_node->m_suffix_link == nullptr);
                assert(search_end != nullptr);
                last_internal_node->m_suffix_link = search_end;
                last_internal_node = nullptr;
            }

            if (new_internal_node != nullptr)
            {
                last_internal_node = new_internal_node;
            }

            if (no_op_applied)
            {
                break;
            }
        }
    }
}

int suffix_tree_impl::length(node* node, int implicit_end)
{
    if (node == this->m_root)
    {
        return 0;
    }
    else if (node->m_first_child == nullptr)
    {
        return implicit_end - node->m_begin;
    }
    else
    {
        return node->m_end - node->m_begin;
    }
}

char suffix_tree_impl::first_char(node* node)
{
    return this->m_s[node->m_begin];
}

suffix_tree_impl::~suffix_tree_impl()
{
    delete this->m_root;
}

suffix_tree::suffix_tree(string s) : m_impl(new suffix_tree_impl(s))
{

}

suffix_tree::~suffix_tree()
{
    delete this->m_impl;
}

Answer 1

A couple of notes about idiomatic code writing.

1. Checking that a pointer isn't null before deleting it is needlessly verbose. If the parameter of the delete expression is null, it will be a no-op by definition.

2. You use both a naming convention stating with m_ for data members, and access them via this->. That is again needlessly verbose, since either will distinguish them as members. I recommend you choose one and stick to it.

3. In your c'tor you declare all your variables at the top of the function, uninitialized, and then proceeds to assign to them, again at the top. This is unidiomatic even in c nowadays. You should move each variable to the smallest scope where it is needed, and be sure to declare it with initialization. You seem to be doing that with some of the variables in your deeply nested loops, already.

4. Continuing with the previous line of thought, that is one big constructor body. It does a lot of things. And to do those, you have very deeply nested loops. This makes reasoning about the code, let alone maintaining it later, that much more difficult. Break the c'tor body into smaller functions. Give those functions meaningful names, and perhaps even break those down further. It's very hard to understand what you code does, as it is written now. To contrast, if it was written as

   for(; start < end; start++) {
     bool found = find_existing_node_for_suffix(/* ... */);
     // More things
   }
   

   Then you would know at a glance what the loop does first. You may not know if it does it well yet when debugging, but you'd have a name for that operation right in front of you. Furthermore, you'd be able to reason about that named operation, and improve it, in isolation.

   Functions aren't just for encapsulating repetitive tasks, they are to name actions. Naming an action abstracts the details away, and allows to understand what the code around it does on a higher level.

Answer 2

I'll do a partial review, just of class node. There's lessons there that are useful and applicable to the rest of the code:

class node
{
public:
    node();
    ~node();
    int m_begin;
    int m_end;
    node* m_parent;
    node* m_first_child;
    node* m_sibling;
    node* m_suffix_link;
};

node::node() : m_begin(0), m_end(0), m_parent(nullptr), m_first_child(nullptr), m_sibling(nullptr), m_suffix_link(nullptr)
{

}

node::~node()
{
    if (this->m_first_child != nullptr)
    {
        delete this->m_first_child;
    }
    if (this->m_sibling != nullptr)
    {
        delete this->m_sibling;
    }
}

Firstly, a class that's all public is usually written struct. In this case, it appears that it isn't intended to be user-visible, so perhaps it should be an inner class to the suffix_tree_impl which is its only client.

We can provide initializers for the members, and avoid the need to write our own constructor:

struct node
{
    ~node();
    int m_begin = 0;
    int m_end = 0;
    node* m_parent = {};
    node* m_first_child = {};
    node* m_sibling = {};
    node* m_suffix_link = {};
};

The destructor gives us a clue that m_first_child and m_sibling are owning pointers, and that m_parent and m_suffix_link are non-owning. This signals to us that the compiler-generated default copy/move constructors and assignment operators will break our invariants (in this case, causing a double free).

We could write our own versions of these methods - but if we did, then we'd need to maintain them. Instead, we can use smart pointers and the Rule of Zero, to make copying do the Right Thing without any ongoing responsibility on our part:

#include <memory>
struct node
{
    int m_begin = 0;
    int m_end = 0;
    node* m_parent = {};
    std::unique_ptr<node> m_first_child = {};
    std::unique_ptr<node> m_sibling = {};
    node* m_suffix_link = {};
};

Look, no methods!