Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection.priorityqueue
Class SlowEventQueue

java.lang.Object
  extended by algs.model.problems.segmentIntersection.priorityqueue.SlowEventQueue

public class SlowEventQueue
extends java.lang.Object

The EventQueue for a horizontal-sweep line algorithm for line segment intersection.

This EventQueue shows what happens when the wrong data structure is used, specifically if a heap-based implementation the priority queue is used, then contains is inefficient. We use the PriorityQueue class provided by the JDK to show how this can happen. To use this SlowEventQueue instead of the default one, you must actually modify the LineSweep class.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
SlowEventQueue()
          Default constructor.
 
Method Summary
 boolean contains(EventPoint ep)
          Determine whether event point already exists within the queue.
 EventPoint event(EventPoint ep)
          Determine whether event point already exists within the queue, and return it if it does.
 void insert(EventPoint ep)
          Insert the Event Point into the queue, taking care to properly maintain the set of segments associated with this EventPoint if it is indeed has upper Segments.
 boolean isEmpty()
          Return whether the event queue is empty.
 EventPoint min()
          Remove and return left-most child [the smallest one].
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SlowEventQueue

public SlowEventQueue()
Default constructor.

Method Detail

isEmpty

public boolean isEmpty()
Return whether the event queue is empty.


insert

public void insert(EventPoint ep)
Insert the Event Point into the queue, taking care to properly maintain the set of segments associated with this EventPoint if it is indeed has upper Segments.

Note that we must merge the upper endpoints associated with ep with the existing event point in the queue, should one exist.

Parameters:
ep - point to be inserted.

min

public EventPoint min()
Remove and return left-most child [the smallest one].


contains

public boolean contains(EventPoint ep)
Determine whether event point already exists within the queue.


event

public EventPoint event(EventPoint ep)
Determine whether event point already exists within the queue, and return it if it does.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.