libUTL++
algorithms_inl.h
1 #pragma once
2 
4 
5 UTL_NS_BEGIN;
6 
8 
13 template <class Arg1, class Arg2, class Result>
15 {
16  typedef Arg1 arg1_t;
17  typedef Arg2 arg2_t;
18  typedef Result result_t;
19 };
20 
22 
27 template <class T>
28 struct subtract : public binaryFunction<T, T, T>
29 {
36  T operator()(const T& lhs, const T& rhs) const
37  {
38  return (lhs - rhs);
39  }
40 };
41 
43 
48 template <class T>
49 struct subtractReverse : public binaryFunction<T, T, T>
50 {
57  T operator()(const T& lhs, const T& rhs) const
58  {
59  return (rhs - lhs);
60  }
61 };
62 
64 
70 {
71 public:
73  {
74  _object = nullptr;
75  _str = nullptr;
76  }
77 
78  MultiKeyObject(const Object* object, const char* str)
79  {
80  _object = object;
81  _str = str;
82  }
83 
85  const Object*
86  getObject() const
87  {
88  return _object;
89  }
90 
92  const char& operator[](size_t idx) const
93  {
94  return _str[idx];
95  }
96 
98  const char* operator+(size_t num) const
99  {
100  return _str + num;
101  }
102 
103  // required by Vector
104  bool operator==(const MultiKeyObject& rhs) const
105  {
106  ABORT();
107  return 0;
108  }
109 
110  // required by Vector
111  int operator<(const MultiKeyObject& rhs) const
112  {
113  ABORT();
114  return 0;
115  }
116 
117  // required by Vector
118  int operator>(const MultiKeyObject& rhs) const
119  {
120  ABORT();
121  return 0;
122  }
123 
124 private:
125  const Object* _object;
126  const char* _str;
127 };
128 
130 
132 
134 
135 UTL_NS_END;
136 
138 
139 #include <libutl/algorithms.h>
140 #include <libutl/Vector.h>
141 
143 
144 UTL_NS_BEGIN;
145 
147 
159 template <class T, class P, class C>
160 void
161 multiKeyInsertionSort(P* array, C cmp, size_t begin, size_t end, size_t depth = 0)
162 {
163  array += begin;
164  P* pi;
165  P* pj;
166  const T* s;
167  const T* t;
168  P tmp;
169  const T defT = T();
170 
171  size_t n = end - begin;
172  if (n <= 1) return;
173 
174  for (pi = array + 1; --n > 0; pi++)
175  {
176  for (pj = pi; pj > array; pj--)
177  {
178  for (s = *(pj - 1) + depth, t = *pj + depth; (cmp(*s, *t) == 0) && (cmp(*s, defT) != 0);
179  s++, t++)
180  ;
181  if (cmp(*s, *t) <= 0) break;
182  tmp = *pj;
183  *pj = *(pj - 1);
184  *(pj - 1) = tmp;
185  }
186  }
187 }
188 
190 
201 template <class T, class P, class C>
202 size_t
203 multiKeyMedianOfThree(P* array, C cmp, size_t l, size_t m, size_t h, size_t depth = 0)
204 {
205  T vl, vm, vh;
206  if (cmp(vl = array[l][depth], vm = array[m][depth]) == 0)
207  {
208  return l;
209  }
210  if ((cmp(vh = array[h][depth], vl) == 0) || (cmp(vh, vm) == 0))
211  {
212  return h;
213  }
214  if (cmp(vl, vm) < 0)
215  {
216  return (cmp(vm, vh) < 0) ? m : ((cmp(vl, vh) < 0) ? h : l);
217  }
218  else
219  {
220  return (cmp(vm, vh) > 0) ? m : ((cmp(vl, vh) < 0) ? l : h);
221  }
222 }
223 
225 
237 template <class T, class P, class C>
238 void
239 multiKeyQuickSort(P* array, C cmp, size_t begin, size_t end, size_t depth = 0)
240 {
241  int r;
242  size_t i, l, m, h, a, b, c, d, n;
243  size_t stack[96];
244  size_t* sp = stack;
245  size_t bed[4][4];
246 
247  for (;;)
248  {
249  n = end - begin;
250  while (n <= 10)
251  {
252  // insertion-sort the block
253  if (n > 1)
254  {
255  multiKeyInsertionSort<T>(array, cmp, begin, end, depth);
256  }
257 
258  // pop a segment off the stack -- we're done if the stack is empty
259  if (sp == stack)
260  {
261  return;
262  }
263  depth = *(--sp);
264  end = *(--sp);
265  begin = *(--sp);
266  n = end - begin;
267  }
268 
269  // median-of-three (or pseudo-median of 9) partitioning
270  l = begin;
271  m = (begin + end) / 2;
272  h = end - 1;
273  if (n > 30)
274  {
275  size_t n8 = n / 8;
276  l = multiKeyMedianOfThree<T>(array, cmp, l, l + n8, l + 2 * n8, depth);
277  m = multiKeyMedianOfThree<T>(array, cmp, m - n8, m, m + n8, depth);
278  h = multiKeyMedianOfThree<T>(array, cmp, h - 2 * n8, h - n8, h, depth);
279  }
280  m = multiKeyMedianOfThree<T>(array, cmp, l, m, h, depth);
281  utl::swap(array, begin, m);
282  T v = array[begin][depth];
283 
284  a = b = begin + 1;
285  c = d = end - 1;
286 
287  for (;;)
288  {
289  while (b <= c)
290  {
291  r = cmp(array[b][depth], v);
292  if (r > 0)
293  {
294  break;
295  }
296  if (r == 0)
297  {
298  utl::swap(array, a, b);
299  a++;
300  }
301  b++;
302  }
303  // [begin,a) = v
304  // [a, b) < v
305  // [begin,b) <= v
306  // (b > c) || ([b] > v)
307 
308  while (b <= c)
309  {
310  r = cmp(array[c][depth], v);
311  if (r < 0)
312  {
313  break;
314  }
315  if (r == 0)
316  {
317  utl::swap(array, c, d);
318  d--;
319  }
320  c--;
321  }
322  // [c + 1,d + 1) > v
323  // [d + 1,end) = v
324  // [c + 1,end) >= v
325  // (b > c) || ([c] < v)
326 
327  if (b > c)
328  {
329  break;
330  }
331  // ([b] > v) && ([c] < v)
332  utl::swap(array, b, c);
333  // ([b] < v) && ([c] > v)
334  b++;
335  c--;
336  }
337 
338  r = min(a - begin, b - a);
339  utl::swap(array, begin, b - r, r);
340  r = min(d - c, end - d - 1);
341  utl::swap(array, b, end - r, r);
342 
343  // identify segments to be sorted
344  r = b - a;
345  bed[0][0] = begin;
346  bed[0][1] = begin + r;
347  bed[0][2] = depth;
348  bed[0][3] = r;
349  bed[1][0] = begin + r;
350  bed[1][1] = end - (d - c);
351  bed[1][2] = depth + 1;
352  if (cmp(array[begin + r][depth], T()) == 0)
353  {
354  bed[1][1] = bed[1][0];
355  bed[1][3] = 0;
356  }
357  else
358  {
359  bed[1][3] = bed[1][1] - bed[1][0];
360  }
361  r = d - c;
362  bed[2][0] = end - r;
363  bed[2][1] = end;
364  bed[2][2] = depth;
365  bed[2][3] = r;
366 
367  // bubble sort in order of increasing size
368  if (bed[2][3] < bed[1][3])
369  {
370  memmove(bed[3], bed[1], 4 * sizeof(size_t));
371  memmove(bed[1], bed[2], 4 * sizeof(size_t));
372  memmove(bed[2], bed[3], 4 * sizeof(size_t));
373  }
374  if (bed[1][3] < bed[0][3])
375  {
376  memmove(bed[3], bed[0], 4 * sizeof(size_t));
377  memmove(bed[0], bed[1], 4 * sizeof(size_t));
378  memmove(bed[1], bed[3], 4 * sizeof(size_t));
379  }
380  if (bed[2][3] < bed[1][3])
381  {
382  memmove(bed[3], bed[1], 4 * sizeof(size_t));
383  memmove(bed[1], bed[2], 4 * sizeof(size_t));
384  memmove(bed[2], bed[3], 4 * sizeof(size_t));
385  }
386 
387  // push larger segments onto the stack
388  for (i = 2; i >= 1; i--)
389  {
390  if (bed[i][3] > 1)
391  {
392  ASSERTD(sp != (stack + 96));
393  *sp++ = bed[i][0];
394  *sp++ = bed[i][1];
395  *sp++ = bed[i][2];
396  }
397  }
398 
399  // prepare to sort the smallest segment
400  begin = bed[0][0];
401  end = bed[0][1];
402  depth = bed[0][2];
403  }
404 }
405 
407 
419 template <class T, class C>
420 size_t
422  const T* array, size_t begin, size_t end, const T& key, C cmpFn, uint_t findType = find_first)
423 {
424  size_t low, high, mid, res;
425  int cmpRes;
426 
427  low = begin;
428  high = end;
429 
430  // nothing to do -- return immediately
431  if ((high-- - low) == 0) return low;
432 
433  // while low and high make sense
434  while ((low <= high) && (high != size_t_max))
435  {
436  // mid is half-way between low and high
437  res = mid = (low + high) / 2;
438 
439  // see how the key compares against the object at mid
440  cmpRes = cmpFn(key, array[mid]);
441  // if key < array[mid], search the lower half
442  if (cmpRes < 0)
443  {
444  high = mid - 1;
445  }
446  // else if key > begin[mid], search the upper half
447  else if (cmpRes > 0)
448  {
449  // new low is mid + 1
450  low = mid + 1;
451  }
452  else
453  {
454  break;
455  }
456  }
457 
458  // we're done if this is an insertion point search
459  if (findType == find_ip) return (cmpRes != 0) ? low : res;
460 
461  // didn't find a match?
462  if (cmpRes != 0) return size_t_max;
463 
464  // there could be multiple matches for the same key
465  if (findType == find_first)
466  {
467  if ((res > low) && (cmpFn(key, array[res - 1]) == 0))
468  {
469  res = binarySearch(array, low, res, key, cmpFn, findType);
470  }
471  }
472  else if (findType == find_last)
473  {
474  if ((res < high) && (cmpFn(key, array[res + 1]) == 0))
475  {
476  res = binarySearch(array, res + 1, high + 1, key, cmpFn, findType);
477  }
478  }
479 
480  return res;
481 }
482 
484 
485 UTL_NS_END;
find last matching object
Definition: util.h:45
Reverse subtraction function.
Abstraction for binary functions.
Allows multi-key sort algorithms to be used with objects.
Subtraction function.
const size_t size_t_max
Maximum size_t value.
void swap(T *array, size_t lhsIdx, size_t rhsIdx)
Swap two elements of the given array.
Definition: util_inl.h:930
const char & operator[](size_t idx) const
Array element access operator.
find insertion point
Definition: util.h:46
void multiKeyQuickSort(P *array, C cmp, size_t begin, size_t end, size_t depth=0)
Multi-key quick-sort (part of) the given sequence.
T operator()(const T &lhs, const T &rhs) const
Return the result of (rhs - lhs).
unsigned int uint_t
Unsigned integer.
Definition: types.h:59
#define ABORT()
Immediately terminates the program.
Definition: macros.h:59
const char * operator+(size_t num) const
Addition operator.
const T & min(const T &a, const T &b, const R &... args)
Return the smallest value among two or more provided values of the same type.
Definition: util_inl.h:61
find first matching object
Definition: util.h:44
void multiKeyInsertionSort(P *array, C cmp, size_t begin, size_t end, size_t depth=0)
Multi-key insertion-sort (part of) the given sequence.
#define UTL_TYPE_NO_SERIALIZE(typeName)
Declare that a type cannot be serialized.
Definition: macros.h:638
size_t binarySearch(const T *array, size_t begin, size_t end, const T &key, C cmpFn, uint_t findType=find_first)
Binary search an ordered sequence for a key.
Root of UTL++ class hierarchy.
Definition: Object.h:52
const Object * getObject() const
Return the object.
size_t multiKeyMedianOfThree(P *array, C cmp, size_t l, size_t m, size_t h, size_t depth=0)
Perform median-of-three partitioning.
#define ASSERTD
Do an assertion in DEBUG mode only.
T operator()(const T &lhs, const T &rhs) const
Return the result of (lhs - rhs).