org.mattbusche.util.partition
Class Domain<M,V>

java.lang.Object
  org.mattbusche.util.partition.Domain<M,V>

public class Domain<M,V>
extends java.lang.Object

A resizable array of Entry<M> objects having sequentially numbered IDs which may be partitioned across an arbitrary number of associated Groups.

Read the package summary for introductory information about Domain and its related classes.

The ID of the first Entry object (being the Entry with the lowest numbered ID in the Domain's internal array) may have an arbitrary value and is tracked by min(). The ID of the last Entry object (being the Entry with the highest numbered ID in the Domain's internal array) is given by min()+size()-1. This internal array may be dynamically resized in either direction (either by adding entries after the end of the array which increases the maximum ID or by adding entries before the beginning of the array which decreases the minimum ID).

The methods addEntry(), compact(), reserve(), and resize() (and their overloaded variants) are the operations that can result in memory reallocation. Memory reallocation does not disturb Group membership nor does it invalidate GroupIterators.

Version:

0.1

Author:

Matthew T. Busche

Constructor Summary

Domain()
Constructs an empty Domain.

Domain(Domain<M,V> d)
Constructs a Domain that is a copy of d.

Domain(int size)
Constructs a Domain with size Entry objects having IDs ranging from 0 to size-1.

Domain(int size, int min)
Constructs a Domain with size Entry objects having IDs ranging from min to min+size-1.

Method Summary

void	addEntry(int id) Equivalent to addEntry(id, null).
void	addEntry(int id, M member) Similar to setMember(id, member) but will resize this Domain as neccessary to accomodate the given id.
int	capacity() Returns high() - low().
void	compact() If the capacity of the Domain exceeds its size(), then compact reallocates internal storage reducing capacity to match the current size of the Domain.
Entry<M>	getEntry(int id) Returns the Entry object with the given id.
Group<M,V>	getGroup(int id) Returns the Group to which the Entry with given id belongs or null if that member belongs to no Group.
M	getMember(int id) Returns the member object associated with the given id.
V	getValue(int id) Returns the value of the Group to which the Entry with the given id belongs.
int	high() Returns one plus the highest numbered ID that can be added to the Domain without memory reallocation.
int	low() Returns the lowest numbered ID that can be added to the Domain without memory reallocation.
int	min() Returns the lowest numbered ID of this Domain.
void	reserve(int newHigh) Equivalent to reserve(newHigh, low()).
void	reserve(int newHigh, int newLow) If either high() < newHigh or low() > newLow, then the internal array is reallocated so that high is increased to at least newHigh and low is reduced to at most newLow.
void	resize(int newSize) Equivalent to resize(newSize, min())
void	resize(int newSize, int newMin) Resizes this Domain to contain newSize Entry objects with IDs ranging from newMin to newMin+newSize-1.
void	setMember(int id, M m) Finds the Entry in this Domain with the given ID and sets its member field to m.
int	size() Returns the number of Entry objects in this Domain
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

Domain

public Domain()

Constructs an empty Domain. The Domain's min property is set to 0.

Domain

public Domain(int size)

Constructs a Domain with size Entry objects having IDs ranging from 0 to size-1. All Entry member fields are initialized to null.

Throws:

PartitionException - if size is negative.

Domain

public Domain(int size,
              int min)

Constructs a Domain with size Entry objects having IDs ranging from min to min+size-1. All Entry member fields are initialized to null

.

Throws:

PartitionException - if size is negative.

Domain

public Domain(Domain<M,V> d)

Constructs a Domain that is a copy of d. Members are only copied by reference (not a deep copy or clone). The capacity of the new Domain matches the size of the original (minimizing storage requirements for the copy).

Throws:

java.lang.NullPointerException - if d is null.

Method Detail

size

public int size()

Returns the number of Entry objects in this Domain

.

min

public int min()

Returns the lowest numbered ID of this Domain.

getGroup

public Group<M,V> getGroup(int id)

Returns the Group to which the Entry with given id belongs or null if that member belongs to no Group.

Computational Complexity: Constant.

Throws:

PartitionException - if id is less than min() or greater than min()+size()-1.

getValue

public V getValue(int id)

Returns the value of the Group to which the Entry with the given id belongs. Equivalent to getGroup(id).getValue().

Computational Complexity: Constant.

Throws:

PartitionException - if id is less than min() or greater than min()+size()-1.

java.lang.NullPointerException - if the Entry with the given id belongs to no Group.

getMember

public M getMember(int id)

Returns the member object associated with the given id.

Computational Complexity: Constant.

Throws:

PartitionException - if id is less than min() or greater than min()+size()-1.

setMember

public void setMember(int id,
                      M m)

Finds the Entry in this Domain with the given ID and sets its member field to m.

Computational Complexity: Constant.

Throws:

PartitionException - if id is less than min() or greater than min()+size()-1.

getEntry

public Entry<M> getEntry(int id)

Returns the Entry object with the given id.

Computational Complexity: Constant.

Throws:

PartitionException - if id is less than min() or greater than min()+size()-1.

addEntry

public void addEntry(int id)

Equivalent to addEntry(id, null).

addEntry

public void addEntry(int id,
                     M member)

Similar to setMember(id, member) but will resize this Domain as neccessary to accomodate the given id. If the Domain has size zero or if id is less than the current min, then min is set to id. If the Domain has capacity zero, then both min and low are set to id.

resize

public void resize(int newSize)

Equivalent to resize(newSize, min())

resize

public void resize(int newSize,
                   int newMin)

Resizes this Domain to contain newSize Entry objects with IDs ranging from newMin to newMin+newSize-1.

Previously existing Entry objects having IDs that fall in this newly defined range have both their member fields as well as their group memberships preserved.

Previously existing Entry objects having IDs that fall outside this newly defined range are removed from their Groups and have internal references to the Entry removed.

If newMin < low() or newMin+newSize > high() then resize will perform a reallocation to accomodate the requested Entry range.

Throws:

PartitionException - if newSize is negative.

high

public int high()

Returns one plus the highest numbered ID that can be added to the Domain without memory reallocation.

low

public int low()

Returns the lowest numbered ID that can be added to the Domain without memory reallocation.

capacity

public int capacity()

Returns high() - low().

reserve

public void reserve(int newHigh)

Equivalent to reserve(newHigh, low()).

reserve

public void reserve(int newHigh,
                    int newLow)

If either high() < newHigh or low() > newLow, then the internal array is reallocated so that high is increased to at least newHigh and low is reduced to at most newLow. After the call, IDs from newLow to newHigh-1 may subsequently added to the Domain without additional reallocations.

Throws:

PartitionException - if newHigh is less than newLow.

compact

public void compact()

If the capacity of the Domain exceeds its size(), then compact reallocates internal storage reducing capacity to match the current size of the Domain.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object