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