#include <list>
#include <utility>
#include <iostream>

typedef std::pair<char, int> PAIR;

// NOTE: the Key() virtual methods use the first letter
//       of the class (b,c,g) as the first pair member since
//       they are (conveniently) already sorted alphabetically.
//       Were this not the case, any other sorted choice would work.

// Question 1: Should Grandchild also have an id/val?
// Question 2: How do we sort amongst Grandchildren?
// ANYWAY....

class BaseObject
{
 public:
   BaseObject(int i) : id(i) {}
   virtual PAIR Key() const {return(std::make_pair('b', id));}
   virtual ~BaseObject() {}
 private:
   int id;
};


class Child : public BaseObject
{
 public:
   Child(int id1, int n) : BaseObject(id1), var(n) {}
   virtual PAIR Key() const {return(std::make_pair('c', var));}
   virtual ~Child() {}
 private:
   int var;
};

class GrandChild : public Child
{
 public:
   GrandChild(int id1, int n) : Child(id1,n) {};
   virtual PAIR Key() const {return(std::make_pair('g', 0));}
   virtual ~GrandChild() {}
};


struct Comparator
{
   bool operator()(const BaseObject* o1, const BaseObject* o2) const
   {
       // std::pair already has built-in comparison
       return (o1->Key() < o2->Key());
   }
};

typedef std::list<BaseObject*>                  MYLIST;
typedef std::list<BaseObject*>::const_iterator  ITER;

int main()
{
 // TODO: Deletes, exception handling, etc.
 MYLIST mylist;

 // Build the list...
 // Bases sorted before Children; Children sorted before Grandchildren
 // Within a class, the id/var/etc. is used to sort.

 mylist.push_back(new BaseObject(99));
 mylist.push_back(new BaseObject(98));
 mylist.push_back(new Child(50, 22));
 mylist.push_back(new Child(98, 21));
 mylist.push_back(new Child(99, 20));
 mylist.push_back(new GrandChild(50, 40));
 mylist.push_back(new GrandChild(98, 35));

 // Sort the list using our Comparator
 mylist.sort(Comparator());

 // Output (display) the sorted list
 ITER pos;
 for (pos = mylist.begin(); pos != mylist.end(); ++pos)
 {
   PAIR p = (*pos)->Key();
   std::cout << p.first << " " << p.second << std::endl;
 }

}