View Javadoc

    1   /*
    2    * @(#) RedBlackTree.java Feb 16, 2004
    3    *
    4    * Copyright (c) 2003 Delft University of Technology Jaffalaan 5, 2628 BX Delft,
    5    * the Netherlands All rights reserved.
    6    *
    7    * This software is proprietary information of Delft University of Technology
    8    * The code is published under the General Public License
    9    */
    10
    11  package nl.tudelft.simulation.dsol.eventlists;
    12
    13  import java.io.Serializable;
    14  import java.util.ArrayList;
    15  import java.util.Collection;
    16  import java.util.ConcurrentModificationException;
    17  import java.util.Iterator;
    18  import java.util.List;
    19  import java.util.NoSuchElementException;
    20  import nl.tudelft.simulation.dsol.formalisms.devs.SimEventInterface;
    21
    22  /***
    23   * A RedBlackTree implementation of the eventlistInterface. This implementation
    24   * is based on Java's TreeSet.
    25   * <p>
    26   * (c) copyright 2003 <a href="http://www.simulation.tudelft.nl">Delft
    27   * University of Technology </a>, the Netherlands. <br>
    28   * See for project information <a href="http://www.simulation.tudelft.nl">
    29   * www.simulation.tudelft.nl </a> <br>
    30   * License of use: <a href="http://www.gnu.org/copyleft/gpl.html">General Public
    31   * License (GPL) </a>, no warranty <br>
    32   *
    33   * @author <a href="http://www.simulation.tudelft.nl/people/jacobs.html">Peter
    34   *         Jacobs </a>
    35   * @version 1.4 2004-03-28
    36   * @since 1.0
    37   */
    38  public class RedBlackTree implements EventListInterface
    39  {
    40  	/*** the counter of events added to this list */
    41  	private static long counter = 0L;
    42
    43  	/*** RED */
    44  	protected static final boolean RED = false;
    45
    46  	/*** BLACK */
    47  	protected static final boolean BLACK = true;
    48
    49  	/*** the root of the tree */
    50  	protected transient Entry root = null;
    51
    52  	/*** The number of entries in the tree */
    53  	protected transient int size = 0;
    54
    55  	/*** The number of structural modifications to the tree. */
    56  	protected transient int modCount = 0;
    57
    58  	/***
    59  	 * constructs a new RedBlackTree
    60  	 */
    61  	public RedBlackTree()
    62  	{
    63  		super();
    64  	}
    65
    66  	/***
    67  	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    68  	 *      #add(nl.tudelft.simulation.dsol.formalisms.devs.SimEventInterface)
    69  	 */
    70  	public synchronized boolean add(final SimEventInterface event)
    71  	{
    72  		event.setID(RedBlackTree.counter++);
    73  		Entry entry = this.root;
    74  		if (entry == null)
    75  		{
    76  			this.incrementSize();
    77  			this.root = new Entry(event, null);
    78  			return true;
    79  		}
    80  		while (true)
    81  		{
    82  			int cmp = event.compareTo(entry.simEvent);
    83  			if (cmp == 0)
    84  			{
    85  				entry.simEvent = event;
    86  				return false;
    87  			} else if (cmp < 0)
    88  			{
    89  				if (entry.left != null)
    90  				{
    91  					entry = entry.left;
    92  				} else
    93  				{
    94  					this.incrementSize();
    95  					entry.left = new Entry(event, entry);
    96  					fixAfterInsertion(entry.left);
    97  					return true;
    98  				}
    99  			} else
    100 			{ // cmp > 0
    101 				if (entry.right != null)
    102 				{
    103 					entry = entry.right;
    104 				} else
    105 				{
    106 					incrementSize();
    107 					entry.right = new Entry(event, entry);
    108 					fixAfterInsertion(entry.right);
    109 					return true;
    110 				}
    111 			}
    112 		}
    113 	}
    114
    115 	/***
    116 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    117 	 *      #addAll(Collection)
    118 	 */
    119 	public synchronized boolean addAll(final Collection collection)
    120 	{
    121 		for (Iterator iterator = collection.iterator(); iterator.hasNext();)
    122 		{
    123 			if (!this.add((SimEventInterface) iterator.next()))
    124 			{
    125 				return false;
    126 			}
    127 		}
    128 		return true;
    129 	}
    130
    131 	/***
    132 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#clear()
    133 	 */
    134 	public synchronized void clear()
    135 	{
    136 		this.modCount++;
    137 		this.size = 0;
    138 		this.root = null;
    139 	}
    140
    141 	/***
    142 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    143 	 *      #contains(nl.tudelft.simulation.dsol.formalisms.devs.SimEventInterface)
    144 	 */
    145 	public synchronized boolean contains(final SimEventInterface event)
    146 	{
    147 		if (this.root == null)
    148 		{
    149 			return false;
    150 		}
    151 		if (event == null)
    152 		{
    153 			return this.eventSearchNull(this.root);
    154 		}
    155 		return this.eventSearchNonNull(this.root, event);
    156 	}
    157
    158 	/***
    159 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    160 	 *      #containsAll(Collection)
    161 	 */
    162 	public synchronized boolean containsAll(final Collection collection)
    163 	{
    164 		for (Iterator iterator = collection.iterator(); iterator.hasNext();)
    165 		{
    166 			if (!this.contains((SimEventInterface) iterator.next()))
    167 			{
    168 				return false;
    169 			}
    170 		}
    171 		return true;
    172 	}
    173
    174 	/***
    175 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface #first()
    176 	 */
    177 	public synchronized SimEventInterface first()
    178 	{
    179 		Entry first = this.firstEntry();
    180 		if (first == null)
    181 		{
    182 			return null;
    183 		}
    184 		return first.simEvent;
    185 	}
    186
    187 	/***
    188 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#isEmpty()
    189 	 */
    190 	public synchronized boolean isEmpty()
    191 	{
    192 		if (this.size == 0)
    193 		{
    194 			return true;
    195 		}
    196 		return false;
    197 	}
    198
    199 	/***
    200 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface #iterator()
    201 	 */
    202 	public synchronized Iterator iterator()
    203 	{
    204 		return new EventListIterator();
    205 	}
    206
    207 	/***
    208 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#last()
    209 	 */
    210 	public synchronized SimEventInterface last()
    211 	{
    212 		Entry last = this.lastEntry();
    213 		if (last == null)
    214 		{
    215 			return null;
    216 		}
    217 		return last.simEvent;
    218 	}
    219
    220 	/***
    221 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    222 	 *      #remove(nl.tudelft.simulation.dsol.formalisms.devs.SimEventInterface)
    223 	 */
    224 	public synchronized boolean remove(final SimEventInterface event)
    225 	{
    226 		Entry entry = getEntry(event);
    227 		if (entry == null)
    228 		{
    229 			return false;
    230 		}
    231 		this.deleteEntry(entry);
    232 		return true;
    233 	}
    234
    235 	/***
    236 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#removeAll(Collection)
    237 	 */
    238 	public synchronized boolean removeAll(final Collection collection)
    239 	{
    240 		for (Iterator iterator = collection.iterator(); iterator.hasNext();)
    241 		{
    242 			if (!this.remove((SimEventInterface) iterator.next()))
    243 			{
    244 				return false;
    245 			}
    246 		}
    247 		return true;
    248 	}
    249
    250 	/***
    251 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface
    252 	 *      #removeFirst()
    253 	 */
    254 	public synchronized SimEventInterface removeFirst()
    255 	{
    256 		Entry entry = this.firstEntry();
    257 		this.deleteEntry(entry);
    258 		return entry.simEvent;
    259 	}
    260
    261 	/***
    262 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#removeLast()
    263 	 */
    264 	public synchronized SimEventInterface removeLast()
    265 	{
    266 		Entry entry = this.lastEntry();
    267 		this.deleteEntry(entry);
    268 		return entry.simEvent;
    269 	}
    270
    271 	/***
    272 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface#size()
    273 	 */
    274 	public synchronized int size()
    275 	{
    276 		return this.size;
    277 	}
    278
    279 	/***
    280 	 * @see nl.tudelft.simulation.dsol.eventlists.EventListInterface #toArray()
    281 	 */
    282 	public synchronized SimEventInterface[] toArray()
    283 	{
    284 		List result = new ArrayList();
    285 		for (Iterator i = this.iterator(); i.hasNext();)
    286 		{
    287 			result.add(i.next());
    288 		}
    289 		return (SimEventInterface[]) result
    290 				.toArray(new SimEventInterface[result.size()]);
    291 	}
    292
    293 	/*** ********************** PRIVATE METHODS ******************************** */
    294 	/***
    295 	 * decrements the size
    296 	 */
    297 	private void decrementSize()
    298 	{
    299 		this.modCount++;
    300 		this.size--;
    301 	}
    302
    303 	/***
    304 	 * incrementSize
    305 	 */
    306 	private void incrementSize()
    307 	{
    308 		this.modCount++;
    309 		this.size++;
    310 	}
    311
    312 	/***
    313 	 * returns the first entry from the RedBlackTree
    314 	 *
    315 	 * @return the first Entry
    316 	 */
    317 	protected Entry firstEntry()
    318 	{
    319 		Entry entry = this.root;
    320 		if (entry != null)
    321 		{
    322 			while (entry.left != null)
    323 			{
    324 				entry = entry.left;
    325 			}
    326 		}
    327 		return entry;
    328 	}
    329
    330 	/***
    331 	 * returns the last entry from the RedBlackTree
    332 	 *
    333 	 * @return the last Entry
    334 	 */
    335 	private Entry lastEntry()
    336 	{
    337 		Entry entry = this.root;
    338 		if (entry != null)
    339 		{
    340 			while (entry.right != null)
    341 			{
    342 				entry = entry.right;
    343 			}
    344 		}
    345 		return entry;
    346 	}
    347
    348 	/***
    349 	 * searches for nonnull events
    350 	 *
    351 	 * @param entry the entry to search
    352 	 * @param event the event
    353 	 * @return null?
    354 	 */
    355 	private boolean eventSearchNonNull(final Entry entry,
    356 			final SimEventInterface event)
    357 	{
    358 		if (event.equals(entry.simEvent))
    359 		{
    360 			return true;
    361 		}
    362 		// Check left and right subtrees for event
    363 		return (entry.left != null && eventSearchNonNull(entry.left, event))
    364 				|| (entry.right != null && eventSearchNonNull(entry.right,
    365 						event));
    366 	}
    367
    368 	/***
    369 	 * searches for null events
    370 	 *
    371 	 * @param entry the entry to search
    372 	 * @return null?
    373 	 */
    374 	private boolean eventSearchNull(final Entry entry)
    375 	{
    376 		if (entry.simEvent == null)
    377 		{
    378 			return true;
    379 		}
    380 		// Check left and right subtrees for event
    381 		return (entry.left != null && eventSearchNull(entry.left))
    382 				|| (entry.right != null && eventSearchNull(entry.right));
    383 	}
    384
    385 	/***
    386 	 * returns the color of an entry
    387 	 *
    388 	 * @param entry the entry
    389 	 * @return the color
    390 	 */
    391 	private static boolean colorOf(final Entry entry)
    392 	{
    393 		if (entry == null)
    394 		{
    395 			return BLACK;
    396 		}
    397 		return entry.color;
    398 	}
    399
    400 	/***
    401 	 * returns the parent of p
    402 	 *
    403 	 * @param entry the entry
    404 	 * @return Entry
    405 	 */
    406 	private static Entry parentOf(final Entry entry)
    407 	{
    408 		if (entry == null)
    409 		{
    410 			return null;
    411 		}
    412 		return entry.parent;
    413 	}
    414
    415 	/***
    416 	 * sets the color of p
    417 	 *
    418 	 * @param entry the entry
    419 	 * @param color the color
    420 	 */
    421 	private static void setColor(final Entry entry, final boolean color)
    422 	{
    423 		if (entry != null)
    424 		{
    425 			entry.color = color;
    426 		}
    427 	}
    428
    429 	/***
    430 	 * returns the left child of entry
    431 	 *
    432 	 * @param entry the entry
    433 	 * @return Entry
    434 	 */
    435 	private static Entry leftOf(final Entry entry)
    436 	{
    437 		if (entry == null)
    438 		{
    439 			return null;
    440 		}
    441 		return entry.left;
    442 	}
    443
    444 	/***
    445 	 * returns the right entry of entry
    446 	 *
    447 	 * @param entry the entry
    448 	 * @return Entry
    449 	 */
    450 	private static Entry rightOf(final Entry entry)
    451 	{
    452 		if (entry == null)
    453 		{
    454 			return null;
    455 		}
    456 		return entry.right;
    457 	}
    458
    459 	/***
    460 	 * rotates left
    461 	 *
    462 	 * @param entry the entry to rotate
    463 	 */
    464 	private void rotateLeft(final Entry entry)
    465 	{
    466 		Entry right = entry.right;
    467 		entry.right = right.left;
    468 		if (right.left != null)
    469 		{
    470 			right.left.parent = entry;
    471 		}
    472 		right.parent = entry.parent;
    473 		if (entry.parent == null)
    474 		{
    475 			this.root = right;
    476 		} else if (entry.parent.left == entry)
    477 		{
    478 			entry.parent.left = right;
    479 		} else
    480 		{
    481 			entry.parent.right = right;
    482 		}
    483 		right.left = entry;
    484 		entry.parent = right;
    485 	}
    486
    487 	/***
    488 	 * rotates to the right
    489 	 *
    490 	 * @param entry the entry to rotate
    491 	 */
    492 	private void rotateRight(final Entry entry)
    493 	{
    494 		Entry left = entry.left;
    495 		entry.left = left.right;
    496 		if (left.right != null)
    497 		{
    498 			left.right.parent = entry;
    499 		}
    500 		left.parent = entry.parent;
    501 		if (entry.parent == null)
    502 		{
    503 			this.root = left;
    504 		} else if (entry.parent.right == entry)
    505 		{
    506 			entry.parent.right = left;
    507 		} else
    508 		{
    509 			entry.parent.left = left;
    510 		}
    511 		left.right = entry;
    512 		entry.parent = left;
    513 	}
    514
    515 	/***
    516 	 * fixes after insertion
    517 	 *
    518 	 * @param entry the entry
    519 	 */
    520 	private void fixAfterInsertion(Entry entry)
    521 	{
    522 		entry.color = RED;
    523 		while (entry != null && entry != this.root && entry.parent.color == RED)
    524 		{
    525 			if (parentOf(entry) == leftOf(parentOf(parentOf(entry))))
    526 			{
    527 				Entry y = rightOf(parentOf(parentOf(entry)));
    528 				if (colorOf(y) == RED)
    529 				{
    530 					setColor(parentOf(entry), BLACK);
    531 					setColor(y, BLACK);
    532 					setColor(parentOf(parentOf(entry)), RED);
    533 					entry = parentOf(parentOf(entry));
    534 				} else
    535 				{
    536 					if (entry == rightOf(parentOf(entry)))
    537 					{
    538 						entry = parentOf(entry);
    539 						rotateLeft(entry);
    540 					}
    541 					setColor(parentOf(entry), BLACK);
    542 					setColor(parentOf(parentOf(entry)), RED);
    543 					if (parentOf(parentOf(entry)) != null)
    544 					{
    545 						rotateRight(parentOf(parentOf(entry)));
    546 					}
    547 				}
    548 			} else
    549 			{
    550 				Entry y = leftOf(parentOf(parentOf(entry)));
    551 				if (colorOf(y) == RED)
    552 				{
    553 					setColor(parentOf(entry), BLACK);
    554 					setColor(y, BLACK);
    555 					setColor(parentOf(parentOf(entry)), RED);
    556 					entry = parentOf(parentOf(entry));
    557 				} else
    558 				{
    559 					if (entry == leftOf(parentOf(entry)))
    560 					{
    561 						entry = parentOf(entry);
    562 						rotateRight(entry);
    563 					}
    564 					setColor(parentOf(entry), BLACK);
    565 					setColor(parentOf(parentOf(entry)), RED);
    566 					if (parentOf(parentOf(entry)) != null)
    567 					{
    568 						rotateLeft(parentOf(parentOf(entry)));
    569 					}
    570 				}
    571 			}
    572 		}
    573 		this.root.color = BLACK;
    574 	}
    575
    576 	/***
    577 	 * deletes entry , and then rebalance the tree.
    578 	 *
    579 	 * @param entry entry
    580 	 */
    581 	protected void deleteEntry(Entry entry)
    582 	{
    583 		this.decrementSize();
    584 		// If strictly internal, copy successor's element to entry and then
    585 		// make entry
    586 		// point to successor.
    587 		if (entry.left != null && entry.right != null)
    588 		{
    589 			Entry s = successor(entry);
    590 			entry.simEvent = s.simEvent;
    591 			entry = s;
    592 		} // entry has 2 children
    593 		// Start fixup at replacement node, if it exists.
    594 		Entry replacement = entry.left;
    595 		if (replacement == null)
    596 		{
    597 			replacement = entry.right;
    598 		}
    599 		if (replacement != null)
    600 		{
    601 			// Link replacement to parent
    602 			replacement.parent = entry.parent;
    603 			if (entry.parent == null)
    604 			{
    605 				this.root = replacement;
    606 			} else if (entry == entry.parent.left)
    607 			{
    608 				entry.parent.left = replacement;
    609 			} else
    610 			{
    611 				entry.parent.right = replacement;
    612 			}
    613 			// Null out links so they are OK to use by fixAfterDeletion.
    614 			entry.left = null;
    615 			entry.right = null;
    616 			entry.parent = null;
    617 			// Fix replacement
    618 			if (entry.color == BLACK)
    619 			{
    620 				fixAfterDeletion(replacement);
    621 			}
    622 		} else if (entry.parent == null)
    623 		{ // return if we are the only node.
    624 			this.root = null;
    625 		} else
    626 		{ //  No children. Use self as phantom replacement and unlink.
    627 			if (entry.color == BLACK)
    628 			{
    629 				fixAfterDeletion(entry);
    630 			}
    631 			if (entry.parent != null)
    632 			{
    633 				if (entry == entry.parent.left)
    634 				{
    635 					entry.parent.left = null;
    636 				} else if (entry == entry.parent.right)
    637 				{
    638 					entry.parent.right = null;
    639 				}
    640 				entry.parent = null;
    641 			}
    642 		}
    643 	}
    644
    645 	/***
    646 	 * fixes after deletion
    647 	 *
    648 	 * @param entry the entry
    649 	 */
    650 	private void fixAfterDeletion(Entry entry)
    651 	{
    652 		while (entry != this.root && colorOf(entry) == BLACK)
    653 		{
    654 			if (entry == leftOf(parentOf(entry)))
    655 			{
    656 				Entry sib = rightOf(parentOf(entry));
    657 				if (colorOf(sib) == RED)
    658 				{
    659 					setColor(sib, BLACK);
    660 					setColor(parentOf(entry), RED);
    661 					rotateLeft(parentOf(entry));
    662 					sib = rightOf(parentOf(entry));
    663 				}
    664 				if (colorOf(leftOf(sib)) == BLACK
    665 						&& colorOf(rightOf(sib)) == BLACK)
    666 				{
    667 					setColor(sib, RED);
    668 					entry = parentOf(entry);
    669 				} else
    670 				{
    671 					if (colorOf(rightOf(sib)) == BLACK)
    672 					{
    673 						setColor(leftOf(sib), BLACK);
    674 						setColor(sib, RED);
    675 						rotateRight(sib);
    676 						sib = rightOf(parentOf(entry));
    677 					}
    678 					setColor(sib, colorOf(parentOf(entry)));
    679 					setColor(parentOf(entry), BLACK);
    680 					setColor(rightOf(sib), BLACK);
    681 					rotateLeft(parentOf(entry));
    682 					entry = this.root;
    683 				}
    684 			} else
    685 			{ // symmetric
    686 				Entry sib = leftOf(parentOf(entry));
    687 				if (colorOf(sib) == RED)
    688 				{
    689 					setColor(sib, BLACK);
    690 					setColor(parentOf(entry), RED);
    691 					rotateRight(parentOf(entry));
    692 					sib = leftOf(parentOf(entry));
    693 				}
    694 				if (colorOf(rightOf(sib)) == BLACK
    695 						&& colorOf(leftOf(sib)) == BLACK)
    696 				{
    697 					setColor(sib, RED);
    698 					entry = parentOf(entry);
    699 				} else
    700 				{
    701 					if (colorOf(leftOf(sib)) == BLACK)
    702 					{
    703 						setColor(rightOf(sib), BLACK);
    704 						setColor(sib, RED);
    705 						rotateLeft(sib);
    706 						sib = leftOf(parentOf(entry));
    707 					}
    708 					setColor(sib, colorOf(parentOf(entry)));
    709 					setColor(parentOf(entry), BLACK);
    710 					setColor(leftOf(sib), BLACK);
    711 					rotateRight(parentOf(entry));
    712 					entry = this.root;
    713 				}
    714 			}
    715 		}
    716 		setColor(entry, BLACK);
    717 	}
    718
    719 	/***
    720 	 * gets the entry
    721 	 *
    722 	 * @param event the event
    723 	 * @return Entry the entry
    724 	 */
    725 	private Entry getEntry(final SimEventInterface event)
    726 	{
    727 		Entry entry = this.root;
    728 		while (entry != null)
    729 		{
    730 			int cmp = event.compareTo(entry.simEvent);
    731 			if (cmp < 0)
    732 			{
    733 				entry = entry.left;
    734 			} else if (cmp > 0)
    735 			{
    736 				entry = entry.right;
    737 			} else if (cmp == 0)
    738 			{
    739 				return entry;
    740 			}
    741 		}
    742 		return null;
    743 	}
    744
    745 	/***
    746 	 * Returns the successor of the specified Entry, or null if no such.
    747 	 *
    748 	 * @param entry the entry
    749 	 * @return Entry the successor
    750 	 */
    751 	protected Entry successor(final Entry entry)
    752 	{
    753 		if (entry == null)
    754 		{
    755 			return null;
    756 		} else if (entry.right != null)
    757 		{
    758 			Entry right = entry.right;
    759 			while (right.left != null)
    760 			{
    761 				right = right.left;
    762 			}
    763 			return right;
    764 		} else
    765 		{
    766 			Entry right = entry.parent;
    767 			Entry ch = entry;
    768 			while (right != null && ch == right.right)
    769 			{
    770 				ch = right;
    771 				right = right.parent;
    772 			}
    773 			return right;
    774 		}
    775 	}
    776
    777 	/***
    778 	 * A Entry <br>
    779 	 * (c) copyright 2003 <a href="http://www.simulation.tudelft.nl">Delft
    780 	 * University of Technology </a>, the Netherlands. <br>
    781 	 * See for project information <a
    782 	 * href="http://www.simulation.tudelft.nl">www.simulation.tudelft.nl </a>
    783 	 * <br>
    784 	 * License of use: <a href="http://www.gnu.org/copyleft/gpl.html">General
    785 	 * Public License (GPL) </a>, no warranty <br>
    786 	 *
    787 	 * @version 1.0 Feb 24, 2004 <br>
    788 	 * @author <a
    789 	 *         href="http://www.simulation.tudelft.nl/people/jacobs.html">Peter
    790 	 *         Jacobs </a>
    791 	 */
    792 	private static class Entry implements Serializable
    793 	{
    794 		/*** the simEvent stored in the entry */
    795 		protected SimEventInterface simEvent = null;
    796
    797 		/*** the left entry */
    798 		protected Entry left = null;
    799
    800 		/*** the right entry */
    801 		protected Entry right = null;
    802
    803 		/*** the parent */
    804 		protected Entry parent = null;
    805
    806 		/*** the color of the entry */
    807 		protected boolean color = BLACK;
    808
    809 		/***
    810 		 * constructs a new Entry
    811 		 */
    812 		public Entry()
    813 		{
    814 			super();
    815 		}
    816
    817 		/***
    818 		 * constructs a new Entry
    819 		 *
    820 		 * @param simEvent the simEvent of the entry
    821 		 */
    822 		public Entry(final SimEventInterface simEvent)
    823 		{
    824 			this();
    825 			this.simEvent = simEvent;
    826 		}
    827
    828 		/***
    829 		 * constructs a new Entry
    830 		 *
    831 		 * @param simEvent the simEvent of the entry
    832 		 * @param parent the parent
    833 		 */
    834 		public Entry(final SimEventInterface simEvent, final Entry parent)
    835 		{
    836 			this(simEvent);
    837 			this.parent = parent;
    838 		}
    839
    840 		/***
    841 		 * constructs a new Entry
    842 		 *
    843 		 * @param simEvent the simEvent of the entry
    844 		 * @param parent the parent
    845 		 * @param left the left child
    846 		 * @param right the right child
    847 		 */
    848 		public Entry(final SimEventInterface simEvent, final Entry parent,
    849 				final Entry left, final Entry right)
    850 		{
    851 			this(simEvent, parent);
    852 			this.left = left;
    853 			this.right = right;
    854 		}
    855 	}
    856 	/***
    857 	 * A EntryIterator <br>
    858 	 * (c) copyright 2003 <a href="http://www.simulation.tudelft.nl">Delft
    859 	 * University of Technology </a>, the Netherlands. <br>
    860 	 * See for project information <a
    861 	 * href="http://www.simulation.tudelft.nl">www.simulation.tudelft.nl </a>
    862 	 * <br>
    863 	 * License of use: <a href="http://www.gnu.org/copyleft/gpl.html">General
    864 	 * Public License (GPL) </a>, no warranty <br>
    865 	 *
    866 	 * @version 1.0 Feb 16, 2004 <br>
    867 	 * @author <a href="http://www.simulation.tudelft.nl/people/jacobs.html">
    868 	 *         Peter Jacobs </a>
    869 	 */
    870 	private class EntryIterator implements Iterator
    871 	{
    872 		/*** the expectedModCount */
    873 		protected int expectedModCount = RedBlackTree.this.modCount;
    874
    875 		/*** the event of the lastReturned entry */
    876 		protected Entry lastReturned = null;
    877
    878 		/*** the event of the next entry */
    879 		protected Entry next = null;
    880
    881 		/***
    882 		 * constructs a new EntryIterator
    883 		 */
    884 		public EntryIterator()
    885 		{
    886 			this.next = firstEntry();
    887 		}
    888
    889 		/***
    890 		 * constructs a new EntryIterator
    891 		 *
    892 		 * @param first the starting point
    893 		 */
    894 		public EntryIterator(final Entry first)
    895 		{
    896 			this.next = first;
    897 		}
    898
    899 		/***
    900 		 * @see java.util.Iterator#hasNext()
    901 		 */
    902 		public boolean hasNext()
    903 		{
    904 			return this.next != null;
    905 		}
    906
    907 		/***
    908 		 * @return the next Entry
    909 		 */
    910 		public final Entry nextEntry()
    911 		{
    912 			if (this.next == null)
    913 			{
    914 				throw new NoSuchElementException();
    915 			}
    916 			if (RedBlackTree.this.modCount != this.expectedModCount)
    917 			{
    918 				throw new ConcurrentModificationException();
    919 			}
    920 			this.lastReturned = this.next;
    921 			this.next = successor(this.next);
    922 			return this.lastReturned;
    923 		}
    924
    925 		/***
    926 		 * @see java.util.Iterator#next()
    927 		 */
    928 		public Object next()
    929 		{
    930 			return this.nextEntry();
    931 		}
    932
    933 		/***
    934 		 * @see java.util.Iterator#remove()
    935 		 */
    936 		public void remove()
    937 		{
    938 			if (this.lastReturned == null)
    939 			{
    940 				throw new IllegalStateException();
    941 			}
    942 			if (RedBlackTree.this.modCount != this.expectedModCount)
    943 			{
    944 				throw new ConcurrentModificationException();
    945 			}
    946 			if (this.lastReturned.left != null
    947 					&& this.lastReturned.right != null)
    948 			{
    949 				this.next = this.lastReturned;
    950 			}
    951 			deleteEntry(this.lastReturned);
    952 			this.expectedModCount++;
    953 			this.lastReturned = null;
    954 		}
    955 	}
    956 	/***
    957 	 * A EventListIterator <br>
    958 	 * (c) copyright 2003 <a href="http://www.simulation.tudelft.nl">Delft
    959 	 * University of Technology </a>, the Netherlands. <br>
    960 	 * See for project information <a
    961 	 * href="http://www.simulation.tudelft.nl">www.simulation.tudelft.nl </a>
    962 	 * <br>
    963 	 * License of use: <a href="http://www.gnu.org/copyleft/gpl.html">General
    964 	 * Public License (GPL) </a>, no warranty <br>
    965 	 *
    966 	 * @version 1.0 Feb 16, 2004 <br>
    967 	 * @author <a href="http://www.simulation.tudelft.nl/people/jacobs.html">
    968 	 *         Peter Jacobs </a>
    969 	 */
    970 	private class EventListIterator extends EntryIterator
    971 	{
    972 		/***
    973 		 * constructs a new EventListIterator
    974 		 */
    975 		public EventListIterator()
    976 		{
    977 			super();
    978 		}
    979
    980 		/***
    981 		 * @see java.util.Iterator#next()
    982 		 */
    983 		public Object next()
    984 		{
    985 			return ((Entry) super.next()).simEvent;
    986 		}
    987 	}
    988 }