Line data Source code
1 : /*******************************************************************************
2 : * *
3 : * Cosmos:(C)oncept et (O)utils (S)tatistique pour les (Mo)deles *
4 : * (S)tochastiques *
5 : * *
6 : * Copyright (C) 2009-2012 LSV & LACL *
7 : * Authors: Benoît Barbot & Paolo Ballarini & Hilal Djafri *
8 : * Website: http://www.lsv.ens-cachan.fr/Software/cosmos *
9 : * *
10 : * This program is free software; you can redistribute it and/or modify *
11 : * it under the terms of the GNU General Public License as published by *
12 : * the Free Software Foundation; either version 3 of the License, or *
13 : * (at your option) any later version. *
14 : * *
15 : * This program is distributed in the hope that it will be useful, *
16 : * but WITHOUT ANY WARRANTY; without even the implied warranty of *
17 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
18 : * GNU General Public License for more details. *
19 : * *
20 : * You should have received a copy of the GNU General Public License along *
21 : * with this program; if not, write to the Free Software Foundation, Inc., *
22 : * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. *
23 : * file EventsQueueSet.cpp created by on 31/05/2016 *
24 : *******************************************************************************
25 : */
26 :
27 : #include <iostream>
28 : #include <assert.h>
29 : #include <algorithm>
30 : #include <iomanip>
31 :
32 : #include "Event.hpp"
33 : #include "EventsQueueSet.hpp"
34 :
35 :
36 : using namespace std;
37 :
38 : /**
39 : * Build an Event queue for the Petri net given as parameter.
40 : */
41 4 : EventsQueueSet::EventsQueueSet(const std::vector<size_t> &t):
42 : evtHeapIndex(t.size()),
43 4 : evtTbl(t.size()){
44 4 : }
45 :
46 : /**
47 : * Clear the events queue. The resulting events queues does not contain any event.
48 : */
49 39550 : void EventsQueueSet::reset() {
50 132100 : for(size_t it = 0; it< evtTbl.size(); ++it ){
51 92550 : evtHeapIndex[it].clear();
52 92550 : evtTbl[it].clear();
53 : }
54 39550 : evtHeap.clear();
55 : //Qsize = 0;
56 39550 : }
57 :
58 : /**
59 : * Copy of events queue
60 : */
61 0 : EventsQueueSet::EventsQueueSet(const EventsQueueSet& orig) {
62 :
63 : //Qsize = orig.Qsize;
64 :
65 0 : evtTbl = orig.evtTbl;
66 0 : evtHeap = orig.evtHeap;
67 0 : evtHeapIndex = orig.evtHeapIndex;
68 :
69 : /*eq = orig.eq;
70 : TransTableSize = orig.TransTableSize;
71 : TransTable = orig.TransTable;*/
72 0 : }
73 :
74 8 : EventsQueueSet::~EventsQueueSet() {
75 8 : }
76 :
77 : /*
78 : * Insert a new event in the events queue and update the tree.
79 : * @param e an event of the Petri net.
80 : */
81 1598915 : void EventsQueueSet::insert(const Event &e) {
82 : //assert(!isScheduled(e.transition, e.binding.id()));
83 : //cerr << "EQS insert"<< e << endl;
84 1598915 : Event& ep = evtTbl[e.transition][e.binding.id()];
85 1598915 : ep =e;
86 1598915 : evtHeapIndex[e.transition][e.binding.id()] = evtHeap.size();
87 1598915 : evtHeap.push_back( &ep );
88 :
89 1598915 : siftUp(evtHeap.size()-1);
90 1598915 : }
91 :
92 : /*
93 : * Replace the time, priority,service of an event and update the tree.
94 : * @param e an event of the Petri net.
95 : */
96 5346000 : void EventsQueueSet::replace(const Event &e) {
97 : //assert(isScheduled(e.transition, e.binding.id()));
98 : //cerr << "EQS replace"<< e << ":" << evtHeap.size() << endl;
99 5346000 : long int k = evtHeapIndex[e.transition][e.binding.id()];
100 5346000 : evtTbl[e.transition][e.binding.id()] = e;
101 :
102 5346000 : siftUp(k);
103 5346000 : siftDown(k);
104 : //cerr << "EQS replace" << evtHeap.size() << endl;
105 5346000 : }
106 :
107 1533820 : void inline EventsQueueSet::remove(size_t tr,size_t i, size_t b){
108 : //cerr << "remove tr:"<< tr << "\t index: " << i << "binding: " <<b << "\t eventtable size : "<< evtHeap.size() << endl;
109 :
110 1533820 : if (i == evtHeap.size()-1) {
111 : //evtHeapIndex[tr].erase(b);
112 114517 : evtHeap.pop_back();
113 : } else {
114 1419303 : Event& lastEvent = *evtHeap.back();
115 1419303 : evtHeapIndex[lastEvent.transition][lastEvent.binding.id()] = i;
116 : //evtHeapIndex[tr].erase(b);
117 1419303 : evtHeap[i] = evtHeap.back();
118 1419303 : evtHeap.pop_back();
119 :
120 1419303 : siftDown(i);
121 1419303 : siftUp(i);
122 : }
123 1533820 : }
124 :
125 : /*
126 : * Remove all event related to a transition.
127 : * @param tr a transition of the Petri net.
128 : */
129 0 : void EventsQueueSet::remove(size_t tr) {
130 : //cerr << "remove tr:"<< tr << "\t binding: ALL\t eventtable size : "<< evtHeap.size() << endl;
131 0 : for(const auto &bindmap: evtHeapIndex[tr]){
132 0 : auto i = bindmap.first;
133 0 : auto b = bindmap.second;
134 0 : remove(tr,i,b);
135 : }
136 0 : evtHeapIndex[tr].clear();
137 0 : }
138 :
139 : /*
140 : * Remove an event and update the tree.
141 : * @param tr a transition of the Petri net.
142 : * @param b a binding of the Petri net.
143 : */
144 1533820 : void EventsQueueSet::remove(size_t tr, size_t b) {
145 1533820 : long int i = -1;
146 1533820 : if(evtHeapIndex[tr].count(b)>0)i = evtHeapIndex[tr][b];
147 1533820 : evtTbl[tr].erase(b);
148 : //assert(i>=0);
149 1533820 : if(i>=0){
150 1533820 : remove(tr,i,b);
151 1533820 : evtHeapIndex[tr].erase(b);
152 : }
153 1533820 : }
154 :
155 : /**
156 : * Pause an event, remove it from the tree
157 : * @param t is the current time
158 : * @param tr a transition of the Petri net.
159 : * @param b a binding of the Petri net.
160 : */
161 0 : void EventsQueueSet::pause(double t, size_t tr,size_t b){
162 : //assert(i>=0);
163 0 : if(evtHeapIndex[tr].count(b)>0){
164 0 : evtTbl[tr][b].time -= t;
165 0 : long int i = evtHeapIndex[tr][b];
166 0 : if(i>=0){
167 0 : if ((size_t)i == evtHeap.size()-1) {
168 0 : evtHeapIndex[tr][b] = -1;
169 0 : evtHeap.pop_back();
170 : } else {
171 0 : Event& lastEvent = *evtHeap.back();
172 0 : evtHeapIndex[lastEvent.transition][lastEvent.binding.id()] = i;
173 0 : evtHeapIndex[tr][b] = -1 ;
174 0 : evtHeap[i] = evtHeap.back();
175 0 : evtHeap.pop_back();
176 :
177 0 : siftDown(i);
178 0 : siftUp(i);
179 : }
180 : }
181 : }
182 0 : }
183 :
184 : /**
185 : * Check if an event can be restarted. If it is possible
186 : * restart it otherwise return false.
187 : * @param t is the current time
188 : * @param tr a transition of the Petri net.
189 : * @param b a binding of the Petri net.
190 : */
191 1311915 : bool EventsQueueSet::restart(double t, size_t tr,size_t b){
192 1311915 : if(evtTbl[tr].count(b) == 0)return false;
193 0 : Event& e = evtTbl[tr][b];
194 0 : if(e.time < 0.0)return false;
195 0 : e.time += t;
196 0 : evtHeapIndex[tr][b] = evtHeap.size();
197 0 : evtHeap.push_back(&e);
198 :
199 0 : siftUp(evtHeap.size()-1);
200 0 : return true;
201 : }
202 :
203 63567017 : const Event& EventsQueueSet::InPosition(size_t i)const {
204 : //cerr << i << "," << evtHeap.size() << endl;
205 : //assert(i < evtHeap.size());
206 63567017 : return *evtHeap[i];
207 : }
208 :
209 :
210 7316451 : const std::map<size_t, long int>& EventsQueueSet::getScheduledBinding(size_t tr)const {
211 7316451 : return evtHeapIndex[tr];
212 : }
213 :
214 37638668 : bool EventsQueueSet::isScheduled(size_t tr,size_t b)const {
215 37638668 : return (evtHeapIndex[tr].count(b) > 0);
216 : }
217 :
218 36227640 : Event& EventsQueueSet::getEvent(size_t tr, size_t b) {
219 36227640 : Event &e = evtTbl[tr][b];
220 36227640 : return e;
221 : }
222 :
223 :
224 :
225 15617544 : void EventsQueueSet::swapEvt(size_t i,size_t j){
226 : //assert((size_t)evtHeapIndex[evtHeap[j].first][evtHeap[j].second] ==j
227 : // && (size_t)evtHeapIndex[evtHeap[i].first][evtHeap[i].second] == i);
228 15617544 : const Event& ei = *evtHeap[i];
229 15617544 : Event& ej = *evtHeap[j];
230 15617544 : evtHeapIndex[ej.transition][ej.binding.id()] = i;
231 15617544 : evtHeapIndex[ei.transition][ei.binding.id()] = j;
232 :
233 15617544 : evtHeap[j] = evtHeap[i];
234 15617544 : evtHeap[i] = &ej;
235 15617544 : }
236 :
237 10616810 : void EventsQueueSet::siftUp(size_t i) {
238 : size_t parentIndex;
239 :
240 10616810 : if (i != 0) {
241 3402650 : parentIndex = getParentIndex(i);
242 :
243 3402650 : if (InPosition(i).isPriorer(InPosition(parentIndex))){
244 2252592 : swapEvt(i, parentIndex);
245 2252592 : siftUp(parentIndex);
246 : }
247 : }
248 10616810 : }
249 :
250 20130255 : void EventsQueueSet::siftDown(size_t i) {
251 : size_t leftChildIndex, rightChildIndex, minIndex;
252 20130255 : leftChildIndex = getLeftChildIndex(i);
253 20130255 : rightChildIndex = getRightChildIndex(i);
254 20130255 : if (rightChildIndex >= evtHeap.size()) {
255 8883175 : if (leftChildIndex >= evtHeap.size())
256 6292051 : return;
257 : else
258 2591124 : minIndex = leftChildIndex;
259 : } else {
260 :
261 11247080 : if (InPosition(leftChildIndex).isPriorer(InPosition(rightChildIndex)))
262 6464058 : minIndex = leftChildIndex;
263 : else
264 4783022 : minIndex = rightChildIndex;
265 : }
266 :
267 13838204 : if (InPosition(minIndex).isPriorer(InPosition(i))) {
268 13364952 : swapEvt(minIndex,i);
269 13364952 : siftDown(minIndex);
270 : }
271 :
272 :
273 : }
274 :
275 6621149 : bool EventsQueueSet::isEmpty()const {
276 6621149 : return (evtHeap.size()==0);
277 : }
278 :
279 0 : void EventsQueueSet::printSedCmd(const std::vector<std::string> &trlabel, ostream& df)const {
280 0 : if(evtHeap.size()>0){
281 0 : df << "-e 's/\\$CF_" << trlabel[InPosition(0).transition] << "\\$/Red/g' ";
282 0 : for (unsigned int i = 1; i < evtHeap.size(); i++){
283 0 : df << "-e 's/\\$CF_" << trlabel[InPosition(i).transition] << "\\$/Blue/g' ";
284 : }
285 : }
286 0 : df << "-e 's/\\$CF_[^\\$]*\\$/Black/g' ";
287 0 : }
288 :
289 : /**
290 : * Print the content of the queues in a human readable format.
291 : */
292 0 : void EventsQueueSet::view(const std::vector<std::string> &trlabel)const {
293 0 : cerr << "********** EVENTS-QUEUE VIEW **********" << endl;
294 :
295 : //cerr << "Qsize:" << evtHeap.size() << endl;
296 :
297 0 : if (evtHeap.size() == 0)
298 0 : cerr << "EVENTS-QUEUE is empty!" << endl;
299 : else
300 0 : for (unsigned int i = 0; i < evtHeap.size(); i++){
301 0 : let e = InPosition(i);
302 : //cerr << "Equeue[" << i << "]:" << "( ";
303 0 : auto tr = trlabel[e.transition];
304 : //if(tr.DistTypeIndex == IMMEDIATE)cerr << "\033[1;33m";
305 0 : cerr << setw(15) << left << tr << ":";
306 : //cerr << "tr ID:" << setw(4)<< e.transition << " ";
307 0 : e.binding.print();
308 0 : cerr << ",\tt=" << e.time << ",\tp=" << e.priority << ",\tw=" << e.weight;
309 : //if(tr.DistTypeIndex == IMMEDIATE)cerr << "\033[0m";
310 0 : cerr << endl;
311 : }
312 0 : }
313 :
314 0 : size_t EventsQueueSet::getSize()const {
315 0 : return evtHeap.size();
316 24 : }
317 :
|
