A linked list class. Define a spare array. Useful when there is few data on a wide array. In this case, we can save a lot of memory. Also contain an internal iterator.
Author: Aidin Gharibnavaz
Constructors |
SpareArray(int i,
int j)
Create an empty ixj array.
Methods |
int add(Type data, int i, int j)
Add a node with 'data' value to the (i,j) position. Return -1 on error, 0 otherwise.
int remove(int i, int j)
Remove node from (i,j). Return 0 on success, -1 otherwise.
int move(int i, int j,int dir)
Move node at (i,j) position to the given direction. 'dir' can be NORTH, SOUTH, WEST or EAST. Related ints for directions can be found at 'constants.hpp'
int isEmpty(int i, int j)
Return 0 if there's a node in the given position, 1 otherwise.
vector<int> getSize()
Return size of the array. vector.at(0) is the length and vector.at(1) is the width.
Type get(int i, int j)
Return 'value' of the node in (i,j) position. Return an uninitialized Type on error.
Type* getReference(int i, int j)
Return a reference to the 'value' of the node in (i,j) position. Return zero pointer on error.
void startIterator()
Set 'current' to the 'first'. Should be call before iterating. Also reset the iterator and start it over.
Type* next()
Return value of the next node in the array. Will return 0 when reach the end of the array.
int nextIsAvailable()
Return 0 if iterator reach the end of the array. Return 1 otherwise.
int moveCurrent(int dir)
Move the 'current' node (returned by the iterator) to the specific direction.
vector<int> getCurrentPosition()
Return the position of the 'current' node (returned by the iterator). vector.at(0) is i (row), vector.at(1) is j (column).
How it works? |
Each node in the array consist of four parts: 'i' and 'j' which holds position of this node in the array. 'i' is the row and 'j' is the column. 'nextHead' which points to the next 'headNode' (beginning of the next row). 'next' which points to the next node in the current row.
'first' is the start of the SpareArray. 'first' is hold size of the array in its 'i' and 'j'. For each row, there's a 'headNode'. 'i' of a 'headNode' is zero. 'nextHead' is point to the next 'headNode' (next row) and 'next' is point to the first node in that row. Last node in a row points to the next 'headNode' and last 'headNode' points to the first 'headNode'.
