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.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
int n
Number of negative literals for node type.
Gecode::IntArgs i({1, 2, 3, 4})
Static stack for quicksort.
int const QuickSortCutoff
Perform quicksort only for more elements.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
bool empty(void) const
Test whether stack is empty.
Post propagator for SetVar SetOpType SetVar SetRelType r
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.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.