|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.problems.segmentIntersection.priorityqueue.SlowEventQueue
public class SlowEventQueue
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.
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 |
---|
public SlowEventQueue()
Method Detail |
---|
public boolean isEmpty()
public void insert(EventPoint ep)
Note that we must merge the upper endpoints associated with ep with the existing event point in the queue, should one exist.
ep
- point to be inserted.public EventPoint min()
public boolean contains(EventPoint ep)
public EventPoint event(EventPoint ep)
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |