Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
36namespace 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>
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:
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:
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:
225 }
226 }
227
228}}
229
230// STATISTICS: int-other
NodeType t
Type of node.
int n
Number of negative literals for node type.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Sorting maps rather than tasks.
Definition sort.hpp:72
bool operator()(int &i, int &j) const
Sort order.
Definition sort.hpp:127
SortMap(const TaskViewArray< TaskView > &t)
Initialize.
Definition sort.hpp:123
Sort by earliest completion times.
Definition sort.hpp:48
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:97
Sort by earliest start times.
Definition sort.hpp:40
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:88
Sort by latest completion times.
Definition sort.hpp:64
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:115
Sort by latest start times.
Definition sort.hpp:56
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:106
Task view array.
Definition task.hh:233
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition sort.hpp:133
@ STO_ECT
Sort by earliest completion times.
Definition task.hh:284
@ STO_EST
Sort by earliest start times.
Definition task.hh:283
@ STO_LST
Sort by latest start times.
Definition task.hh:285
@ STO_LCT
Sort by latest completion times.
Definition task.hh:286
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56