1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the class library                   */
4    	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SoPlex; see the file LICENSE. If not email to soplex@zib.de.  */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file  sorter.h
26   	 * @brief Generic QuickSort implementation.
27   	 */
28   	#ifndef _SORTER_H_
29   	#define _SORTER_H_
30   	
31   	#include <assert.h>
32   	
33   	namespace soplex
34   	{
35   	#define SOPLEX_SHELLSORTMAX 25
36   	
37   	/** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */
38   	template < class T, class COMPARATOR >
39   	void SPxShellsort(T* keys, int end, COMPARATOR& compare, int start = 0)
40   	{
41   	   static const int incs[3] = {1, 5, 19}; /* sequence of increments */
42   	   int k;
43   	
44   	   assert(start <= end);
45   	
46   	   for(k = 2; k >= 0; --k)
47   	   {
48   	      int h = incs[k];
49   	      int first = h + start;
50   	      int i;
51   	
52   	      for(i = first; i <= end; ++i)
53   	      {
54   	         int j;
55   	         T tempkey = keys[i];
56   	
57   	         j = i;
58   	
59   	         while(j >= first && compare(tempkey, keys[j - h]) < 0)
60   	         {
61   	            keys[j] = keys[j - h];
62   	            j -= h;
63   	         }
64   	
65   	         keys[j] = tempkey;
66   	      }
67   	   }
68   	}
69   	
70   	
71   	
72   	/// Generic QuickSort implementation.
73   	/** This template function sorts an array \p t holding \p n elements of
74   	    type T using \p compare for comparisons. Class COMPARATOR must provide
75   	    an overloaded operator()(const T& t1,const T& t2) which returns
76   	    - < 0, if \p t1 is to appear before \p t2,
77   	    - = 0, if \p t1 and \p t2 can appear in any order, or
78   	    - > 0, if \p t1 is to appear after \p t2.
79   	*/
80   	
81   	template < class T, class COMPARATOR >
82   	void SPxQuicksort(T* keys, int end, COMPARATOR& compare, int start = 0, bool type = true)
83   	{
84   	   assert(start >= 0);
85   	
86   	   /* nothing to sort for less than two elements */
87   	   if(end <= start + 1)
88   	      return;
89   	
90   	   /* reduce end position to last element index */
91   	   --end;
92   	
93   	   /* use quick-sort for long lists */
94   	   while(end - start >= SOPLEX_SHELLSORTMAX)
95   	   {
96   	      T pivotkey;
97   	      T tmp;
98   	      int lo;
99   	      int hi;
100  	      int mid;
101  	
102  	      /* select pivot element */
103  	      mid = start + (end - start) / 2; // Instead of (start + end)/2 because the
104  	      // latter can overflow if start + end >
105  	      // INT_MAX
106  	      pivotkey = keys[mid];
107  	
108  	      /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
109  	      lo = start;
110  	      hi = end;
111  	
112  	      for(;;)
113  	      {
114  	         if(type)
115  	         {
116  	            while(lo < end && compare(keys[lo], pivotkey) < 0)
117  	               lo++;
118  	
119  	            while(hi > start && compare(keys[hi], pivotkey) >= 0)
120  	               hi--;
121  	         }
122  	         else
123  	         {
124  	            while(lo < end && compare(keys[lo], pivotkey) <= 0)
125  	               lo++;
126  	
127  	            while(hi > start && compare(keys[hi], pivotkey) > 0)
128  	               hi--;
129  	         }
130  	
131  	         if(lo >= hi)
132  	            break;
133  	
134  	         tmp = keys[lo];
135  	         keys[lo] = keys[hi];
136  	         keys[hi] = tmp;
137  	
138  	         lo++;
139  	         hi--;
140  	      }
141  	
142  	      assert((hi == lo - 1) || (type && hi == start) || (!type && lo == end));
143  	
144  	      /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
145  	      if(type)
146  	      {
147  	         while(lo < end && compare(pivotkey, keys[lo]) >= 0)
148  	            lo++;
149  	
150  	         /* make sure that we have at least one element in the smaller partition */
151  	         if(lo == start)
152  	         {
153  	            /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
154  	            assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */
155  	
156  	            tmp = keys[lo];
157  	            keys[lo] = keys[mid];
158  	            keys[mid] = tmp;
159  	
160  	            lo++;
161  	         }
162  	      }
163  	      else
164  	      {
165  	         while(hi > start && compare(pivotkey, keys[hi]) <= 0)
166  	            hi--;
167  	
168  	         /* make sure that we have at least one element in the smaller partition */
169  	         if(hi == end)
170  	         {
171  	            /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
172  	            assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */
173  	
174  	            tmp = keys[hi];
175  	            keys[hi] = keys[mid];
176  	            keys[mid] = tmp;
177  	
178  	            hi--;
179  	         }
180  	      }
181  	
182  	      /* sort the smaller partition by a recursive call, sort the larger part without recursion */
183  	      if(hi - start <= end - lo)
184  	      {
185  	         /* sort [start,hi] with a recursive call */
186  	         if(start < hi)
187  	         {
188  	            SPxQuicksort(keys, hi + 1, compare, start, !type);
189  	         }
190  	
191  	         /* now focus on the larger part [lo,end] */
192  	         start = lo;
193  	      }
194  	      else
195  	      {
196  	         if(lo < end)
197  	         {
198  	            SPxQuicksort(keys, end + 1, compare, lo, !type);
199  	         }
200  	
201  	         /* now focus on the larger part [start,hi] */
202  	         end = hi;
203  	      }
204  	
205  	      type = !type;
206  	   }
207  	
208  	   /* use shell sort on the remaining small list */
209  	   if(end - start >= 1)
210  	   {
211  	      SPxShellsort(keys, end, compare, start);
212  	   }
213  	
214  	
215  	#ifdef CHECK_SORTING
216  	
217  	   for(int i = start; i < end; ++i)
218  	      assert(compare(keys[i], keys[i + 1]) <= 0);
219  	
220  	#endif
221  	}
222  	
223  	
224  	/**@brief  Generic implementation of Partial QuickSort.
225  	 *
226  	 * This template function sorts an array \p t holding \p n elements of
227  	 * type T partially using \p compare for comparisons, i.e. ensures that
228  	 * the \p size smallest elements are sorted to the front.
229  	 *
230  	 * Class COMPARATOR must provide an overloaded
231  	 * operator()(const T& t1,const T& t2) which returns
232  	 * - < 0, if \p t1 is to appear before \p t2,
233  	 * - = 0, if \p t1 and \p t2 can appear in any order, or
234  	 * - > 0, if \p t1 is to appear after \p t2.
235  	 *
236  	 * @param keys               array of elements to be sorted between index start and end
237  	 * @param compare            comparator
238  	 * @param start              index of first element in range to be sorted
239  	 * @param end                index of last element in range to be sorted, plus 1
240  	 * @param size               guaranteed number of sorted elements
241  	 * @param start2             auxiliary start index of sub range used for recursive call
242  	 * @param end2               auxiliary end index of sub range used for recursive call
243  	 * @param type               type of sorting, to be more flexable on degenerated cases
244  	 */
245  	template < class T, class COMPARATOR >
246  	int SPxQuicksortPart(T* keys, COMPARATOR& compare, int start, int end, int size, int start2 = 0,
247  	                     int end2 = 0, bool type = true)
248  	{
249  	   assert(start >= 0);
250  	
251  	   /* nothing to sort for less than two elements */
252  	   if(end < start + 1)
253  	      return 0;
254  	   else if(end == start + 1)
255  	      return 1;
256  	
257  	   /* we assume that range {start, ..., start2-1} already contains the start2-start smallest elements in sorted order;
258  	    * start2 has to lie in {start, ..., end-1} */
259  	   if(start2 < start)
260  	      start2 = start;
261  	
262  	#ifdef CHECK_SORTING
263  	   assert(start2 < end);
264  	
265  	   for(int i = start; i < start2 - 1; ++i)
266  	      assert(compare(keys[i], keys[i + 1]) <= 0);
267  	
268  	#endif
269  	   assert(end2 <= end);
270  	
271  	   /* if all remaining elements should be sorted, we simply call standard quicksort */
272  	   if(start2 + size >= end - 1)
273  	   {
274  	      SPxQuicksort(keys, end, compare, start2, type);
275  	      return end - 1;
276  	   }
277  	
278  	   T pivotkey;
279  	   T tmp;
280  	   int lo;
281  	   int hi;
282  	   int mid;
283  	
284  	   /* reduce end position to last element index */
285  	   --end;
286  	
287  	   /* select pivot element */
288  	   mid = (start2 + end) / 2;
289  	   pivotkey = keys[mid];
290  	
291  	   /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
292  	   lo = start2;
293  	   hi = end;
294  	
295  	   for(;;)
296  	   {
297  	      if(type)
298  	      {
299  	         while(lo < end && compare(keys[lo], pivotkey) < 0)
300  	            lo++;
301  	
302  	         while(hi > start2 && compare(keys[hi], pivotkey) >= 0)
303  	            hi--;
304  	      }
305  	      else
306  	      {
307  	         while(lo < end && compare(keys[lo], pivotkey) <= 0)
308  	            lo++;
309  	
310  	         while(hi > start2 && compare(keys[hi], pivotkey) > 0)
311  	            hi--;
312  	      }
313  	
314  	      if(lo >= hi)
315  	         break;
316  	
317  	      tmp = keys[lo];
318  	      keys[lo] = keys[hi];
319  	      keys[hi] = tmp;
320  	
321  	      lo++;
322  	      hi--;
323  	   }
324  	
325  	   assert((hi == lo - 1) || (type && hi == start2) || (!type && lo == end));
326  	
327  	   /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
328  	   if(type)
329  	   {
330  	      while(lo < end && compare(pivotkey, keys[lo]) >= 0)
331  	         lo++;
332  	
333  	      /* make sure that we have at least one element in the smaller partition */
334  	      if(lo == start2)
335  	      {
336  	         /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
337  	         assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */
338  	
339  	         tmp = keys[lo];
340  	         keys[lo] = keys[mid];
341  	         keys[mid] = tmp;
342  	
343  	         lo++;
344  	      }
345  	   }
346  	   else
347  	   {
348  	      while(hi > start2 && compare(pivotkey, keys[hi]) <= 0)
349  	         hi--;
350  	
351  	      /* make sure that we have at least one element in the smaller partition */
352  	      if(hi == end)
353  	      {
354  	         /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
355  	         assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */
356  	
357  	         tmp = keys[hi];
358  	         keys[hi] = keys[mid];
359  	         keys[mid] = tmp;
360  	
361  	         hi--;
362  	      }
363  	   }
364  	
365  	#ifdef CHECK_SORTING
366  	
367  	   for(int i = start2; i < lo; ++i)
368  	      assert(compare(keys[i], pivotkey) <= 0);
369  	
370  	#endif
371  	
372  	   /* if we only need to sort less than half of the "<" part, use partial sort again */
373  	   if(2 * size <= hi - start2)
374  	   {
375  	      return SPxQuicksortPart(keys, compare, start, hi + 1, size, start2, end2, !type);
376  	   }
377  	   /* otherwise, and if we do not need to sort the ">" part, use standard quicksort on the "<" part */
378  	   else if(size <= lo - start2)
379  	   {
380  	      SPxQuicksort(keys, hi + 1, compare, start2, !type);
381  	      return lo - 1;
382  	   }
383  	   /* otherwise we have to sort the "<" part fully (use standard quicksort) and the ">" part partially */
384  	   else
385  	   {
386  	      SPxQuicksort(keys, hi + 1, compare, start2, !type);
387  	      return SPxQuicksortPart(keys, compare, start, end + 1, size + start2 - lo, lo, end2, !type);
388  	   }
389  	}
390  	
391  	} // namespace soplex
392  	#endif // _SORTER_H_
393