40 template<
class Type,
class Less>
43 if (less(b,a)) std::swap(a,b);
54 static const int maxsize =
sizeof(int) * CHAR_BIT;
58 Type* stack[2*maxsize+1];
63 bool empty(
void)
const;
65 void push(Type* l, Type*
r);
67 void pop(Type*& l, Type*&
r);
79 return *(tos-1) == NULL;
85 *(tos++) = l; *(tos++) =
r;
91 r = *(--tos); l = *(--tos);
95 template<
class Type,
class Less>
98 for (Type* i =
r; i > l; i--)
100 for (Type* i = l+2; i <=
r; i++) {
103 while (less(v,*(j-1))) {
111 template<
class Type,
class Less>
118 while (less(*(++i),v)) {}
119 while (less(v,*(--j)))
if (j == l)
break;
128 template<
class Type,
class Less>
133 std::swap(*(l+((
r-l) >> 1)),*(
r-1));
140 s.
push(l,i-1); l=i+1;
continue;
147 s.
push(i+1,
r);
r=i-1;
continue;
183 template<
class Type,
class Less>
188 assert(!l(
x[0],
x[0]));
209 assert(!l(
x[0],
x[0]));
228 template<
class Type,
class Less>
233 assert(!l(
x[0],
x[0]));
256 assert(!l(
x[0],
x[0]));
Comparison class for sorting using <.
bool operator()(const Type &lhs, const Type &rhs)
Static stack for quicksort.
QuickSortStack(void)
Initialize stack as empty.
void pop(Type *&l, Type *&r)
Pop two positions l and r.
bool empty(void) const
Test whether stack is empty.
void push(Type *l, Type *r)
Push two positions l and r.
Support algorithms and datastructures
void exchange(Type &a, Type &b, Less &less)
Exchange elements according to order.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
int const QuickSortCutoff
Perform quicksort only for more elements.
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Post propagator for SetVar x