com.partnersoft.data
Class DynamicArray

java.lang.Object
  com.partnersoft.data.DynamicArray

Direct Known Subclasses:

AbstractDynamicArray, DynamicByteArray, DynamicCharArray, DynamicDoubleArray, DynamicFloatArray, DynamicIntArray, DynamicLongArray, DynamicShortArray, DynamicXyzPointArray

public abstract class DynamicArray
extends java.lang.Object

Generic superclass for direct-access arrays with decoupled content size and actual size.

DynamicArrays are a happy medium between a standard Java array (e.g. int[]) type and the collections provided by Collection.

Unlike a bare array, they keep track of the region of valid data, so that you don't have to track it separately or resize your array constantly (aren't you tired of write(array, 0, len) calls?).

Unlike the more object-oriented ArrayList, they allow public, direct access to the contents, without getters and setters and primitive wrappers and such to slow you down.

DynamicArrays can be used for input/output buffers, caches, geometry, and other performance-intensive tasks. They are neither as convenient nor as safe to use as a Collection, and you should also look into the Buffer framework, since it is specifically designed for I/O and works with memory-mapped files and other such stuff.

But, when neither of these seem to do the trick, a DynamicArray can be your friend. It certainly works well with terse looping code like:

 while (myArray.start < myArray.end)
        doSomethingWith(myArray.array[myArray.start++]);
 myArray.start = 0; // reset
 while (myArray.start < myArray.end)
        doSomethingElseWith(myArray.array[myArray.start++]);
 

Subclasses must do the following:

• define a subclass-specific public variable named array to eliminate the need for casting
• implement newArray(int size) to replace both the arrayObject and subclass-specific array variable
• add type-specific convenience methods such as add()

See the documentation for the abstract methods for details and examples for implementation.

Copyright 1997-2007 Partner Software, Inc.

Version:

$Id: DynamicArray.java 2328 2010-01-06 15:38:22Z paul $

Author:

Paul Reavis

Field Summary

java.lang.Object	arrayObject Superclass copy of the array object.
int	capacity Total capacity.
int	end End of valid data range, exclusive.
double	fastGrowthFactor Percentage amount of existing capacity to add to the array's capacity when makeRoomFor(int) requires more than the existing capacity.
int	fastGrowthLimit Size at which makeRoomFor(int) switches from fast growth model to slow growth model.
int	slowGrowthAmount After the array exceeds the fastGrowthLimit amount, calls to makeRoomFor(int) requiring growth will add this fixed amount to the size of the array rather than multiplying the existing size by the fastGrowthFactor.
int	start Start of valid data range, inclusive.

Constructor Summary

DynamicArray()
Default constructor.

DynamicArray(int capacity)
Creates a DynamicArray with the given initial capacity.

Method Summary

void	append(DynamicArray nother) Append the contents of the given array onto the end of this one.
void	clear() Clears the contents by setting start and end to zero.
DynamicArray	copy() Returns a copy of this array with the same contents.
void	copy(int oldIndex, int newIndex, int size) Copies range of contents to new spot in array.
DynamicArray	copyExactly() Returns an exact copy of this array with the same contents, capacity, start, and end.
void	copyFrom(DynamicArray nother) Copies the contents from the given array into this one so that the contents are equivalent.
void	copyTo(java.lang.Object notherArray) Exports the contents into the given array.
void	insert(int whereAt) Inserts a slot in the array, copying contents up one.
boolean	isEmpty() True if size() is zero.
void	makeRoomFor(int roomNeeded) Standard array enlarger; determines a reasonable minimumIncrease factor then calls makeRoomFor(int, int).
void	makeRoomFor(int roomNeeded, int minimumIncrease) This method ensures that there is enough unused capacity in the array to fill with the given number of items.
abstract void	newArray(int size) Allocates a new, empty array of the given size and assign it to the arrayObject property.
void	pack() Packs the array into the minimum space required, throwing out excess capacity.
void	remove(int whereAt) Removes the item at the given slot in the array, copying contents past that point down by one index.
int	size() Size of the array contents (end - start).
DynamicArray	subsection(int sectionStart, int sectionEnd) Returns a subsection of the array.
void	tidy() Moves the contents to the beginning of the array.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

start

public int start

Start of valid data range, inclusive. The first valid item is at array[start].

end

public int end

End of valid data range, exclusive. The last valid item is at array[end - 1].

capacity

public int capacity

Total capacity. Change this at your peril - it is maintained by the convenience functions in this class, and only public because of the no-seatbelts philosophy of this class. Should generally be the same as array.length in the subclass implementation.

arrayObject

public java.lang.Object arrayObject

Superclass copy of the array object. Subclasses should provide a type-specific variable named just "array".

fastGrowthFactor

public double fastGrowthFactor

Percentage amount of existing capacity to add to the array's capacity when makeRoomFor(int) requires more than the existing capacity. This is used until the fastGrowthLimit is reached, after which slowGrowthAmount is used. This is a size/performance tuning factor with a default value of 1.0 (which doubles the size of the array each time). Value must be > 0.

fastGrowthLimit

public int fastGrowthLimit

