sort.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2009 00009 * Guido Tack, 2010 00010 * 00011 * Last modified: 00012 * $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $ 00013 * $Revision: 11551 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { namespace Scheduling { 00041 00043 template<class TaskView, bool inc> 00044 class StoEst { 00045 public: 00047 bool operator ()(const TaskView& t1, const TaskView& t2) const; 00048 }; 00049 00051 template<class TaskView, bool inc> 00052 class StoEct { 00053 public: 00055 bool operator ()(const TaskView& t1, const TaskView& t2) const; 00056 }; 00057 00059 template<class TaskView, bool inc> 00060 class StoLst { 00061 public: 00063 bool operator ()(const TaskView& t1, const TaskView& t2) const; 00064 }; 00065 00067 template<class TaskView, bool inc> 00068 class StoLct { 00069 public: 00071 bool operator ()(const TaskView& t1, const TaskView& t2) const; 00072 }; 00073 00075 template<class TaskView, template<class,bool> class STO, bool inc> 00076 class SortMap { 00077 private: 00079 const TaskViewArray<TaskView>& tasks; 00081 STO<TaskView,inc> sto; 00082 public: 00084 SortMap(const TaskViewArray<TaskView>& t); 00086 bool operator ()(int& i, int& j) const; 00087 }; 00088 00089 template<class TaskView, bool inc> 00090 forceinline bool 00091 StoEst<TaskView,inc>::operator () 00092 (const TaskView& t1, const TaskView& t2) const { 00093 return inc ? 00094 (t1.est() < t2.est() || (t1.est()==t2.est() && t1.lct() < t2.lct())) 00095 : (t2.est() < t1.est() || (t2.est()==t1.est() && t2.lct() < t1.lct())); 00096 } 00097 00098 template<class TaskView, bool inc> 00099 forceinline bool 00100 StoEct<TaskView,inc>::operator () 00101 (const TaskView& t1, const TaskView& t2) const { 00102 return inc ? 00103 (t1.ect() < t2.ect() || (t1.ect()==t2.ect() && t1.lst() < t2.lst())) 00104 : (t2.ect() < t1.ect() || (t2.ect()==t1.ect() && t2.lst() < t1.lst())); 00105 } 00106 00107 template<class TaskView, bool inc> 00108 forceinline bool 00109 StoLst<TaskView,inc>::operator () 00110 (const TaskView& t1, const TaskView& t2) const { 00111 return inc ? 00112 (t1.lst() < t2.lst() || (t1.lst()==t2.lst() && t1.ect() < t2.ect())) 00113 : (t2.lst() < t1.lst() || (t2.lst()==t1.lst() && t2.ect() < t1.ect())); 00114 } 00115 00116 template<class TaskView, bool inc> 00117 forceinline bool 00118 StoLct<TaskView,inc>::operator () 00119 (const TaskView& t1, const TaskView& t2) const { 00120 return inc ? 00121 (t1.lct() < t2.lct() || (t1.lct()==t2.lct() && t1.est() < t2.est())) 00122 : (t2.lct() < t1.lct() || (t2.lct()==t1.lct() && t2.est() < t1.est())); 00123 } 00124 00125 template<class TaskView, template<class,bool> class STO, bool inc> 00126 forceinline 00127 SortMap<TaskView,STO,inc>::SortMap(const TaskViewArray<TaskView>& t) 00128 : tasks(t) {} 00129 template<class TaskView, template<class,bool> class STO, bool inc> 00130 forceinline bool 00131 SortMap<TaskView,STO,inc>::operator ()(int& i, int& j) const { 00132 return sto(tasks[i],tasks[j]); 00133 } 00134 00135 template<class TaskView, SortTaskOrder sto, bool inc> 00136 forceinline void 00137 sort(TaskViewArray<TaskView>& t) { 00138 switch (sto) { 00139 case STO_EST: 00140 { 00141 StoEst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o); 00142 } 00143 break; 00144 case STO_ECT: 00145 { 00146 StoEct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o); 00147 } 00148 break; 00149 case STO_LST: 00150 { 00151 StoLst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o); 00152 } 00153 break; 00154 case STO_LCT: 00155 { 00156 StoLct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o); 00157 } 00158 break; 00159 default: 00160 GECODE_NEVER; 00161 } 00162 } 00163 00164 template<class TaskView, SortTaskOrder sto, bool inc> 00165 forceinline void 00166 sort(int* map, const TaskViewArray<TaskView>& t) { 00167 for (int i=t.size(); i--; ) 00168 map[i]=i; 00169 switch (sto) { 00170 case STO_EST: 00171 { 00172 SortMap<TaskView,StoEst,inc> o(t); 00173 Support::quicksort(map, t.size(), o); 00174 } 00175 break; 00176 case STO_ECT: 00177 { 00178 SortMap<TaskView,StoEct,inc> o(t); 00179 Support::quicksort(map, t.size(), o); 00180 } 00181 break; 00182 case STO_LST: 00183 { 00184 SortMap<TaskView,StoLst,inc> o(t); 00185 Support::quicksort(map, t.size(), o); 00186 } 00187 break; 00188 case STO_LCT: 00189 { 00190 SortMap<TaskView,StoLct,inc> o(t); 00191 Support::quicksort(map, t.size(), o); 00192 } 00193 break; 00194 default: 00195 GECODE_NEVER; 00196 } 00197 } 00198 00199 template<class TaskView, SortTaskOrder sto, bool inc> 00200 forceinline void 00201 sort(int* map, int n, const TaskViewArray<TaskView>& t) { 00202 switch (sto) { 00203 case STO_EST: 00204 { 00205 SortMap<TaskView,StoEst,inc> o(t); 00206 Support::quicksort(map, n, o); 00207 } 00208 break; 00209 case STO_ECT: 00210 { 00211 SortMap<TaskView,StoEct,inc> o(t); 00212 Support::quicksort(map, n, o); 00213 } 00214 break; 00215 case STO_LST: 00216 { 00217 SortMap<TaskView,StoLst,inc> o(t); 00218 Support::quicksort(map, n, o); 00219 } 00220 break; 00221 case STO_LCT: 00222 { 00223 SortMap<TaskView,StoLct,inc> o(t); 00224 Support::quicksort(map, n, o); 00225 } 00226 break; 00227 default: 00228 GECODE_NEVER; 00229 } 00230 } 00231 00232 }} 00233 00234 // STATISTICS: scheduling-other