3
\$\begingroup\$

I have just implemented a simple model of binary search tree. It can store template values with unique keys. All implementation is encapsulated so there's no access to nodes.

#define RZD_BEGIN namespace rzd {
#define RZD_END }
#define ANYWAY
#define THEN

#include <list>
#include <memory>
#include <optional>

RZD_BEGIN

using std::list;
using std::optional;

// binary search tree
template <typename T>
class Tree
{
    // prototype
    struct Node;

    // aliases
    using pointer = std::shared_ptr<Node>;
    using pair = std::pair<int, T>;

    // unit of tree
    struct Node {
        pair data;
        pointer left;
        pointer right;
        Node(pair data) : data{ data }, left{ nullptr }, right{ nullptr } {}
    };

    // start point
    pointer root;

    //  IF      CONDITION                           ACTION

    void _insert(pointer& leaf, const pair data)
    {
        if      (!leaf)                             leaf = pointer{ new Node{ data } };
        else if (data.first < leaf->data.first)     _insert(leaf->left, data);
        else if (data.first > leaf->data.first)     _insert(leaf->right, data);
        else                                        leaf->data.first = data.first;
    }

    pointer _find(const pointer& leaf, const int key) const
    {
        if      (!leaf || leaf->data.first == key)  return leaf;
        else if (key < leaf->data.first)            return _find(leaf->left, key);
        else                                        return _find(leaf->right, key);
    }

    pointer _minimum(const pointer& leaf) const
    {
        if      (leaf->left)                        return _minimum(leaf->left);
        else                                        return leaf;
    }

    void _remove(pointer& leaf, const int key)
    {
        if      (!leaf)                             return;
        else if (key < leaf->data.first)            _remove(leaf->left, key);
        else if (key > leaf->data.first)            _remove(leaf->right, key);
        else if (leaf->left && leaf->right) {
            THEN                                    leaf->data.first = _minimum(leaf->right)->data.first;
            THEN                                    _remove(leaf->right, leaf->data.first);
        }
        else if (leaf->left)                        leaf = leaf->left;
        else if (leaf->right)                       leaf = leaf->right;
        else                                        leaf = nullptr;
    }

    void _clear(pointer& leaf)
    {
        if      (leaf) {
            THEN                                    _clear(leaf->left);
            THEN                                    _clear(leaf->right);
            THEN                                    leaf = nullptr;
        }
    }

    int _size(const pointer& leaf) const
    {
        if      (leaf)                              return _size(leaf->left) + 1 + _size(leaf->right);
        else                                        return 0;
    }

    list<pair>& _get_list(const pointer& leaf, list<pair>& list) const
    {
        if      (leaf) {
            THEN                                    _get_list(leaf->left, list);
            THEN                                    list.push_back(leaf->data);
            THEN                                    _get_list(leaf->right, list);
        }
        ANYWAY                                      return list;
    }

public:

    // inserts new node with key and value
    inline void insert(const int key, const T& value)
    {
        ANYWAY                                      _insert(root, pair{ key, value });
    }

    // returns optional value by key
    inline optional<T> find(const int key) const
    {
        if      (pointer leaf = _find(root, key))   return { leaf->data.second };
        else                                        return {};
    }

    // removes node by key
    inline void remove(const int key)
    {
        ANYWAY                                      _remove(root, key);
    }

    inline void clear()
    {
        ANYWAY                                      _clear(root);
    }

    // returns number of nodes
    inline int size() const
    {
        ANYWAY                                      return _size(root);
    }

    // returns sorted list 
    inline list<pair> get_list() const
    {
        ANYWAY                                      return _get_list(root, list<pair>());
    }

    // returns optional value by key
    inline optional<T> operator[](const int key)
    {
        ANYWAY                                      return find(key);
    }

    // constructors

    Tree() : root{ nullptr } {}

    Tree(const int key, const T& value) : root{ new Node{ pair{ key, value } } } {}

};

RZD_END

I use optional class from C++17 for find method. It supported by gcc 7.1 and latest vs compiler. Usage:

rzd::Tree<std::string> tree;

tree.insert(42, "root");
tree.insert(41, "foo");
tree.insert(43, "bar");

std::cout << tree[42].value() << "\n";
std::cout << tree.find(41).value() << "\n";
std::cout << tree[43].value() << "\n";
std::cout << tree << "\n";

tree.remove(42);
std::cout << tree[42].value_or("not found") << "\n";

I'm interested in bug fixes, optimisations, std library usages and maybe better solutions for storing data.

\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Peilonrayz Jun 16 '17 at 10:39
  • \$\begingroup\$ @Peilonrayz Will you let me slightly update not mentioned parts of code? \$\endgroup\$ – lisovskey Jun 16 '17 at 10:50
  • \$\begingroup\$ I'd recommend not doing that, but I can't stop you. If I were you, I'd write the code to the best of your abilities, give it a couple of days, go over it again fixing any problems. If you've not changed anything post it as a follow up question. \$\endgroup\$ – Peilonrayz Jun 16 '17 at 10:53
  • \$\begingroup\$ @Peilonrayz Forgive me for the first time \$\endgroup\$ – lisovskey Jun 16 '17 at 11:01
  • \$\begingroup\$ I don't know what you want me to forgive... But you're forgiven, :) \$\endgroup\$ – Peilonrayz Jun 16 '17 at 11:03
