Skip to content

Instantly share code, notes, and snippets.

@theoperatore
Last active February 28, 2016 20:51
Show Gist options
  • Save theoperatore/5073976 to your computer and use it in GitHub Desktop.
Save theoperatore/5073976 to your computer and use it in GitHub Desktop.
An array that uses a shadow array method to expand the underlying array data structure Should be Constant Time, independent of the size of the arrays
public class ShadowArray<E> implements ShadowArrayInterface<E>{
private E[] k;
private E[] s;
private int numItems;
private int carryIndex;
static final int INIT_SIZE = 5;
@SuppressWarnings("unchecked")
public ShadowArray() {
k = (E[])(new Object[INIT_SIZE]);
s = (E[])(new Object[2*INIT_SIZE]);
numItems = 0;
carryIndex = 0;
}
@SuppressWarnings("unchecked")
public void add(E item) {
//try to add the next item to the end of the array
try {
//if the array isn't full, add the item to both the current array
//and the shadow array
k[numItems] = item;
s[numItems] = item;
//if this is an expanded array, copy down the previous elements
//to the new shadow array
s[carryIndex] = k[carryIndex];
//implement indexes
carryIndex++;
numItems++;
} catch (IndexOutOfBoundsException e) {
//if the current array is full, expand it
//set the current array to the shadow array
//and create a new shadow array with double the length
k = s;
s = (E[])(new Object[2*k.length]);
//return the index to copy to 0
carryIndex = 0;
//add the new item
k[numItems] = item;
s[numItems] = item;
//carry down the first item in the current array
s[carryIndex] = k[carryIndex];
//increment indexes
carryIndex++;
numItems++;
}
}
public class ShadowArray<E> implements ShadowArrayInterface<E>{
private E[] k;
private E[] s;
private int numItems;
private int carryIndex;
static final int INIT_SIZE = 10;
@SuppressWarnings("unchecked")
public ShadowArray() {
k = (E[])(new Object[INIT_SIZE]);
s = (E[])(new Object[2*INIT_SIZE]);
numItems = 0;
carryIndex = 0;
}
@SuppressWarnings("unchecked")
public void add(E item) {
if (numItems >= k.length) {
k = s;
s = (E[])(new Object[2*k.length]);
carryIndex = 0;
k[numItems] = item;
s[numItems] = item;
s[carryIndex] = k[carryIndex];
}
else {
k[numItems] = item;
s[numItems] = item;
s[carryIndex] = k[carryIndex];
}
carryIndex++;
numItems++;
}
@BDGLunde
Copy link

Have you thought about implementing the shadow array method with add(int pos, E item)?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment