5
\$\begingroup\$

I have the following C++ interface (in Qt) for a tree node, inspired somewhat by Valve's implementation of a culling octree:

/**
 * @brief Interface for a recursive tree node.
 */
class ITreeNode
{
public:
    /**
     * @brief Virtual destructor.
     */
    virtual ~ITreeNode() {}

    /**
     * @brief Adds a child node to this node.
     * @param node Node to add.
     */
    virtual void addChild(ITreeNode* node) = 0;

    /**
     * @brief Removes the child node at the given index from this node.
     * @param index Index of child to remove.
     * @return Child removed, or NULL if the index was invalid.
     */
    virtual ITreeNode* removeChild(int index) = 0;

    /**
     * @brief Removes the given child node if it exists.
     * @param node Node to remove.
     */
    virtual void removeChild(ITreeNode* node) = 0;

    /**
     * @brief Returns the child at a given index.
     * @param index Index of the child.
     * @return Child at this index, or NULL if the index was invalid.
     */
    virtual ITreeNode* childAt(int index) const = 0;

    /**
     * @brief Returns whether the given node is recorded as a child of this node.
     * @param node Node to search for.
     * @return True if the given node is recorded as a child; false otherwise, or if the node provided is NULL.
     */
    virtual bool containsChild(ITreeNode* node) const = 0;

    /**
     * @brief Returns whether this node is an ancestor of the given node.
     * @note This means that this node is present further up the path from the root node to the given node.
     * @param node Node to check ancestry of.
     * @return True if this node is an ancestor of the given node, false otherwise or if the given node is NULL.
     */
    virtual bool isAncestor(const ITreeNode* node) const = 0;

    /**
     * @brief Returns whether this node is a successor of the given node.
     * @note This means that the given node is present further up the path from the root node to this node.
     * @param node Node to check successors of.
     * @return True if this node is a successor of the given node, false otherwise or if the given node is NULL.
     */
    virtual bool isSuccessor(const ITreeNode *node) const = 0;

    /**
     * @brief Returns the number of direct children this node has
     * @return Number of children recorded in this node.
     */
    virtual int childCount() const = 0;

    /**
     * @brief Returns whether this node is a leaf (ie. it has no children).
     * @return True if the node is a leaf, false otherwise.
     */
    virtual bool isLeaf() const  = 0;

    /**
     * @brief Returns a pointer to the parent of this node.
     * @return Pointer to parent, or NULL if no parent is recorded.
     */
    virtual ITreeNode* parent() const = 0;

    /**
     * @brief Sets the parent of this node.
     * @param parent Parent node to set.
     */
    virtual void setParent(ITreeNode* parent) = 0;

    /**
     * @brief Returns whether this node is the root (ie. it has no parent).
     * @return True if the node is the root of the tree, false otherwise.
     */
    virtual bool isRoot() const = 0;

    /**
     * @brief Recursively deletes all of this node's children, leaving this node as a leaf.
     */
    virtual void pruneSubtree() = 0;

    /**
     * @brief Removes the node from the tree structure, leaving the remainder disjoint.
     * 
     * The node will be removed as a child from its parent, and will leave all its children as roots of
     * their respective subtrees.
     * @return List of child nodes removed from this node.
     */
    virtual QList<ITreeNode*> detachNode() = 0;
};

In order to improve my understanding of how interfaces should be designed I'm looking for a critique, if possible, of the functionality of this interface. My general target was to include a useful set of basic tree-related functions - obviously the bare minimum would be simply adding/removing/getting children, but I also felt as though automating potentially useful processes such as removing all children (pruneSubtree() - thinking recursive deletion) and removing a node from a given tree structure to leave a forest might help make future tasks easier.

I'm also torn on whether it's better to pass a node pointer in when adding a child (the method Valve used, where the node takes ownership of the child being added) or to have the add method not require a pointer and simply have the node create and manage its own children - I'm not clued up on the relative merits of these two choices, so arguments for and against would be helpful.

So basically:

  • Is this interface complete? Does it attempt to do too much or too little?
  • Is it a good idea to include potentially specialised functions such as pruneSubtree() and detachNode() early on, or leave them for subclasses?
  • Is it better to have the implementing class manage all children in memory, or allow them to be passed in externally?
  • Are there situations in which functionality such as this wouldn't necessarily require an interface? In what situations do interfaces begin to become necessary?
  • Should enforcing potentially high-level conditions, such as no circular node links, etc., be considered at this stage?
  • Any other important points I have failed to mention?
\$\endgroup\$
6
\$\begingroup\$

Is this interface complete? Does it attempt to do too much or too little?

In my opinion, interfaces should be as small as possible, providing only methods that are really required to be called without knowing (or casting to) the actual subclass. I don't know how you use it, but my first impression is: your interface contains too many methods...

Are there situations in which functionality such as this wouldn't necessarily require an interface?

An interface is useful if you have two or more classes that are implemented differently but require the same interface. In your case I don't think that the actual subclasses will implement this interface with significant differences. (Actually I don't see any methods I would expect to behave differently)

So maybe instead of an interface a real base class would be the better choice to avoid code duplicates. You could implement a treenode class (implementing all those methods itself) and inherit from it to only change/add the different behaviours... (Again I can only guess as I don't see your subclasses)

Is it better to have the implementing class manage all children in memory, or allow them to be passed in externally?

Well, your children's nodes are passed in externally (and I think that's the only way that makes sense) - you only have to decide whether to let the parent node take over ownership of its children or not.

As long as you don't share single instances of your nodes between different trees (or at least different parents) or reuse them in any other way, I would prefer the parents to take ownership (delete them when they are no longer needed).

Objects taking ownership of their children is also a well known practice in Qt. As you're using Qt, I would recommend mimicking this behaviour.

\$\endgroup\$
  • \$\begingroup\$ Great analysis, that's really helpful. Thanks. \$\endgroup\$ – x6herbius May 28 '14 at 10:26

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.