41 namespace Gecode {
namespace Support {
44 template<
class Type,
class Less>
58 static const int maxsize =
sizeof(int) * CHAR_BIT;
62 Type* stack[2*maxsize+1];
67 bool empty(
void)
const;
69 void push(Type*
l, Type*
r);
71 void pop(Type*& l, Type*& r);
83 return *(tos-1) == NULL;
89 *(tos++) = l; *(tos++) = r;
95 r = *(--tos); l = *(--tos);
99 template<
class Type,
class Less>
102 for (Type*
i = r;
i >
l;
i--)
104 for (Type*
i = l+2;
i <=
r;
i++) {
107 while (less(v,*(j-1))) {
115 template<
class Type,
class Less>
122 while (less(*(++i),v)) {}
123 while (less(v,*(--j)))
if (j == l)
break;
132 template<
class Type,
class Less>
143 if (r-i > QuickSortCutoff) {
144 s.
push(l,i-1); l=i+1;
continue;
146 if (i-l > QuickSortCutoff) {
150 if (i-l > QuickSortCutoff) {
151 s.
push(i+1,r); r=i-1;
continue;
153 if (r-i > QuickSortCutoff) {
167 bool operator ()(
const Type& lhs,
const Type& rhs) {
187 template<
class Type,
class Less>
192 assert(!
l(x[0],x[0]));
213 assert(!
l(x[0],x[0]));
232 template<
class Type,
class Less>
237 assert(!
l(x[0],x[0]));
238 if (n > QuickSortCutoff)
260 assert(!
l(x[0],x[0]));
261 if (n > QuickSortCutoff)
void pop(Type *&l, Type *&r)
Pop two positions l and r.
Comparison class for sorting using <.
void exchange(Type &a, Type &b, Less &less)
Exchange elements according to order.
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
int n
Number of negative literals for node type.
Static stack for quicksort.
int const QuickSortCutoff
Perform quicksort only for more elements.
bool empty(void) const
Test whether stack is empty.
Post propagator for SetVar SetOpType SetVar SetRelType r
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Post propagator for SetVar x
QuickSortStack(void)
Initialize stack as empty.
Gecode toplevel namespace
void push(Type *l, Type *r)
Push two positions l and r.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.