rice.pastry
Class Id

java.lang.Object
  rice.pastry.Id

All Implemented Interfaces:

java.lang.Comparable, Id, java.io.Serializable

Direct Known Subclasses:

NodeId

public class Id

extends java.lang.Object

implements Id

Represents a Pastry identifier for a node, object or key. A single identifier and the bit length for Ids is stored in this class. Ids are stored little endian.

See Also:

Serialized Form

Nested Class Summary

static class

Id.Distance A class for representing and manipulating the distance between two Ids on the circle.

Field Summary

static int[]	Half
static int	IdBitLength This is the bit length of the node ids.
static int[]	NegOne
static int[]	Null
static int[]	One

Constructor Summary

Id()
Constructor.

Id(byte[] material)
Constructor.

Id(int[] material)
Constructor.

Method Summary

Id	add(Id.Distance offset) Returns an Id corresponding to this Id plus a given distance
Id	addToId(Id.Distance offset) Returns an Id corresponding to this Id plus a given distance
void	blit(byte[] target) Blits the Id into a target array.
boolean	checkBit(int i) Checks if the ith bit is flipped.
boolean	clockwise(Id nid) Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring.
boolean	clockwise(Id nid) Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring.
int	compareTo(java.lang.Object obj) Comparison operator for Ids.
byte[]	copy() Copy the Id into a freshly generated array.
Id.Distance	distance(Id nid) Returns the shorter numerical distance on the ring between a pair of Ids.
Id.Distance	distanceFromId(Id nid) Returns the shorter numerical distance on the ring between a pair of Ids.
boolean	equals(Id nid) Equivalence relation for Ids.
boolean	equals(java.lang.Object obj) Equality operator for Ids.
Id	getAlternateId(int num, int b, int i) produces a set of ids (keys) that are evenly distributed around the id ring.
Id	getCCW() gets the Id just counterclockwise from this
Id	getCW() gets the Id just clockwise from this
int	getDigit(int i, int b) Gets the ith digit in base 2^b.
Id	getDomainPrefix(int row, int column, int suffixDigit, int b) produces a Id whose prefix up to row is identical to this, followed by a digit with value column, followed by a suffix of digits with value suffixDigits.
int	hashCode() Hash codes for Ids.
int	indexOfMSDB(Id nid) Returns the index of the most significant differing bit (MSDB).
int	indexOfMSDD(Id nid, int base) Returns the index of the most significant different digit (MSDD) in a given base.
boolean	isBetween(Id ccw, Id cw) Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle
boolean	isBetween(Id ccw, Id cw) Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle
Id.Distance	longDistance(Id nid) Returns the longer numerical distance on the ring between a pair of Ids.
Id.Distance	longDistanceFromId(Id nid) Returns the longer numerical distance on the ring between a pair of Ids.
static Id	makeRandomId(java.util.Random rng) Creates a random Id.
static int	numDigits(int base) return the number of digits in a given base
void	setBit(int i, int v) Sets the ith bit to a given value i = 0 is the least significant bit.
void	setDigit(int i, int v, int b) Sets the ith digit in base 2^b.
byte[]	toByteArray() Returns the byte array representation of this Id
java.lang.String	toString() Returns a string representation of the Id in base 16.
java.lang.String	toStringFull() Returns the complete represntation of this Id, in hex.
void	xor(Id otherId) Xor operator for Ids.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

Null

public static final int[] Null

One

public static final int[] One

NegOne

public static final int[] NegOne

Half

public static final int[] Half

IdBitLength

public static final int IdBitLength

This is the bit length of the node ids. If it is n, then there are 2^n possible different Ids. We currently assume that it is divisible by 32.

See Also:

Constant Field Values

Constructor Detail

Id

public Id(byte[] material)

Constructor.

Parameters:

material - an array of length at least IdBitLength/8 containing raw Id material.

Id

public Id(int[] material)

Constructor.

Parameters:

material - an array of length at least IdBitLength/32 containing raw Id material.

Id

public Id()

Constructor. It constructs a new Id with a value of 0 for all bits.

Method Detail

numDigits

public static int numDigits(int base)

return the number of digits in a given base

Parameters:

base - the number of bits in the base

Returns:

the number of digits in that base

makeRandomId

public static Id makeRandomId(java.util.Random rng)

Creates a random Id. For testing purposed only -- should NOT be used to generate real node or object identifiers (low quality of random material).

Parameters:

rng - random number generator

Returns:

a random Id

getCW

public Id getCW()

gets the Id just clockwise from this

Returns:

The CW value

getCCW

public Id getCCW()

gets the Id just counterclockwise from this

Returns:

The CCW value

isBetween

public boolean isBetween(Id ccw,
                         Id cw)

Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle

Parameters:

ccw - the counterclockwise id

cw - the clockwise id

Returns:

true if this is between ccw (inclusive) and cw (exclusive), false otherwise

getDigit

public int getDigit(int i,
                    int b)

Gets the ith digit in base 2^b. i = 0 is the least significant digit.

Parameters:

i - which digit to get.

b - which power of 2 is the base to get it in.

Returns:

the ith digit in base 2^b.

getDomainPrefix

public Id getDomainPrefix(int row,
                          int column,
                          int suffixDigit,
                          int b)

produces a Id whose prefix up to row is identical to this, followed by a digit with value column, followed by a suffix of digits with value suffixDigits.

