Algorithm
Development Kit 1.0

algs.model.interval
Class SegmentTreeNode

java.lang.Object
  extended by algs.model.interval.SegmentTreeNode
All Implemented Interfaces:
IBinaryTreeNode, IInterval
Direct Known Subclasses:
StoredIntervalsNode

public class SegmentTreeNode
extends java.lang.Object
implements IBinaryTreeNode, IInterval

Nodes of the SegmentTree are constructed from this class.

Extended classes can store additional information as well as provide their own update method, as required.

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

Field Summary
static IConstructor constructor
          Default Constructor to use for all SegmentTrees.
 
Constructor Summary
protected SegmentTreeNode(int left, int right)
          Construct node for this range.
 
Method Summary
 void checkInterval(IInterval interval)
          Used to validate IInterval before being incorporated into this data structure.
 void checkInterval(int begin, int end)
          Used to validate [left, right) interval before being incorporated into this data structure.
protected  void dispose(IInterval interval)
          Algorithms over SegmentTrees often store additional information with each node, and may wish to clear information and/or perform computations when a segment is deleted.
 boolean equals(java.lang.Object obj)
          Determine the matching test.
 int getCount()
          Return the count associated with this node.
 int getLeft()
          Return the left value for this node.
 SegmentTreeNode getLeftSon()
          Return the left child.
 SegmentTreeNode getNode(int target)
          Return smallest granularity node for the given [left,left+1)
 int getRight()
          Return the right value for this node.
 SegmentTreeNode getRightSon()
          Return the right child.
 boolean insert(IInterval interval)
          Insert the given segment into the SegmentTree.
 boolean intersects(int q)
          Determines if the q value is greater than or equal to getLeft() and strictly less than getRight()
 boolean remove(IInterval interval)
          Remove the given segment from the SegmentTree.
 java.lang.String toString()
          A shallow representation of this node.
 boolean toTheLeft(int q)
          Determines if the q value is strictly less than the getLeft() value.
 boolean toTheRight(int q)
          Determines if the q value is greater than or equal to the getRight() value.
protected  void update(IInterval interval)
          Algorithms over SegmentTrees often store additional information with each node, and may perform complex computations on insert.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

constructor

public static final IConstructor constructor
Default Constructor to use for all SegmentTrees.

Constructor Detail

SegmentTreeNode

protected SegmentTreeNode(int left,
                          int right)
Construct node for this range.

Parameters:
left - left value of the range
right - right value of the range
Throws:
java.lang.IllegalArgumentException - if interval is invalid.
Method Detail

getLeft

public int getLeft()
Return the left value for this node.

Specified by:
getLeft in interface IInterval
Returns:
left index whose value is strictly less than right index

getRight

public int getRight()
Return the right value for this node.

Specified by:
getRight in interface IInterval
Returns:
right index whose value is strictly greater than left index

intersects

public boolean intersects(int q)
Description copied from interface: IInterval
Determines if the q value is greater than or equal to getLeft() and strictly less than getRight()

Specified by:
intersects in interface IInterval

toTheLeft

public boolean toTheLeft(int q)
Description copied from interface: IInterval
Determines if the q value is strictly less than the getLeft() value.

Specified by:
toTheLeft in interface IInterval

toTheRight

public boolean toTheRight(int q)
Description copied from interface: IInterval
Determines if the q value is greater than or equal to the getRight() value.

Specified by:
toTheRight in interface IInterval

getCount

public int getCount()
Return the count associated with this node.


getLeftSon

public SegmentTreeNode getLeftSon()
Return the left child.

Specified by:
getLeftSon in interface IBinaryTreeNode

getRightSon

public SegmentTreeNode getRightSon()
Return the right child.

Specified by:
getRightSon in interface IBinaryTreeNode

equals

public boolean equals(java.lang.Object obj)
Determine the matching test. Defaults to equality of the node based upon the interval. Subclasses can override, for example, to determine if the interval is contained within the node's information, but only if information is only compared using IInterval information.

Overrides:
equals in class java.lang.Object
Parameters:
obj - the interval with whom we wish to match Test.

checkInterval

public void checkInterval(IInterval interval)
Used to validate IInterval before being incorporated into this data structure.

Parameters:
interval - proposed IInterval object to be validated.
Throws:
java.lang.IllegalArgumentException - if (interval.getLeft() >= interval.getRight())

checkInterval

public void checkInterval(int begin,
                          int end)
Used to validate [left, right) interval before being incorporated into this data structure.

Parameters:
begin - open left border of interval
end - closed right border of interval
Throws:
java.lang.IllegalArgumentException - if (begin >= end)

getNode

public SegmentTreeNode getNode(int target)
Return smallest granularity node for the given [left,left+1)


insert

public boolean insert(IInterval interval)
Insert the given segment into the SegmentTree.

Parameters:
interval - interval segment being inserted.
Returns:
true if segment was updated
Throws:
java.lang.IllegalArgumentException - if interval is ill-formed.

remove

public boolean remove(IInterval interval)
Remove the given segment from the SegmentTree. Only removal of previously inserted intervals ensures correctness!

Parameters:
interval - interval segment being inserted.
Returns:
true if segment was updated
Throws:
java.lang.IllegalArgumentException - if interval is invalid.

update

protected void update(IInterval interval)
Algorithms over SegmentTrees often store additional information with each node, and may perform complex computations on insert. This method is overridden by subclasses as required.

Parameters:
interval - interval segment being updated.

dispose

protected void dispose(IInterval interval)
Algorithms over SegmentTrees often store additional information with each node, and may wish to clear information and/or perform computations when a segment is deleted. This method is overridden by subclasses as required.

Parameters:
interval - interval segment being disposed of.

toString

public java.lang.String toString()
A shallow representation of this node.

Overrides:
toString in class java.lang.Object

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.