code reuse

This is a discussion on code reuse within the C++ Programming forums, part of the General Programming Boards category; I'm trying to learn algorithm and get better with C++. So instead of using all the sorting procedure comes with ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460

    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?
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,763
    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.
    Last edited by whiteflags; 12-18-2010 at 09:54 PM.

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by whiteflags View Post

    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
    "All that we see or seem
    Is but a dream within a dream." - Poe

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)
    Last edited by tabstop; 12-18-2010 at 11:35 PM.

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,763
    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.

  6. #6
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by tabstop View Post
    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.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  7. #7
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by whiteflags View Post
    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?
    "All that we see or seem
    Is but a dream within a dream." - Poe

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,763
    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.)

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,679
    Quote Originally Posted by iMalc View Post
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,033
    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
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Thank you everyone so much for the excellent inputs.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Extended ASCII Characters in an RTF Control
    By JustMax in forum C Programming
    Replies: 18
    Last Post: 04-03-2009, 09:20 PM
  2. Enforcing Machine Code Restrictions?
    By SMurf in forum Tech Board
    Replies: 21
    Last Post: 03-30-2009, 08:34 AM
  3. Obfuscated Code Contest
    By Stack Overflow in forum Contests Board
    Replies: 51
    Last Post: 01-21-2005, 04:17 PM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 06:06 PM
  5. Replies: 0
    Last Post: 02-21-2002, 06:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21