1 /* 2 * tArrayUtils.h 3 * Avida 4 * from ThinkTank 5 * 6 * Created by David on 11/19/06. 7 * Copyright 2006,2008 David Michael Bryson. All rights reserved. 8 * 9 * This file is part of Avida. 10 * 11 * Avida is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License 12 * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. 13 * 14 * Avida is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public License along with Avida. 18 * If not, see <http://www.gnu.org/licenses/>. 19 * 20 */ 21 22 #ifndef tArrayUtils_h 23 #define tArrayUtils_h 24 25 template<typename T> class tArray; 26 template<typename T> class tManagedPointerArray; 27 template<typename T> class tSmartArray; 28 29 30 class tArrayUtils 31 { 32 private: 33 static const int QUICKSORT_THRESHOLD = 10; 34 35 tArrayUtils(); // @not_implemented 36 tArrayUtils(const tArrayUtils&); // @not_implemented 37 tArrayUtils& operator=(const tArrayUtils&); // @not_implemented 38 39 40 public: 41 QSort(tArray<T> & array)42 template<typename T> inline static void QSort(tArray<T>& array) { QSort(array, 0, array.GetSize() - 1); } QSort(tArray<T> & array,int begin,int end)43 template<typename T> static void QSort(tArray<T>& array, int begin, int end) 44 { 45 if (end < begin) return; 46 47 if (begin - end <= QUICKSORT_THRESHOLD) { 48 ISort(array, begin, end); 49 return; 50 } 51 52 T pivot = array[begin]; 53 int l = begin + 1; 54 int r = end; 55 56 while (l != r - 1) { 57 if (array[l] > pivot) 58 l++; 59 else 60 array.Swap(l, r--); 61 } 62 63 if (array[l] > pivot && array[r] > pivot) { 64 l = r + 1; 65 } else if (array[l] > pivot && array[r] <= pivot) { 66 l++; r--; 67 } else if (array[l] <= pivot && array[r] > pivot) { 68 array.Swap(l++, r--); 69 } else { 70 r = l - 1; 71 } 72 73 array.Swap(r--, begin); 74 QSort(array, begin, r); 75 QSort(array, l, end); 76 } 77 QSort(tManagedPointerArray<T> & array)78 template<typename T> inline static void QSort(tManagedPointerArray<T>& array) { QSort(array, 0, array.GetSize() - 1); } QSort(tManagedPointerArray<T> & array,int begin,int end)79 template<typename T> static void QSort(tManagedPointerArray<T>& array, int begin, int end) 80 { 81 if (end < begin) return; 82 83 if (begin - end <= QUICKSORT_THRESHOLD) { 84 ISort(array, begin, end); 85 return; 86 } 87 88 T& pivot = array[begin]; 89 int l = begin + 1; 90 int r = end; 91 92 while (l != r - 1) { 93 if (array[l] > pivot) 94 l++; 95 else 96 array.Swap(l, r--); 97 } 98 99 if (array[l] > pivot && array[r] > pivot) { 100 l = r + 1; 101 } else if (array[l] > pivot && array[r] <= pivot) { 102 l++; r--; 103 } else if (array[l] <= pivot && array[r] > pivot) { 104 array.Swap(l++, r--); 105 } else { 106 r = l - 1; 107 } 108 109 array.Swap(r--, begin); 110 QSort(array, begin, r); 111 QSort(array, l, end); 112 } 113 QSort(tSmartArray<T> & array)114 template<typename T> inline static void QSort(tSmartArray<T>& array) { QSort(array, 0, array.GetSize() - 1); } QSort(tSmartArray<T> & array,int begin,int end)115 template<typename T> static void QSort(tSmartArray<T>& array, int begin, int end) 116 { 117 if (end < begin) return; 118 119 if (begin - end <= QUICKSORT_THRESHOLD) { 120 ISort(array, begin, end); 121 return; 122 } 123 124 T pivot = array[begin]; 125 int l = begin + 1; 126 int r = end; 127 128 while (l != r - 1) { 129 if (array[l] > pivot) 130 l++; 131 else 132 array.Swap(l, r--); 133 } 134 135 if (array[l] > pivot && array[r] > pivot) { 136 l = r + 1; 137 } else if (array[l] > pivot && array[r] <= pivot) { 138 l++; r--; 139 } else if (array[l] <= pivot && array[r] > pivot) { 140 array.Swap(l++, r--); 141 } else { 142 r = l - 1; 143 } 144 145 array.Swap(r--, begin); 146 QSort(array, begin, r); 147 QSort(array, l, end); 148 } 149 150 151 ISort(tArray<T> & array)152 template<typename T> inline static void ISort(tArray<T>& array) { ISort(array, 0, array.GetSize() - 1); } ISort(tArray<T> & array,int begin,int end)153 template<typename T> static void ISort(tArray<T>& array, int begin, int end) 154 { 155 T value; 156 int j; 157 158 // for each entry 159 for (int i = begin + 1; i <= end; i++) { 160 // insert into array starting from the end of our sub-array 161 value = array[i]; 162 j = i - 1; 163 while (j >= begin && array[j] < value) { 164 array[j + 1] = array[j]; 165 j--; 166 } 167 array[j + 1] = value; 168 } 169 } 170 ISort(tManagedPointerArray<T> & array)171 template<typename T> inline static void ISort(tManagedPointerArray<T>& array) { ISort(array, 0, array.GetSize() - 1); } ISort(tManagedPointerArray<T> & array,int begin,int end)172 template<typename T> static void ISort(tManagedPointerArray<T>& array, int begin, int end) 173 { 174 T value; 175 int j; 176 177 // for each entry 178 for (int i = begin + 1; i <= end; i++) { 179 // insert into array starting from the end of our sub-array 180 value = array[i]; 181 j = i - 1; 182 while (j >= begin && array[j] < array[j + 1]) { 183 array.Swap(j, j + 1); 184 j--; 185 } 186 } 187 } 188 ISort(tSmartArray<T> & array)189 template<typename T> inline static void ISort(tSmartArray<T>& array) { ISort(array, 0, array.GetSize() - 1); } ISort(tSmartArray<T> & array,int begin,int end)190 template<typename T> static void ISort(tSmartArray<T>& array, int begin, int end) 191 { 192 T value; 193 int j; 194 195 // for each entry 196 for (int i = begin + 1; i <= end; i++) { 197 // insert into array starting from the end of our sub-array 198 value = array[i]; 199 j = i - 1; 200 while (j >= begin && array[j] < value) { 201 array[j + 1] = array[j]; 202 j--; 203 } 204 array[j + 1] = value; 205 } 206 } 207 }; 208 209 #endif 210