git.cworth.org Git - vogl/blob - src/voglcore/vogl_mergesort.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_mergesort.h
  28 // This isn't very fast, and requires extra storage, but it's a reasonably fast stable sort with no degenerate cases.
  29 #ifndef VOGL_MERGESORT_H
  30 #define VOGL_MERGESORT_H
  31
  32 #include "vogl_core.h"
  33
  34 namespace vogl
  35 {
  36     template <typename T>
  37     struct mergesort_use_swaps_during_merge
  38     {
  39         enum
  40         {
  41             cFlag = false
  42         };
  43     };
  44
  45 #define VOGL_MERGESORT_USE_SWAPS_DURING_MERGE(T)         \
  46     template <> struct mergesort_use_swaps_during_merge<T> \
  47     {                                                      \
  48         enum { cFlag = true };                             \
  49     };
  50
  51     VOGL_MERGESORT_USE_SWAPS_DURING_MERGE(dynamic_string);
  52
  53     namespace detail
  54     {
  55
  56         template <typename T, typename Comparator>
  57         inline void BottomUpMerge(vogl::vector<T> &A, uint iLeft, uint iRight, uint iEnd, vogl::vector<T> &B, Comparator comp)
  58         {
  59             uint i0 = iLeft;
  60             uint i1 = iRight;
  61
  62 #if 0
  63         /* While there are elements in the left or right lists */
  64         for (uint j = iLeft; j < iEnd; j++)
  65         {
  66                 /* If left list head exists and is <= existing right list head */
  67                 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
  68                 {
  69                         B[j] = A[i0];
  70                         ++i0;
  71                 }
  72                 else
  73                 {
  74                         B[j] = A[i1];
  75                         ++i1;
  76                 }
  77         }
  78 #else
  79             uint j = iLeft;
  80
  81             if ((i0 < iRight) && (i1 < iEnd))
  82             {
  83                 while (j < iEnd)
  84                 {
  85                     if (!comp(A[i1], A[i0]))
  86                     {
  87                         B[j++] = A[i0++];
  88                         if (i0 >= iRight)
  89                             goto special;
  90                     }
  91                     else
  92                     {
  93                         B[j++] = A[i1++];
  94                         if (i1 >= iEnd)
  95                             goto special;
  96                     }
  97                 }
  98                 return;
  99             }
 100
 101         special:
 102             while (j < iEnd)
 103             {
 104                 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
 105                     B[j++] = A[i0++];
 106                 else
 107                     B[j++] = A[i1++];
 108             }
 109 #endif
 110         }
 111
 112         template <typename T, typename Comparator>
 113         inline void BottomUpMergeSwap(vogl::vector<T> &A, uint iLeft, uint iRight, uint iEnd, vogl::vector<T> &B, Comparator comp)
 114         {
 115             uint i0 = iLeft;
 116             uint i1 = iRight;
 117
 118 #if 0
 119         /* While there are elements in the left or right lists */
 120         for (uint j = iLeft; j < iEnd; j++)
 121         {
 122                 /* If left list head exists and is <= existing right list head */
 123                 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
 124                 {
 125                         B[j] = A[i0];
 126                         ++i0;
 127                 }
 128                 else
 129                 {
 130                         B[j] = A[i1];
 131                         ++i1;
 132                 }
 133         }
 134 #else
 135             uint j = iLeft;
 136
 137             if ((i0 < iRight) && (i1 < iEnd))
 138             {
 139                 while (j < iEnd)
 140                 {
 141                     if (!comp(A[i1], A[i0]))
 142                     {
 143                         std::swap(B[j++], A[i0++]);
 144                         if (i0 >= iRight)
 145                             goto special;
 146                     }
 147                     else
 148                     {
 149                         std::swap(B[j++], A[i1++]);
 150                         if (i1 >= iEnd)
 151                             goto special;
 152                     }
 153                 }
 154                 return;
 155             }
 156
 157         special:
 158             while (j < iEnd)
 159             {
 160                 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
 161                     std::swap(B[j++], A[i0++]);
 162                 else
 163                     std::swap(B[j++], A[i1++]);
 164             }
 165 #endif
 166         }
 167
 168         /* array A[] has the items to sort; array B[] is a work array */
 169         template <typename T, typename Comparator>
 170         inline void BottomUpSort(vogl::vector<T> &A, Comparator comp)
 171         {
 172             const uint n = A.size();
 173
 174             vogl::vector<T> B(n);
 175
 176             /* Each 1-element run in A is already "sorted". */
 177
 178             /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
 179             for (uint width = 1; width < n; width = 2 * width)
 180             {
 181                 /* Array A is full of runs of length width. */
 182                 for (uint i = 0; i < n; i = i + 2 * width)
 183                 {
 184                     /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
 185                     /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
 186                     if (mergesort_use_swaps_during_merge<T>::cFlag)
 187                         BottomUpMergeSwap(A, i, math::minimum(i + width, n), math::minimum(i + 2 * width, n), B, comp);
 188                     else
 189                         BottomUpMerge(A, i, math::minimum(i + width, n), math::minimum(i + 2 * width, n), B, comp);
 190                 }
 191
 192                 /* Now work array B is full of runs of length 2*width. */
 193                 /* Swap array B to array A for next iteration. */
 194                 A.swap(B);
 195                 /* Now array A is full of runs of length 2*width. */
 196             }
 197         }
 198
 199     } // namespace detail
 200
 201     template <typename T, typename Comparator>
 202     inline void mergesort(vogl::vector<T> &elems, Comparator comp)
 203     {
 204         detail::BottomUpSort(elems, comp);
 205     }
 206
 207     template <typename T>
 208     inline void mergesort(vogl::vector<T> &elems)
 209     {
 210         mergesort(elems, std::less<T>());
 211     }
 212
 213 } // namespace vogl
 214
 215 #endif // VOGL_MERGESORT_H