michael@0: /*
michael@0: *******************************************************************************
michael@0: *
michael@0: *   Copyright (C) 2003-2013, International Business Machines
michael@0: *   Corporation and others.  All Rights Reserved.
michael@0: *
michael@0: *******************************************************************************
michael@0: *   file name:  uarrsort.c
michael@0: *   encoding:   US-ASCII
michael@0: *   tab size:   8 (not used)
michael@0: *   indentation:4
michael@0: *
michael@0: *   created on: 2003aug04
michael@0: *   created by: Markus W. Scherer
michael@0: *
michael@0: *   Internal function for sorting arrays.
michael@0: */
michael@0: 
michael@0: #include "unicode/utypes.h"
michael@0: #include "cmemory.h"
michael@0: #include "uarrsort.h"
michael@0: 
michael@0: enum {
michael@0:     /**
michael@0:      * "from Knuth"
michael@0:      *
michael@0:      * A binary search over 8 items performs 4 comparisons:
michael@0:      * log2(8)=3 to subdivide, +1 to check for equality.
michael@0:      * A linear search over 8 items on average also performs 4 comparisons.
michael@0:      */
michael@0:     MIN_QSORT=9,
michael@0:     STACK_ITEM_SIZE=200
michael@0: };
michael@0: 
michael@0: /* UComparator convenience implementations ---------------------------------- */
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2
michael@0: uprv_uint16Comparator(const void *context, const void *left, const void *right) {
michael@0:     return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2
michael@0: uprv_int32Comparator(const void *context, const void *left, const void *right) {
michael@0:     return *(const int32_t *)left - *(const int32_t *)right;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2
michael@0: uprv_uint32Comparator(const void *context, const void *left, const void *right) {
michael@0:     uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
michael@0: 
michael@0:     /* compare directly because (l-r) would overflow the int32_t result */
michael@0:     if(l<r) {
michael@0:         return -1;
michael@0:     } else if(l==r) {
michael@0:         return 0;
michael@0:     } else /* l>r */ {
michael@0:         return 1;
michael@0:     }
michael@0: }
michael@0: 
michael@0: /* Insertion sort using binary search --------------------------------------- */
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2
michael@0: uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
michael@0:                         UComparator *cmp, const void *context) {
michael@0:     int32_t start=0;
michael@0:     UBool found=FALSE;
michael@0: 
michael@0:     /* Binary search until we get down to a tiny sub-array. */
michael@0:     while((limit-start)>=MIN_QSORT) {
michael@0:         int32_t i=(start+limit)/2;
michael@0:         int32_t diff=cmp(context, item, array+i*itemSize);
michael@0:         if(diff==0) {
michael@0:             /*
michael@0:              * Found the item. We look for the *last* occurrence of such
michael@0:              * an item, for stable sorting.
michael@0:              * If we knew that there will be only few equal items,
michael@0:              * we could break now and enter the linear search.
michael@0:              * However, if there are many equal items, then it should be
michael@0:              * faster to continue with the binary search.
michael@0:              * It seems likely that we either have all unique items
michael@0:              * (where found will never become TRUE in the insertion sort)
michael@0:              * or potentially many duplicates.
michael@0:              */
michael@0:             found=TRUE;
michael@0:             start=i+1;
michael@0:         } else if(diff<0) {
michael@0:             limit=i;
michael@0:         } else {
michael@0:             start=i;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Linear search over the remaining tiny sub-array. */
michael@0:     while(start<limit) {
michael@0:         int32_t diff=cmp(context, item, array+start*itemSize);
michael@0:         if(diff==0) {
michael@0:             found=TRUE;
michael@0:         } else if(diff<0) {
michael@0:             break;
michael@0:         }
michael@0:         ++start;
michael@0:     }
michael@0:     return found ? (start-1) : ~start;
michael@0: }
michael@0: 
michael@0: static void
michael@0: doInsertionSort(char *array, int32_t length, int32_t itemSize,
michael@0:                 UComparator *cmp, const void *context, void *pv) {
michael@0:     int32_t j;
michael@0: 
michael@0:     for(j=1; j<length; ++j) {
michael@0:         char *item=array+j*itemSize;
michael@0:         int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
michael@0:         if(insertionPoint<0) {
michael@0:             insertionPoint=~insertionPoint;
michael@0:         } else {
michael@0:             ++insertionPoint;  /* one past the last equal item */
michael@0:         }
michael@0:         if(insertionPoint<j) {
michael@0:             char *dest=array+insertionPoint*itemSize;
michael@0:             uprv_memcpy(pv, item, itemSize);  /* v=array[j] */
michael@0:             uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*itemSize);
michael@0:             uprv_memcpy(dest, pv, itemSize);  /* array[insertionPoint]=v */
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void
michael@0: insertionSort(char *array, int32_t length, int32_t itemSize,
michael@0:               UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
michael@0:     UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
michael@0:     void *pv;
michael@0: 
michael@0:     /* allocate an intermediate item variable (v) */
michael@0:     if(itemSize<=STACK_ITEM_SIZE) {
michael@0:         pv=v;
michael@0:     } else {
michael@0:         pv=uprv_malloc(itemSize);
michael@0:         if(pv==NULL) {
michael@0:             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     doInsertionSort(array, length, itemSize, cmp, context, pv);
michael@0: 
michael@0:     if(pv!=v) {
michael@0:         uprv_free(pv);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /* QuickSort ---------------------------------------------------------------- */
michael@0: 
michael@0: /*
michael@0:  * This implementation is semi-recursive:
michael@0:  * It recurses for the smaller sub-array to shorten the recursion depth,
michael@0:  * and loops for the larger sub-array.
michael@0:  *
michael@0:  * Loosely after QuickSort algorithms in
michael@0:  * Niklaus Wirth
michael@0:  * Algorithmen und Datenstrukturen mit Modula-2
michael@0:  * B.G. Teubner Stuttgart
michael@0:  * 4. Auflage 1986
michael@0:  * ISBN 3-519-02260-5
michael@0:  */
michael@0: static void
michael@0: subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
michael@0:              UComparator *cmp, const void *context,
michael@0:              void *px, void *pw) {
michael@0:     int32_t left, right;
michael@0: 
michael@0:     /* start and left are inclusive, limit and right are exclusive */
michael@0:     do {
michael@0:         if((start+MIN_QSORT)>=limit) {
michael@0:             doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         left=start;
michael@0:         right=limit;
michael@0: 
michael@0:         /* x=array[middle] */
michael@0:         uprv_memcpy(px, array+((start+limit)/2)*itemSize, itemSize);
michael@0: 
michael@0:         do {
michael@0:             while(/* array[left]<x */
michael@0:                   cmp(context, array+left*itemSize, px)<0
michael@0:             ) {
michael@0:                 ++left;
michael@0:             }
michael@0:             while(/* x<array[right-1] */
michael@0:                   cmp(context, px, array+(right-1)*itemSize)<0
michael@0:             ) {
michael@0:                 --right;
michael@0:             }
michael@0: 
michael@0:             /* swap array[left] and array[right-1] via w; ++left; --right */
michael@0:             if(left<right) {
michael@0:                 --right;
michael@0: 
michael@0:                 if(left<right) {
michael@0:                     uprv_memcpy(pw, array+left*itemSize, itemSize);
michael@0:                     uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize);
michael@0:                     uprv_memcpy(array+right*itemSize, pw, itemSize);
michael@0:                 }
michael@0: 
michael@0:                 ++left;
michael@0:             }
michael@0:         } while(left<right);
michael@0: 
michael@0:         /* sort sub-arrays */
michael@0:         if((right-start)<(limit-left)) {
michael@0:             /* sort [start..right[ */
michael@0:             if(start<(right-1)) {
michael@0:                 subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
michael@0:             }
michael@0: 
michael@0:             /* sort [left..limit[ */
michael@0:             start=left;
michael@0:         } else {
michael@0:             /* sort [left..limit[ */
michael@0:             if(left<(limit-1)) {
michael@0:                 subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
michael@0:             }
michael@0: 
michael@0:             /* sort [start..right[ */
michael@0:             limit=right;
michael@0:         }
michael@0:     } while(start<(limit-1));
michael@0: }
michael@0: 
michael@0: static void
michael@0: quickSort(char *array, int32_t length, int32_t itemSize,
michael@0:             UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
michael@0:     UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
michael@0:     void *p;
michael@0: 
michael@0:     /* allocate two intermediate item variables (x and w) */
michael@0:     if(itemSize<=STACK_ITEM_SIZE) {
michael@0:         p=xw;
michael@0:     } else {
michael@0:         p=uprv_malloc(2*itemSize);
michael@0:         if(p==NULL) {
michael@0:             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     subQuickSort(array, 0, length, itemSize,
michael@0:                  cmp, context, p, (char *)p+itemSize);
michael@0: 
michael@0:     if(p!=xw) {
michael@0:         uprv_free(p);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /* uprv_sortArray() API ----------------------------------------------------- */
michael@0: 
michael@0: /*
michael@0:  * Check arguments, select an appropriate implementation,
michael@0:  * cast the array to char * so that array+i*itemSize works.
michael@0:  */
michael@0: U_CAPI void U_EXPORT2
michael@0: uprv_sortArray(void *array, int32_t length, int32_t itemSize,
michael@0:                UComparator *cmp, const void *context,
michael@0:                UBool sortStable, UErrorCode *pErrorCode) {
michael@0:     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
michael@0:         return;
michael@0:     }
michael@0:     if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
michael@0:         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if(length<=1) {
michael@0:         return;
michael@0:     } else if(length<MIN_QSORT || sortStable) {
michael@0:         insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
michael@0:     } else {
michael@0:         quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
michael@0:     }
michael@0: }