hypercast.DT
Class DT_Neighborhood

java.lang.Object
  |
  +--hypercast.DT.DT_Neighborhood

public final class DT_Neighborhood
extends java.lang.Object

This class keeps track of the Neighborhood table and LogicalAddress of a node in the Delaunay triangulation. It also provides a large variety of helper functions.

The neighbors are kept unsorted in a Vector. The neighbors can be accessed either through their index in the Vector, or by the neighbor's Physical Address. For each neighbor, DT_Neighborhood stores an AddressPair and the time the most recent message was received from that neighbor.

DT_Neighborhood maintains a property on the neighbors. This property is: In a Delaunay triangulation of the node's Logical Address and its neighbors' Logical Addresses, there would be an edge connecting the node's LA to each of its neighbor's LAs. When a node is inserted causes this property to be violate, neighbors are removed to restore the property. For any problems, contact Jorg Liebeherr at jorg@cs.virginia.edu


Constructor Summary
DT_Neighborhood(hypercast.HyperCastConfig c, hypercast.I_UnicastAdapter ua, hypercast.DT.DT_LogicalAddress startingCoords, hypercast.StatsProcessor sPro)
          Constructor.
 
Method Summary
 void addNeighbor(hypercast.DT.DT_AddressPair addr, hypercast.DT.DT_AddressPair cw, hypercast.DT.DT_AddressPair ccw, boolean hasThisNodeAsNeighbor)
          Inserts a neighbor and then removes neighbors to make neighborhood consistent
 boolean amIParent(hypercast.DT.DT_LogicalAddress node, hypercast.DT.DT_LogicalAddress root)
          Returns true if this node is the parent of the neighbor node in a spanning tree rooted at root
 boolean contains(hypercast.I_LogicalAddress addr)
          Returns true if one of the neighbors has a logical address equal to the parameter.
 boolean contains(hypercast.I_NetworkAddress addr)
          Returns true if one of the neighbors has a phyiscal address equal to the parameter.
 boolean contains(hypercast.I_PhysicalAddress addr)
          Returns true if one of the neighbors has a phyiscal address equal to the parameter.
 hypercast.DT.DT_AddressPair[] getAllNeighbors()
          Returns the AddressPairs of all the neighbors
 hypercast.DT.DT_AddressPair getCCWNeighbor(hypercast.DT.DT_LogicalAddress la)
          Finds the neighbor with the CCW smallest angle to the parameter with respect to this node.
 hypercast.DT.DT_AddressPair getCCWNeighborAddressPair(int index)
          Returns the address pair of a CCW neighbor correspondin to the neighbor with given index.
 hypercast.DT.DT_AddressPair[] getChildren(hypercast.DT.DT_LogicalAddress root)
          Return the AddressPairs of neighbor that are children of this node in a spanning tree rooted at rootCoords.
 hypercast.DT.DT_AddressPair getCWNeighbor(hypercast.DT.DT_LogicalAddress la)
          Finds the neighbor with the CCW smallest angle to the parameter with respect to this node.
 hypercast.DT.DT_AddressPair getCWNeighborAddressPair(int index)
          Returns the address pair of a CW neighbor correspondin to the neighbor with given index.
 long getLastContactTimeOfNeighborAtIndex(int i)
          Returns the Nth neighbor's LastContactTime (the last time a message was received from that neighbor).
 hypercast.DT.DT_LogicalAddress getLogicalAddress()
          Returns logical address of this node.
 hypercast.DT.DT_AddressPair getMyAddressPair()
          Returns address pair of this node.
 hypercast.DT.DT_AddressPair getNeighborAddressPair(int index)
          Returns the address pair of neighbor with given index.
 hypercast.DT.DT_AddressPair getNeighborAtIndex(int i)
          Returns the Nth neighbor's AddressPair.
 hypercast.DT.DT_AddressPair getNeighborAtSameAngle(hypercast.DT.DT_LogicalAddress la)
          Returns neighbors that lies as the same angle as the parameter with respect to this node.
 hypercast.DT.DT_AddressPair getNeighborWithThisLA(hypercast.I_LogicalAddress addr)
          Returns the AddressPair of the neighbor whose logical address equals the parameter.
 hypercast.DT.DT_AddressPair getNeighborWithThisPA(hypercast.I_PhysicalAddress addr)
          Returns the AddressPair of the neighbor whose physical address equals the parameter.
 hypercast.DT.DT_AddressPair getNextHopToLeader()
          Returns the neighbor with the greatest coordinates.
 hypercast.DT.DT_AddressPair getNodeCCWOfNeighborAtIndex(int i)
          Returns the Nth neighbor's CCW neighbor's AddressPair.
 hypercast.DT.DT_AddressPair getNodeCWOfNeighborAtIndex(int i)
          Returns the Nth neighbor's CW neighbor's AddressPair.
 int getNumOfNeighbors()
          Returns the number of neighbors.
 hypercast.DT.DT_AddressPair getParent(hypercast.DT.DT_LogicalAddress rootCoords)
          Returns AddressPair of neighbor that is parent of this node in a spanning tree rooted at rootCoords.
 hypercast.I_PhysicalAddress getPhysicalAddress()
          Returns physical address of this node.
 int getTableSize()
          Returns the size of neighborhood table.
 boolean hasFourOnCircle()
          Returns true if any 4 neighbors lie on a circle
 int indexOfNeighbor(hypercast.I_LogicalAddress addr)
          Finds the index of the neighbor whose logical address equals the parameter.
 int indexOfNeighbor(hypercast.I_NetworkAddress addr)
          Finds the index of the neighbor whose physical address equals the parameter.
 int indexOfNeighbor(hypercast.I_PhysicalAddress addr)
          Finds the index of the neighbor whose physical address equals the parameter.
 int isConsistent()
          Test Function.
 boolean isEmpty()
          Returns true if there are no neighbors.
 boolean isLeader()
          Returns true if no neighbor's Logical Address is greaterThan this node's LogicalAddress.
 boolean isNeighborTableChanged()
          Return the neighbor table change flag.
 boolean isStable()
          Returns true every neighbor's CW and CCW entry are in the neighborhood.
 boolean isThisClosest(hypercast.DT.DT_Point p)
          Returns true if this node is at least as close to the point p as any of its neighbors.
 boolean neighborAtIndexHasThisNodeAsNeighbor(int i)
          Returns if Nth neighbor has this node as a neighbor.
 boolean neighborHasThisLA(hypercast.DT.DT_LogicalAddress la)
          Returns true if there exists a neighbor with a LogicalAddress equal to the parameter.
 void removeAllNeighbors()
          Remove all neighbors from the Neighborhood.
 void removeNeighbor(hypercast.DT.DT_AddressPair addrs)
          Removes neighbor identified by the PhysicalAddress of its AddressPair.
 void removeNeighbor(hypercast.I_PhysicalAddress addr)
          Removes neighbor identified by its PhysicalAddress.
 void removeNeighbor(int i)
          Removes neighbor identified by its index
 void setNeighborTableChangeFlag(boolean changeFlag)
          Sets the neighbor table change flag.
 void setNotificationHandler(hypercast.NotificationHandler nh)
          Sets notification handler.
 boolean shouldBeNeighbor(hypercast.DT.DT_LogicalAddress la)
          Returns true if the node with LogicalAddress la can be added as a neighbor.
 java.lang.String toString()
          Creates a string containing the state of the neighborhood.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

