oogp2p.pastry
Class LeafSet

java.lang.Object
  oogp2p.pastry.LeafSet

All Implemented Interfaces:

java.io.Serializable

public class LeafSet

extends java.lang.Object

implements java.io.Serializable

A class for representing and manipulating the leaf set. The leafset is not strictly a set: when the ring is small, a node may appear in both the cw and the ccw half of the "set".

Version:

$Id: LeafSet.java,v 1.4 2003/12/01 23:31:04 sjg Exp $

Author:

Andrew Ladd, Peter Druschel

See Also:

Serialized Form

Field Summary

private PastryLocation	baseId
private SimilarSet	ccwSet
private SimilarSet	cwSet
private int	theSize

Constructor Summary

LeafSet(PastryLocation localNode, int size)
Constructor.

Method Summary

int	ccwSize() Gets the current counterclockwise size.
private int	complement(int inx) complement - given an index of a node in the leafset, produces the index of the same nodeId in the opposite half of the leafset
int	cwSize() Gets the current clockwise size.
PastryLocation	get(int index) Finds the NodeHandle at a given index.
PastryLocation	get(PastryLocation nid) Finds the NodeHandle associated with the NodeId.
int	getIndex(PastryLocation nid) Gets the index of the element with the given node id.
java.util.Collection	getSet()
private int	getUniqueCount() Returns the number of unique nodes in the leafset
int	maxSize() Gets the maximal size of the leaf set.
boolean	member(PastryLocation nid) Verifies if the set contains this particular id.
boolean	merge(LeafSet remotels, PastryLocation from, RoutingTable routeTable, boolean testOnly, java.util.Set insertedHandles) Merge a remote leafset into this
private int	mod(int x, int y) Perform (x mod y).
int	mostSimilar(PastryLocation nid) Numerically closests node to a given a node in the leaf set.
boolean	overlaps() Test if the leafset overlaps
boolean	put(PastryLocation handle) Puts a NodeHandle into the set.
PastryLocation	remove(PastryLocation nid) Removes a node id and its handle from the set.
int	size() Gets the current size of the leaf set.
boolean	test(PastryLocation handle) Test if a put of the given NodeHandle would succeed.
java.lang.String	toString() Returns a string representation of the leaf set
boolean	withinRange(PastryLocation pLoc)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

baseId

private PastryLocation baseId

cwSet

private SimilarSet cwSet

ccwSet

private SimilarSet ccwSet

theSize

private int theSize

Constructor Detail

LeafSet

public LeafSet(PastryLocation localNode,
               int size)

Constructor.

Parameters:

size - the size of the leaf set.

Method Detail

put

public boolean put(PastryLocation handle)

Puts a NodeHandle into the set.

Parameters:

handle - the handle to put.

Returns:

true if successful, false otherwise.

test

public boolean test(PastryLocation handle)

Test if a put of the given NodeHandle would succeed.

Parameters:

handle - the handle to test.

Returns:

true if a put would succeed, false otherwise.

overlaps

public boolean overlaps()

Test if the leafset overlaps

Returns:

true if the most distant cw member appears in the ccw set or vice versa, false otherwise

get

public PastryLocation get(PastryLocation nid)

Finds the NodeHandle associated with the NodeId.

Parameters:

nid - a node id.

Returns:

the handle associated with that id or null if no such handle is found.

getIndex

public int getIndex(PastryLocation nid)
             throws java.util.NoSuchElementException

Gets the index of the element with the given node id.

Parameters:

nid - the node id.

Returns:

the index or throws a NoSuchElementException

Throws:

java.util.NoSuchElementException

get

public PastryLocation get(int index)

Finds the NodeHandle at a given index.

Parameters:

index - an index.

Returns:

the handle associated with that index.

member

public boolean member(PastryLocation nid)

Verifies if the set contains this particular id.

Parameters:

nid - a node id.

Returns:

true if that node id is in the set, false otherwise.

withinRange

public boolean withinRange(PastryLocation pLoc)

remove

public PastryLocation remove(PastryLocation nid)

Removes a node id and its handle from the set.

Parameters:

nid - the node to remove.

Returns:

the node handle removed or null if nothing.

maxSize

public int maxSize()

Gets the maximal size of the leaf set.

Returns:

the size.

size

public int size()

Gets the current size of the leaf set.

Returns:

the size.

cwSize

public int cwSize()

Gets the current clockwise size.

Returns:

the size.

ccwSize

public int ccwSize()

Gets the current counterclockwise size.

Returns:

the size.

complement

private int complement(int inx)

complement - given an index of a node in the leafset, produces the index of the same nodeId in the opposite half of the leafset

mostSimilar

public int mostSimilar(PastryLocation nid)

Numerically closests node to a given a node in the leaf set.

Parameters:

nid - a node id.

Returns:

the index of the numerically closest node (0 if baseId is the closest).

getUniqueCount

private int getUniqueCount()

Returns the number of unique nodes in the leafset

Returns:

the number of unique nodes in the leafset

mod

private int mod(int x,
                int y)

Perform (x mod y). This is necessary because the java % operator is actually remainder instead of mod. Useless.

Returns:

x mod y

merge

public boolean merge(LeafSet remotels,
                     PastryLocation from,
                     RoutingTable routeTable,
                     boolean testOnly,
                     java.util.Set insertedHandles)

Merge a remote leafset into this

Parameters:

remotels - the remote leafset

from - the node from which we received the leafset

routeTable - the routing table

testOnly - if true, do not change the leafset

insertedHandles - if not null, a Set that contains, upon return of this method, the nodeHandles that would be inserted into this LeafSet if testOnly is true

Returns:

true if the local leafset changed

getSet

public java.util.Collection getSet()

Returns:

-- the set of PastryLocations contained within

toString

public java.lang.String toString()

Returns a string representation of the leaf set