1

I have a quad-tree structure where each node has some of its own data, but there is also data which applies to the tree as a whole.

I'll explain my current solution and I would appreciate feedback on whether this is the best solution or whether better solutions exist.

I have two classes:

  • One for the node
  • One for the tree

The tree class contains a root node pointer and the data relevant for that tree. The nodes in the tree need to access that data, so one option would be to have the node class include a data member which is a pointer to the tree object, and then invoke its accessor methods to get at the data.

This would increase the side of each node, though, so I decided to have a single static pointer for the node class. When a tree object wants to do something to all the nodes (most of the algorithms are recursive beginning at the root), it first sets the static pointer to point to its tree data (which I put in a struct) and then invokes the static pointer to point to its data.

Here is some pseudo-code:

struct TreeData {
    // data relevant to tree as a whole
};

class Tree {
public:
    void algorithm() {
        root.set_data(&data);
        root.algorithm();
    };

private:
    Node root;
    TreeData data;
};

class Root {
public:
    static void set_data(TreeData * data) {
        tree_data = data;
    }

    void algorithm() {
        // code that uses tree_data
    }

private:
    static TreeData * tree_data;
};

I wanted to avoid having every node increase in size, but there can be multiple trees instantiated at a time, so it couldn't just be static data for the node class.

So where should I put data for tree structure which every node requires?

  • 1
    Could you simply pass the TreeData object into algorithm()? – Ixrec Jan 4 '15 at 22:21
2

Your current solution has a major down side in that it is not thread safe. I would definitely redesign so that you can have multiple tree operations preformed in parallel.

Assuming that nodes are purely internal to the tree structure, and always called via the tree, I would consider simply having their owner tree passed in as a parameter when you call any of their methods that needs access to this data.

  • Good point. I don't do much multi-threaded programming so I hadn't thought about that concern. Another downside is that I have to remember to invoke the set_data method, and if Tree has a wrapper method that basically invokes a chain of other methods (which I have), then there's the question of where to put that set_data, and there is nothing making it obvious if it has already been invoked. – master_latch Jan 4 '15 at 22:28
  • I was able to easily update my code to accept a pointer to the TreeData struct. This solves the "did I remember to invoke the set_data method?" problem because the argument is mandatory. – master_latch Jan 4 '15 at 22:34

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.