|
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.linkedlist.LinkedListLineState
public class LinkedListLineState
Class that shows the performance degradation when the line state is stored using a linked list instead of an augmented, balanced binary tree.
Field Summary | |
---|---|
java.util.Comparator<ILineSegment> |
seg_order
The key point about this comparator is that it is only called when both line segments intersect the horizontal line defined by the y-value of the sweep pt. |
Constructor Summary | |
---|---|
LinkedListLineState()
|
Method Summary | |
---|---|
void |
deleteRange(DoubleNode<ILineSegment> left,
DoubleNode<ILineSegment> right)
Delete all line segments from the state in the range (left, right). |
void |
insertSegments(List<ILineSegment> list)
insert the set of line segments into the state at their proper location based upon the sort order. |
DoubleNode<ILineSegment> |
leftNeighbor(EventPoint ep)
|
DoubleNode<ILineSegment> |
pred(DoubleNode<ILineSegment> n)
Return predecessor line segment in the state to given one. |
DoubleNode<ILineSegment> |
rightNeighbor(EventPoint ep)
|
void |
setSweepPoint(IPoint sweep)
|
DoubleNode<ILineSegment> |
successor(DoubleNode<ILineSegment> n)
Return successor line segment in the state to given one. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public java.util.Comparator<ILineSegment> seg_order
One last point. This method is only invoked from within the insert method where o1 already has been placed in the tree. Thus we know that o2 contains the sweep point. Perhaps this optimization is unnecessary...
Once this point is clear, then it is simple how to order the segments.
Constructor Detail |
---|
public LinkedListLineState()
Method Detail |
---|
public void setSweepPoint(IPoint sweep)
sweep
- the new Sweep Point.LineState.setSweepPoint(IPoint)
public DoubleNode<ILineSegment> leftNeighbor(EventPoint ep)
ep
- point for which we want the left neighbor in the line state.LineState.leftNeighbor(EventPoint)
public DoubleNode<ILineSegment> rightNeighbor(EventPoint ep)
ep
- point for which we want the right neighbor in the line state.LineState.rightNeighbor(EventPoint)
public DoubleNode<ILineSegment> successor(DoubleNode<ILineSegment> n)
n
- given line segmentpublic DoubleNode<ILineSegment> pred(DoubleNode<ILineSegment> n)
n
- given line segmentpublic void insertSegments(List<ILineSegment> list)
list
- set of line segments to insert into the state.public void deleteRange(DoubleNode<ILineSegment> left, DoubleNode<ILineSegment> right)
Note that left and right are not removed from the state.
left
- leftmost boundary of the segments to removeright
- rightmost boundary of the segments to remove
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |