1 | package desmoj.core.simulator; |
2 | |
3 | import java.util.Iterator; |
4 | import org.apache.commons.collections.list.TreeList; |
5 | import desmoj.core.exception.SimAbortedException; |
6 | import desmoj.core.report.ErrorMessage; |
7 | |
8 | /** |
9 | * Alternative Implementation of the interface <code>EventList</code> using a |
10 | * tree-based list as a container for the event-notes, yielding both access and |
11 | * removal of event-list entries in O(log n) time. |
12 | * |
13 | * Disadvantages compared to <code>EventVector</code> include |
14 | * non-thread-safeness (however, discrete Event simulation should never attempt |
15 | * concurrent modifications of the event-list) and the slightly higher memory |
16 | * requirement. |
17 | * |
18 | * The internal tree-based list is provided by the class |
19 | * <code>org.apache.commons.collections.list.TreeList</code> from the Commons |
20 | * Collections package from the Apache Jakarta Commons Project (see |
21 | * http://jakarta.apache.org/commons/index.html). Thus, his product includes |
22 | * software developed by The Apache Software Foundation |
23 | * (http://www.apache.org/). For License see |
24 | * http://www.apache.org/licenses/LICENSE-2.0 (of which a copy can be found in |
25 | * the root directory of this distribtuon). |
26 | * |
27 | * @see org.apache.commons.collections.list.TreeList |
28 | * @see EventVectorList |
29 | * @see EventNote |
30 | * |
31 | * @version DESMO-J, Ver. 2.3.3 copyright (c) 2011 |
32 | * @author Tim Lechler, Ruth Meyer, modified by Johannes Göbel |
33 | * |
34 | * Licensed under the Apache License, Version 2.0 (the "License"); |
35 | * you may not use this file except in compliance with the License. You |
36 | * may obtain a copy of the License at |
37 | * http://www.apache.org/licenses/LICENSE-2.0 |
38 | * |
39 | * Unless required by applicable law or agreed to in writing, software |
40 | * distributed under the License is distributed on an "AS IS" |
41 | * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
42 | * or implied. See the License for the specific language governing |
43 | * permissions and limitations under the License. |
44 | * |
45 | */ |
46 | public class EventTreeList extends EventList { |
47 | |
48 | /** |
49 | * The tree list container used to store the event-notes. |
50 | */ |
51 | TreeList eTreeList; // The tree list containing all Event notes. |
52 | |
53 | /** |
54 | * Constructs an empty event-list. |
55 | */ |
56 | EventTreeList() { |
57 | |
58 | // create event-list |
59 | eTreeList = new TreeList(); |
60 | |
61 | } |
62 | |
63 | /** |
64 | * Creates a new event-note with the initial values given as parameters. This |
65 | * resembles the factory method design pattern described in [Gamm95] p. 107. |
66 | * This design pattern is used to ensure that always the appropriate |
67 | * implementation of Event notes is used together with an individual |
68 | * implementation of an event-list. EventTreeList does not need any special |
69 | * implementation of Event notes and thus simply passes the construction |
70 | * through to the default implementation of EventNote. |
71 | * |
72 | * @param who |
73 | * Entity : the entity or process associated with the event-note |
74 | * @param what |
75 | * Event : the event or external event associated with the |
76 | * EventNote |
77 | * @param when |
78 | * TimeInstant : the point in simulation time associated with the |
79 | * EventNote |
80 | * @see EventNote |
81 | */ |
82 | EventNote createEventNote(Entity who, Event<Entity> what, TimeInstant when) { |
83 | |
84 | return new EventNote(who, what, when); |
85 | |
86 | } |
87 | |
88 | /** |
89 | * Returns the first event-note in the event-list. It is the event-note with |
90 | * the lowest (nearest) associated point of simulation time of all |
91 | * Event notes contained in the evnet-list. Note that the event-note is not |
92 | * removed from the event-list. |
93 | * |
94 | * @return EventNote : the event-note to be processed next in the order of |
95 | * time. Returns <code>null</code> if the event-list is empty. |
96 | */ |
97 | EventNote firstNote() { |
98 | |
99 | if (isEmpty()) |
100 | return null; // nothing there, nothing returned |
101 | else |
102 | return (EventNote) eTreeList.get(0); // return but not remove |
103 | |
104 | } |
105 | |
106 | |
107 | /** |
108 | * Inserts the new event-note preserving the temporal order of the event-notes |
109 | * contained in the event-list. It uses binary search to determine the |
110 | * position where to insert the new event-note to increase performance. |
111 | * |
112 | * @param newNote |
113 | * EventNote : the new note to be inserted in the event-list |
114 | * keeping the temporal order |
115 | */ |
116 | void insert(EventNote newNote) { |
117 | |
118 | // code for adding EventNote to all possible entities |
119 | |
120 | Entity who1 = newNote.getEntity1(); |
121 | if (who1 != null) |
122 | { |
123 | who1.addEventNote(newNote); |
124 | } |
125 | |
126 | Entity who2 = newNote.getEntity2(); |
127 | if (who2 != null) |
128 | { |
129 | who2.addEventNote(newNote); |
130 | } |
131 | |
132 | Entity who3 = newNote.getEntity3(); |
133 | if (who3 != null) |
134 | { |
135 | who3.addEventNote(newNote); |
136 | } |
137 | |
138 | EventAbstract Event = newNote.getEvent(); |
139 | if (Event != null) { |
140 | Event.addEventNote(newNote); |
141 | } |
142 | |
143 | if (isEmpty()) { // no worry about order if it's first |
144 | eTreeList.add(newNote); // easy if empty ;-) |
145 | return; // no need to continue |
146 | } else { // now here comes the binary sorting |
147 | |
148 | int left = 0; // left border of search partition |
149 | int right = eTreeList.size() - 1; // right border of search |
150 | // partition |
151 | int index = 0; // current position in tree list |
152 | TimeInstant refTime = newNote.getTime(); |
153 | // shortcut for call to newNote |
154 | |
155 | do { |
156 | index = (left + right) / 2; // center on searchable partition |
157 | // check if EventNote at index has smaller or equal time |
158 | if (TimeInstant.isBeforeOrEqual(((EventNote) eTreeList |
159 | .get(index)).getTime(), refTime)) { |
160 | if (index < (eTreeList.size() - 1)) { |
161 | // is there a note to the right |
162 | if (TimeInstant.isAfter(((EventNote) eTreeList |
163 | .get(index + 1)).getTime(), refTime)) { |
164 | // if note to the right is larger |
165 | eTreeList.add(index + 1, newNote); |
166 | // found position |
167 | return; // everything done, no need to continue |
168 | } else { |
169 | left = index + 1; |
170 | // no hit, so set new boundaries and go on |
171 | } |
172 | } // no Event notes right of the index, so all |
173 | else { // notes are smaller, thus append to end |
174 | eTreeList.add(newNote); |
175 | return; // everything done, get out of here fast! |
176 | } |
177 | } else { // EventNote at index has larger time |
178 | if (index > 0) { // is there a note left of the index? |
179 | if (TimeInstant.isBeforeOrEqual(((EventNote) eTreeList |
180 | .get(index - 1)).getTime(), refTime)) { |
181 | // if note to the left is smallerOrEqual |
182 | eTreeList.add(index, newNote); |
183 | // found position |
184 | return; // everything done, no need to continue |
185 | } else { |
186 | right = index - 1; |
187 | // no hit, so set new boundaries and go on |
188 | } |
189 | } // no Event notes left of the index, so all |
190 | else { // notes are larger, thus insert at pos. 0 |
191 | eTreeList.add(0, newNote); |
192 | return; // everything done, get out of here! |
193 | } |
194 | } |
195 | } while ((left <= right)); |
196 | eTreeList.add(newNote); |
197 | } |
198 | } |
199 | |
200 | /** |
201 | * Inserts a new event-note after another EventNote specified. Note that to |
202 | * keep the temporal order of the event-list, the scheduled time will be set |
203 | * to the same time as the referred "afterNote". Note also, that afterNote |
204 | * must be contained in the event-list. If the referred "where" is not |
205 | * contained in the event-list, there is no chance to determine the time |
206 | * that the new note is intended to be scheduled at. Thus the new event-note |
207 | * will not be inserted and a <code>EventNotScheduledException</code> will |
208 | * be thrown, stopping the simulation. |
209 | * |
210 | * @param where |
211 | * EventNote : The event-note containing the event after which the |
212 | * new note is supposed to be inserted into the event-list. |
213 | * @param newNote |
214 | * EventNote : The new event-note to be inserted after the |
215 | * specified EventNote in the event-list. |
216 | * @throws SimAbortedException |
217 | * : if referred EventNote is not contained in the event-list |
218 | */ |
219 | void insertAfter(EventNote where, EventNote newNote) { |
220 | |
221 | // code for adding EventNote to all possible entities |
222 | |
223 | Entity who1 = newNote.getEntity1(); |
224 | if (who1 != null) |
225 | { |
226 | who1.addEventNote(newNote); |
227 | } |
228 | |
229 | Entity who2 = newNote.getEntity2(); |
230 | if (who2 != null) |
231 | { |
232 | who2.addEventNote(newNote); |
233 | } |
234 | |
235 | Entity who3 = newNote.getEntity3(); |
236 | if (who3 != null) |
237 | { |
238 | who3.addEventNote(newNote); |
239 | } |
240 | |
241 | EventAbstract Event = newNote.getEvent(); |
242 | if (Event != null) { |
243 | Event.addEventNote(newNote); |
244 | } |
245 | |
246 | int i = eTreeList.indexOf(where); |
247 | |
248 | if (i < 0) { // negative index means, that where is not contained |
249 | Model mBuffer = null; // buffer current model |
250 | if (newNote.getEntity1() != null) { |
251 | mBuffer = newNote.getEntity1().getModel(); |
252 | } |
253 | if (newNote.getEvent() != null) { |
254 | mBuffer = newNote.getEvent().getModel(); |
255 | } |
256 | throw new SimAbortedException( |
257 | new ErrorMessage( |
258 | mBuffer, |
259 | "Can not insert new event-note after given EventNote! " |
260 | + "Simulation aborted", |
261 | "Internal DESMO-J class : EventTreeList Method : " |
262 | + "insertAfter(EventNote where, EventNote newNote)", |
263 | "The event-note to insert the new note after is not contained " |
264 | + "in the event tree list.", |
265 | "This is a fatal error. Contact DESMOJ support", |
266 | newNote.getTime())); |
267 | } else { // if where is contained, put newNote at next position |
268 | newNote.setTime(where.getTime()); |
269 | // synchronize times to keep order |
270 | eTreeList.add(i + 1, newNote); |
271 | // everything fine, exit... |
272 | } |
273 | } |
274 | |
275 | /** |
276 | * Inserts the given EventNote at the first position in the event-list. The |
277 | * Event encapsulated in that EventNote will probably be the next event to |
278 | * be processed by the scheduler (unless some other calls to this method are |
279 | * made before). Note that the time of the new event-note is set to the |
280 | * actual simulation time. |
281 | * |
282 | * @param newNote |
283 | * EventNote : The event-note to be inserted at the first position |
284 | * in the event-list. |
285 | */ |
286 | void insertAsFirst(EventNote newNote) { |
287 | |
288 | eTreeList.add(0, newNote); |
289 | |
290 | // code for adding EventNote to all possible entities |
291 | |
292 | Entity who1 = newNote.getEntity1(); |
293 | if (who1 != null) |
294 | { |
295 | who1.addEventNote(newNote); |
296 | } |
297 | |
298 | Entity who2 = newNote.getEntity2(); |
299 | if (who2 != null) |
300 | { |
301 | who2.addEventNote(newNote); |
302 | } |
303 | |
304 | Entity who3 = newNote.getEntity3(); |
305 | if (who3 != null) |
306 | { |
307 | who3.addEventNote(newNote); |
308 | } |
309 | |
310 | EventAbstract Event = newNote.getEvent(); |
311 | if (Event != null) { |
312 | Event.addEventNote(newNote); |
313 | } |
314 | |
315 | } |
316 | |
317 | /** |
318 | * Inserts an event-note at the last position in the event-list. Also adapts |
319 | * the new event-note's scheduled point of time to the same time as the last |
320 | * elment in the event-list. Time is not changed, if the event-list is |
321 | * empty. |
322 | * |
323 | * @param newNote |
324 | * EventNote : The event-note to be inserted at the last position |
325 | * in the event-list. |
326 | */ |
327 | void insertAsLast(EventNote newNote) { |
328 | |
329 | if (!isEmpty()) // if notes in EventList, set time to time of last note |
330 | newNote.setTime(((EventNote) eTreeList.get(eTreeList.size() - 1)) |
331 | .getTime()); |
332 | |
333 | eTreeList.add(newNote); // always append note to end of |
334 | // EventList |
335 | |
336 | // code for adding EventNote to all possible entities |
337 | |
338 | Entity who1 = newNote.getEntity1(); |
339 | if (who1 != null) |
340 | { |
341 | who1.addEventNote(newNote); |
342 | } |
343 | |
344 | Entity who2 = newNote.getEntity2(); |
345 | if (who2 != null) |
346 | { |
347 | who2.addEventNote(newNote); |
348 | } |
349 | |
350 | Entity who3 = newNote.getEntity3(); |
351 | if (who3 != null) |
352 | { |
353 | who3.addEventNote(newNote); |
354 | } |
355 | |
356 | EventAbstract Event = newNote.getEvent(); |
357 | if (Event != null) { |
358 | Event.addEventNote(newNote); |
359 | } |
360 | |
361 | } |
362 | |
363 | /** |
364 | * Inserts a new event-note before another EventNote specified. Note that |
365 | * this could disturb the temporal order of the event-list. So this method |
366 | * should only be used carefully. Note also, that EventNote 'where' must be |
367 | * contained in the event-list or otherwise an exception will be thrown. |
368 | * |
369 | * @param where |
370 | * EventNote : The event-note containing the event before which |
371 | * the newNote is supposed to be inserted into the event-list. |
372 | * @param newNote |
373 | * EventNote : The new event-note to be inserted before the |
374 | * specified EventNote in the event-list |
375 | * @throws SimAbortedException |
376 | * : if referred EventNote is not contained in the event-list |
377 | */ |
378 | void insertBefore(EventNote where, EventNote newNote) { |
379 | |
380 | // code for adding EventNote to all possible entities |
381 | |
382 | Entity who1 = newNote.getEntity1(); |
383 | if (who1 != null) |
384 | { |
385 | who1.addEventNote(newNote); |
386 | } |
387 | |
388 | Entity who2 = newNote.getEntity2(); |
389 | if (who2 != null) |
390 | { |
391 | who2.addEventNote(newNote); |
392 | } |
393 | |
394 | Entity who3 = newNote.getEntity3(); |
395 | if (who3 != null) |
396 | { |
397 | who3.addEventNote(newNote); |
398 | } |
399 | |
400 | EventAbstract Event = newNote.getEvent(); |
401 | if (Event != null) { |
402 | Event.addEventNote(newNote); |
403 | } |
404 | |
405 | int i = eTreeList.indexOf(where); |
406 | |
407 | if (i < 0) { |
408 | Model mBuffer = null; // buffer current model |
409 | if (newNote.getEntity1() != null) { |
410 | mBuffer = newNote.getEntity1().getModel(); |
411 | } |
412 | if (newNote.getEvent() != null) { |
413 | mBuffer = newNote.getEvent().getModel(); |
414 | } |
415 | throw new SimAbortedException( |
416 | new ErrorMessage( |
417 | mBuffer, |
418 | "Can not insert new event-note before given EventNote! " |
419 | + "Simulation aborted", |
420 | "Internal DESMO-J class : EventTreeList Method : " |
421 | + "insertBefore(EventNote where, EventNote newNote)", |
422 | "The event-note to insert the new note before is not contained " |
423 | + "in the event tree list.", |
424 | "This is a fatal error. Contact DESMOJ support", |
425 | newNote.getTime())); |
426 | } else { |
427 | newNote.setTime(where.getTime()); |
428 | // synchronize times to keep order |
429 | eTreeList.add(i, newNote); |
430 | // insert newN. & push afterN. one up |
431 | |
432 | // code for adding EventNote to Entity |
433 | //variable was not used |
434 | //Entity who = newNote.getEntity1(); |
435 | //variable was not used |
436 | //Object o = who; |
437 | } |
438 | |
439 | } |
440 | |
441 | /** |
442 | * Tests if there are any scheduled events contained in the event-list. If |
443 | * the event-list happens to be empty during the run of a simulation, this |
444 | * is a criterium to stop the simulation, since no further action is |
445 | * scheduled. |
446 | * |
447 | * @return boolean : True if there are no Event notes contained in the |
448 | * event-list, false otherwise. |
449 | */ |
450 | boolean isEmpty() { |
451 | |
452 | return eTreeList.isEmpty(); |
453 | // simply pass the call through to the tree list. |
454 | |
455 | } |
456 | |
457 | /** |
458 | * Returns the last EventNote in the event-list. If the event-list is empty, |
459 | * <code>null</code> will be returned. |
460 | * |
461 | * @return EventNote : the last EventNote in the event-list, null if the |
462 | * event-list is empty |
463 | */ |
464 | EventNote lastNote() { |
465 | |
466 | if (isEmpty()) |
467 | return null; // Nothing here, nothign to return... |
468 | else |
469 | return (EventNote) eTreeList.get(eTreeList.size() - 1); |
470 | // return last |
471 | |
472 | } |
473 | |
474 | /** |
475 | * Returns the next event-note in the event-list relative to the given |
476 | * EventNote. If the given EventNote is not contained in the event-list or |
477 | * happens to be the last EventNote in the event-list, null will be |
478 | * returned. |
479 | * |
480 | * @return EventNote : The event-note following the given EventNote or |
481 | * <ocde>null</code> if the given EventNote was last or not found |
482 | * @param origin |
483 | * EventNote : The event-note whose successor is wanted |
484 | */ |
485 | EventNote nextNote(EventNote origin) { |
486 | |
487 | if (eTreeList.contains(origin)) { |
488 | if (origin == eTreeList.get(eTreeList.size() - 1)) { |
489 | return null; |
490 | } else |
491 | return (EventNote) eTreeList.get(eTreeList.indexOf(origin) + 1); |
492 | } |
493 | return null; |
494 | |
495 | } |
496 | |
497 | /** |
498 | * Returns the previous EventNote in the event-list relative to the given |
499 | * EventNote. If the given EventNote is not contained in the event-list or |
500 | * happens to be the first event-note in the event-list, null will be |
501 | * returned. |
502 | * |
503 | * @return EventNote : The event-note following the given EventNote or |
504 | * <ocde>null</code> if the given EventNote was first or not found |
505 | * @param origin |
506 | * EventNote : The event-note whose predecessor is wanted |
507 | */ |
508 | EventNote prevNote(EventNote origin) { |
509 | |
510 | if (eTreeList.contains(origin)) { |
511 | if (origin == eTreeList.get(0)) { |
512 | return null; |
513 | } |
514 | return (EventNote) eTreeList.get(eTreeList.indexOf(origin) - 1); |
515 | } |
516 | return null; |
517 | |
518 | } |
519 | |
520 | /** |
521 | * Removes the given EventNote from the event-list. |
522 | * |
523 | * Warning: Make sure to tell the entity of the event-note to delete |
524 | * the Note from its List as well. |
525 | * |
526 | * Warning: Make sure to tell the entity of the event-note to delete |
527 | * the Note from its List as well. |
528 | * |
529 | * @param note |
530 | * EventNote : The event-note to be removed from the event-list |
531 | */ |
532 | void remove(EventNote note) { |
533 | |
534 | if (!eTreeList.contains(note)) |
535 | return; // do nothing if it doesn't exist |
536 | else |
537 | { |
538 | eTreeList.remove(note); // go ahead and crunch it! |
539 | |
540 | if (note.getEntity1() != null) // if an entity exists (no external event) |
541 | { |
542 | note.getEntity1().removeEventNote(note); // removes list entry in Entity! |
543 | } |
544 | |
545 | if (note.getEntity2() != null) // if an entity exists (no external event) |
546 | { |
547 | note.getEntity2().removeEventNote(note); // removes list entry in Entity! |
548 | } |
549 | |
550 | if (note.getEntity3() != null) // if an entity exists (no external event) |
551 | { |
552 | note.getEntity3().removeEventNote(note); // removes list entry in Entity! |
553 | } |
554 | |
555 | if (note.getEvent() != null) // if an event exists |
556 | { |
557 | note.getEvent().removeEventNote(note); // remove EventNote |
558 | } |
559 | } |
560 | |
561 | } |
562 | |
563 | /** |
564 | * Removes the first event-note from the event-list. Does nothing if the |
565 | * event-list is already empty. |
566 | */ |
567 | void removeFirst() { |
568 | |
569 | if (!eTreeList.isEmpty()) |
570 | { |
571 | EventNote note = firstNote(); |
572 | |
573 | eTreeList.remove(0); // no comment ;-) |
574 | |
575 | if (note.getEntity1() != null) // if an entity exists (no external event) |
576 | { |
577 | note.getEntity1().removeEventNote(note); // removes list entry in Entity! |
578 | } |
579 | |
580 | if (note.getEntity2() != null) // if an entity exists (no external event) |
581 | { |
582 | note.getEntity2().removeEventNote(note); // removes list entry in Entity! |
583 | } |
584 | |
585 | if (note.getEntity3() != null) // if an entity exists (no external event) |
586 | { |
587 | note.getEntity3().removeEventNote(note); // removes list entry in Entity! |
588 | } |
589 | |
590 | if (note.getEvent() != null) // if an event exists |
591 | { |
592 | note.getEvent().removeEventNote(note); // remove EventNote |
593 | } |
594 | } |
595 | } |
596 | |
597 | /** |
598 | * Returns a string representing the entries of this tree list in a row. The |
599 | * resulting string includes all Event notes in ascending order as they are |
600 | * placed inside the event tree list. |
601 | */ |
602 | public String toString() { |
603 | |
604 | StringBuffer textBuffer = new StringBuffer(); |
605 | // faster than String and '+' |
606 | Iterator<?> notes = eTreeList.iterator(); // get all elements |
607 | |
608 | while (notes.hasNext()) { // loop through all elements |
609 | textBuffer.append("["); |
610 | textBuffer.append((EventNote) notes.next()); |
611 | textBuffer.append("]"); // compose Note |
612 | } |
613 | |
614 | return textBuffer.toString(); |
615 | // return String representation of StringBuffer |
616 | |
617 | } |
618 | |
619 | } |