Created
June 23, 2021 08:50
-
-
Save legendmohe/a1b1e3c7d10f5c464122dd78ffd2e8d0 to your computer and use it in GitHub Desktop.
SparseIntArray in Java
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 SparseIntArray<T> { | |
/* Define Object DELETED */ | |
private static final Object DELETED = new Object(); | |
/* Flag for garbage collection */ | |
private boolean garbage = false; | |
/* Default Capacity */ | |
private static final int DEFAULT_CAPACITY = 10; | |
/* Variables for keys, values and size */ | |
private int[] keys; | |
private Object[] values; | |
private int size; | |
/** | |
* Constructor | |
*/ | |
public SparseIntArray() { | |
this(DEFAULT_CAPACITY); | |
} | |
/** | |
* Constructor | |
* | |
* @param initialCapacity | |
*/ | |
public SparseIntArray(int initialCapacity) { | |
if (initialCapacity == 0) { | |
keys = new int[0]; | |
values = new Object[0]; | |
} else { | |
values = new Object[initialCapacity]; | |
keys = new int[values.length]; | |
} | |
size = 0; | |
} | |
/** | |
* Method to get the value associated with the key | |
* | |
* @param key | |
* @return {@link T} | |
*/ | |
public T get(int key) { | |
return get(key, null); | |
} | |
/** | |
* Method to get the value associated with the key, | |
* If not found, return default value specified | |
* | |
* @param key | |
* @param valueIfKeyNotFound | |
* @return {@link T} | |
*/ | |
@SuppressWarnings("unchecked") | |
public T get(int key, T valueIfKeyNotFound) { | |
int i = binarySearch(keys, size, key); | |
if (i < 0 || values[i] == DELETED) { | |
return valueIfKeyNotFound; | |
} else { | |
return (T) values[i]; | |
} | |
} | |
/** | |
* Method to add the key and value in sparse array | |
* | |
* @param key | |
* @param value | |
*/ | |
public void put(int key, T value) { | |
int i = binarySearch(keys, size, key); | |
if (i >= 0) { | |
values[i] = value; | |
} else { | |
i = ~i; | |
if (i < size && values[i] == DELETED) { | |
keys[i] = key; | |
values[i] = value; | |
return; | |
} | |
if (garbage && size >= keys.length) { | |
performGC(); | |
i = ~binarySearch(keys, size, key); | |
} | |
keys = insert(keys, size, i, key); | |
values = insert(values, size, i, value); | |
size++; | |
} | |
} | |
/** | |
* Method to delete a Key value pair for a key | |
* | |
* @param key | |
*/ | |
public void delete(int key) { | |
int i = binarySearch(keys, size, key); | |
if (i >= 0) { | |
if (values[i] != DELETED) { | |
values[i] = DELETED; | |
garbage = true; | |
} | |
} | |
} | |
/** | |
* Method to remove a Key value pair for a key | |
* | |
* @param key | |
*/ | |
public void remove(int key) { | |
delete(key); | |
} | |
/** | |
* Method to remove the value at index | |
* | |
* @param index | |
*/ | |
public void removeAt(int index) { | |
if (values[index] != DELETED) { | |
values[index] = DELETED; | |
garbage = true; | |
} | |
} | |
/** | |
* Method to get the key at index | |
* | |
* @param index | |
* @return {@int key} | |
*/ | |
public int keyAt(int index) { | |
if (garbage) { | |
performGC(); | |
} | |
return keys[index]; | |
} | |
/** | |
* Method to find the value at index | |
* | |
* @param index | |
* @return {@link T} | |
*/ | |
@SuppressWarnings("unchecked") | |
public T valueAt(int index) { | |
if (garbage) { | |
performGC(); | |
} | |
return (T) values[index]; | |
} | |
/** | |
* Method to set the value at given index | |
* | |
* @param index | |
* @param value | |
*/ | |
public void setValueAt(int index, T value) { | |
if (garbage) { | |
performGC(); | |
} | |
values[index] = value; | |
} | |
/** | |
* Method to clear | |
*/ | |
public void clear() { | |
int n = size; | |
Object[] valArray = values; | |
for (int i = 0; i < n; i++) { | |
valArray[i] = null; | |
} | |
size = 0; | |
garbage = false; | |
} | |
/** | |
* Method to find size of the array | |
* | |
* @return {@link int} | |
*/ | |
public int size() { | |
if (garbage) { | |
performGC(); | |
} | |
return size; | |
} | |
/** | |
* Method to check if array is empty | |
* | |
* @return {@link boolean} | |
*/ | |
public boolean isEmpty() { | |
return size == 0; | |
} | |
/** | |
* Method to perform GC | |
*/ | |
private void performGC() { | |
int n = size; | |
int position = 0; | |
int[] keyArray = keys; | |
Object[] valArray = values; | |
for (int i = 0; i < n; i++) { | |
Object val = valArray[i]; | |
if (val != DELETED) { | |
if (i != position) { | |
keyArray[position] = keyArray[i]; | |
valArray[position] = val; | |
valArray[i] = null; | |
} | |
position++; | |
} | |
garbage = false; | |
size = position; | |
} | |
} | |
/** | |
* Method to insert an element at a given index | |
* | |
* @param array | |
* @param currentSize | |
* @param index | |
* @param element | |
* @return {@link Object[]} | |
*/ | |
private Object[] insert(Object[] array, int currentSize, int index, T element) { | |
assert currentSize <= array.length; | |
if (currentSize + 1 <= array.length) { | |
System.arraycopy(array, index, array, index + 1, currentSize - index); | |
array[index] = element; | |
return array; | |
} | |
Object[] newArray = new Object[currentSize * 2]; | |
System.arraycopy(array, 0, newArray, 0, index); | |
newArray[index] = element; | |
System.arraycopy(array, index, newArray, index + 1, array.length - index); | |
return newArray; | |
} | |
/** | |
* Method to insert an integer at given index | |
* | |
* @param array | |
* @param currentSize | |
* @param index | |
* @param element | |
* @return {@link int[]} | |
*/ | |
private static int[] insert(int[] array, int currentSize, int index, int element) { | |
assert currentSize <= array.length; | |
if (currentSize + 1 <= array.length) { | |
System.arraycopy(array, index, array, index + 1, currentSize - index); | |
array[index] = element; | |
return array; | |
} | |
int[] newArray = new int[currentSize * 2]; | |
System.arraycopy(array, 0, newArray, 0, index); | |
newArray[index] = element; | |
System.arraycopy(array, index, newArray, index + 1, array.length - index); | |
return newArray; | |
} | |
/** | |
* Method to do a binary search on int array | |
* | |
* @param array | |
* @param size | |
* @param value | |
* @return {@link int} | |
*/ | |
public static int binarySearch(int[] array, int size, int value) { | |
int lo = 0; | |
int hi = size - 1; | |
while (lo <= hi) { | |
final int mid = (lo + hi) >>> 1; | |
final int midVal = array[mid]; | |
if (midVal < value) { | |
lo = mid + 1; | |
} else if (midVal > value) { | |
hi = mid - 1; | |
} else { | |
return mid; | |
} | |
} | |
return ~lo; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment