CODEWITHSUNDEEP
c++inheritancedata-structures
K J
K J

Reputation: 33

C++ Data Structure to represent Single Inheritance

I need to build a data structure that represents the inheritance graph of the classes present in the file. This is part of writing a compiler for a language which supports only single inheritance.

The names of all the classes present are stored in a linked list. I need to traverse that list and build a inheritance graph out of it. Then I need to check if there cycles in inheritance, For example If 

    B inherits A
    C inherits B

then 

    A cannot inherit C.

Cycles like these are not allowed in the language.

What data structure would be best suited for this?

Upvotes: 1

Views: 543

Answers (4)

Michel Billaud
Michel Billaud

Reputation: 1826

A simple tree structure suffices (under your hypothesis of single inheritance).

#include <iostream>
#include <cassert>
using namespace std;

class Class {
private:
    const string name;
    const Class *parent;
public:
    Class(const string aName) :
       name{aName},
       parent(nullptr)
    {}
    bool setParent(const Class &otherClass) {
        // I dont already have a parent class
        if (parent)
            return false;  // no multiple inheritance 
        // so I am the root of some inheritance tree.
        // Now searching for the root ot the otherClass tree
        auto root = &otherClass;
        while (root->parent != nullptr) {
           root = root->parent;
        };
        // it shouldn't be me !
        if (root == this)
            return false;
        // let's remember the inheritance
        parent = &otherClass;
        return true;
   }
};

// some tests
int main(int argc, char **argv)
{
     cout << "Tests :" << endl;
     Class a("A");
     assert(! a.setParent(a));
     Class b("B");
     assert(b.setParent(a));
     Class c("C");
     assert(c.setParent(b));
     assert( ! a.setParent(c));
     cout << "Success !" << endl;
     return 0;
 }

Can be made faster with the path compression trick, see http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests

Upvotes: 1

Michel Billaud
Michel Billaud

Reputation: 1826

With the single inheritance constraint, your graph is a forest, that is a set of trees. And your problem is known in the literature as cycle detection in graphs http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29#Cycle_detection

Upvotes: 2

Alan Wolfe
Alan Wolfe

Reputation: 645

Game programming gems 8 has a great "fast is-a" implementation written by an old boss of mine that would lend itself well to this. I don't remember all the details so you'll have to check it out but it uses some clever bit pattern tricks to do things quickly (beyond bit packing). http://www.gameenginegems.net/gemsdb/article.php?id=516

Upvotes: 1

user4842163
user4842163

Reputation:

Given that inheritance is typically done somewhat infrequently and because the hierarchy generally doesn't get very deep (as in like, you generally don't have 10,000+ classes in an inheritance hierarchy let alone 1,000), I think you're fine with just your straightforward linked structure.

A<->B<->C<---->A<->B<->C

When trying to link C to A, first traverse the graph (tree) from A before establishing the link (recursive tree search should be fine). If you find that C already exists in A's graph, then you're establishing a cycle and want to reject the connection (generate a compiler error or something).

If you find this becomes a hotspot and your specific programming language actually encourages a way of programming where inheritance hierarchies can often get very deep with a massive number of classes in them, then a simple way to optimize that check from linear time to logarithmic is to store std::shared_ptr<std::set<Node*>>.

When linking from A to B, first search the shared std::set in A for B. If B doesn't exist in the set, then we're free to establish the connection (to make B inherit from A). Then you copy the shared_ptr in A to B.

When unlinking B from A (though I don't think you need to deal with this case since it would be strange to have a language that allows things to become 'uninherited'), remove B from the shared set and set B's shared_ptr to null (release the reference).

That said, does your language really allow for dynamic inheritance of this sort outside of the class definition? Typically most programming languages have you specifying the inheritance at the time in which the class is defined. So unless you have this kind of "dynamic inheritance", then it would normally be impossible for A to try to inherit from C which already inherits from B which already inherits from A. That would be trying to make A inherit from something long after it was defined.

Upvotes: 1

Related Questions