2
\$\begingroup\$

Let me explain the layout problem in much more detail. It will need some of your cooperation.

Some assumptions:

People generally use a wide screen, with 16:9 aspect ratio. Some people use more than one, or some use ultra wide. As a result, to read full horizontal line one will need head movement.

Assuming that average programmers uses chair with some back support, the head is fixed in one position. Navigating through the code vertically requires only mouse scrolling, whereas horizontal navigation requires head movement. Moving head is arguably much harder than slightly moving a finger. Also, muscles of a finger are much more suited to extensive movement, unlike neck.

Code Review:

  • Weird usage of BEGIN and END

XXX_BEGIN (pun not intended) is usually used in some standard library implementation. Though the way they use it is very different. The macro is usually a product of some concatenation of current version, current ABI (not API!) version and what not. namespace xxx reads much better and less diverts with the surrounding.

  • No possible way to safely iterate a tree

Usually people would want to just iterate the tree. Currently there is no straightforward way to do it (well, one can keep increasing key while optional doesn't contain value), but if someone removes a node, it won't be possible to iterate it in a safe manner at all. I recommend providing an in-order traversal iterator. Thus, traversing it becomes much like traversing a set, because in-order traversal means that elements will come out ordered.

  • Lost and forgotten constructor

    Tree(const int key, const T& value) : root{ new Node{ pair{ key, value } } } {}
    

The constructor looks really weird. I'd expect at least std::initializer_list based one and one with ranges denoted by iterators. Not to be offensive, but the constructor made my day.

Better approach:

I think that using int as a key is not a good idea. It would be better to just use the T objects for ordering and layout. Usually access in C++ is done by iterators, for which most of the data structures are optimized for in standard library implementations. If being and end are provided, one can just use std::advance<>() or std::next<>() to make pseudo index based access.

Also the recursion could be transformed into a loop, but that might be slightly more costly in engineering costs.

\$\endgroup\$
  • \$\begingroup\$ Can you explain why it is a redundant delegation? My private methods are recursive so how should I fix it? About layout: yes, everything is clearly understandable for me, this code is written this way experimentally, and to save some space I had to use XXX_BEGIN. Constructor: okay, it was not a good idea. Iterators and template key: this night I have added these features so my tree became like std::map. almost. \$\endgroup\$ – lisovskey Jun 17 '17 at 17:50
  • \$\begingroup\$ yes, you're right about recursing functions, but you could still implement them as a loop (I'll remove wrong part in the morning). Ideally it should become like set (I meant that T itself should be a key), but if there is another template parameter for the key, then sure. Also you might want to have a look at red black trees. \$\endgroup\$ – Incomputable Jun 17 '17 at 21:44
  • \$\begingroup\$ Maybe you'd wish to see the updated version? Waiting for pull request :) \$\endgroup\$ – lisovskey Jun 18 '17 at 13:17
  • \$\begingroup\$ seems ok. I'll give it closer look tomorrow. \$\endgroup\$ – Incomputable Jun 18 '17 at 18:11
7
\$\begingroup\$

That code makes my eyes bleed.

  1. What is the purpose of the macros. They are completely useless and even worse obfuscating the real code. Anyone reading the code will wonder what ANYWAY and THEN are. Just burn them with fire.

  2. Do not put if else and friends on the same line as the body. This is a terrible practice that renders code flow completely unreadable. Is this a strange condition, a long statement. Are there multiple statements. It is just a mess. One statement one line.

  3. As far as i know leading underscores are illegal, so maybe just depend on your namespace

\$\endgroup\$
  • \$\begingroup\$ I know all these code conventions, and don't lie to yourself, everything is clear if you just get used to this style and see to the top of the header to figure out what is ANYWAY. If not, so sorry, I've asked about logic but not about code conventions. \$\endgroup\$ – lisovskey Jun 15 '17 at 17:39
  • 4
    \$\begingroup\$ The point about code style is that you should NOT have to get used to it. That is literally the only reason there are code styles. \$\endgroup\$ – miscco Jun 15 '17 at 17:46
  • \$\begingroup\$ Okay I understand it. What can you propose instead leading underscores? \$\endgroup\$ – lisovskey Jun 15 '17 at 18:00
  • \$\begingroup\$ @lisovskey not a leading underscore. There is no need for it. \$\endgroup\$ – Martin York Jun 15 '17 at 19:55
  • 2
    \$\begingroup\$ Get rid of all those macros at the top. It just makes the code unreadable. \$\endgroup\$ – Martin York Jun 15 '17 at 19:55
0
\$\begingroup\$

Point of fact, underscores are not illegal for identifiers, and macros are fine if they make sense. It's unclear what the macro's are attempting to accomplish, so a comment paragraph on the top about the macros would help.

http://en.cppreference.com/w/cpp/language/identifiers

I think it's readable.

\$\endgroup\$

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.