|
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.interval.SegmentTreeNode
public class SegmentTreeNode
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.
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 |
---|
public static final IConstructor constructor
Constructor Detail |
---|
protected SegmentTreeNode(int left, int right)
left
- left value of the rangeright
- right value of the range
java.lang.IllegalArgumentException
- if interval is invalid.Method Detail |
---|
public int getLeft()
getLeft
in interface IInterval
public int getRight()
getRight
in interface IInterval
public boolean intersects(int q)
IInterval
intersects
in interface IInterval
public boolean toTheLeft(int q)
IInterval
toTheLeft
in interface IInterval
public boolean toTheRight(int q)
IInterval
toTheRight
in interface IInterval
public int getCount()
public SegmentTreeNode getLeftSon()
getLeftSon
in interface IBinaryTreeNode
public SegmentTreeNode getRightSon()
getRightSon
in interface IBinaryTreeNode
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object
obj
- the interval with whom we wish to match Test.public void checkInterval(IInterval interval)
interval
- proposed IInterval object to be validated.
java.lang.IllegalArgumentException
- if (interval.getLeft() >= interval.getRight())public void checkInterval(int begin, int end)
begin
- open left border of intervalend
- closed right border of interval
java.lang.IllegalArgumentException
- if (begin >= end)public SegmentTreeNode getNode(int target)
public boolean insert(IInterval interval)
interval
- interval segment being inserted.
java.lang.IllegalArgumentException
- if interval is ill-formed.public boolean remove(IInterval interval)
interval
- interval segment being inserted.
java.lang.IllegalArgumentException
- if interval is invalid.protected void update(IInterval interval)
interval
- interval segment being updated.protected void dispose(IInterval interval)
interval
- interval segment being disposed of.public java.lang.String toString()
toString
in class java.lang.Object
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |