1
\$\begingroup\$

I have a tree of objects.

Object id:0 Object type:0
  Object id:1 Object type:0
    Object id:3 Object type:0
  Object id:2 Object type:0
    Object id:4 Object type:0
    Object id:5 Object type:0

For each object I have a method that returns its "index" in the tree down to the root item.

Indices:

0 - 0
1 - 0 0
2 - 0 1
3 - 0 0 0
4 - 0 1 0
5 - 0 1 1

I need to be able to check for "visibility" from one object to another object, with the rules being pretty much identical to those of C/C++ scopes. E.g. the root item is like a global, so it should be visible to every other items, and items are only visible to items on their level or higher as long as they are in the same branch.

In short:

0 - visible to all
1 - visible to 2, 3, 4, 5
2 - visible to 4, 5
3 - visible to none
4 - visible to 5
5 - visible to none

After some trial and error I came up with this code, and it does seem to work as expected given the above tree hierarchy.

bool isVisibleTo(Node * accessor) {
    QList<uint> accessedI = getIndex();
    QList<uint> accessorI = accessor->getIndex();
    if (accessedI.size() > accessorI.size()) return false; // item is deeper than its accessor
    else if (accessedI.size() == accessorI.size()) { // same size - check if all but the last are compatible
        for (int i = 0; i < accessedI.size() - 1; ++i) if (accessedI.at(i) != accessorI.at(i)) return false; // indecies not identical
        if (accessedI.last() > accessorI.last()) return false; // identical, but accessor index is larger
    }
    for (int i = 0; i < accessorI.size() - (accessorI.size() - accessedI.size()); ++i) {
        if (accessedI.at(i) > accessorI.at(i)) return false; // wrong subtree
    }
    return true;
}

test output:

node  0 is visible to node  0 
node  0 is visible to node  1 
node  0 is visible to node  2 
node  0 is visible to node  3 
node  0 is visible to node  4 
node  0 is visible to node  5 
node  1 is visible to node  1 
node  1 is visible to node  2 
node  1 is visible to node  3 
node  1 is visible to node  4 
node  1 is visible to node  5 
node  2 is visible to node  2 
node  2 is visible to node  4 
node  2 is visible to node  5 
node  3 is visible to node  3 
node  4 is visible to node  4 
node  4 is visible to node  5 
node  5 is visible to node  5 

But still, I am fairly new and inexperienced to programming, so any notes, corrections and recommendations are welcome.

\$\endgroup\$
1
\$\begingroup\$

I came up with a cleaner looking solution:

bool isVisibleTo(Node * accessor) {
    Node * node = accessor;
    while (node) {
        if (node == this) return true;
        if (node->_parent) {
            uint i = node->_parent->_children.indexOf(node);
            while (i) if (node->_parent->_children.at(--i) == this) return true;
        } node = node->_parent;
    } return false;
}

But it will be inevitably slower in a scenario with lots of children. While the first "messy" solution uses the relative tree indices and only traverses the object tree from child to parent, this cleaner solution goes through all children nodes before going to the parent. I will have to do some profiling with a bigger tree to verify if that is the case.

EDIT: I take it back, despite what appeared as an obvious performance penalty this method is actually about 4 times faster consistently. I tested with a whooping 10 million nodes

\$\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.