Algorithm
Development Kit 1.0

algs.model.interval
Class StoredIntervalsNode

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

public class StoredIntervalsNode
extends SegmentTreeNode

When a Segment Tree uses StoredIntervalsNode as the base node type, then a reference to the actual Intervals is stored (in no specific order) with each node in the tree.

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

Field Summary
static IConstructor constructor
          Constructor to use with this node type.
protected  java.util.ArrayList<IInterval> intervals
          Store Interval.
 
Constructor Summary
StoredIntervalsNode(int left, int right)
          Store additional information with each SegmentTreeNode
 
Method Summary
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 interval)
          Determine the matching test.
 java.util.Collection<IInterval> gather(IInterval target)
          Gather the set of stored intervals that are in common with the given target interval.
 java.util.Collection<IInterval> intervals()
          Return all IInterval objects for this node as a collection.
 java.lang.String toString()
          Reasonable extension to toString() method.
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 algs.model.interval.SegmentTreeNode
checkInterval, checkInterval, getCount, getLeft, getLeftSon, getNode, getRight, getRightSon, insert, intersects, remove, toTheLeft, toTheRight
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

intervals

protected java.util.ArrayList<IInterval> intervals
Store Interval.


constructor

public static final IConstructor constructor
Constructor to use with this node type.

Constructor Detail

StoredIntervalsNode

public StoredIntervalsNode(int left,
                           int right)
Store additional information with each SegmentTreeNode

Parameters:
left -
right -
Method Detail

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.

Just append to the end.

Overrides:
update in class SegmentTreeNode
Parameters:
interval - interval segment being updated.

equals

public boolean equals(java.lang.Object interval)
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.

Overrides:
equals in class SegmentTreeNode
Parameters:
interval - the interval with whom we wish to match Test.

gather

public java.util.Collection<IInterval> gather(IInterval target)
Gather the set of stored intervals that are in common with the given target interval.

Throws:
java.lang.IllegalArgumentException - if target is ill-formed.

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. For dynamic reasons, search from end to front.

Overrides:
dispose in class SegmentTreeNode
Parameters:
interval - interval segment being disposed of.

intervals

public java.util.Collection<IInterval> intervals()
Return all IInterval objects for this node as a collection.

Returns:
Collection of IInterval objects stored for this node.

toString

public java.lang.String toString()
Reasonable extension to toString() method.

Overrides:
toString in class SegmentTreeNode

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.