# code reuse

• 12-18-2010
nimitzhunter
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?
• 12-18-2010
whiteflags
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.
• 12-18-2010
nimitzhunter
Quote:

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```
• 12-18-2010
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.)
• 12-18-2010
whiteflags
Quote:

Originally Posted by nimitzhunter
I need ~sort() because A is dynamically allocated. I saw it's done in C++ Primer Plus, so I thought I could do it.

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.
• 12-18-2010
nimitzhunter
Quote:

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.
• 12-18-2010
nimitzhunter
Quote:

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?
• 12-19-2010
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.
• 12-19-2010
whiteflags
Quote:

Originally Posted by nimitzhunter
Is this wrong and I'm not supposed to do that?

Yes and no. No because like I said, you can't create an AcctABC. Call AcctABC cash([params]); and you wouldn't be able to instantiate the object. You would only create types of accounts, which are extensions of the AcctABC.

But yes, sometimes an ABC constructor makes sense. It means that every type of class derived from AcctABC will share that particular initialization as defined by the constructor, and also those members (which are accessable through AcctABC's interface -- the part you aren't expected to override, at least). No, because the ABC could be just an interface, a list of pure virtual functions; this makes up the majority of ABC's.

I could criticize the example you showed me further, but I won't. Instead, consider if you made your SortABC like the other ABCs, like what I described as the majority. If the interface fits, then your sort class could include linked list sorts as well as array sorts, but they aren't initialized or represented similarly at all. Something like what the book showed you would make no sense to follow. That sort of situation, where similar interfaces have wildly different implementations arises all the time. (Honestly I can't say I would make a monolith sort class anyway, but I'm trying to illustrate that particular code in Primer Plus is not something you should emulate. I can't conclude they are properly teaching what ABCs are for.)
• 12-19-2010
grumpy
Quote:

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.
• 12-19-2010
Elysia
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
• 12-19-2010
nimitzhunter
Thank you everyone so much for the excellent inputs.