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