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  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2011-05-25 16:56:41 +0200 (Wed, 25 May 2011) $ by $Author: schulte $
13  * $Revision: 12022 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int {
41 
43  template<class TaskView, bool inc>
44  class StoEst {
45  public:
47  bool operator ()(const TaskView& t1, const TaskView& t2) const;
48  };
49 
51  template<class TaskView, bool inc>
52  class StoEct {
53  public:
55  bool operator ()(const TaskView& t1, const TaskView& t2) const;
56  };
57 
59  template<class TaskView, bool inc>
60  class StoLst {
61  public:
63  bool operator ()(const TaskView& t1, const TaskView& t2) const;
64  };
65 
67  template<class TaskView, bool inc>
68  class StoLct {
69  public:
71  bool operator ()(const TaskView& t1, const TaskView& t2) const;
72  };
73 
75  template<class TaskView, template<class,bool> class STO, bool inc>
76  class SortMap {
77  private:
79  const TaskViewArray<TaskView>& tasks;
81  STO<TaskView,inc> sto;
82  public:
86  bool operator ()(int& i, int& j) const;
87  };
88 
89  template<class TaskView, bool inc>
90  forceinline bool
92  (const TaskView& t1, const TaskView& t2) const {
93  return inc ?
94  (t1.est() < t2.est() || (t1.est()==t2.est() && t1.lct() < t2.lct()))
95  : (t2.est() < t1.est() || (t2.est()==t1.est() && t2.lct() < t1.lct()));
96  }
97 
98  template<class TaskView, bool inc>
99  forceinline bool
101  (const TaskView& t1, const TaskView& t2) const {
102  return inc ?
103  (t1.ect() < t2.ect() || (t1.ect()==t2.ect() && t1.lst() < t2.lst()))
104  : (t2.ect() < t1.ect() || (t2.ect()==t1.ect() && t2.lst() < t1.lst()));
105  }
106 
107  template<class TaskView, bool inc>
108  forceinline bool
110  (const TaskView& t1, const TaskView& t2) const {
111  return inc ?
112  (t1.lst() < t2.lst() || (t1.lst()==t2.lst() && t1.ect() < t2.ect()))
113  : (t2.lst() < t1.lst() || (t2.lst()==t1.lst() && t2.ect() < t1.ect()));
114  }
115 
116  template<class TaskView, bool inc>
117  forceinline bool
119  (const TaskView& t1, const TaskView& t2) const {
120  return inc ?
121  (t1.lct() < t2.lct() || (t1.lct()==t2.lct() && t1.est() < t2.est()))
122  : (t2.lct() < t1.lct() || (t2.lct()==t1.lct() && t2.est() < t1.est()));
123  }
124 
125  template<class TaskView, template<class,bool> class STO, bool inc>
128  : tasks(t) {}
129  template<class TaskView, template<class,bool> class STO, bool inc>
130  forceinline bool
132  return sto(tasks[i],tasks[j]);
133  }
134 
135  template<class TaskView, SortTaskOrder sto, bool inc>
136  forceinline void
138  switch (sto) {
139  case STO_EST:
140  {
141  StoEst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
142  }
143  break;
144  case STO_ECT:
145  {
146  StoEct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
147  }
148  break;
149  case STO_LST:
150  {
151  StoLst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
152  }
153  break;
154  case STO_LCT:
155  {
156  StoLct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
157  }
158  break;
159  default:
160  GECODE_NEVER;
161  }
162  }
163 
164  template<class TaskView, SortTaskOrder sto, bool inc>
165  forceinline void
166  sort(int* map, const TaskViewArray<TaskView>& t) {
167  for (int i=t.size(); i--; )
168  map[i]=i;
169  switch (sto) {
170  case STO_EST:
171  {
173  Support::quicksort(map, t.size(), o);
174  }
175  break;
176  case STO_ECT:
177  {
179  Support::quicksort(map, t.size(), o);
180  }
181  break;
182  case STO_LST:
183  {
185  Support::quicksort(map, t.size(), o);
186  }
187  break;
188  case STO_LCT:
189  {
191  Support::quicksort(map, t.size(), o);
192  }
193  break;
194  default:
195  GECODE_NEVER;
196  }
197  }
198 
199  template<class TaskView, SortTaskOrder sto, bool inc>
200  forceinline void
201  sort(int* map, int n, const TaskViewArray<TaskView>& t) {
202  switch (sto) {
203  case STO_EST:
204  {
206  Support::quicksort(map, n, o);
207  }
208  break;
209  case STO_ECT:
210  {
212  Support::quicksort(map, n, o);
213  }
214  break;
215  case STO_LST:
216  {
218  Support::quicksort(map, n, o);
219  }
220  break;
221  case STO_LCT:
222  {
224  Support::quicksort(map, n, o);
225  }
226  break;
227  default:
228  GECODE_NEVER;
229  }
230  }
231 
232 }}
233 
234 // STATISTICS: int-other
Sort by earliest completion times.
Definition: task.hh:284
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:233
SortMap(const TaskViewArray< TaskView > &t)
Initialize.
Definition: sort.hpp:127
bool operator()(int &i, int &j) const
Sort order.
Definition: sort.hpp:131
Sort by earliest start times.
Definition: task.hh:283
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
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
Sorting maps rather than tasks.
Definition: sort.hpp:76
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:139
Sort by latest completion times.
Definition: sort.hpp:68
Sort by latest start times.
Definition: sort.hpp:60
Sort by latest completion times.
Definition: task.hh:286
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition: sort.hpp:101
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition: sort.hpp:92
Sort by earliest completion times.
Definition: sort.hpp:52
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition: sort.hpp:110
Sort by earliest start times.
Definition: sort.hpp:44
#define forceinline
Definition: config.hpp:132
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition: sort.hpp:119
Gecode toplevel namespace
Sort by latest start times.
Definition: task.hh:285
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60