source/modules/juce_core/containers/juce_ElementComparator.h

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library.
   5    Copyright (c) 2022 - Raw Material Software Limited
   6
   7    JUCE is an open source library subject to commercial or open-source
   8    licensing.
   9
  10    The code included in this file is provided under the terms of the ISC license
  11    http://www.isc.org/downloads/software-support-policy/isc-license. Permission
  12    To use, copy, modify, and/or distribute this software for any purpose with or
  13    without fee is hereby granted provided that the above copyright notice and
  14    this permission notice appear in all copies.
  15
  16    JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
  17    EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
  18    DISCLAIMED.
  19
  20   ==============================================================================
  21 */
  22
  23 namespace juce
  24 {
  25
  26 #ifndef DOXYGEN
  27
  28 /** This is an internal helper class which converts a juce ElementComparator style
  29     class (using a "compareElements" method) into a class that's compatible with
  30     std::sort (i.e. using an operator() to compare the elements)
  31
  32     @tags{Core}
  33 */
  34 template <typename ElementComparator>
  35 struct SortFunctionConverter
  36 {
  37     SortFunctionConverter (ElementComparator& e) : comparator (e) {}
  38     SortFunctionConverter (const SortFunctionConverter&) = default;
  39
  40     template <typename Type>
  41     bool operator() (Type a, Type b)  { return comparator.compareElements (a, b) < 0; }
  42
  43 private:
  44     ElementComparator& comparator;
  45
  46     SortFunctionConverter& operator= (const SortFunctionConverter&) = delete;
  47 };
  48
  49 #endif
  50
  51
  52 //==============================================================================
  53 /**
  54     Sorts a range of elements in an array.
  55
  56     The comparator object that is passed-in must define a public method with the following
  57     signature:
  58     @code
  59     int compareElements (ElementType first, ElementType second);
  60     @endcode
  61
  62     ..and this method must return:
  63       - a value of < 0 if the first comes before the second
  64       - a value of 0 if the two objects are equivalent
  65       - a value of > 0 if the second comes before the first
  66
  67     To improve performance, the compareElements() method can be declared as static or const.
  68
  69     @param comparator       an object which defines a compareElements() method
  70     @param array            the array to sort
  71     @param firstElement     the index of the first element of the range to be sorted
  72     @param lastElement      the index of the last element in the range that needs
  73                             sorting (this is inclusive)
  74     @param retainOrderOfEquivalentItems     if true, the order of items that the
  75                             comparator deems the same will be maintained - this will be
  76                             a slower algorithm than if they are allowed to be moved around.
  77
  78     @see sortArrayRetainingOrder
  79 */
  80 template <class ElementType, class ElementComparator>
  81 static void sortArray (ElementComparator& comparator,
  82                        ElementType* const array,
  83                        int firstElement,
  84                        int lastElement,
  85                        const bool retainOrderOfEquivalentItems)
  86 {
  87     jassert (firstElement >= 0);
  88
  89     if (lastElement > firstElement)
  90     {
  91         SortFunctionConverter<ElementComparator> converter (comparator);
  92
  93         if (retainOrderOfEquivalentItems)
  94             std::stable_sort (array + firstElement, array + lastElement + 1, converter);
  95         else
  96             std::sort        (array + firstElement, array + lastElement + 1, converter);
  97     }
  98 }
  99
 100
 101 //==============================================================================
 102 /**
 103     Searches a sorted array of elements, looking for the index at which a specified value
 104     should be inserted for it to be in the correct order.
 105
 106     The comparator object that is passed-in must define a public method with the following
 107     signature:
 108     @code
 109     int compareElements (ElementType first, ElementType second);
 110     @endcode
 111
 112     ..and this method must return:
 113       - a value of < 0 if the first comes before the second
 114       - a value of 0 if the two objects are equivalent
 115       - a value of > 0 if the second comes before the first
 116
 117     To improve performance, the compareElements() method can be declared as static or const.
 118
 119     @param comparator       an object which defines a compareElements() method
 120     @param array            the array to search
 121     @param newElement       the value that is going to be inserted
 122     @param firstElement     the index of the first element to search
 123     @param lastElement      the index of the last element in the range (this is non-inclusive)
 124 */
 125 template <class ElementType, class ElementComparator>
 126 static int findInsertIndexInSortedArray (ElementComparator& comparator,
 127                                          ElementType* const array,
 128                                          const ElementType newElement,
 129                                          int firstElement,
 130                                          int lastElement)
 131 {
 132     jassert (firstElement <= lastElement);
 133
 134     ignoreUnused (comparator); // if you pass in an object with a static compareElements() method, this
 135                                // avoids getting warning messages about the parameter being unused
 136
 137     while (firstElement < lastElement)
 138     {
 139         if (comparator.compareElements (newElement, array [firstElement]) == 0)
 140         {
 141             ++firstElement;
 142             break;
 143         }
 144         else
 145         {
 146             const int halfway = (firstElement + lastElement) >> 1;
 147
 148             if (halfway == firstElement)
 149             {
 150                 if (comparator.compareElements (newElement, array [halfway]) >= 0)
 151                     ++firstElement;
 152
 153                 break;
 154             }
 155             else if (comparator.compareElements (newElement, array [halfway]) >= 0)
 156             {
 157                 firstElement = halfway;
 158             }
 159             else
 160             {
 161                 lastElement = halfway;
 162             }
 163         }
 164     }
 165
 166     return firstElement;
 167 }
 168
 169 //==============================================================================
 170 /**
 171     A simple ElementComparator class that can be used to sort an array of
 172     objects that support the '<' operator.
 173
 174     This will work for primitive types and objects that implement operator<().
 175
 176     Example: @code
 177     Array<int> myArray;
 178     DefaultElementComparator<int> sorter;
 179     myArray.sort (sorter);
 180     @endcode
 181
 182     @see ElementComparator
 183
 184     @tags{Core}
 185 */
 186 template <class ElementType>
 187 class DefaultElementComparator
 188 {
 189 private:
 190     using ParameterType = typename TypeHelpers::ParameterType<ElementType>::type;
 191
 192 public:
 193     static int compareElements (ParameterType first, ParameterType second)
 194     {
 195         return (first < second) ? -1 : ((second < first) ? 1 : 0);
 196     }
 197 };
 198
 199 } // namespace juce