Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
basic.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2010
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
13  * $Revision: 13068 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int { namespace Cumulative {
41 
43  class Event {
44  public:
46  enum Type {
47  LRT = 0,
48  LCT = 1,
49  EST = 2,
50  ZRO = 3,
51  ERT = 4,
52  END = 5
53  };
54  Type e;
55  int t;
56  int i;
57  void init(Type e, int t, int i);
60  bool operator <(const Event& e) const;
61  };
62 
64  template<class Task>
65  class TaskByDecCap {
66  public:
68  bool operator ()(const Task& t1, const Task& t2) const;
69  };
70 
71  forceinline void
72  Event::init(Event::Type e0, int t0, int i0) {
73  e=e0; t=t0; i=i0;
74  }
75 
76  forceinline bool
77  Event::operator <(const Event& e) const {
78  if (this->t == e.t)
79  return this->e < e.e;
80  return this->t < e.t;
81  }
82 
83  template<class Task>
84  forceinline bool
85  TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
86  return t1.c() > t2.c();
87  }
88 
89 
90  // Basic propagation
91  template<class Task, class Cap>
93  basic(Space& home, bool& subsumed, Cap c, TaskArray<Task>& t) {
94  subsumed = false;
95  int ccur = c.max();
96  int cmax = ccur;
97  int cmin = ccur;
98  // Sort tasks by decreasing capacity
99  TaskByDecCap<Task> tbdc;
100  Support::quicksort(&t[0], t.size(), tbdc);
101 
102  Region r(home);
103 
104  Event* e = r.alloc<Event>(4*t.size()+1);
105 
106  // Initialize events
107  bool assigned=true;
108  {
109  bool required=false;
110  int n=0;
111  for (int i=t.size(); i--; )
112  if (t[i].assigned()) {
113  // Only add required part
114  if (t[i].pmin() > 0) {
115  required = true;
116  e[n++].init(Event::ERT,t[i].lst(),i);
117  e[n++].init(Event::LRT,t[i].ect(),i);
118  } else if (t[i].pmax() == 0) {
119  required = true;
120  e[n++].init(Event::ZRO,t[i].lst(),i);
121  }
122  } else {
123  assigned = false;
124  e[n++].init(Event::EST,t[i].est(),i);
125  e[n++].init(Event::LCT,t[i].lct(),i);
126  // Check whether task has required part
127  if (t[i].lst() < t[i].ect()) {
128  required = true;
129  e[n++].init(Event::ERT,t[i].lst(),i);
130  e[n++].init(Event::LRT,t[i].ect(),i);
131  }
132  }
133 
134  // Check whether no task has a required part
135  if (!required) {
136  subsumed = assigned;
137  return ES_FIX;
138  }
139 
140  // Write end marker
142 
143  // Sort events
144  Support::quicksort(e, n);
145  }
146 
147  // Set of current but not required tasks
148  Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
149 
150  // Process events, use ccur as the capacity that is still free
151  while (e->e != Event::END) {
152  // Current time
153  int time = e->t;
154 
155  // Process events for completion of required part
156  for ( ; (e->t == time) && (e->e == Event::LRT); e++)
157  if (t[e->i].mandatory()) {
158  tasks.set(static_cast<unsigned int>(e->i)); ccur += t[e->i].c();
159  }
160  // Process events for completion of task
161  for ( ; (e->t == time) && (e->e == Event::LCT); e++)
162  tasks.clear(static_cast<unsigned int>(e->i));
163  // Process events for start of task
164  for ( ; (e->t == time) && (e->e == Event::EST); e++)
165  tasks.set(static_cast<unsigned int>(e->i));
166  // Process events for zero-length task
167  for ( ; (e->t == time) && (e->e == Event::ZRO); e++) {
168  ccur -= t[e->i].c();
169  if (ccur < cmin) cmin=ccur;
170  if (ccur < 0)
171  return ES_FAILED;
172  ccur += t[e->i].c();
173  }
174 
175  // norun start time for 0-length tasks
176  int zltime = time;
177  // Process events for start of required part
178  for ( ; (e->t == time) && (e->e == Event::ERT); e++)
179  if (t[e->i].mandatory()) {
180  tasks.clear(static_cast<unsigned int>(e->i));
181  ccur -= t[e->i].c();
182  if (ccur < cmin) cmin=ccur;
183  zltime = time+1;
184  if (ccur < 0)
185  return ES_FAILED;
186  } else if (t[e->i].optional() && (t[e->i].c() > ccur)) {
187  GECODE_ME_CHECK(t[e->i].excluded(home));
188  }
189 
190  // Exploit that tasks are sorted according to capacity
192  j() && (t[j.val()].c() > ccur); ++j)
193  // Task j cannot run from time to next time - 1
194  if (t[j.val()].mandatory()) {
195  if (t[j.val()].pmin() > 0) {
196  GECODE_ME_CHECK(t[j.val()].norun(home, time, e->t - 1));
197  } else {
198  GECODE_ME_CHECK(t[j.val()].norun(home, zltime, e->t - 1));
199  }
200  }
201  }
202 
203  GECODE_ME_CHECK(c.gq(home,cmax-cmin));
204 
205  subsumed = assigned;
206  return ES_NOFIX;
207  }
208 
209 }}}
210 
211 // STATISTICS: int-prop
int i
Number of task Initialize event.
Definition: basic.hpp:56
NodeType t
Type of node.
Definition: bool-expr.cpp:234
void clear(unsigned int i)
Clear bit i.
Type e
Type of event.
Definition: basic.hpp:54
ExecStatus basic(Space &home, bool &subsumed, Cap c, TaskArray< Task > &t)
Perform basic propagation.
Definition: basic.hpp:93
bool operator<(const Event &e) const
Order among events.
Definition: basic.hpp:77
void init(Type e, int t, int i)
Definition: basic.hpp:72
Task array.
Definition: task.hh:167
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Value iterator for values in a bitset.
int t
Time of event.
Definition: basic.hpp:55
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
Type
Event type for task with order in which they are processed.
Definition: basic.hpp:46
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Zero-length task start time.
Definition: basic.hpp:50
void set(unsigned int i)
Set bit i.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Earliest required time of task.
Definition: basic.hpp:51
Sort order for tasks by decreasing capacity.
Definition: basic.hpp:65
const int infinity
Infinity for integers.
Definition: int.hh:117
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Definition: subsumption.hpp:42
bool operator()(const Task &t1, const Task &t2) const
Sort order.
Definition: basic.hpp:85
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:67
Propagation has not computed fixpoint.
Definition: core.hpp:526
Latest required time of task.
Definition: basic.hpp:47
Latest completion time of task.
Definition: basic.hpp:48
Gecode toplevel namespace
Earliest start time of task.
Definition: basic.hpp:49
Event for task.
Definition: basic.hpp:43