DT_Neighborhood

public DT_Neighborhood(hypercast.HyperCastConfig c,
                       hypercast.I_UnicastAdapter ua,
                       hypercast.DT.DT_LogicalAddress startingCoords,
                       hypercast.StatsProcessor sPro)
Constructor.

Parameters:
startingCoords - The starting address of this node.
Method Detail

getNeighborAddressPair

public hypercast.DT.DT_AddressPair getNeighborAddressPair(int index)
Returns the address pair of neighbor with given index.


getCWNeighborAddressPair

public hypercast.DT.DT_AddressPair getCWNeighborAddressPair(int index)
Returns the address pair of a CW neighbor correspondin to the neighbor with given index.


getCCWNeighborAddressPair

public hypercast.DT.DT_AddressPair getCCWNeighborAddressPair(int index)
Returns the address pair of a CCW neighbor correspondin to the neighbor with given index.


getMyAddressPair

public hypercast.DT.DT_AddressPair getMyAddressPair()
Returns address pair of this node.


getLogicalAddress

public hypercast.DT.DT_LogicalAddress getLogicalAddress()
Returns logical address of this node.


getPhysicalAddress

public hypercast.I_PhysicalAddress getPhysicalAddress()
Returns physical address of this node.


getNumOfNeighbors

public final int getNumOfNeighbors()
Returns the number of neighbors. This is useful when calling getNeighborAtIndex()


