this repo has no description
dekker.one
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
38 /// Sort by earliest start times
39 template<class TaskView, bool inc>
40 class StoEst {
41 public:
42 /// Sort order
43 bool operator ()(const TaskView& t1, const TaskView& t2) const;
44 };
45
46 /// Sort by earliest completion times
47 template<class TaskView, bool inc>
48 class StoEct {
49 public:
50 /// Sort order
51 bool operator ()(const TaskView& t1, const TaskView& t2) const;
52 };
53
54 /// Sort by latest start times
55 template<class TaskView, bool inc>
56 class StoLst {
57 public:
58 /// Sort order
59 bool operator ()(const TaskView& t1, const TaskView& t2) const;
60 };
61
62 /// Sort by latest completion times
63 template<class TaskView, bool inc>
64 class StoLct {
65 public:
66 /// Sort order
67 bool operator ()(const TaskView& t1, const TaskView& t2) const;
68 };
69
70 /// Sorting maps rather than tasks
71 template<class TaskView, template<class,bool> class STO, bool inc>
72 class SortMap {
73 private:
74 /// The tasks
75 const TaskViewArray<TaskView>& tasks;
76 /// The sorting order for tasks
77 STO<TaskView,inc> sto;
78 public:
79 /// Initialize
80 SortMap(const TaskViewArray<TaskView>& t);
81 /// Sort order
82 bool operator ()(int& i, int& j) const;
83 };
84
85 template<class TaskView, bool inc>
86 forceinline bool
87 StoEst<TaskView,inc>::operator ()
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
96 StoEct<TaskView,inc>::operator ()
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
105 StoLst<TaskView,inc>::operator ()
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
114 StoLct<TaskView,inc>::operator ()
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>
122 forceinline
123 SortMap<TaskView,STO,inc>::SortMap(const TaskViewArray<TaskView>& t)
124 : tasks(t) {}
125 template<class TaskView, template<class,bool> class STO, bool inc>
126 forceinline bool
127 SortMap<TaskView,STO,inc>::operator ()(int& i, int& j) const {
128 return sto(tasks[i],tasks[j]);
129 }
130
131 template<class TaskView, SortTaskOrder sto, bool inc>
132 forceinline void
133 sort(TaskViewArray<TaskView>& t) {
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 {
168 SortMap<TaskView,StoEst,inc> o(t);
169 Support::quicksort(map, t.size(), o);
170 }
171 break;
172 case STO_ECT:
173 {
174 SortMap<TaskView,StoEct,inc> o(t);
175 Support::quicksort(map, t.size(), o);
176 }
177 break;
178 case STO_LST:
179 {
180 SortMap<TaskView,StoLst,inc> o(t);
181 Support::quicksort(map, t.size(), o);
182 }
183 break;
184 case STO_LCT:
185 {
186 SortMap<TaskView,StoLct,inc> o(t);
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 {
201 SortMap<TaskView,StoEst,inc> o(t);
202 Support::quicksort(map, n, o);
203 }
204 break;
205 case STO_ECT:
206 {
207 SortMap<TaskView,StoEct,inc> o(t);
208 Support::quicksort(map, n, o);
209 }
210 break;
211 case STO_LST:
212 {
213 SortMap<TaskView,StoLst,inc> o(t);
214 Support::quicksort(map, n, o);
215 }
216 break;
217 case STO_LCT:
218 {
219 SortMap<TaskView,StoLct,inc> o(t);
220 Support::quicksort(map, n, o);
221 }
222 break;
223 default:
224 GECODE_NEVER;
225 }
226 }
227
228}}
229
230// STATISTICS: int-other