37 namespace Gecode {
namespace Support {
40 template<
class Type,
class Less>
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>
139 if (r-i > QuickSortCutoff) {
140 s.
push(l,i-1); l=i+1;
continue;
142 if (i-l > QuickSortCutoff) {
146 if (i-l > QuickSortCutoff) {
147 s.
push(i+1,r); r=i-1;
continue;
149 if (r-i > QuickSortCutoff) {
163 bool operator ()(
const Type& lhs,
const Type& rhs) {
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]));
234 if (n > QuickSortCutoff)
256 assert(!
l(x[0],x[0]));
257 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.