Re: The Sort Excercise

From: Daniel T. (postmaster_at_eathlink.net)
Date: 12/30/03 

Date: Tue, 30 Dec 2003 06:25:41 GMT

"Val" <valmont_gaming@hotmail.com> wrote:

>
> "Daniel T." <postmaster@eathlink.net> wrote in message
> news:postmaster-034C69.08125429122003@news04.east.earthlink.net...
> > "Val" <valmont_gaming@hotmail.com> wrote:
> >
> > > ROFL, now I am doomed!
> > > You play hardball with this hobby-programmer....
> >
> > You have the skill necessary for this task. First get past the first
> > assertion, then the second, and so on. All the while looking for
> > duplication in your code that you can remove.
> >
> > The hard part of creating any class is deciding what the interface is
> > going to be, how does the client code use the class? That is done by the
> > time the test is written. After all, the test is a client.
>
>
> I created a monster!!! :(

First, let's get rid of that "DidSort" function. I don't think clients
care much about that, what they want to know is if the strings are
sorted, that will tell them if the machine did it's job.

int main()
{
 string sortedString[] = { "a", "b", "c" };
   SortingMachine sm;
   sm.SetSortStrategy( new AscendSort );
   sm.SetArray( sortedString, 3 );
   assert( sm.IsSorted() );

   sm.SetSortStrategy( new DescendSort );
   assert( !sm.IsSorted() );

   sm.StartSort();
   assert( sm.IsSorted() );

   cout << "OK" << endl;

 return EXIT_SUCCESS;
}

Here is how I solved the problem. First I wrote IsSorted and StartSort
independently:

class SortingMachine
{
public:
   SortingMachine(): strategy( 0 ), array( 0 ), array_size( 0 ) { }
   
   void SetSortStrategy( SortStrategy* s ) {
      delete strategy;
      strategy = s;
   }
   
   void SetArray( string* arr, int len ) {
      array = arr;
      array_size = len;
   }
   
   bool IsSorted() const {
      bool result = true;
      for ( int i = 0; i < array_size - 1 && result == true; ++i )
         if ( strategy->OutOfOrder( &array[i], &array[i + 1] ) )
            result = false;
      return result;
   }

   void StartSort() {
      for ( int i = 0; i < array_size - 1; ++i ) {
         for ( int j = i + 1; j < array_size; ++j ) {
            if ( strategy->OutOfOrder( &array[i], &array[j] ) ) {
               string temp = array[i];
               array[i] = array[j];
               array[j] = temp;
            }
         }
      }
   }
   
private:
   SortStrategy* strategy;
   string* array;
   int array_size;
};

Simple and works! Now let's look for duplication... Well both functions
have the line "for ( int i..." with the same args and everything. So
let's try to combine that. First break out the stuf inside the two loops
into their own functions...

class SortingMachine
{
public:
   SortingMachine(): strategy( 0 ), array( 0 ), array_size( 0 ) { }
   
   void SetSortStrategy( SortStrategy* s ) {
      delete strategy;
      strategy = s;
   }
   
   void SetArray( string* arr, int len ) {
      array = arr;
      array_size = len;
   }
   
   bool IsSorted() const {
      bool result = true;
      for ( int i = 0; i < array_size - 1 && result == true; ++i )
         result = checkOrder( i );
      return result;
   }

   void StartSort() {
      for ( int i = 0; i < array_size - 1; ++i ) {
         setNext( i );
      }
   }
   
private:
   bool checkOrder( int i ) const {
      return !strategy->OutOfOrder( &array[i], &array[i+1] );
   }
   
   void setNext( int i ) {
      for ( int j = i + 1; j < array_size; ++j ) {
         if ( strategy->OutOfOrder( &array[i], &array[j] ) ) {
            string temp = array[i];
            array[i] = array[j];
            array[j] = temp;
         }
      }
   }
   
   SortStrategy* strategy;
   string* array;
   int array_size;
};

Our two 'for (int i...' loops are nearly identical. We can make them
exactly identical one of two ways, either have checkOrder throw an
exception, or have setNext return a true every time. I'll go with the
exception...

class SortingMachine
{
   class BadOrdering { };
public:
   SortingMachine(): strategy( 0 ), array( 0 ), array_size( 0 ) { }
   
   void SetSortStrategy( SortStrategy* s ) {
      delete strategy;
      strategy = s;
   }
   
   void SetArray( string* arr, int len ) {
      array = arr;
      array_size = len;
   }
   
   bool IsSorted() const {
      bool result = true;
      try {
         for ( int i = 0; i < array_size - 1; ++i )
            requireOrder( i );
      }
      catch ( BadOrdering& ) {
         result = false;
      }
      return result;
   }

   void StartSort() {
      for ( int i = 0; i < array_size - 1; ++i ) {
         setNext( i );
      }
   }
   
private:
   void requireOrder( int i ) const {
      if ( strategy->OutOfOrder( &array[i], &array[i+1] ) )
         throw BadOrdering();
   }
   
   void setNext( int i ) {
      for ( int j = i + 1; j < array_size; ++j ) {
         if ( strategy->OutOfOrder( &array[i], &array[j] ) ) {
            string temp = array[i];
            array[i] = array[j];
            array[j] = temp;
         }
      }
   }
   
   SortStrategy* strategy;
   string* array;
   int array_size;
};

Now let's combine those loops...

class SortingMachine
{
   class BadOrdering { };
   typedef void (SortingMachine::*Fn)( int );
public:
   SortingMachine():
      strategy( new AscendSort ), array( 0 ), array_size( 0 ) { }
   
   void SetSortStrategy( SortStrategy* s ) {
      delete strategy;
      strategy = s;
   }
   
   void SetArray( string* arr, int len ) {
      array = arr;
      array_size = len;
   }
   
   bool IsSorted() {
      bool result = true;
      try {
         loopAndDo( &SortingMachine::requireOrder );
      }
      catch ( BadOrdering& ) {
         result = false;
      }
      return result;
   }

   void StartSort() {
      loopAndDo( &SortingMachine::setNext );
   }
   
private:
   void loopAndDo( Fn fn ) {
      for ( int i = 0; i < array_size - 1; ++i )
         (this->*fn)( i );
   }
   
   void requireOrder( int i ) {
      if ( strategy->OutOfOrder( &array[i], &array[i+1] ) )
         throw BadOrdering();
   }
   
   void setNext( int i ) {
      for ( int j = i + 1; j < array_size; ++j ) {
         if ( strategy->OutOfOrder( &array[i], &array[j] ) ) {
            string temp = array[i];
            array[i] = array[j];
            array[j] = temp;
         }
      }
   }
   
   SortStrategy* strategy;
   string* array;
   int array_size;
};

Is this solution better or worse than yours, or no different? How big a
factor was the fact that I wrote both functions (StartSort and IsSorted)
out before attempting to find duplication?

I could have used another Strategy pattern instead of using
member-function pointers. Why do you think I didn't? Do you think I
should have?

Any other questions? :-)

