Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection.linkedlist
Class LinkedListLineState

java.lang.Object
  extended by algs.model.problems.segmentIntersection.linkedlist.LinkedListLineState

public class LinkedListLineState
extends java.lang.Object

Class that shows the performance degradation when the line state is stored using a linked list instead of an augmented, balanced binary tree.

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

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

seg_order

public 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. If the above is not true, then the two line segments are actually incomparable.

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

LinkedListLineState

public LinkedListLineState()
Method Detail

setSweepPoint

public void setSweepPoint(IPoint sweep)
Parameters:
sweep - the new Sweep Point.
See Also:
LineState.setSweepPoint(IPoint)

leftNeighbor

public DoubleNode<ILineSegment> leftNeighbor(EventPoint ep)
Parameters:
ep - point for which we want the left neighbor in the line state.
See Also:
LineState.leftNeighbor(EventPoint)

rightNeighbor

public DoubleNode<ILineSegment> rightNeighbor(EventPoint ep)
Parameters:
ep - point for which we want the right neighbor in the line state.
See Also:
LineState.rightNeighbor(EventPoint)

successor

public DoubleNode<ILineSegment> successor(DoubleNode<ILineSegment> n)
Return successor line segment in the state to given one.

Parameters:
n - given line segment

pred

public DoubleNode<ILineSegment> pred(DoubleNode<ILineSegment> n)
Return predecessor line segment in the state to given one.

Parameters:
n - given line segment

insertSegments

public void insertSegments(List<ILineSegment> list)
insert the set of line segments into the state at their proper location based upon the sort order.

Parameters:
list - set of line segments to insert into the state.

deleteRange

public void deleteRange(DoubleNode<ILineSegment> left,
                        DoubleNode<ILineSegment> right)
Delete all line segments from the state in the range (left, right).

Note that left and right are not removed from the state.

Parameters:
left - leftmost boundary of the segments to remove
right - rightmost boundary of the segments to remove

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.