MergeSort - A Linked Lists Solution

(see also the Java Solution)

#include < stdio.h >
#include < stdlib.h >
#include < iostream.h >
#include < string.h >

double objectValue(void *obj) {  return (double)*(int *)obj;  }

class Cell
{
private:
   void *object;
   Cell *left;
   Cell *right;
   double (* valfn)(void *);

public:
   Cell (void *obj, Cell *lf, Cell *rt, double (* f)(void *))
   {  object=obj;  left=lf;  right=rt;  valfn = f;  }
   double value()   { return (valfn)(object); }
   void *objectOf() { return object; }
   Cell *leftOf()   { return left; }
   Cell *rightOf()  { return right; }
   void  setLeft(Cell *lf)  { left = lf; }
   void  setRight(Cell *rt) { right = rt; }
};

/***----------------------------------------------------------------
     Merge:
        Input: Two linked lists ll, rl, of increasing values
               linked on Cell left
       Output: A single linked list of increasing values taken from
               ll, rl.  The list is linked on Cell left
--------------------------------------------------------------------***/
Cell *merge(Cell *ll, Cell *rl)
{
   Cell *first = NULL, *last = NULL;

   while (ll != NULL || rl != NULL)
   {
      if (ll==NULL || (ll != NULL && rl != NULL && ll->value() > rl->value()))
      {
         if (first == NULL) first = rl; else last->setLeft(rl);
         last = rl;
         rl = rl->leftOf();
      }
      else
      {
         if (first == NULL) first = ll; else last->setLeft(ll);
         last = ll;
         ll = ll->leftOf();
      }
      last->setLeft(NULL);
   }
   return first;
}

/***--------------------------------------------------------------
     MergeSort:
        Input: A tree linked on Cell left and right, value cells
               are on the bottom level
       Output: A linked list, in increasing order, of objects in
               the input tree.  List is linked on Cell left
------------------------------------------------------------------***/
Cell *mergeSort(Cell *c)
{
   if (c == NULL) return NULL;
   if (c->leftOf() == NULL) return c;
   return merge(mergeSort(c->leftOf()), mergeSort(c->rightOf()));
}

/***----------------------------------------------------------------
     buildTree:
        Input: A number d
       Output: A complete binary tree of depth d with number at
               the bottom level.  This is only for the convenience
               of building a collection of elements to merge
--------------------------------------------------------------------***/
Cell *buildTree(int d)
{
   if (d == 0) return new Cell(new int(rand()/100), NULL, NULL, objectValue);
   return new Cell(NULL, buildTree(d-1), buildTree(d-1), objectValue);
}

void showList(Cell *c)
{
   cout << ">>> Showing List:\n  ";
   for (Cell *p=c ; p!= NULL ; p=p->leftOf())
      cout << p->value() << " ";
   cout << "\n";
}

void main()
{
   showList(mergeSort(buildTree(5)));
}