Parameters:

row - the length of the prefix

column - the value of the following digit

suffixDigit - the value of the suffix digits

b - power of 2 of the base

Returns:

the resulting Id

getAlternateId

public Id getAlternateId(int num,
                         int b,
                         int i)

produces a set of ids (keys) that are evenly distributed around the id ring. One invocation produces the i-th member of a set of size num. The set is evenly distributed around the ring, with an offset given by this Id. The set is useful for constructing, for instance, Scribe trees with disjoint sets of interior nodes.

Parameters:

num - the number of Ids in the set (must be <= 2^b)

b - the routing base (as a power of 2)

i - the index of the requested member of the set (0<=iReturns:

the resulting set member, or null in case of illegal arguments

isBetween

public boolean isBetween(Id ccw,
                         Id cw)

Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle

Specified by:

isBetween in interface Id

Parameters:

ccw - the counterclockwise id

cw - the clockwise id

Returns:

true if this is between ccw (inclusive) and cw (exclusive), false otherwise

setBit

public void setBit(int i,
                   int v)

Sets the ith bit to a given value i = 0 is the least significant bit.

Parameters:

i - which bit to set.

v - new value of bit

setDigit

public void setDigit(int i,
                     int v,
                     int b)

Sets the ith digit in base 2^b. i = 0 is the least significant digit.

Parameters:

i - which digit to get.

v - the new value of the digit

b - which power of 2 is the base to get it in.

blit

public void blit(byte[] target)

Blits the Id into a target array.

Parameters:

target - an array of length at least IdBitLength/8 for the Id to be stored in.

copy

public byte[] copy()

Copy the Id into a freshly generated array.

Returns:

a fresh copy of the Id material

equals

public boolean equals(java.lang.Object obj)

Equality operator for Ids.

Parameters:

obj - a Id object

Returns:

true if they are equal, false otherwise.

compareTo

public int compareTo(java.lang.Object obj)

Comparison operator for Ids. The comparison that occurs is a numerical comparison.

Specified by:

compareTo in interface java.lang.Comparable

Parameters:

obj - the Id to compare with.

Returns:

negative if this < obj, 0 if they are equal and positive if this > obj.

toByteArray

public byte[] toByteArray()

Returns the byte array representation of this Id

Specified by:

toByteArray in interface Id

Returns:

The byte array representation of this id

hashCode

public int hashCode()

Hash codes for Ids.

Returns:

a hash code.

add

public Id add(Id.Distance offset)

Returns an Id corresponding to this Id plus a given distance

Parameters:

offset - the distance to add

Returns:

the new Id

distance

public Id.Distance distance(Id nid)

Returns the shorter numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

longDistance

public Id.Distance longDistance(Id nid)

Returns the longer numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

xor

public void xor(Id otherId)

Xor operator for Ids. Sets this Id to the bit-wise XOR of itself and otherId

Parameters:

otherId - a Id object

equals

public boolean equals(Id nid)

Equivalence relation for Ids.

Parameters:

nid - the other node id.

Returns:

true if they are equal, false otherwise.

clockwise

public boolean clockwise(Id nid)

Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring. An Id is clockwise if it is within the half circle clockwise from this on the ring. An Id is considered counter-clockwise from itself.

Parameters:

nid - The Id we are comparing to

Returns:

true if clockwise, false otherwise.

checkBit

public boolean checkBit(int i)

Checks if the ith bit is flipped. i = 0 is the least significant bit.

Parameters:

i - which bit to check.

Returns:

true if the bit is set, false otherwise.

indexOfMSDB

public int indexOfMSDB(Id nid)

Returns the index of the most significant differing bit (MSDB).

Parameters:

nid - another node id to compare with.

Returns:

the index of the msdb (0 is the least significant) / will return negative if they do not differ.

indexOfMSDD

public int indexOfMSDD(Id nid,
                       int base)

Returns the index of the most significant different digit (MSDD) in a given base.

Parameters:

nid - another node id to compare with.

base - the base (as a power of two) to compare in.

Returns:

the index of the msdd (0 is the least significant) / will return negative if they do not differ.

toString

public java.lang.String toString()

Returns a string representation of the Id in base 16. The string is a byte string from most to least significant.

Returns:

A String representation of this Id, abbreviated

toStringFull

public java.lang.String toStringFull()

Returns the complete represntation of this Id, in hex.

Specified by:

toStringFull in interface Id

Returns:

The complete representation of this Id, in hexadecimal

clockwise

public boolean clockwise(Id nid)

Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring. An Id is clockwise if it is within the half circle clockwise from this on the ring. An Id is considered counter-clockwise from itself.

Specified by:

clockwise in interface Id

Parameters:

nid - DESCRIBE THE PARAMETER

Returns:

true if clockwise, false otherwise.

addToId

public Id addToId(Id.Distance offset)

Returns an Id corresponding to this Id plus a given distance

Specified by:

addToId in interface Id

Parameters:

offset - the distance to add

Returns:

the new Id

distanceFromId

public Id.Distance distanceFromId(Id nid)

Returns the shorter numerical distance on the ring between a pair of Ids.

Specified by:

distanceFromId in interface Id

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

longDistanceFromId

public Id.Distance longDistanceFromId(Id nid)

Returns the longer numerical distance on the ring between a pair of Ids.

Specified by:

longDistanceFromId in interface Id

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.