Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
7.8 kB · 272 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273/* -*- 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. * */
#include <algorithm>#include <cmath>
namespace Gecode { namespace Int { namespace Cumulative {
/* * Omega tree */
forceinline void OmegaNode::init(const OmegaNode&, const OmegaNode&) { e = 0; env = -Limits::llinfinity; }
forceinline void OmegaNode::update(const OmegaNode& l, const OmegaNode& r) { e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env); }
template<class TaskView> OmegaTree<TaskView>::OmegaTree(Region& r, int c0, const TaskViewArray<TaskView>& t) : TaskTree<TaskView,OmegaNode>(r,t), c(c0) { for (int i=0; i<tasks.size(); i++) { leaf(i).e = 0; leaf(i).env = -Limits::llinfinity; } init(); }
template<class TaskView> forceinline void OmegaTree<TaskView>::insert(int i) { leaf(i).e = tasks[i].e(); leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e(); update(i); }
template<class TaskView> forceinline void OmegaTree<TaskView>::remove(int i) { leaf(i).e = 0; leaf(i).env = -Limits::llinfinity; update(i); }
template<class TaskView> forceinline long long int OmegaTree<TaskView>::env(void) const { return root().env; }
/* * Extended Omega tree */
forceinline void ExtOmegaNode::init(const ExtOmegaNode& l, const ExtOmegaNode& r) { OmegaNode::init(l,r); cenv = -Limits::llinfinity; }
forceinline void ExtOmegaNode::update(const ExtOmegaNode& l, const ExtOmegaNode& r) { OmegaNode::update(l,r); cenv = std::max(plus(l.cenv,r.e), r.cenv); }
template<class TaskView> void ExtOmegaTree<TaskView>::init(int ci0) { ci = ci0; for (int i=0; i<tasks.size(); i++) { leaf(i).e = 0; leaf(i).env = leaf(i).cenv = -Limits::llinfinity; } init(); }
template<class TaskView> template<class Node> ExtOmegaTree<TaskView>::ExtOmegaTree(Region& r, int c0, const TaskTree<TaskView,Node>& t) : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
template<class TaskView> forceinline long long int ExtOmegaTree<TaskView>::env(int i) { // Enter task i leaf(i).e = tasks[i].e(); leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e(); leaf(i).cenv = static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e(); TaskTree<TaskView,ExtOmegaNode>::update(i);
// Perform computation of node for task with minest int met = 0; { long long int e = 0; while (!n_leaf(met)) { if (plus(node[n_right(met)].cenv,e) > static_cast<long long int>(c-ci) * tasks[i].lct()) { met = n_right(met); } else { e += node[n_right(met)].e; met = n_left(met); } } }
/* * The following idea to compute the cut in one go is taken from: * Joseph Scott, Filtering Algorithms for Discrete Resources, * Master Thesis, Uppsala University, 2010 (in preparation). */
// Now perform split from leaf met upwards long long int a_e = node[met].e; long long int a_env = node[met].env; long long int b_e = 0;
while (!n_root(met)) { if (left(met)) { b_e += node[n_right(n_parent(met))].e; } else { a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e)); a_e += node[n_left(n_parent(met))].e; } met = n_parent(met); }
return plus(a_env,b_e); }
/* * Omega lambda tree */
forceinline void OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) { OmegaNode::init(l,r); le = 0; lenv = -Limits::llinfinity; resLe = undef; resLenv = undef; }
forceinline void OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) { OmegaNode::update(l,r); if (l.le + r.e > l.e + r.le) { le = l.le + r.e; resLe = l.resLe; } else { le = l.e + r.le; resLe = r.resLe; } if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) { lenv = r.lenv; resLenv = r.resLenv; } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) { assert(plus(l.env,r.le) > r.lenv); lenv = plus(l.env,r.le); resLenv = r.resLe; } else { assert((plus(l.lenv,r.e) > r.lenv) && (plus(l.lenv,r.e) > plus(l.env,r.le))); lenv = plus(l.lenv,r.e); resLenv = l.resLenv; } }
template<class TaskView> OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, int c0, const TaskViewArray<TaskView>& t) : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) { // Enter all tasks into tree (omega = all tasks, lambda = empty) for (int i=0; i<tasks.size(); i++) { leaf(i).e = tasks[i].e(); leaf(i).le = 0; leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e(); leaf(i).lenv = -Limits::llinfinity; leaf(i).resLe = OmegaLambdaNode::undef; leaf(i).resLenv = OmegaLambdaNode::undef; } update(); }
template<class TaskView> forceinline void OmegaLambdaTree<TaskView>::shift(int i) { // i is in omega assert(leaf(i).env > -Limits::llinfinity); leaf(i).le = leaf(i).e; leaf(i).e = 0; leaf(i).lenv = leaf(i).env; leaf(i).env = -Limits::llinfinity; leaf(i).resLe = i; leaf(i).resLenv = i; update(i); }
template<class TaskView> forceinline void OmegaLambdaTree<TaskView>::lremove(int i) { // i not in omega but in lambda assert(leaf(i).env == -Limits::llinfinity); assert(leaf(i).lenv > -Limits::llinfinity); leaf(i).le = 0; leaf(i).lenv = -Limits::llinfinity; leaf(i).resLe = OmegaLambdaNode::undef; leaf(i).resLenv = OmegaLambdaNode::undef; update(i); }
template<class TaskView> forceinline bool OmegaLambdaTree<TaskView>::lempty(void) const { return root().resLenv < 0; }
template<class TaskView> forceinline int OmegaLambdaTree<TaskView>::responsible(void) const { return root().resLenv; }
template<class TaskView> forceinline long long int OmegaLambdaTree<TaskView>::env(void) const { return root().env; }
template<class TaskView> forceinline long long int OmegaLambdaTree<TaskView>::lenv(void) const { return root().lenv; }
}}}
// STATISTICS: int-prop