/************************************************************************
* File: ExtendibleArray.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of the List interface backed by a variant of the
* ArrayList. Internally, ArrayList works by maintaining a dynamic
* array of elements that doubles in size whenever the capacity is
* exhausted and more space must become available. This gives insert
* an amortized cost O(1), but any individual operation may take O(n)
* time to complete. In some situations, this is unacceptably slow,
* either from a practical or a theoretical perspective.
*
* The implementation used in this ExtendibleArray class is similar
* to the ArrayList, except with a worst-case guarantee of O(1) for
* lookup, size, add-to-end, and remove-from-end. Addition or
* removal in the middle of the list still takes O(n).
*
* The main difference in the implementation is that while the ArrayList
* mathematically amortizes the cost of a copy across the elements
* (by making each insert contribute to future resize operations),
* the ExtendibleArray class amortizes the cost explicitly by copying
* the elements from the old array into the new one lazily as future
* elements are inserted. For example, suppose that we have an array
* of size four and that we need to insert the element 5. Initially
* we have this setup:
*
* [1] [2] [3] [4]
*
* Next, we allocate a new array twice the size of the old one, but
* we still keep the old one around, as seen here:
*
* [1] [2] [3] [4]
* [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
*
* Next, we insert the element five into the new array. We also copy
* the element four over from the previous array, as seen here:
*
* [1] [2] [3] [ ]
* [ ] [ ] [ ] [4] [5] [ ] [ ] [ ]
*
* If we then insert a new element, we append it to the new array and
* copy yet another element from the old array to the new:
*
* [1] [2] [ ] [ ]
* [ ] [ ] [3] [4] [5] [6] [ ] [ ]
*
* If we keep this up over time, eventually the new array becomes filled:
*
* [ ] [ ] [ ] [ ]
* [1] [2] [3] [4] [5] [6] [7] [8]
*
* Now, when we need to double the size of the array again, we can
* discard the older array, use the bigger array as the old array, and
* put a new array up in front:
*
* [1] [2] [3] [4] [5] [6] [7] [ ]
* [ ] [ ] [ ] [ ] [ ] [ ] [ ] [8] [9] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
*
* Internally, this structure maintains the two arrays, along with two
* pointers, "end," which points to the first unused spot in the new
* array, and "shadow," which points to the last element of the old array
* that hasn't yet been transferred:
*
* [1] [2] [ ] [ ]
* [ ] [ ] [3] [4] [5] [6] [ ] [ ]
* ^ ^
* | |
* shadow end
*
* Whenever we insert an element, we add it to the spot marked with "end,"
* move the element marked by "shadow" from the old array to the new.
* We then march each pointer outward one step.
*
* When removing an element, we run this process backward, moving the
* appropriate pointers inward, then copying an element back to the
* old array if necessary. However, at some point we may find that
* we've removed every element from the new array. If this happens,
* we'll find that the shadow and end pointers cross. We can then
* move the old array to the new array and then put a dummy array
* holding all null behind it. For example, after removing the
* last element in this setup:
*
* [1] [2] [3] [ ]
* [ ] [ ] [ ] [4] [5] [ ] [ ] [ ]
* ^ ^
* | |
* shadow end
*
* We would arrive at this configuration:
*
* [ ] [ ]
* [1] [2] [3] [4]
* ^ ^
* | |
* shadow end
*
* There is one major edge case to consider - what happens when we
* first create the structure? In that case, we don't have an old
* array, and so none of this logic will make sense. We'll address
* this by initially creating the new array as a singleton array
* holding null. This means that our array will carry around a
* dummy null element the whole time, but the total overhead only
* ends up being O(1).
*/
import java.util.*; // For AbstractList
@SuppressWarnings("unchecked") // Array typecasting
public final class ExtendibleArray<T> extends AbstractList<T> {
/* Initially, the old array is null and the new array is a singleton
* that holds null.
*/
T[] mOld = null;
T[] mNew = (T[]) new Object[1];
/* The shadow and end pointers need to point to the next write location
* and the spot right before the last element that was pulled up.
* This is shown here:
*
* [X]
* ^ ^
* | |
* shadow end
*
* This means that mShadow is -1 and mEnd is +1. On the very first
* insert, this will get converted to
*
* [ ]
* [X] [*]
* ^ ^
* | |
* shadow end
*
* And from here things can proceed as usual.
*/
int mShadow = -1;
int mEnd = +1;
/**
* Adds a new element to the ExtendibleArray, possibly allocating a new
* array if necessary.
*
* @param elem The element to add.
* @return true
*/
@Override
public boolean add(T elem) {
/* First, check whether we need to do a reallocation. This is true
* if the end pointer is past the end of the new array.
*/
if (mEnd == mNew.length) {
/* Drop the old buffer. The new buffer becomes the old
* buffer and a fresh buffer is made.
*/
mOld = mNew;
mNew = (T[]) new Object[mNew.length * 2];
/* The end position stays put, since it's telling us where the
* next write location is. The shadow pointer now is right
* before the end pointer.
*/
mShadow = mEnd - 1;
}
/* Write the element in its proper place. */
mNew[mEnd] = elem;
/* Pull from the old array into the new, then null out the old spot
* to place nicely with the garbage collector.
*/
mNew[mShadow] = mOld[mShadow];
/* Move the two pointers outward. */
++mEnd; --mShadow;
/* By contract, must return true. */
return true;
}
/**
* Returns the element in the ExtendibleArray at the specified position,
* throwing an IndexOutOfBoundsException if there is no element at that
* position.
*
* @param index The index to query.
* @return The element at that index.
* @throws IndexOutOfBoundsException If index is invalid.
*/
@Override
public T get(int index) {
/* Check that the index is valid. */
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException("Index " + index + ", size " + size());
/* Now, there are two places we might need to look. If index is
* at or below the shadow point, we read from the old array.
* Otherwise, read from the new array. However, we have to be
* careful, because the raw index is not the true index into the
* structure because of the dummy element, so we bump the user
* index by one first.
*/
return (index + 1 <= mShadow) ? mOld[index + 1] : mNew[index + 1];
}
/**
* Returns the size of the ExtendibleArray.
*
* @return The size of the ExtendibleArray.
*/
@Override
public int size() {
/* The size of the array is marked by the mEnd pointer. However,
* because of the dummy element, we need to subtract one from that
* value.
*/
return mEnd - 1;
}
/**
* Sets the value of the element at the particular index to be the
* client-specified value. If the index is out of bounds, an
* IndexOutOfBoundsException will be thrown.
*
* @param index The index of the element to set.
* @param value The new value to write.
* @return The value of that element before the write.
* @throws IndexOutOfBoundsException If the index is invalid.
*/
@Override public
T set(int index, T value) {
/* Cache the old value. This call to get also checks that the index
* is in bounds.
*/
T originalValue = get(index);
/* Write to the appropriate array. */
if (index + 1 <= mShadow)
mOld[index + 1] = value;
else
mNew[index + 1] = value;
/* Return the old value. */
return originalValue;
}
/**
* Removes the element in the specified position from the list, throwing
* an IndexOutOfBoundsException if the index is invalid.
*
* @param index The index of the element to remove.
* @return The value of the removed element.
* @throws IndexOutOfBoundsException If the index is invalid.
*/
@Override public
T remove(int index) {
/* Grab the value of the element we're removing; this also verifies
* the index.
*/
T result = get(index);
/* Removing an element from the array is tricky because we have to
* maintain the invariant that there are an even number of elements
* in the new array and that they are in the central elements.
* There are two cases we need to consider.
*
* 1. The element to remove is in the new array. We need to remove
* two elements from this array, one that actually got deleted
* and one that needs to be moved back to the old array. We'll
* do a standard shuffle-down algorithm to cover up the element
* that was deleted, then we'll move the oldest element down.
* 2. The element to remove is in the old array. We need to move
* two elements from the new array down into the old one. To
* do this, we'll do the standard array shuffle-down algorithm
* on the old array, then will copy the first two elements of
* the new array into the old. Finally, we shuffle the remaining
* elements of the new array down one spot.
*
* After doing this step, we'll need to determine whether or not
* to do a rebalance by tossing out the new list and swapping the
* old list forward.
*/
if (index + 1 > mShadow) { // In the new array
/* Scoot the elements past this element down on top of the
* element itself. The number of elements to copy is given
* by the number of elements between mEnd - 1 (the last element)
* and index + 1 (the element to delete)
*/
System.arraycopy(mNew, index + 2, mNew, index + 1,
(mEnd - 1) - (index + 1));
/* Move the element before the shadow down. */
mOld[mShadow + 1] = mNew[mShadow + 1];
/* To be nice to the garbage collector, clear the endpoints. */
mNew[mEnd - 1] = null;
mNew[mShadow + 1] = null;
/* Pull the shadow and endpoint closer together. */
++mShadow; --mEnd;
} else { // In old array
/* Shuffle down the elements in the old array to cover the
* element that was removed. The math is similar to above.
*/
System.arraycopy(mOld, index + 2, mOld, index + 1,
mShadow - (index + 1));
/* Move the last two elements of the new array into the old one.
* Recall that mShadow points to the last unshadowed element in
* the old array, and so we'll copy from one spot past there
* in the new array.
*/
for (int i = 0; i < 2; ++i) {
mOld[mShadow + i] = mNew[mShadow + 1 + i];
mNew[mShadow + 1 + i] = null; // Place nice with the GC
}
/* The new shadow point is one step past where it once was,
* since we just pulled two elements down, but lost an
* old element.
*/
++mShadow;
/* Shuffle the elements of the new array down one position.
* The beginning position is one past the shadow, as it always
* is.
*/
System.arraycopy(mNew, mShadow + 2, mNew, mShadow + 1,
mEnd - mShadow - 1);
/* Clear the element that just got moved. */
mNew[mEnd - 1] = null;
/* Back up the end position, since we just lost an element. */
--mEnd;
}
/* Finally, see if we just emptied the new array. This happens if
* the end pointer is one step past the shadow pointer.
*/
if (mEnd == mShadow + 1) {
/* Drop the new array and promote the old array to new. */
mNew = mOld;
/* Make a blank array for new elements. */
mOld = (T[]) new Object[mNew.length / 2];
/* Move the end and shadow pointers off the ends of the array. */
mShadow = -1;
mEnd = mNew.length;
}
return result;
}
/**
* Adds the specfied element to the ExtendibleArray at the specified
* position, increasing the size by one.
*
* @param index The index before which to insert.
* @param elem The value of the element to insert.
* @throws IndexOutOfBoundsException If index is invalid.
*/
@Override
public void add(int index, T elem) {
/* Bounds-check. */
if (index < 0 || index > size())
throw new IndexOutOfBoundsException("Index " + index + ", size " + size());
/* Begin by throwing the element on the end, which will do all of the
* tricky balancing work.
*/
add(elem);
/* Now, we need to put the element in its proper position. This
* requires us to check whether the element is in the new or old
* array. If it's in the new array, we just scoot everything
* down and put it in its proper place. Otherwise, we have to
* scoot the whole new array down a spot, then push the old array
* elements over, then drop the new element in.
*/
if (index + 1 > mShadow) { // New array
/* The number of elements to copy is the number of old elements
* after the insert point, which is given by
* (mEnd - 2) - (index + 1)
*/
System.arraycopy(mNew, index + 1,
mNew, index + 2,
(mEnd - 2) - (index + 1));
mNew[index + 1] = elem;
} else { // Old array
/* Shuffle all the new elements down one spot. */
System.arraycopy(mNew, mShadow + 1,
mNew, mShadow + 2,
(mEnd - 2) - (mShadow + 1));
/* Shuffle all the old elements down one spot. */
System.arraycopy(mOld, index + 1,
mOld, index + 2,
(mShadow - (index + 1)) + 1);
/* Drop the element in its place. */
mOld[index + 1] = elem;
/* Promote last element of the list. It will be at position
* shadow + 1, since we just pushed past the end of the shadow.
*/
mNew[mShadow + 1] = mOld[mShadow + 1];
mOld[mShadow + 1] = null;
}
}
}