jgroup.util
Class IntList

java.lang.Object
  jgroup.util.IntList

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable

public final class IntList
extends java.lang.Object
implements java.io.Externalizable

The IntList class represents ordered lists of integers. This class has been optimized to maintain list of integers containing long sequence of consecutive numbers. It is particularly useful for maintaining list of received ack numbers, that are normally consecutive (except in the case of connectivity problems).

The list is maintained by a chain of integer pairs; in each pair, the first integer represents the beginning of a consecutive sequence, while the second integer represents the end of a consecutive sequence.

For example, a list of this type:

 1 2 3 4 5  7 8 9 10 11  13 14 15 16 17 18 19 20 21 22 23 

is mantained in this way:

 (1-5),(7-11),(13-23) 

thus saving both memory and time to scan a list searching for a number.

IntList contains methods to add, lookup and remove integers, and to merge the contents of other IntLists.

Implementation note: As mentioned, IntList is based on a linked list of pairs. Each of these pairs are IntList objects, to avoid the need to introduce a inner class to hold pairs. For this reason, each integer list starts with an "empty" IntList containing no pair. The first pair of an IntList l is contained in l.next.

Since:

Jgroup 0.3

Author:

Alberto Montresor, Hein Meling

See Also:

Serialized Form

Constructor Summary

IntList()
Build an empty IntList.

Method Summary

void	clean() Clear the content of this IntList.
boolean	contains(int key) Returns true if value key is contained in this IntList.
IntList	copy() Deep clone this IntList.
int	getFirst() Returns the first element of the list, or -1 if the list is empty.
int	getLast() Returns the last element of the list, or -1 if the list is empty.
int	getMaxConsecutive() Returns the end value of the first consecutive sequence of integers contained in the list.
void	insert(int key) Insert value key in the IntList.
boolean	isEmpty() Returns true if the list is empty; false otherwise.
void	merge(IntList addend) Merge IntList addend to the IntList.
void	readExternal(java.io.ObjectInput in) Restores the content of this object from the marshalled data contained in the specified input stream.
void	remove(int key) Remove value key from the IntList.
void	remove(int start, int stop) Remove range from start to stop.
void	remove(IntList removed) Remove IntList removed from the IntList.
int	removeFirst() Returns and removes the first element of the list; -1 is returned if the list is empty.
IntList	split(int key) Split the IntList at position key, leaving the upper part in this IntList, while returning the lower part of the list, key inclusive.
int[]	toIntArray() Return an int array containing the values contained in this IntList.
java.lang.String	toString() Returns a string representation of this object
void	writeExternal(java.io.ObjectOutput out) Write the contents of this IntList to the object output stream out.

Methods inherited from class java.lang.Object

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

Constructor Detail

IntList

public IntList()

Build an empty IntList.

Method Detail

getFirst

public int getFirst()

Returns the first element of the list, or -1 if the list is empty.

getLast

public int getLast()

Returns the last element of the list, or -1 if the list is empty.

isEmpty

public boolean isEmpty()

Returns true if the list is empty; false otherwise.

getMaxConsecutive

public int getMaxConsecutive()

Returns the end value of the first consecutive sequence of integers contained in the list. For example, if the list contains

 1 2 3 4 5  7 8 9 10 11 

this methods return 5. If the list is empty, it returns -1.

contains

public boolean contains(int key)

Returns true if value key is contained in this IntList.

insert

public void insert(int key)

Insert value key in the IntList.

merge

public void merge(IntList addend)

Merge IntList addend to the IntList.

split

public IntList split(int key)

Split the IntList at position key, leaving the upper part in this IntList, while returning the lower part of the list, key inclusive.

Parameters:

key - the position in the list to make the split.

Returns:

the lower part of this list is returned.

remove

public void remove(int start,
                   int stop)

Remove range from start to stop. If stop is zero, the remainder of the list is deleted.

removeFirst

public int removeFirst()

Returns and removes the first element of the list; -1 is returned if the list is empty.

remove

public void remove(int key)

Remove value key from the IntList.

remove

public void remove(IntList removed)

Remove IntList removed from the IntList.

toIntArray

public int[] toIntArray()

Return an int array containing the values contained in this IntList.

clean

public void clean()

Clear the content of this IntList.

copy

public IntList copy()

Deep clone this IntList.

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException

Write the contents of this IntList to the object output stream out. The external format of the string is the following: each pair is written to the stream, terminated by -1.

Specified by:

writeExternal in interface java.io.Externalizable

Parameters:

out - the stream to be written

Throws:

java.io.IOException

readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException

Restores the content of this object from the marshalled data contained in the specified input stream.

Specified by:

readExternal in interface java.io.Externalizable

Parameters:

in - the stream to be read

Throws:

java.io.IOException

java.lang.ClassNotFoundException

toString

public java.lang.String toString()

Returns a string representation of this object

Overrides:

toString in class java.lang.Object