/*#################################################################
# Copyright (c) 1991 AT&T Bell Laboratories, All Rights Reserved   
# Published in ``A C++ Primer''  by Stanley Lippman, Addison-Wesley
#################################################################*/
#include <iostream.h>
#include "String.h"

template <class Type>
static void swap (Type *ia, int i, int j )
{ // swap two elements of an array
     Type tmp = ia[ i ];
     ia[ i ] = ia[ j ];
     ia[ j ] = tmp;
}

template <class Type>
void qsort( Type *ia, int low, int high )
{ // quick sort
     if ( low < high ) {
	  int lo = low;
	  int hi = high + 1;
	  Type elem = ia[ low ];
			
          for (;;) {
	      while ( ia[ ++lo ] < elem ) ;
	      while ( ia[ --hi ] > elem ) ;
				
	      if ( lo < hi )
		 swap( ia, lo, hi );
	      else break;
	   }  

	swap( ia, low, hi );
	qsort( ia, low, hi - 1 );
	qsort( ia, hi + 1, high );
	} 
}

const lineLength = 8; // elements to a line

template <class Type>
void display(Type *ia, int size) 
{ // ( 4 ) < 7, 3, 9, 14 > 

     cout << "( " << size << " )< ";
     for (int ix = 0; ix < size; ++ix ) 
     { 
        if (ix % lineLength == 0 && ix)
             cout << "\n\t"; // line filled
        cout << ia[ix];

        // separate all but last element
        if (ix % lineLength != lineLength-1 
            && ix != size-1)
             	cout << ", ";
     }
     cout << " >" << endl;
}

String Sa[] = { "I", "do", "not", "know", "Crane",
	"what", "is", "worse", "this", "job", "or",
	"this", "job", "of", "writing", "you" 
};

main() {
  int size = sizeof(Sa)/sizeof(String);
  cout << "Quicksort of String array (size == " 
       << size << ")" << endl;
  qsort(Sa,0,size-1);
  display(Sa,size); 

  return 0;
}