Inexor
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
cube_sort.hpp
Go to the documentation of this file.
1 
6 #pragma once
7 
8 #include <string.h>
9 #include <algorithm>
10 
11 struct sortless
12 {
13  template<class T> bool operator()(const T &x, const T &y) const { return x < y; }
14  bool operator()(char *x, char *y) const { return strcmp(x, y) < 0; }
15  bool operator()(const char *x, const char *y) const { return strcmp(x, y) < 0; }
16 };
17 
19 {
20  template<class T> bool operator()(const T &x, const T &y) const { return sortless()(x.name, y.name); }
21  template<class T> bool operator()(T *x, T *y) const { return sortless()(x->name, y->name); }
22  template<class T> bool operator()(const T *x, const T *y) const { return sortless()(x->name, y->name); }
23 };
24 
25 template<class T, class F>
26 static inline void insertionsort(T *start, T *end, F fun)
27 {
28  for(T *i = start+1; i < end; i++)
29  {
30  if(fun(*i, i[-1]))
31  {
32  T tmp = *i;
33  *i = i[-1];
34  T *j = i-1;
35  for(; j > start && fun(tmp, j[-1]); --j)
36  *j = j[-1];
37  *j = tmp;
38  }
39  }
40 
41 }
42 template<class T, class F>
43 static inline void insertionsort(T *buf, int n, F fun)
44 {
45  insertionsort(buf, buf+n, fun);
46 }
47 template<class T>
48 static inline void insertionsort(T *buf, int n)
49 {
50  insertionsort(buf, buf+n, sortless());
51 }
52 
53 template<class T, class F>
54 static inline void quicksort(T *start, T *end, F fun)
55 {
56  while(end-start > 10)
57  {
58  T *mid = &start[(end-start)/2], *i = start+1, *j = end-2, pivot;
59  if(fun(*start, *mid)) /* start < mid */
60  {
61  if(fun(end[-1], *start)) { pivot = *start; *start = end[-1]; end[-1] = *mid; } /* end < start < mid */
62  else if(fun(end[-1], *mid)) { pivot = end[-1]; end[-1] = *mid; } /* start <= end < mid */
63  else { pivot = *mid; } /* start < mid <= end */
64  }
65  else if(fun(*start, end[-1])) { pivot = *start; *start = *mid; } /*mid <= start < end */
66  else if(fun(*mid, end[-1])) { pivot = end[-1]; end[-1] = *start; *start = *mid; } /* mid < end <= start */
67  else { pivot = *mid; std::swap(*start, end[-1]); } /* end <= mid <= start */
68  *mid = end[-2];
69  do
70  {
71  while(fun(*i, pivot)) if(++i >= j) goto partitioned;
72  while(fun(pivot, *--j)) if(i >= j) goto partitioned;
73  std::swap(*i, *j);
74  } while(++i < j);
75  partitioned:
76  end[-2] = *i;
77  *i = pivot;
78 
79  if(i-start < end-(i+1))
80  {
81  quicksort(start, i, fun);
82  start = i+1;
83  }
84  else
85  {
86  quicksort(i+1, end, fun);
87  end = i;
88  }
89  }
90  insertionsort(start, end, fun);
91 }
92 
93 template<class T, class F>
94 static inline void quicksort(T *buf, int n, F fun)
95 {
96  quicksort(buf, buf+n, fun);
97 }
98 
99 template<class T>
100 static inline void quicksort(T *buf, int n)
101 {
102  quicksort(buf, buf+n, sortless());
103 }
104 
bool operator()(const T &x, const T &y) const
Definition: cube_sort.hpp:20
bool operator()(const T *x, const T *y) const
Definition: cube_sort.hpp:22
bool operator()(T *x, T *y) const
Definition: cube_sort.hpp:21
static void quicksort(T *start, T *end, F fun)
Definition: cube_sort.hpp:54
bool operator()(const char *x, const char *y) const
Definition: cube_sort.hpp:15
bool operator()(const T &x, const T &y) const
Definition: cube_sort.hpp:13
void start(const char *filename, int videofps, int videow, int videoh, bool sound)
Definition: movie.cpp:975
Legacy Sorting algorithms.
Definition: cube_sort.hpp:11
static void insertionsort(T *start, T *end, F fun)
Definition: cube_sort.hpp:26
int end()
Definition: glemu.cpp:256
Definition: cube_sort.hpp:18
bool operator()(char *x, char *y) const
Definition: cube_sort.hpp:14