Relevant Pages

  • RE: Controling Modal Dialogs (Solution)
    ... doesn't return until the 'modal' browser returns. ... string varOptions) ... public void DocumentComplete ... int rc = winDisp.Invoke(rgDispId, ref guid, 0, ...
    (microsoft.public.inetsdk.programming.webbrowser_ctl)
  • Help in Java swings(internal Frame)
    ... public int getSize() ... public void valueChanged{ ... private JScrollPane scrollPane1; ... public class PeakContainer extends JInternalFrame ...
    (comp.lang.java.programmer)
  • [PATCH] get rid if __cpuinit and __cpuexit
    ... unsigned long action, void *hcpu) ... unsigned int cpu = hcpu; ... -static int __cpuinit ... __cpu_up(unsigned int cpu) ...
    (Linux-Kernel)
  • Re: question about assigning null to a reference object
    ... String getAuthor() ... int getPages() ... void setAuthor ... b.setTitle("Thinking in Java 54th Edition"); ...
    (comp.lang.java.help)
  • [PATCH,RFC 2.6.14 09/15] KGDB: SuperH-specific changes
    ... This adds basic support for KGDB on SuperH as well as adding some architecture ... -static int kgdb_uart_getchar ... -static void kgdb_uart_putchar ... * The command-line option can include a serial port specification ...
    (Linux-Kernel)