getTableSize

public final int getTableSize()
Returns the size of neighborhood table.


isEmpty

public boolean isEmpty()
Returns true if there are no neighbors.


isLeader

public boolean isLeader()
Returns true if no neighbor's Logical Address is greaterThan this node's LogicalAddress.


isStable

public boolean isStable()
Returns true every neighbor's CW and CCW entry are in the neighborhood.


setNotificationHandler

public void setNotificationHandler(hypercast.NotificationHandler nh)
Sets notification handler.


isNeighborTableChanged

public boolean isNeighborTableChanged()
Return the neighbor table change flag.


setNeighborTableChangeFlag

public void setNeighborTableChangeFlag(boolean changeFlag)
Sets the neighbor table change flag.


getNeighborAtIndex

public hypercast.DT.DT_AddressPair getNeighborAtIndex(int i)
Returns the Nth neighbor's AddressPair. The neighbors are not ordered.


getNodeCWOfNeighborAtIndex

public hypercast.DT.DT_AddressPair getNodeCWOfNeighborAtIndex(int i)
Returns the Nth neighbor's CW neighbor's AddressPair.


getNodeCCWOfNeighborAtIndex

public hypercast.DT.DT_AddressPair getNodeCCWOfNeighborAtIndex(int i)
Returns the Nth neighbor's CCW neighbor's AddressPair.


neighborAtIndexHasThisNodeAsNeighbor

public boolean neighborAtIndexHasThisNodeAsNeighbor(int i)
Returns if Nth neighbor has this node as a neighbor.


getLastContactTimeOfNeighborAtIndex

public long getLastContactTimeOfNeighborAtIndex(int i)
Returns the Nth neighbor's LastContactTime (the last time a message was received from that neighbor). The neighbors are not ordered.


contains

public boolean contains(hypercast.I_PhysicalAddress addr)
Returns true if one of the neighbors has a phyiscal address equal to the parameter. Recall, a physical address uniquely identifies a node.


contains

public boolean contains(hypercast.I_LogicalAddress addr)
Returns true if one of the neighbors has a logical address equal to the parameter. Recall, a physical address uniquely identifies a node.


indexOfNeighbor

public int indexOfNeighbor(hypercast.I_PhysicalAddress addr)
Finds the index of the neighbor whose physical address equals the parameter. Recall, a physical address uniquely identifies a node.


contains

public boolean contains(hypercast.I_NetworkAddress addr)
Returns true if one of the neighbors has a phyiscal address equal to the parameter.


indexOfNeighbor

public int indexOfNeighbor(hypercast.I_NetworkAddress addr)
Finds the index of the neighbor whose physical address equals the parameter.


indexOfNeighbor

public int indexOfNeighbor(hypercast.I_LogicalAddress addr)
Finds the index of the neighbor whose logical address equals the parameter. Recall, a logical address uniquely identifies a node.


getNeighborWithThisPA

public hypercast.DT.DT_AddressPair getNeighborWithThisPA(hypercast.I_PhysicalAddress addr)
Returns the AddressPair of the neighbor whose physical address equals the parameter. Recall, a physical address uniquely identifies a node.


getNeighborWithThisLA

public hypercast.DT.DT_AddressPair getNeighborWithThisLA(hypercast.I_LogicalAddress addr)
Returns the AddressPair of the neighbor whose logical address equals the parameter. Recall, a logical address uniquely identifies a node.


