Data access functions: Set, Get, InsertAt, RemoveAt
Dynamic array data structure encapsulates underlying storage, but the interface must provide access functions to work with it. We can also add range check to the access functions.
Range check
There is no much to say about the range check. Algorithm checks, whether index is inside the 0..size-1 range and if not, throws an exception.
Get and set
After we ensured, that index is inside of the proper range, write a value to the storage or read a value from the storage.
InsertAt
This operation may require array expanding, so algorithm invokes ensure capacity method first, which should ensure size + 1 minimal capacity. Then shift all elements from i to size - 1, where i is the insertion position, one element right. Note, that if new element is inserted after the last element in the array, then no shifting required. After shifting, put the value to i-th element and increase size by one.
RemoveAt
Shift all elements from i to size - 1, where i is the removal position, one element left. Then decrease size by 1 and invoke pack opeartion. Packing is done, if there are too few elements left after removal.
Code snippets
Java
public class DynamicArray {
…
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
}
public void set(int index, int value)
{
rangeCheck(index);
storage[index] = value;
}
public int get(int index)
{
rangeCheck(index);
return storage[index];
}
public void removeAt(int index) {
rangeCheck(index);
int moveCount = size - index - 1;
if (moveCount > 0)
System.arraycopy(storage, index + 1, storage, index, moveCount);
size--;
pack();
}
public void insertAt(int index, int value) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
ensureCapacity(size + 1);
int moveCount = size - index;
if (moveCount > 0)
System.arraycopy(storage, index, storage, index + 1, moveCount);
storage[index] = value;
size++;
}
}
C++
#include <cstring>
#include <exception>
void DynamicArray::rangeCheck(int index) {
if (index < 0 || index >= size)
throw "Index out of bounds!";
}
void DynamicArray::set(int index, int value) {
rangeCheck(index);
storage[index] = value;
}
int DynamicArray::get(int index) {
rangeCheck(index);
return storage[index];
}
void DynamicArray::removeAt(int index) {
rangeCheck(index);
int moveCount = size - index - 1;
if (moveCount > 0)
memmove(storage + index, storage + (index + 1), sizeof(int) * moveCount);
size--;
pack();
}
void DynamicArray::insertAt(int index, int value) {
if (index < 0 || index > size)
throw "Index out of bounds!";
ensureCapacity(size + 1);
int moveCount = size - index;
if (moveCount != 0)
memmove(storage + index + 1, storage + index, sizeof(int) * moveCount);
storage[index] = value;
size++;
}
|
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!