Thread: code reuse

I'm trying to learn algorithm and get better with C++. So instead of using all the sorting procedure comes with STL, I have learn to write a few sorting codes. Now I want to merge them together. I'm working on two right now, merging the heap sort and quick sort together.

Code:

template <class Type>
class Heap
 {
 private:
   Type *A;
   int heap_size;
   int heap_length;
   
   
 public:
   //Heap();
   Heap(Type * array, int length);
   ~Heap();
   int parent(int i) { return i/2;};
   int left  (int j) { return 2*j+1;};
   int right (int k) { return 2*k+2;}; 
   void exch(double *x, double *y);
   void show();
   void max_heapify(int i);
   void build_max_heap();
   void sort();
   Type heap_max() {return A[0];};
   double heap_extract_max();
   
 };

#endif

Code:

template<class Type>
class Qsort
{
private:
  Type *A;
  int length;
public:
  Qsort();
  Qsort( int n, Type * Arr);
  ~Qsort();
  // Quick sort
  void sort(int p , int r);
  int partition( int p, int r);
  // Randomized quick sort
  void random_sort(int p, int r);
  int random_partition(int p, int r);
  void show();
  void exch(Type * a, Type * b);
};

Since these two classes are very similar, I want to merge them together. Should I used the abstract based class and alter these two classes since they both require to store the array "A" and its length. Also they share some functions.

So I have this abstract base class:

Code:

template <class Type>
class SortABC
{
private:
  Type *A;
  int length;
public:
  Sort();
  virtual ~Sort() = 0;
  virtual void show() = 0;
}

I include show() in the ABC because both derived classes will have the same function for show(). Should I include the "exch()" function as well since its present in other two classes?

This means I need another class that inherits from both heap-sort and quick-sort classes. Is this the situation that container would not work and I have to use multiple inheritance? So if I have like 5 or 6 different sorting algorithms, I need to inherit all of them?

This is about as related as the two sorts get -- implementing them through a common interface:

Code:

template <class Type>
class SortABC
{
private:
  Type *A;
  int length;
public:
  Sort();
  virtual ~Sort() = 0;
  virtual void show() = 0;
}

If you can decide on an interface that works for both algorithms, then implementing them in derived classes wouldn't be a problem. You have some issues though:

I don't recall seeing constructors, or destructors like ~Sort, in ABCs, because ABCs themselves cannot be made into objects; only their child classes are. The one method that should additionally be pure virtual, Sort(), is not. Your child classes will not inherit their own A and length either because those members are private, which seems weird.

Originally Posted by whiteflags

I don't recall seeing constructors, or destructors like ~Sort, in ABCs, because ABCs themselves cannot be made into objects; only their child classes are. The one method that should additionally be pure virtual, Sort(), is not. Your child classes will not inherit their own A and length either because those members are private, which seems weird.

I need ~sort() because A is dynamically allocated. I saw it's done in C++ Primer Plus, so I thought I could do it.
You are absolutely correct. I couldn't access A and length, so I made them protected. I don't know if that's the correct way or not. I do so because both I need access to A and length.
Here's what i have so far:

Code:

#ifndef _SORT_ABC_
#define _SORT_ABC_

template <class Type>
class SortABC
{
protected:
  int length;
  Type *A;
  
public:
  SortABC( Type *Arr, int n);
  virtual ~SortABC() ;
  void exch(Type & x, Type & y);

  // pure virtual method
  virtual void show() const = 0;
  virtual void sort() = 0;

  
};

template <class Type>
SortABC<Type>::SortABC( Type *Arr ,int n ) : length(n)
{
  A = new Type [n];
  for ( int i = 0 ; i < length ; i++)
    A[i] = Arr[i];
}

template <class Type>
SortABC<Type>::~SortABC()
{
  delete [] A;
}

template<class Type>
void SortABC<Type>::exch(Type & x, Type & y)
{
  Type temp;
  temp = x;
  x = y;
  y = temp;
}

#endif

Code:

#ifndef HEAP_N_
#define HEAP_N_
#include "abc.h"
//////////////////////////////////////////////
template <class Type>
class Heap: virtual public SortABC<Type>
{
 private:
  int heap_size;

 protected:
  int parent(int i) { return i/2;};
  int left  (int j) { return 2*j+1;};
  int right (int k) { return 2*k+2;}; 
  void max_heapify(int i);
  double heap_max() {return SortABC<Type>::A[0];};
  void build_max_heap();

 public:
 Heap( Type * array ,int n)
   :SortABC<Type>(array,n),heap_size(n) {};
   
   //public method:
   Type heap_extract_max();
   virtual void show() const;
   virtual void sort();
};

//////////////////////////////////////////////
template <class Type>
void Heap<Type>::max_heapify(int i)
{

  int l = left(i);
  int r = right(i);
  int largest;
  
 
  if ( l < heap_size && SortABC<Type>::A[l] > SortABC<Type>::A[i])
    largest = l;
  else
    largest = i;
  if ( r < heap_size && SortABC<Type>::A[r] > SortABC<Type>::A[largest] )
    largest = r;
  if (largest != i)
    {
      SortABC<Type>::exch( SortABC<Type>::A[i] , SortABC<Type>::A[largest] );
      max_heapify(largest);
    }
}

//////////////////////////////////////////////
template <class Type>
void Heap<Type>::build_max_heap()
{
  for( int i = heap_size/2; i >= 0 ;i--)
    {
      max_heapify(i);
    }
}

