Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
sort.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * Last modified:
10  * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
11  * $Revision: 9692 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 #include <climits>
40 
41 namespace Gecode { namespace Support {
42 
44  template<class Type, class Less>
45  forceinline void
46  exchange(Type &a, Type &b, Less &less) {
47  if (less(b,a)) std::swap(a,b);
48  }
49 
51  int const QuickSortCutoff = 20;
52 
54  template<class Type>
56  private:
58  static const int maxsize = sizeof(int) * CHAR_BIT;
60  Type** tos;
62  Type* stack[2*maxsize+1];
63  public:
65  QuickSortStack(void);
67  bool empty(void) const;
69  void push(Type* l, Type* r);
71  void pop(Type*& l, Type*& r);
72  };
73 
74  template<class Type>
76  QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) {
77  *(tos++) = NULL;
78  }
79 
80  template<class Type>
81  forceinline bool
83  return *(tos-1) == NULL;
84  }
85 
86  template<class Type>
87  forceinline void
88  QuickSortStack<Type>::push(Type* l, Type* r) {
89  *(tos++) = l; *(tos++) = r;
90  }
91 
92  template<class Type>
93  forceinline void
94  QuickSortStack<Type>::pop(Type*& l, Type*& r) {
95  r = *(--tos); l = *(--tos);
96  }
97 
99  template<class Type, class Less>
100  forceinline void
101  insertion(Type* l, Type* r, Less &less) {
102  for (Type* i = r; i > l; i--)
103  exchange(*(i-1),*i,less);
104  for (Type* i = l+2; i <= r; i++) {
105  Type* j = i;
106  Type v = *i;
107  while (less(v,*(j-1))) {
108  *j = *(j-1); j--;
109  }
110  *j = v;
111  }
112  }
113 
115  template<class Type, class Less>
116  forceinline Type*
117  partition(Type* l, Type* r, Less &less) {
118  Type* i = l-1;
119  Type* j = r;
120  Type v = *r;
121  while (true) {
122  while (less(*(++i),v)) {}
123  while (less(v,*(--j))) if (j == l) break;
124  if (i >= j) break;
125  std::swap(*i,*j);
126  }
127  std::swap(*i,*r);
128  return i;
129  }
130 
132  template<class Type, class Less>
133  inline void
134  quicksort(Type* l, Type* r, Less &less) {
136  while (true) {
137  std::swap(*(l+((r-l) >> 1)),*(r-1));
138  exchange(*l,*(r-1),less);
139  exchange(*l,*r,less);
140  exchange(*(r-1),*r,less);
141  Type* i = partition(l+1,r-1,less);
142  if (i-l > r-i) {
143  if (r-i > QuickSortCutoff) {
144  s.push(l,i-1); l=i+1; continue;
145  }
146  if (i-l > QuickSortCutoff) {
147  r=i-1; continue;
148  }
149  } else {
150  if (i-l > QuickSortCutoff) {
151  s.push(i+1,r); r=i-1; continue;
152  }
153  if (r-i > QuickSortCutoff) {
154  l=i+1; continue;
155  }
156  }
157  if (s.empty())
158  break;
159  s.pop(l,r);
160  }
161  }
162 
164  template<class Type>
165  class Less {
166  public:
167  bool operator ()(const Type& lhs, const Type& rhs) {
168  return lhs < rhs;
169  }
170  };
171 
187  template<class Type, class Less>
188  forceinline void
189  insertion(Type* x, int n, Less &l) {
190  if (n < 2)
191  return;
192  assert(!l(x[0],x[0]));
193  insertion(x,x+n-1,l);
194  }
195 
207  template<class Type>
208  forceinline void
209  insertion(Type* x, int n) {
210  if (n < 2)
211  return;
212  Less<Type> l;
213  assert(!l(x[0],x[0]));
214  insertion(x,x+n-1,l);
215  }
216 
232  template<class Type, class Less>
233  forceinline void
234  quicksort(Type* x, int n, Less &l) {
235  if (n < 2)
236  return;
237  assert(!l(x[0],x[0]));
238  if (n > QuickSortCutoff)
239  quicksort(x,x+n-1,l);
240  insertion(x,x+n-1,l);
241  }
242 
254  template<class Type>
255  forceinline void
256  quicksort(Type* x, int n) {
257  if (n < 2)
258  return;
259  Less<Type> l;
260  assert(!l(x[0],x[0]));
261  if (n > QuickSortCutoff)
262  quicksort(x,x+n-1,l);
263  insertion(x,x+n-1,l);
264  }
265 
266 }}
267 
268 // STATISTICS: support-any
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void pop(Type *&l, Type *&r)
Pop two positions l and r.
Definition: sort.hpp:94
bool empty(void) const
Test whether stack is empty.
Definition: sort.hpp:82
Comparison class for sorting using <.
Definition: sort.hpp:165
void exchange(Type &a, Type &b, Less &less)
Exchange elements according to order.
Definition: sort.hpp:46
Type * partition(Type *l, Type *r, Less &less)
Standard partioning.
Definition: sort.hpp:117
bool operator()(const Type &lhs, const Type &rhs)
Definition: sort.hpp:167
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Static stack for quicksort.
Definition: sort.hpp:55
int const QuickSortCutoff
Perform quicksort only for more elements.
Definition: sort.hpp:51
const int v[7]
Definition: distinct.cpp:207
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
#define forceinline
Definition: config.hpp:132
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition: sort.hpp:101
QuickSortStack(void)
Initialize stack as empty.
Definition: sort.hpp:76
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.
Definition: sort.hpp:88
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.