Created
December 12, 2013 15:48
-
-
Save ClickerMonkey/7930124 to your computer and use it in GitHub Desktop.
Array class (similar to ArrayList) but with reordering options and automatic downsizing.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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