Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class AugmentedNode<K>

java.lang.Object
  extended by algs.model.tree.BalancedBinaryNode<K,K>
      extended by algs.model.problems.segmentIntersection.AugmentedNode<K>
Type Parameters:
K - The key to be used for the nodes in the tree. Note that both the key and the value of the nodes will be of type K for simplicity
All Implemented Interfaces:
IGraphEntity

public class AugmentedNode<K>
extends BalancedBinaryNode<K,K>

The line sweep intersection algorithm stores information with internal nodes, and the leaf nodes contain the actual segments.

This example shows how to "extend" a balanced binary tree class structure.

Note that the Key,Values are the same type in the Augmented node, so we silently drop the use of values for the parameterizations.

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

Nested Class Summary
 
Nested classes/interfaces inherited from interface algs.debug.IGraphEntity
IGraphEntity.Formatter
 
Field Summary
 K max
          Minimum segment to appear in left sub-tree.
 K min
          Maximum segment to appear in right sub-tree.
 
Fields inherited from class algs.model.tree.BalancedBinaryNode
BLACK, color, left, parent, RED, right
 
Constructor Summary
AugmentedNode(K key, K value, AugmentedNode<K> parent)
          Construct augmented node as before.
 
Method Summary
 AugmentedNode<K> left()
          Return left son.
 AugmentedNode<K> parent()
          Get parent (needed for rotations and the like).
 AugmentedNode<K> right()
          Return right son.
 
Methods inherited from class algs.model.tree.BalancedBinaryNode
color, color, equals, key, left, nodeLabel, parent, right, setValue, toString, value
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

max

public K max
Minimum segment to appear in left sub-tree.


min

public K min
Maximum segment to appear in right sub-tree.

Constructor Detail

AugmentedNode

public AugmentedNode(K key,
                     K value,
                     AugmentedNode<K> parent)
Construct augmented node as before.

Parameters:
key -
value -
parent -
Method Detail

right

public AugmentedNode<K> right()
Description copied from class: BalancedBinaryNode
Return right son.

Overrides:
right in class BalancedBinaryNode<K,K>

left

public AugmentedNode<K> left()
Description copied from class: BalancedBinaryNode
Return left son.

Overrides:
left in class BalancedBinaryNode<K,K>

parent

public AugmentedNode<K> parent()
Description copied from class: BalancedBinaryNode
Get parent (needed for rotations and the like).

Overrides:
parent in class BalancedBinaryNode<K,K>

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.