//////////////////////////////////////////////
template <class Type>
void Heap<Type>::show() const
{
  for (int i=0; i< SortABC<Type>::length; i++)
    std::cout <<SortABC<Type>:: A[i] << std::endl;
  std::cout << std::endl;
}

//////////////////////////////////////////////
template <class Type>
void Heap<Type>::sort()
{
  build_max_heap();
  for(int i = SortABC<Type>::length-1; i >= 1 ; i--)
    {
      SortABC<Type>::exch( SortABC<Type>::A[0] , SortABC<Type>::A[i]);
      --heap_size;
      max_heapify(0); 
    }
  heap_size = SortABC<Type>::length;
}

//////////////////////////////////////////////
template <class Type>
Type Heap<Type>::heap_extract_max()
{
  if( heap_size < 0 )
    std::cout << "Heap underflow";
  int ll=SortABC<Type>::length;
  Type max = SortABC<Type>::A[0];
  SortABC<Type>::exch(SortABC<Type>::A[0] , SortABC<Type>::A[ll-1]);
  --heap_size;
  max_heapify(0);
  std::cout << std::endl;
  show();
  std::cout << std::endl;
  return max;
}


#endif

So I'm not entirely sure why you want to combine these two classes, as they're not the same "category" to me. A heap is a container (granted a container that obeys some properties), while quicksort is a way to sort things that are contained elsewhere and does not contain any information in itself. Put another way: a heap is a noun, quicksort is a verb. I would expect trying to combine them to end in heartache.

(EDIT: Or is this supposed to be heapsort, as opposed to a heap data structure? In that case, then, you should be looking at "what would a user want no matter what kind of a sort it is" which would probably be what should go in the base class. And I'm thinking the only thing the user needs is "sort()", so that would be your virtual function in the base class (and probably the only thing in the base class at all, unless you want to add a comparator function). The implementation details, like why you need a Type* in QSort, is specific to the implementation of that algorithm.)

Originally Posted by tabstop

So I'm not entirely sure why you want to combine these two classes, as they're not the same "category" to me. A heap is a container (granted a container that obeys some properties), while quicksort is a way to sort things that are contained elsewhere and does not contain any information in itself. Put another way: a heap is a noun, quicksort is a verb. I would expect trying to combine them to end in heartache.

(EDIT: Or is this supposed to be heapsort, as opposed to a heap data structure? In that case, then, you should be looking at "what would a user want no matter what kind of a sort it is" which would probably be what should go in the base class. And I'm thinking the only thing the user needs is "sort()", so that would be your virtual function in the base class (and probably the only thing in the base class at all, unless you want to add a comparator function). The implementation details, like why you need a Type* in QSort, is specific to the implementation of that algorithm.)

Yeah, I am trying to combine all the sorting algorithms that I have together as a way to learn about inheritance. Something like a class that gives the user a different options to sort.

Originally Posted by whiteflags

I can't comment on that book's code, but I am fairly certain you've misunderstood something. In the first place, you aren't meant to create ABC instances (objects). You will never write a call to an ABC's constructor, so anything that you would do in an ABC's constructor would be done in a derived class's constructor. This applies for destructors, and copy constructors. Though, you can decide if derived classes can implement a copy constructor or not by making the ABC(ABC&); private. The reason you make an ABC is to create classes that are similar in design, but necessarily different in implementation.

I have the code from that book. Here is just the abbreviated version:

Code:

class AcctABC
{
private:
  enum { MAX = 35};
  char fullName[MAX];
  long acctNum;
  double balance;
public:
  AcctABC(const char *s, long an, double bal);
  void Deposit(double amt);
  virtual void Withdraw(double amt) = 0;
  virtual void ViewAcct() const = 0;
  virtual ~AcctABC() {};
};

class Brass:public AcctABC
{
public:
  Brass(const char s, long an, double ball): AcctABC(s,an,bal), {};
  ...
};


AcctABC:: AcctABC(const char *s, long an, double bal)
{
  std::strncpy(full,s, MAX-1);
  fullName[Max-1]='\0';
  acctNum = an;
  balance = bal;
}

void AcctABC::Deposit(double amt)
{
  if (amt<0)
    ;
  
}

I just intrapolated from that code example that I could use the ABC's as an object since it has a constructor and destructor as well as other public methods. And the derived class Brass call on the constructor of the ABC. Is this wrong and I'm not supposed to do that?

I'm not even sure why these are classes, and it makes even less sense to use polymorphism here.

There are far more appropriate ways of learning about polymorphism. How about writing and evolving a simple drawing program with shape, circle, rectangle, line, and group classes etc.

Originally Posted by iMalc

I'm not even sure why these are classes, and it makes even less sense to use polymorphism here.

There are far more appropriate ways of learning about polymorphism. How about writing and evolving a simple drawing program with shape, circle, rectangle, line, and group classes etc.

I agree with iMalc here.

I'm not really a fan of using object techniques like polymorphism - which are related to data or physical structure - for organising what is, in effect, types of algorithms.

Different sorts would really just be at best a function call with two parameters. I don't really see a need for a class, either.
Furthermore, this book of yours doesn't seem to be very good since it uses C-style strings. I'd recommend Accelerated C++ instead.
Suggested reading: SourceForge.net: Raw pointer issues - cpwiki

Thank you everyone so much for the excellent inputs.