41 namespace Gecode {
namespace Support {
44 template<
class Type,
class Less>
47 if (less(b,a)) std::swap(a,b);
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>
137 std::swap(*(l+((r-l) >> 1)),*(r-1));
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) {
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.
bool empty(void) const
Test whether stack is empty.
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.
bool operator()(const Type &lhs, const Type &rhs)
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.
Node * x
Pointer to corresponding Boolean expression node.
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
QuickSortStack(void)
Initialize stack as empty.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
void push(Type *l, Type *r)
Push two positions l and r.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.