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