Size at which makeRoomFor(int) switches from fast growth model to slow growth model. Once the array reaches this capacity, the slowGrowthAmount is used rather than multiplying the existing size by the fastGrowthFactor. This keeps the array from growing ridiculously for large sizes. This is a size/performance tuning parameter with a default value of 10000.

slowGrowthAmount

public int slowGrowthAmount

After the array exceeds the fastGrowthLimit amount, calls to makeRoomFor(int) requiring growth will add this fixed amount to the size of the array rather than multiplying the existing size by the fastGrowthFactor. This keeps the array from growing ridiculously for large sizes. This is a size/performance tuning parameter with a default value of 1000. It must be > 0.

Constructor Detail

DynamicArray

public DynamicArray()

Default constructor. Subclasses should override this, setting array and arrayObject to an empty array, which may be a static variable since it is immutable. For example:

 private static final byte[] emptyArray = new byte[0];
 
 public DynamicByteArray() {
        arrayObject = array = emptyArray;
 }
 

DynamicArray

public DynamicArray(int capacity)

Creates a DynamicArray with the given initial capacity.

Method Detail

newArray

public abstract void newArray(int size)

Allocates a new, empty array of the given size and assign it to the arrayObject property. It is assumed that subclasses will also set it to a variable of the correct class (e.g. char[]) for ease of access as well. Copying of existing contents is Dynamic by this superclass. Your code should look something like this:

 public abstract void newArray(int size) {
     arrayObject = array = new Foo[size];
 }
 

makeRoomFor

public void makeRoomFor(int roomNeeded)

Standard array enlarger; determines a reasonable minimumIncrease factor then calls makeRoomFor(int, int).

This is fairly aggressive on sizing by default; you can modify its behavior via the tuning parameters fastGrowthFactor, fastGrowthLimit, and slowGrowthAmount. As long as capacity is less than fastGrowthLimit, it will call makeRoomFor(int, int) with a minimumIncrease value equal to fastGrowthFactor * capacity. Once fastGrowthLimit is reached, it uses a minimumIncrease of slowGrowthAmount.

Otherwise, it calls and therefore has the same behavior as makeRoomFor(int, int); see that method for a full description of the affect on this array.

makeRoomFor

public void makeRoomFor(int roomNeeded,
                        int minimumIncrease)

This method ensures that there is enough unused capacity in the array to fill with the given number of items.

Unless you have some specific growth algorithm you want to use that differs from the default fast/slow growth model, you should use the makeRoomFor(int) method instead of this one. You can tune it using the fastGrowthFactor, fastGrowthLimit, and slowGrowthAmount properties.

The current contents are preserved, though they may be moved to the beginning of the buffer if necessary.

If there is already enough room (capacity - end - 1 > roomNeeded) nothing is done. Otherwise, it tries to make enough room first by moving the contents to the beginning and then enlarging the buffer if more room is still needed. The minimumIncrease parameter is used to prevent microgrowage - e.g. you don't want to add 1000 items to an array by expanding the array capacity by 1 each time.

Depending on what has to be done, the array, arrayObject, start, end, and capacity variables may all change.

pack

public void pack()

Packs the array into the minimum space required, throwing out excess capacity. Unless there is nothing to do, this can change the array, arrayObject, capacity, start, and end fields.

tidy

public void tidy()

Moves the contents to the beginning of the array. Unless this is already true, changes the start and end properties.

clear

public void clear()

Clears the contents by setting start and end to zero. Does not cause objects in the unused part of the array to be deallocated! If you really want a clean start, create a new DynamicArray.

size

public int size()

Size of the array contents (end - start).

Returns:

size of the array's contents region.

isEmpty

public boolean isEmpty()

True if size() is zero.

copy

public void copy(int oldIndex,
                 int newIndex,
                 int size)

Copies range of contents to new spot in array. Increases capacity if needed but does not change start or end.

insert

public void insert(int whereAt)

Inserts a slot in the array, copying contents up one. Increments end but does not blank out slot.

Parameters:

whereAt - absolute index to insert before

remove

public void remove(int whereAt)

Removes the item at the given slot in the array, copying contents past that point down by one index. Decrements end.

Parameters:

whereAt - absolute index to remove

subsection

public DynamicArray subsection(int sectionStart,
                               int sectionEnd)

Returns a subsection of the array. Start and end indices are absolute indexes into the array.

copyFrom

public void copyFrom(DynamicArray nother)

Copies the contents from the given array into this one so that the contents are equivalent. The arrays must be of compatible type.

Parameters:

nother -

append

public void append(DynamicArray nother)

Append the contents of the given array onto the end of this one. The arrays must be of compatible type.

Parameters:

nother - array to append

copyTo

public void copyTo(java.lang.Object notherArray)

Exports the contents into the given array. The array must be of compatible type.

Parameters:

notherArray -

copy

public DynamicArray copy()

Returns a copy of this array with the same contents. Result will be of the correct type and have the same contents and size but not necessarily the same capacity, start, end, etc.

copyExactly

public DynamicArray copyExactly()

Returns an exact copy of this array with the same contents, capacity, start, and end. It even copies references or values outside the contents range (start <= i < end).

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object