Last active
February 28, 2016 20:51
-
-
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
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
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++; | |
} | |
} |
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
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++; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Have you thought about implementing the shadow array method with add(int pos, E item)?