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: 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 : *******************************************************************************
24 : */
25 :
26 : #include "EventsQueue.hpp"
27 : #include "Event.hpp"
28 : #include <iostream>
29 : #include <assert.h>
30 : #include <algorithm>
31 : #include <iomanip>
32 :
33 : using namespace std;
34 :
35 : /**
36 : * Build an Event queue for the Petri net given as parameter.
37 : */
38 22 : EventsQueue::EventsQueue(const std::vector<size_t> &t):evtTbl(t.size(),vector<Event>()){
39 22 : auto comp =0;
40 436 : for(size_t it = 0; it< t.size(); ++it ){
41 : //evtTbl.push_back(vector<Event>());
42 414 : evtHeapIndex.push_back(vector<long int>(t[it],-1));
43 1274 : for (size_t it2 = 0 ; it2< t[it]; ++it2) {
44 860 : evtTbl[it].push_back(Event());
45 860 : comp++;
46 : }
47 : }
48 22 : evtHeap.reserve(comp);
49 22 : }
50 :
51 : /**
52 : * Clear the events queue. The resulting events queues does not contain any event.
53 : */
54 182552 : void EventsQueue::reset() {
55 4052112 : for(size_t it = 0; it< evtHeapIndex.size(); ++it )
56 8635570 : for(size_t it2 = 0; it2< evtHeapIndex[it].size(); ++it2 ){
57 4766010 : evtHeapIndex[it][it2]= -1;
58 4766010 : evtTbl[it][it2].time = -1.0;
59 : }
60 182552 : evtHeap.clear();
61 : //Qsize = 0;
62 182552 : }
63 :
64 : /**
65 : * Copy of events queue
66 : */
67 0 : EventsQueue::EventsQueue(const EventsQueue& orig) {
68 :
69 : //Qsize = orig.Qsize;
70 :
71 0 : evtTbl = orig.evtTbl;
72 0 : evtHeap = orig.evtHeap;
73 0 : evtHeapIndex = orig.evtHeapIndex;
74 :
75 : /*eq = orig.eq;
76 : TransTableSize = orig.TransTableSize;
77 : TransTable = orig.TransTable;*/
78 0 : }
79 :
80 44 : EventsQueue::~EventsQueue() {
81 44 : }
82 :
83 : /*
84 : * Insert a new event in the events queue and update the tree.
85 : * @param e an event of the Petri net.
86 : */
87 10570913 : void EventsQueue::insert(const Event &e) {
88 : //assert(!isScheduled(e.transition, e.binding.id()));
89 10570913 : evtTbl[e.transition][e.binding.id()] = e;
90 10570913 : evtHeapIndex[e.transition][e.binding.id()] = evtHeap.size();
91 10570913 : evtHeap.push_back(sizeSq(e.transition,e.binding.id()));
92 :
93 10570913 : siftUp(evtHeap.size()-1);
94 10570913 : }
95 :
96 : /*
97 : * Replace the time, priority,service of an event and update the tree.
98 : * @param e an event of the Petri net.
99 : */
100 52000573 : void EventsQueue::replace(const Event &e) {
101 : //assert(isScheduled(e.transition, e.binding.id()));
102 52000573 : long int k = evtHeapIndex[e.transition][e.binding.id()];
103 52000573 : evtTbl[e.transition][e.binding.id()] = e;
104 :
105 52000573 : siftUp(k);
106 52000573 : siftDown(k);
107 52000573 : }
108 :
109 : /*
110 : * Remove an event and update the tree.
111 : * @param tr a transition of the Petri net.
112 : * @param b a binding of the Petri net.
113 : */
114 10210375 : void EventsQueue::remove(size_t tr, size_t b) {
115 10210375 : long int i = evtHeapIndex[tr][b];
116 10210375 : evtTbl[tr][b].time = -1.0;
117 : //assert(i>=0);
118 10210375 : if(i>=0){
119 10210375 : if ((size_t)i == evtHeap.size()-1) {
120 423312 : evtHeapIndex[tr][b] = -1;
121 423312 : evtHeap.pop_back();
122 : } else {
123 9787063 : evtHeapIndex[evtHeap.back().tr][evtHeap.back().bid] = i;
124 9787063 : evtHeapIndex[tr][b] = -1 ;
125 9787063 : evtHeap[i] = evtHeap.back();
126 9787063 : evtHeap.pop_back();
127 :
128 9787063 : siftDown(i);
129 9787063 : siftUp(i);
130 : }
131 : }
132 10210375 : }
133 :
134 : /**
135 : * Pause an event, remove it from the tree
136 : * @param t is the current time
137 : * @param tr a transition of the Petri net.
138 : * @param b a binding of the Petri net.
139 : */
140 0 : void EventsQueue::pause(double t, size_t tr,size_t b){
141 0 : evtTbl[tr][b].time -= t;
142 0 : long int i = evtHeapIndex[tr][b];
143 : //assert(i>=0);
144 0 : if(i>=0){
145 0 : if ((size_t)i == evtHeap.size()-1) {
146 0 : evtHeapIndex[tr][b] = -1;
147 0 : evtHeap.pop_back();
148 : } else {
149 0 : evtHeapIndex[evtHeap.back().tr][evtHeap.back().bid] = i;
150 0 : evtHeapIndex[tr][b] = -1 ;
151 0 : evtHeap[i] = evtHeap.back();
152 0 : evtHeap.pop_back();
153 :
154 0 : siftDown(i);
155 0 : siftUp(i);
156 : }
157 : }
158 0 : }
159 :
160 : /**
161 : * Check if an event can be restarted. If it is possible
162 : * restart it otherwise return false.
163 : * @param t is the current time
164 : * @param tr a transition of the Petri net.
165 : * @param b a binding of the Petri net.
166 : */
167 9629218 : bool EventsQueue::restart(double t, size_t tr,size_t b){
168 9629218 : if(evtTbl[tr][b].time < 0.0)return false;
169 0 : evtTbl[tr][b].time += t;
170 0 : evtHeapIndex[tr][b] = evtHeap.size();
171 0 : evtHeap.push_back(sizeSq(tr,b));
172 :
173 0 : siftUp(evtHeap.size()-1);
174 0 : return true;
175 : }
176 :
177 :
178 278189546 : const Event& EventsQueue::InPosition(size_t i)const {
179 : //assert(i < evtHeap.size());
180 278189546 : return evtTbl[evtHeap[i].tr][evtHeap[i].bid];
181 : }
182 :
183 :
184 168644228 : bool EventsQueue::isScheduled(size_t tr,size_t b)const {
185 168644228 : return (evtHeapIndex[tr][b] >= 0);
186 : }
187 :
188 0 : Event& EventsQueue::getEvent(size_t tr, size_t b) {
189 0 : Event &e = evtTbl[tr][b];
190 0 : return e;
191 : }
192 :
193 :
194 :
195 50284836 : void EventsQueue::swapEvt(size_t i,size_t j){
196 : //assert((size_t)evtHeapIndex[evtHeap[j].first][evtHeap[j].second] ==j
197 : // && (size_t)evtHeapIndex[evtHeap[i].first][evtHeap[i].second] == i);
198 50284836 : evtHeapIndex[evtHeap[j].tr][evtHeap[j].bid] = i;
199 50284836 : evtHeapIndex[evtHeap[i].tr][evtHeap[i].bid] = j;
200 :
201 50284836 : sizeSq swappair = evtHeap[j];
202 50284836 : evtHeap[j] = evtHeap[i];
203 50284836 : evtHeap[i] = swappair;
204 50284836 : }
205 :
206 :
207 85426339 : void EventsQueue::siftUp(size_t i) {
208 : size_t parentIndex;
209 :
210 85426339 : if (i != 0) {
211 31866301 : parentIndex = getParentIndex(i);
212 :
213 31866301 : if (InPosition(i).isPriorer(InPosition(parentIndex))){
214 13067790 : swapEvt(i, parentIndex);
215 13067790 : siftUp(parentIndex);
216 : }
217 : }
218 85426339 : }
219 :
220 :
221 99004682 : void EventsQueue::siftDown(size_t i) {
222 : size_t leftChildIndex, rightChildIndex, minIndex;
223 99004682 : leftChildIndex = getLeftChildIndex(i);
224 99004682 : rightChildIndex = getRightChildIndex(i);
225 99004682 : if (rightChildIndex >= evtHeap.size()) {
226 72181446 : if (leftChildIndex >= evtHeap.size())
227 41461035 : return;
228 : else
229 30720411 : minIndex = leftChildIndex;
230 : } else {
231 :
232 26823236 : if (InPosition(leftChildIndex).isPriorer(InPosition(rightChildIndex)))
233 15742532 : minIndex = leftChildIndex;
234 : else
235 11080704 : minIndex = rightChildIndex;
236 : }
237 :
238 57543647 : if (InPosition(minIndex).isPriorer(InPosition(i))) {
239 37217046 : swapEvt(minIndex,i);
240 37217046 : siftDown(minIndex);
241 : }
242 :
243 :
244 : }
245 :
246 :
247 46431025 : bool EventsQueue::isEmpty()const {
248 46431025 : return (evtHeap.size()==0);
249 : }
250 :
251 :
252 0 : void EventsQueue::printSedCmd(const std::vector<std::string> &trlabl,ostream& df)const {
253 0 : if(evtHeap.size()>0){
254 0 : df << "-e 's/\\$CF_" << trlabl[InPosition(0).transition] << "\\$/Red/g' ";
255 0 : for (unsigned int i = 1; i < evtHeap.size(); i++){
256 0 : df << "-e 's/\\$CF_" << trlabl[InPosition(i).transition] << "\\$/Lightblue/g' ";
257 : }
258 : }
259 0 : df << "-e 's/\\$CF_[^\\$]*\\$/Black/g' ";
260 0 : for(size_t i =0; i < trlabl.size(); i++ ){
261 0 : df << "-e 's/\\$ET_" << trlabl[i] << "\\$/";
262 0 : if(isScheduled( i , 0)){
263 0 : let ev = evtTbl[i][0];
264 0 : df << "(" << ev.time << ", " << ev.priority << ", " << ev.weight << ")";
265 : }
266 0 : df << "/g' ";
267 : }
268 0 : }
269 :
270 : /**
271 : * Print the content of the queues in a human readable format.
272 : */
273 0 : void EventsQueue::view(const std::vector<std::string> &trlabl)const {
274 0 : cerr << "********** EVENTS-QUEUE VIEW **********" << endl;
275 :
276 : //cerr << "Qsize:" << evtHeap.size() << endl;
277 :
278 0 : if (evtHeap.size() == 0)
279 0 : cerr << "EVENTS-QUEUE is empty!" << endl;
280 : else
281 0 : for (unsigned int i = 0; i < evtHeap.size(); i++){
282 0 : Event e = InPosition(i);
283 : //cerr << "Equeue[" << i << "]:" << "( ";
284 0 : auto tr = trlabl[e.transition];
285 : //if(tr.DistTypeIndex == IMMEDIATE)cerr << "\033[1;33m";
286 0 : cerr << setw(15) << left << tr << "(" << e.transition << ") :";
287 : //cerr << "tr ID:" << setw(4)<< e.transition << " ";
288 0 : e.binding.print();
289 0 : cerr << ",\tt=" << e.time << ",\tp=" << e.priority << ",\tw=" << e.weight;
290 : //if(tr.DistTypeIndex == IMMEDIATE)cerr << "\033[0m";
291 0 : cerr << endl;
292 : }
293 87 : }
|
