sort.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Christian Schulte, 2009
* Guido Tack, 2010
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Int {
template<class TaskView, bool inc>
class StoEst {
public:
bool operator ()(const TaskView& t1, const TaskView& t2) const;
};
template<class TaskView, bool inc>
class StoEct {
public:
bool operator ()(const TaskView& t1, const TaskView& t2) const;
};
template<class TaskView, bool inc>
class StoLst {
public:
bool operator ()(const TaskView& t1, const TaskView& t2) const;
};
template<class TaskView, bool inc>
class StoLct {
public:
bool operator ()(const TaskView& t1, const TaskView& t2) const;
};
template<class TaskView, template<class,bool> class STO, bool inc>
class SortMap {
private:
const TaskViewArray<TaskView>& tasks;
STO<TaskView,inc> sto;
public:
SortMap(const TaskViewArray<TaskView>& t);
bool operator ()(int& i, int& j) const;
};
template<class TaskView, bool inc>
forceinline bool
StoEst<TaskView,inc>::operator ()
(const TaskView& t1, const TaskView& t2) const {
return inc ?
(t1.est() < t2.est() || (t1.est()==t2.est() && t1.lct() < t2.lct()))
: (t2.est() < t1.est() || (t2.est()==t1.est() && t2.lct() < t1.lct()));
}
template<class TaskView, bool inc>
forceinline bool
StoEct<TaskView,inc>::operator ()
(const TaskView& t1, const TaskView& t2) const {
return inc ?
(t1.ect() < t2.ect() || (t1.ect()==t2.ect() && t1.lst() < t2.lst()))
: (t2.ect() < t1.ect() || (t2.ect()==t1.ect() && t2.lst() < t1.lst()));
}
template<class TaskView, bool inc>
forceinline bool
StoLst<TaskView,inc>::operator ()
(const TaskView& t1, const TaskView& t2) const {
return inc ?
(t1.lst() < t2.lst() || (t1.lst()==t2.lst() && t1.ect() < t2.ect()))
: (t2.lst() < t1.lst() || (t2.lst()==t1.lst() && t2.ect() < t1.ect()));
}
template<class TaskView, bool inc>
forceinline bool
StoLct<TaskView,inc>::operator ()
(const TaskView& t1, const TaskView& t2) const {
return inc ?
(t1.lct() < t2.lct() || (t1.lct()==t2.lct() && t1.est() < t2.est()))
: (t2.lct() < t1.lct() || (t2.lct()==t1.lct() && t2.est() < t1.est()));
}
template<class TaskView, template<class,bool> class STO, bool inc>
forceinline
SortMap<TaskView,STO,inc>::SortMap(const TaskViewArray<TaskView>& t)
: tasks(t) {}
template<class TaskView, template<class,bool> class STO, bool inc>
forceinline bool
SortMap<TaskView,STO,inc>::operator ()(int& i, int& j) const {
return sto(tasks[i],tasks[j]);
}
template<class TaskView, SortTaskOrder sto, bool inc>
forceinline void
sort(TaskViewArray<TaskView>& t) {
switch (sto) {
case STO_EST:
{
StoEst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
}
break;
case STO_ECT:
{
StoEct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
}
break;
case STO_LST:
{
StoLst<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
}
break;
case STO_LCT:
{
StoLct<TaskView,inc> o; Support::quicksort(&t[0], t.size(), o);
}
break;
default:
GECODE_NEVER;
}
}
template<class TaskView, SortTaskOrder sto, bool inc>
forceinline void
sort(int* map, const TaskViewArray<TaskView>& t) {
for (int i=0; i<t.size(); i++)
map[i]=i;
switch (sto) {
case STO_EST:
{
SortMap<TaskView,StoEst,inc> o(t);
Support::quicksort(map, t.size(), o);
}
break;
case STO_ECT:
{
SortMap<TaskView,StoEct,inc> o(t);
Support::quicksort(map, t.size(), o);
}
break;
case STO_LST:
{
SortMap<TaskView,StoLst,inc> o(t);
Support::quicksort(map, t.size(), o);
}
break;
case STO_LCT:
{
SortMap<TaskView,StoLct,inc> o(t);
Support::quicksort(map, t.size(), o);
}
break;
default:
GECODE_NEVER;
}
}
template<class TaskView, SortTaskOrder sto, bool inc>
forceinline void
sort(int* map, int n, const TaskViewArray<TaskView>& t) {
switch (sto) {
case STO_EST:
{
SortMap<TaskView,StoEst,inc> o(t);
Support::quicksort(map, n, o);
}
break;
case STO_ECT:
{
SortMap<TaskView,StoEct,inc> o(t);
Support::quicksort(map, n, o);
}
break;
case STO_LST:
{
SortMap<TaskView,StoLst,inc> o(t);
Support::quicksort(map, n, o);
}
break;
case STO_LCT:
{
SortMap<TaskView,StoLct,inc> o(t);
Support::quicksort(map, n, o);
}
break;
default:
GECODE_NEVER;
}
}
}}
// STATISTICS: int-other
Gecode::Int::SortMap
Sorting maps rather than tasks.
Definition sort.hpp:72
Gecode::Int::SortMap::operator()
bool operator()(int &i, int &j) const
Sort order.
Definition sort.hpp:127
Gecode::Int::SortMap::SortMap
SortMap(const TaskViewArray< TaskView > &t)
Initialize.
Definition sort.hpp:123
Gecode::Int::StoEct
Sort by earliest completion times.
Definition sort.hpp:48
Gecode::Int::StoEct::operator()
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:97
Gecode::Int::StoEst
Sort by earliest start times.
Definition sort.hpp:40
Gecode::Int::StoEst::operator()
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:88
Gecode::Int::StoLct
Sort by latest completion times.
Definition sort.hpp:64
Gecode::Int::StoLct::operator()
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:115
Gecode::Int::StoLst
Sort by latest start times.
Definition sort.hpp:56
Gecode::Int::StoLst::operator()
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition sort.hpp:106
Gecode::Int::TaskViewArray
Task view array.
Definition task.hh:233
Gecode::Int::TaskViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:142
Gecode::Int
Finite domain integers.
Gecode::Int::sort
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing).
Definition sort.hpp:133
Gecode::Int::STO_ECT
@ STO_ECT
Sort by earliest completion times.
Definition task.hh:284
Gecode::Int::STO_EST
@ STO_EST
Sort by earliest start times.
Definition task.hh:283
Gecode::Int::STO_LST
@ STO_LST
Sort by latest start times.
Definition task.hh:285
Gecode::Int::STO_LCT
@ STO_LCT
Sort by latest completion times.
Definition task.hh:286
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56