this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2015
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Int {
35
36 forceinline void
37 Event::init(Event::Type e0, int t0, int i0) {
38 ei=static_cast<unsigned int>(e0 | (i0 << 3)); t=t0;
39 }
40
41 forceinline Event::Type
42 Event::type(void) const {
43 return static_cast<Type>(ei & 7);
44 }
45 forceinline int
46 Event::time(void) const {
47 return t;
48 }
49 forceinline int
50 Event::idx(void) const {
51 return static_cast<int>(ei >> 3);;
52 }
53
54 forceinline bool
55 Event::operator <(const Event& e) const {
56 if (time() == e.time())
57 return type() < e.type();
58 return time() < e.time();
59 }
60
61
62 template<class Char, class Traits>
63 inline std::basic_ostream<Char,Traits>&
64 operator <<(std::basic_ostream<Char,Traits>& os, const Event& e) {
65 std::basic_ostringstream<Char,Traits> s;
66 s.copyfmt(os); s.width(0);
67 s << '[';
68 switch (e.type()) {
69 case Event::LRT: s << "LRT"; break;
70 case Event::LCT: s << "LCT"; break;
71 case Event::EST: s << "EST"; break;
72 case Event::ZRO: s << "ZRO"; break;
73 case Event::ERT: s << "ERT"; break;
74 default: GECODE_NEVER;
75 }
76 s << ',' << e.time() << ',' << e.idx() << ']';
77 return os << s.str();
78 }
79
80
81 template<class Task>
82 forceinline Event*
83 Event::events(Region& r, const TaskArray<Task>& t, bool& assigned) {
84 Event* e = r.alloc<Event>(4*t.size()+1);
85
86 // Initialize events
87 assigned=true;
88 bool required=false;
89
90 int n=0;
91 for (int i=0; i<t.size(); i++)
92 if (t[i].assigned()) {
93 // Only add required part
94 if (t[i].pmin() > 0) {
95 required = true;
96 e[n++].init(Event::ERT,t[i].lst(),i);
97 e[n++].init(Event::LRT,t[i].ect(),i);
98 } else if (t[i].pmax() == 0) {
99 required = true;
100 e[n++].init(Event::ZRO,t[i].lst(),i);
101 }
102 } else {
103 assigned = false;
104 e[n++].init(Event::EST,t[i].est(),i);
105 e[n++].init(Event::LCT,t[i].lct(),i);
106 // Check whether task has required part
107 if (t[i].lst() < t[i].ect()) {
108 required = true;
109 e[n++].init(Event::ERT,t[i].lst(),i);
110 e[n++].init(Event::LRT,t[i].ect(),i);
111 }
112 }
113
114 if (!required)
115 return nullptr;
116
117 // Sort events
118 Support::quicksort(e, n);
119
120 // Write end marker
121 e[n++].init(Event::END,Limits::infinity,0);
122
123 return e;
124 }
125
126 template<class Task>
127 forceinline Event*
128 Event::events(Region& r, const TaskArray<Task>& t) {
129 Event* e = r.alloc<Event>(2*t.size()+1);
130
131 // Only add assigned and mandatory tasks
132 int n=0;
133 for (int i=0; i<t.size(); i++)
134 if (t[i].assigned() && t[i].mandatory()) {
135 if (t[i].pmin() > 0) {
136 e[n++].init(Event::ERT,t[i].lst(),i);
137 e[n++].init(Event::LRT,t[i].ect(),i);
138 } else if (t[i].pmax() == 0) {
139 e[n++].init(Event::ZRO,t[i].lst(),i);
140 }
141 } else {
142 assert(!t[i].excluded());
143 return nullptr;
144 }
145
146 // Sort events
147 Support::quicksort(e, n);
148
149 // Write end marker
150 e[n++].init(Event::END,Limits::infinity,0);
151
152 return e;
153 }
154
155}}
156
157// STATISTICS: int-prop