com.scottlogic.util
Class PatchWorkArray<T>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<T>
          com.scottlogic.util.PatchWorkArray<T>

Type Parameters:

T - The type of element that this list should store.

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.List<T>

Direct Known Subclasses:

AutoFixingPatchWorkArray

public class PatchWorkArray<T>
extends java.util.AbstractList<T>
implements java.io.Serializable

List implementation which is backed by an ArrayList and performs lazy insertions and removals

This implementation is not synchronised so if you need multi-threaded access then consider wrapping it using the Collections.synchronizedList(java.util.List) method.

The iterators this list provides are fail-fast, so any structural modification, other than through the iterator itself, cause it to throw a ConcurrentModificationException.

Version:

1.0

Author:

Mark Rhodes

See Also:

List, Collection, ArrayList, Serialized Form

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

PatchWorkArray()
Creates a new PatchWorkArray backed by an ArrayList with an initial capacity of ten.

PatchWorkArray(int initialCapacity)
Creates a new PatchWorkArray backed by an ArrayList with the given initial capacity.

Method Summary

void	add(int index, T obj) Inserts the specified element at the specified position in this list.
boolean	add(T obj) Adds the given object to the end of this PatchWorkArray.
void	clear() Removes all elements and alterations from this PatchWorkArray.
void	fix() Pushes all the alterations in this PatchWorkArray to the backing list, leaving the number of alterations as zero.
T	get(int index) Obtains the element at the given index in this PatchWorkArray.
int	getPerformanceHit() The performance hit caused by the Alterations to the backingList of this PatchWorkArray.
java.util.Iterator<T>	iterator() Returns an iterator which allows the list to be iterated over in O(a + n), where a is the number of alterations and n is the number of elements in this PatchWorkArray.
T	remove(int index) Removes and returns the element at the given index in this PatchWorkArray.
int	size() Returns the number of elements in this PatchWorkArray.

Methods inherited from class java.util.AbstractList

addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, set, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.List

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

PatchWorkArray

public PatchWorkArray()

Creates a new PatchWorkArray backed by an ArrayList with an initial capacity of ten.

PatchWorkArray

public PatchWorkArray(int initialCapacity)

Creates a new PatchWorkArray backed by an ArrayList with the given initial capacity.

Method Detail

get

public T get(int index)

Obtains the element at the given index in this PatchWorkArray. Note that indices are numbered from zero through to #size()-1.

This implementation works in time O(log(d)), where d is the number of alterations in the list.

Specified by:

get in interface java.util.List<T>

Specified by:

get in class java.util.AbstractList<T>

Returns:

the elements at the given index in this PatchWorkArray.

size

public int size()

Returns the number of elements in this PatchWorkArray.

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in interface java.util.List<T>

Specified by:

size in class java.util.AbstractCollection<T>

Returns:

the number of elements in this PatchWorkArray.

add

public boolean add(T obj)

Adds the given object to the end of this PatchWorkArray. This implementation forbids null values from being added, an IllegalArgumentException is thrown in the case that this is attempted.

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.List<T>

Overrides:

add in class java.util.AbstractList<T>

Parameters:

obj - the object to add to the list.

Returns:

true if the operation to insert the element was successful.

Throws:

java.lang.IllegalArgumentException - in the case that the given element is null.

getPerformanceHit

public int getPerformanceHit()

The performance hit caused by the Alterations to the backingList of this PatchWorkArray. The time it takes to perform the operations: get, remove, add is the log of this value.

Returns:

the effective hit in performance caused by the alterations to the backingList of this PatchWorkArray.

iterator

public java.util.Iterator<T> iterator()

Returns an iterator which allows the list to be iterated over in O(a + n), where a is the number of alterations and n is the number of elements in this PatchWorkArray.

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in interface java.util.List<T>

Overrides:

iterator in class java.util.AbstractList<T>

Returns:

an Iterator for iterating elements of this list.

add

public void add(int index,
                T obj)

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

If the given index is the current size of the list, the #add(Object) method is invoked, otherwise the element is lazily added and the number of alterations is incremented.

Specified by:

add in interface java.util.List<T>

Overrides:

add in class java.util.AbstractList<T>

Parameters:

index - at which the element should be added.

obj - the object to by inserted.

Throws:

java.lang.IllegalArgumentException - in the case that the given element is null.

java.lang.IndexOutOfBoundsException - in the case that (0 <= index <= size()) does not hold.

fix

public void fix()

Pushes all the alterations in this PatchWorkArray to the backing list, leaving the number of alterations as zero.

This method performs structural changes to the list and hence increments the modCount of the list.

clear

public void clear()

Removes all elements and alterations from this PatchWorkArray.

Specified by:

clear in interface java.util.Collection<T>

Specified by:

clear in interface java.util.List<T>

Overrides:

clear in class java.util.AbstractList<T>

remove

public T remove(int index)

Removes and returns the element at the given index in this PatchWorkArray.

This method can increase or decrease the number of alterations, depending on the element on which it is called.

Specified by:

remove in interface java.util.List<T>

Overrides:

remove in class java.util.AbstractList<T>

Parameters:

index - the index of the element to remove.

Returns:

the element which was removed from the list.

Throws:

java.lang.IllegalArgumentException - in the case that the index is not a valid index.