Inheritance, polymorphism, and comparison operators in a binary search tree

[parabola]

I have a binary search tree that the nodes point to object "A". "A" is pure virtual and is the parent class for the derived class "B". In the binary search tree, to compare objects, the class uses operator<. The binary search tree is only aware of the A level, but I somehow need the comparison to be decided at class B. any idea how to do this?

[hamsterman]

struct A{
   virtual int type() = 0;
};
struct B : A{
   virtual int type() { return 0; }
};
struct C : A{
   virtual int type() { return 1; }
};

bool B_less_B(A*a1, A*a2){
   B* b1 = (B*) a1;
   B* b2 = (B*) a2;
   return *b1 < *b2;
}

bool B_less_C(A*a1, A*a2){
   B* b1 = (B*) a1;
   C* c2 = (C*) a2;
   return *b1 < *c2;
}

bool C_less_B(A*a1, A*a2){
   C* c1 = (C*) a1;
   B* b2 = (B*) a2;
   return *c1 < *b2;
}

bool C_less_C(A*a1, A*a2){
   C* c1 = (C*) a1;
   C* c2 = (C*) a2;
   return *c1 < *c2;
}

typedef bool(*less)(A*, A*);
bool operator < (A*a, A*b){
   less table[][] = {
      {B_less_B, B_less_C},
      {C_less_B, C_less_C}
   };
   return table[a->type()][b->type()](a, b);
}

That's how I did it when I had a similar issue. Note that I assumed you had operators < for (B, B), (B, C), (C, B) and (C, C). The comparison functions could be generated with macros.
Though are you sure comparing the addresses wouldn't be sufficient?

[ne555]

But then the derived classes are too much coupled. (the table will have quadratic growth)
And if you screw your type function, you will try to access to a non-existent comparator or perform a bad cast.

I was thinking about returning a comparable object. So A could provide a skeleton of what to do, and the derived classes choose how to do it.
But find such an object could be difficult, could you provide a little context?

[jsmith]

I assume you are using a polymorphic type -- A -- because you want the tree to be polymorphic (otherwise I'd say make it a template class). If that is the case, I'd make A contain a pure virtual compare() method (not operator<, because, as hamsterman's example shows, that can quickly become unmaintainable.

The weird thing, though, is how two arbitrary objects, having nothing in common other than a virtual compare() method, can be compared at all.

[simeonz]

The best way to bind the implementation of some function (predicate in this case) with the type of the objects to which you hold pointers is indeed to use polymorphism. That is, if you need to print the object, for example, you could make the print function virtual in the base class.

However, since you have a binary function/predicate, your situation is more complex than that. And this is not just technical problem. If you need to be able to compare objects of all types in some sub-tree from the type hierarchy with all others in this sub-tree, then look at hamster's solution, because it is as good as it gets. Not that this solution is bad, but if you have many types, then it can become hard to maintain.

On the other hand, if you need to compare only likes with likes - that is, only objects with the same dynamic type, then you probably have homogeneous container. What I mean is, your tree than should be designed to store only objects of the same type. Different trees can store different types of objects, but a single tree is restricted to specific type.

To the point - in this case you can use templates and create lightweight type-aware front-end for the container that derives from some type-oblivious back-end. The back-end carries all the computational and processing weight behind the operations, while the front-end only provides some type intelligence. The split is necessary in order to avoid template code bloat - that is machine code overhead. On the other hand, if you don't care much about memory waste, you can simply make your container generic (no back-end) and forget about polymorphism and what have you.

I have created dummy containers in this example that do nothing but sort and print their data. I have tried to illustrate the use of both polymorphism and type-awareness at once. It is not pretty, and some of the C++ limitations make it even uglier, but it should work. Again, this is all assuming that your container is homogeneous. Otherwise, look at the hamster's solution.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

template<typename Base>
class TypeObliviousContainerBase {

public:

    template <typename D>
    TypeObliviousContainerBase(D*,
                               typename D::derived_t data[],
                               size_t size)
        : m_data(size), compare_obj_ptr(D::compare_obj)
    {
        for (int i = 0; i < (int)size; ++i)
        {
            m_data[i] = data + i;
        }
    }

    void sort()
    {
        std::sort(m_data.begin(), m_data.end(), compare_obj_ptr);
    }

    void print()
    {
        for_each(m_data.begin(), m_data.end(), std::mem_fun(&Base::print));

        std::cout << std::endl;
    }

private:

    std::vector<Base*> m_data;

    bool (* const compare_obj_ptr)(Base*, Base*);
};

template <typename Derived, typename Base>
class TypeAwareContainer : public TypeObliviousContainerBase<Base> {

public:

    typedef Derived derived_t;
    typedef Base base_t;

    template <size_t N>
    TypeAwareContainer(Derived (& data)[N])
        : TypeObliviousContainerBase<Base>(this, data, N) {}

private:

    static bool compare_obj(Base* left, Base* right)
    {
        return static_cast<Derived*>(left)->
                compare(*static_cast<Derived*>(right));
    }

    friend class TypeObliviousContainerBase<Base>;
};

//****************************************************
// Here are the types that are held in the containers.
//****************************************************

struct AbstractBase
{
    virtual void print() const = 0;
};

struct DerivedSortAscending : AbstractBase
{
    int value;

    DerivedSortAscending(int x) : value(x) {};

    bool compare(const DerivedSortAscending& other) const
    {
        return value < other.value;
    }

    virtual void print() const
    {
        std::cout << value << " < ";
    }
};

struct DerivedSortDescending : AbstractBase
{
    int value;

    DerivedSortDescending(int x) : value(x) {};

    bool compare(const DerivedSortDescending& other) const
    {
        return value > other.value;
    }

    virtual void print() const
    {
        std::cout << value << " > ";
    }
};

//********************
// Some demonstration.
//********************

template <typename Derived, typename Base>
void test()
{
    Derived data[] = {Derived(2), Derived(1), Derived(3)};

    TypeAwareContainer<Derived, Base> c(data);

    c.sort();
    c.print();
}

int main()
{
    test<DerivedSortAscending, AbstractBase>();
    test<DerivedSortDescending, AbstractBase>();
}

There is another option - to make the binary operation/predicate virtual and to use dynamic_cast, but this approach provides fewer static type checks, and I am not comfortable with it. It is easier to implement, but more error prone.

Regards