Skip to content

Instantly share code, notes, and snippets.

@ClickerMonkey
Created December 12, 2013 15:48
Show Gist options
  • Save ClickerMonkey/7930124 to your computer and use it in GitHub Desktop.
Save ClickerMonkey/7930124 to your computer and use it in GitHub Desktop.
Array class (similar to ArrayList) but with reordering options and automatic downsizing.
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
public class Array<T> implements Iterable<T>
{
public T[] elements;
public int size;
public int downsizeMinimum = 16;
public int downsizeMaintainPercentFree = 25;
public int downsizePercent = 25;
public int downsizeMaintainDurationMillis = 500;
private long downsizeLastFreeTime = 0;
private long downsizeElapsed = 0;
private ArrayIterator iterator = new ArrayIterator();
public Array( T... initialElements )
{
this.elements = initialElements;
}
public Array( int initialCapacity, T... initialElements )
{
this.elements = Arrays.copyOf( initialElements, initialCapacity );
}
public void add( T e )
{
pad( 1 );
elements[size++] = e;
}
public <R extends T> void add( R... e )
{
pad( e.length );
System.arraycopy( e, 0, elements, size, e.length );
size += e.length;
}
public void add( Iterable<? extends T> iterable )
{
for (T e : iterable)
{
add( e );
}
}
public void add( Collection<? extends T> collection )
{
pad( collection.size() );
for (T e : collection)
{
elements[size++] = e;
}
}
public void add( Array<? extends T> array )
{
pad( array.size );
System.arraycopy( array.elements, 0, elements, size, array.size );
size += array.size;
}
public void insert( int i, T e )
{
if (i >= size - 1)
{
add( e );
}
else
{
pad( 1 );
System.arraycopy( elements, i, elements, i + 1, size - i );
elements[i] = e;
size++;
}
}
public T remove( int i )
{
T removed = elements[--size];
elements[size] = null;
if (i < size)
{
System.arraycopy( elements, i + 1, elements, i, size - i );
}
return removed;
}
public T get( int i )
{
return elements[i];
}
public T set( int i, T e )
{
T previous = elements[i];
elements[i] = e;
return previous;
}
public T pop()
{
if (size == 0)
{
return null;
}
T popped = elements[--size];
elements[size] = null;
return popped;
}
public T poll()
{
if (size == 0)
{
return null;
}
T polled = elements[0];
System.arraycopy( elements, 1, elements, 0, --size );
elements[size] = null;
return polled;
}
public void clear()
{
Arrays.fill( elements, 0, size, null );
size = 0;
}
public void swap( int i, int k )
{
T temp = elements[i];
elements[i] = elements[k];
elements[k] = temp;
}
public void reverse()
{
for (int i = 0, k = size - 1; i < k; i++, k--)
{
swap( i, k );
}
}
public void moveFront( int i )
{
if (i > 0)
{
swap( i, i - 1 );
}
}
public void moveToFront( int i )
{
if (i > 0)
{
T newFront = elements[i];
System.arraycopy( elements, 0, elements, 1, i );
elements[0] = newFront;
}
}
public void moveBack( int i )
{
if (i < size - 1)
{
swap( i, i + 1 );
}
}
public void moveToBack( int i )
{
final int back = size - 1;
if (i < back)
{
T newBack = elements[i];
System.arraycopy( elements, i + 1, elements, i, size - i - 1 );
elements[back] = newBack;
}
}
public void pad( int count )
{
if (available() < count)
{
int nextLength = count + (count >> 1);
int minimumLength = size + count;
int chosenLength = Math.max( nextLength, minimumLength );
elements = Arrays.copyOf( elements, chosenLength );
}
}
public int indexOf( T item )
{
return search( 0, size, 1, item );
}
public int indexOf( int start, T item )
{
return search( start, size, 1, item );
}
public int lastIndexOf( T item )
{
return search( size - 1, -1, -1, item );
}
public int lastIndexOf( int start, T item )
{
return search( start, -1, -1, item );
}
private int search( int start, int end, int dir, T item )
{
while (start != end)
{
T e = elements[start];
if (e == item || (e != null && item != null && e.equals( item )))
{
return start;
}
start += dir;
}
return -1;
}
public int count( T item )
{
int total = 0;
int i = indexOf( 0, item );
while (i != -1)
{
total++;
i = indexOf( i + 1, item );
}
return total;
}
public boolean downsize()
{
final int capacity = capacity();
boolean downsize = false;
if (capacity > downsizeMinimum)
{
if (available() * 100 < downsizeMaintainPercentFree * capacity)
{
if (downsizeLastFreeTime == 0)
{
downsizeElapsed = 0;
}
else
{
downsizeElapsed += System.currentTimeMillis() - downsizeLastFreeTime;
}
downsizeLastFreeTime = System.currentTimeMillis();
downsize = (downsizeElapsed >= downsizeMaintainDurationMillis);
}
else
{
downsizeLastFreeTime = 0;
downsizeElapsed = 0;
}
}
if (downsize)
{
int desiredAmount = downsizePercent * capacity / 100;
int chosenLength = Math.max( downsizeMinimum, capacity - desiredAmount );
elements = Arrays.copyOf( elements, chosenLength );
downsizeLastFreeTime = 0;
downsizeElapsed = 0;
}
return downsize;
}
public void sort()
{
Arrays.sort( elements, 0, size );
}
public void sort( Comparator<T> comparator )
{
Arrays.sort( elements, 0, size, comparator );
}
public void compact()
{
elements = Arrays.copyOf( elements, size );
}
public int available()
{
return elements.length - size;
}
public int capacity()
{
return elements.length;
}
public boolean isEmpty()
{
return (size == 0);
}
@Override
public Iterator<T> iterator()
{
return iterator.hasNext() ? new ArrayIterator() : iterator.reset();
}
private class ArrayIterator implements Iterator<T>
{
private int i = 0;
private int previous = -1;
public ArrayIterator()
{
i = Integer.MAX_VALUE;
}
public ArrayIterator reset()
{
i = 0;
return this;
}
@Override
public boolean hasNext()
{
return i < size;
}
@Override
public T next()
{
previous = i;
T next = elements[i];
if (++i == size)
{
i = Integer.MAX_VALUE;
}
return next;
}
@Override
public void remove()
{
Array.this.remove( previous );
if (i == size)
{
i = Integer.MAX_VALUE;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment