/*
 *  ======================================================================
 *  test_bubble2.c : Implement bubble sort with compare function.
 * 
 *  Copyright (C) 1993-96 by Mark Austin and David Mazzoni.
 *                                                                     
 *  This software is provided "as is" without express or implied warranty.
 *  Permission is granted to use this software on any computer system,
 *  and to redistribute it freely, subject to the following restrictions:
 * 
 *  1. The authors are not responsible for the consequences of use of
 *     this software, even if they arise from defects in the software.
 *  2. The origin of this software must not be misrepresented, either
 *     by explicit claim or by omission.
 *  3. Altered versions must be plainly marked as such, and must not
 *     be misrepresented as being the original software.
 *  4. This notice is to remain intact.
 *  ======================================================================
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum {Max=256};  /* buffer size for copying */

int main( void ) {
   /* [a] : forward function declarations */

   int compare( const void* kvpOne, const void* kvpTwo );
   void bubble( void* vpBase, size_t stSize, size_t stNumber,
               int (*compare)(const void*, const void*) );

   /* [b] : setup strings to sort */

   char* cpaList[] = { "this", "is", "a", "word", "list" };
   size_t stSize   = sizeof( cpaList ) / sizeof( cpaList[0] );

   /* [c] : Print contents of unsorted list */

   int iLine; /* for printing the lines */
   printf("Details of unsorted cpaList[]\n");
   for( iLine = 0; iLine < stSize; iLine++ )
        printf( "cpaList[%2d] : string = %-6s : address = %x\n",
                iLine, cpaList[iLine], &(*cpaList[iLine]) );

   /* [d] : call bubble() to sort strings */

   bubble( (void*) cpaList, sizeof( cpaList[0] ), stSize, compare );

   /* [e] : Print contents of sorted list */

   printf("\nDetails of sorted cpaList[]\n");
   for( iLine = 0; iLine < stSize; iLine++ )
        printf( "cpaList[%2d] : string = %-6s : address = %x\n",
                iLine, cpaList[iLine], &(*cpaList[iLine]) );
}

/* 
 *  ===========================================================
 *  Bubble sort the array "vpBase"
 * 
 *  Input: void * vpBase   --
 *         size_t stSize   --
 *         size_t stNumber --
 *         int (*compare)(const void*, const void*) ) -- pointer
 *                            to comparison function.
 *  Output: void --
 *  ===========================================================
 */ 

void bubble( void* vpBase, size_t stSize, size_t stNumber,
             int (*compare)(const void*, const void*) ) {
  int iIndex,  /* index of elements to test           */
      iPass;   /* number of the pass through the list */

  iPass = stNumber-1;
  while( iPass > 0 ) { /* there are still elements to compare */
    iIndex = 0;
    while( iIndex < iPass ) {
       /* cast addresses to char* then manually index out to the right address */

       char* cpBase   = (char*)vpBase;
       char* cpFirst  = cpBase + iIndex*stSize;
       char* cpSecond = cpBase + (iIndex+1)*stSize;

       if( compare( cpFirst, cpSecond ) > 0 ) { /* swap */
           char caBuf[Max];
           memcpy( caBuf, cpFirst, stSize );
           memcpy( cpFirst, cpSecond, stSize );
           memcpy( cpSecond, caBuf, stSize );
       }
       iIndex += 1; /* compare the next two array elements */
    }
    iPass -= 1;
  }
  return;
}

/* 
 *  =============================================================
 *  Function for string comparison 
 * 
 *  Input: const void* kvpOne --
 *         const void* kvpTwo --
 *  Output: int               --
 * 
 *  Note : We know these void ptrs are really referring to char's 
 *  =============================================================
 */ 

int compare( const void* kvpOne, const void* kvpTwo ) {
    return strcmp( *(char**)kvpOne, *(char**)kvpTwo );
}