juce/source/src/containers/juce_ElementComparator.h

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library - "Jules' Utility Class Extensions"
   5    Copyright 2004-11 by Raw Material Software Ltd.
   6
   7   ------------------------------------------------------------------------------
   8
   9    JUCE can be redistributed and/or modified under the terms of the GNU General
  10    Public License (Version 2), as published by the Free Software Foundation.
  11    A copy of the license is included in the JUCE distribution, or can be found
  12    online at www.gnu.org/licenses.
  13
  14    JUCE is distributed in the hope that it will be useful, but WITHOUT ANY
  15    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  16    A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  17
  18   ------------------------------------------------------------------------------
  19
  20    To release a closed-source product which uses JUCE, commercial licenses are
  21    available: visit www.rawmaterialsoftware.com/juce for more information.
  22
  23   ==============================================================================
  24 */
  25
  26 #ifndef __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__
  27 #define __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__
  28
  29
  30 //==============================================================================
  31 /**
  32     Sorts a range of elements in an array.
  33
  34     The comparator object that is passed-in must define a public method with the following
  35     signature:
  36     @code
  37     int compareElements (ElementType first, ElementType second);
  38     @endcode
  39
  40     ..and this method must return:
  41       - a value of < 0 if the first comes before the second
  42       - a value of 0 if the two objects are equivalent
  43       - a value of > 0 if the second comes before the first
  44
  45     To improve performance, the compareElements() method can be declared as static or const.
  46
  47     @param comparator       an object which defines a compareElements() method
  48     @param array            the array to sort
  49     @param firstElement     the index of the first element of the range to be sorted
  50     @param lastElement      the index of the last element in the range that needs
  51                             sorting (this is inclusive)
  52     @param retainOrderOfEquivalentItems     if true, the order of items that the
  53                             comparator deems the same will be maintained - this will be
  54                             a slower algorithm than if they are allowed to be moved around.
  55
  56     @see sortArrayRetainingOrder
  57 */
  58 template <class ElementType, class ElementComparator>
  59 static void sortArray (ElementComparator& comparator,
  60                        ElementType* const array,
  61                        int firstElement,
  62                        int lastElement,
  63                        const bool retainOrderOfEquivalentItems)
  64 {
  65     (void) comparator;  // if you pass in an object with a static compareElements() method, this
  66                         // avoids getting warning messages about the parameter being unused
  67
  68     if (lastElement > firstElement)
  69     {
  70         if (retainOrderOfEquivalentItems)
  71         {
  72             for (int i = firstElement; i < lastElement; ++i)
  73             {
  74                 if (comparator.compareElements (array[i], array [i + 1]) > 0)
  75                 {
  76                     std::swap (array[i], array[i + 1]);
  77
  78                     if (i > firstElement)
  79                         i -= 2;
  80                 }
  81             }
  82         }
  83         else
  84         {
  85             int fromStack[30], toStack[30];
  86             int stackIndex = 0;
  87
  88             for (;;)
  89             {
  90                 const int size = (lastElement - firstElement) + 1;
  91
  92                 if (size <= 8)
  93                 {
  94                     int j = lastElement;
  95                     int maxIndex;
  96
  97                     while (j > firstElement)
  98                     {
  99                         maxIndex = firstElement;
 100                         for (int k = firstElement + 1; k <= j; ++k)
 101                             if (comparator.compareElements (array[k], array [maxIndex]) > 0)
 102                                 maxIndex = k;
 103
 104                         std::swap (array[j], array[maxIndex]);
 105                         --j;
 106                     }
 107                 }
 108                 else
 109                 {
 110                     const int mid = firstElement + (size >> 1);
 111                     std::swap (array[mid], array[firstElement]);
 112
 113                     int i = firstElement;
 114                     int j = lastElement + 1;
 115
 116                     for (;;)
 117                     {
 118                         while (++i <= lastElement
 119                                 && comparator.compareElements (array[i], array [firstElement]) <= 0)
 120                         {}
 121
 122                         while (--j > firstElement
 123                                 && comparator.compareElements (array[j], array [firstElement]) >= 0)
 124                         {}
 125
 126                         if (j < i)
 127                             break;
 128
 129                         std::swap (array[i], array[j]);
 130                     }
 131
 132                     std::swap (array[j], array[firstElement]);
 133
 134                     if (j - 1 - firstElement >= lastElement - i)
 135                     {
 136                         if (firstElement + 1 < j)
 137                         {
 138                             fromStack [stackIndex] = firstElement;
 139                             toStack [stackIndex] = j - 1;
 140                             ++stackIndex;
 141                         }
 142
 143                         if (i < lastElement)
 144                         {
 145                             firstElement = i;
 146                             continue;
 147                         }
 148                     }
 149                     else
 150                     {
 151                         if (i < lastElement)
 152                         {
 153                             fromStack [stackIndex] = i;
 154                             toStack [stackIndex] = lastElement;
 155                             ++stackIndex;
 156                         }
 157
 158                         if (firstElement + 1 < j)
 159                         {
 160                             lastElement = j - 1;
 161                             continue;
 162                         }
 163                     }
 164                 }
 165
 166                 if (--stackIndex < 0)
 167                     break;
 168
 169                 jassert (stackIndex < numElementsInArray (fromStack));
 170
 171                 firstElement = fromStack [stackIndex];
 172                 lastElement = toStack [stackIndex];
 173             }
 174         }
 175     }
 176 }
 177
 178
 179 //==============================================================================
 180 /**
 181     Searches a sorted array of elements, looking for the index at which a specified value
 182     should be inserted for it to be in the correct order.
 183
 184     The comparator object that is passed-in must define a public method with the following
 185     signature:
 186     @code
 187     int compareElements (ElementType first, ElementType second);
 188     @endcode
 189
 190     ..and this method must return:
 191       - a value of < 0 if the first comes before the second
 192       - a value of 0 if the two objects are equivalent
 193       - a value of > 0 if the second comes before the first
 194
 195     To improve performance, the compareElements() method can be declared as static or const.
 196
 197     @param comparator       an object which defines a compareElements() method
 198     @param array            the array to search
 199     @param newElement       the value that is going to be inserted
 200     @param firstElement     the index of the first element to search
 201     @param lastElement      the index of the last element in the range (this is non-inclusive)
 202 */
 203 template <class ElementType, class ElementComparator>
 204 static int findInsertIndexInSortedArray (ElementComparator& comparator,
 205                                          ElementType* const array,
 206                                          const ElementType newElement,
 207                                          int firstElement,
 208                                          int lastElement)
 209 {
 210     jassert (firstElement <= lastElement);
 211
 212     (void) comparator;  // if you pass in an object with a static compareElements() method, this
 213                         // avoids getting warning messages about the parameter being unused
 214
 215     while (firstElement < lastElement)
 216     {
 217         if (comparator.compareElements (newElement, array [firstElement]) == 0)
 218         {
 219             ++firstElement;
 220             break;
 221         }
 222         else
 223         {
 224             const int halfway = (firstElement + lastElement) >> 1;
 225
 226             if (halfway == firstElement)
 227             {
 228                 if (comparator.compareElements (newElement, array [halfway]) >= 0)
 229                     ++firstElement;
 230
 231                 break;
 232             }
 233             else if (comparator.compareElements (newElement, array [halfway]) >= 0)
 234             {
 235                 firstElement = halfway;
 236             }
 237             else
 238             {
 239                 lastElement = halfway;
 240             }
 241         }
 242     }
 243
 244     return firstElement;
 245 }
 246
 247 //==============================================================================
 248 /**
 249     A simple ElementComparator class that can be used to sort an array of
 250     objects that support the '<' operator.
 251
 252     This will work for primitive types and objects that implement operator<().
 253
 254     Example: @code
 255     Array <int> myArray;
 256     DefaultElementComparator<int> sorter;
 257     myArray.sort (sorter);
 258     @endcode
 259
 260     @see ElementComparator
 261 */
 262 template <class ElementType>
 263 class DefaultElementComparator
 264 {
 265 private:
 266     typedef PARAMETER_TYPE (ElementType) ParameterType;
 267
 268 public:
 269     static int compareElements (ParameterType first, ParameterType second)
 270     {
 271         return (first < second) ? -1 : ((second < first) ? 1 : 0);
 272     }
 273 };
 274
 275
 276 #endif   // __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__