Generated on Tue Jul 27 2010 21:59:18 for Gecode by doxygen 1.7.1

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