neighborHasThisLA

public boolean neighborHasThisLA(hypercast.DT.DT_LogicalAddress la)
Returns true if there exists a neighbor with a LogicalAddress equal to the parameter.


getParent

public hypercast.DT.DT_AddressPair getParent(hypercast.DT.DT_LogicalAddress rootCoords)
Returns AddressPair of neighbor that is parent of this node in a spanning tree rooted at rootCoords. This is calculated by finding the neighbor that forms the smallest angle with rootCoords.


getChildren

public hypercast.DT.DT_AddressPair[] getChildren(hypercast.DT.DT_LogicalAddress root)
Return the AddressPairs of neighbor that are children of this node in a spanning tree rooted at rootCoords. This based on if DT_Neighborhood.getParent() of the neighbor would return this node.


amIParent

public boolean amIParent(hypercast.DT.DT_LogicalAddress node,
                         hypercast.DT.DT_LogicalAddress root)
Returns true if this node is the parent of the neighbor node in a spanning tree rooted at root

See Also:
getParent(DT_LogicalAddress)

getAllNeighbors

public hypercast.DT.DT_AddressPair[] getAllNeighbors()
Returns the AddressPairs of all the neighbors


getNextHopToLeader

public hypercast.DT.DT_AddressPair getNextHopToLeader()
Returns the neighbor with the greatest coordinates.

Returns:
null if this node's LogicalAddress is greater than all its neighbors.

isThisClosest

public boolean isThisClosest(hypercast.DT.DT_Point p)
Returns true if this node is at least as close to the point p as any of its neighbors.

Returns:
true if there exists a neighbor of equal distance. NEEDED ONLY FOR MULTICAST VERSIONS

hasFourOnCircle

public boolean hasFourOnCircle()
Returns true if any 4 neighbors lie on a circle


shouldBeNeighbor

public boolean shouldBeNeighbor(hypercast.DT.DT_LogicalAddress la)
Returns true if the node with LogicalAddress la can be added as a neighbor.


getNeighborAtSameAngle

public hypercast.DT.DT_AddressPair getNeighborAtSameAngle(hypercast.DT.DT_LogicalAddress la)
Returns neighbors that lies as the same angle as the parameter with respect to this node. If this returns a node, then this node, parameter, and returned node lie on a line.


getCCWNeighbor

public hypercast.DT.DT_AddressPair getCCWNeighbor(hypercast.DT.DT_LogicalAddress la)
Finds the neighbor with the CCW smallest angle to the parameter with respect to this node. The angle must be greater than MIN_ANGLE

See Also:
DT_Neighborhood#MIN_ANGLE

getCWNeighbor

public hypercast.DT.DT_AddressPair getCWNeighbor(hypercast.DT.DT_LogicalAddress la)
Finds the neighbor with the CCW smallest angle to the parameter with respect to this node. The angle must be greater than MIN_ANGLE

See Also:
DT_Neighborhood#MIN_ANGLE

isConsistent

public int isConsistent()
Test Function.

Returns:
index of neighbor that is part of inconsistency.

addNeighbor

public void addNeighbor(hypercast.DT.DT_AddressPair addr,
                        hypercast.DT.DT_AddressPair cw,
                        hypercast.DT.DT_AddressPair ccw,
                        boolean hasThisNodeAsNeighbor)
Inserts a neighbor and then removes neighbors to make neighborhood consistent


removeNeighbor

public void removeNeighbor(hypercast.I_PhysicalAddress addr)
Removes neighbor identified by its PhysicalAddress.


removeNeighbor

public void removeNeighbor(int i)
Removes neighbor identified by its index


removeNeighbor

public void removeNeighbor(hypercast.DT.DT_AddressPair addrs)
Removes neighbor identified by the PhysicalAddress of its AddressPair.


removeAllNeighbors

public void removeAllNeighbors()
Remove all neighbors from the Neighborhood.


toString

public java.lang.String toString()
Creates a string containing the state of the neighborhood.

Overrides:
toString in class java.lang.Object