Generally, we would use a std::vector<std::vector> data structure, to hold a matrix, say a 3x3 matrix. Though, here what we will be creating is a custom Matrix class, using nodes and `pointers`.
Possible Use Case ->
- You need a matrix, that may expand and compress many times
In this case, using
vector<vector>will cause memory allocations that may require whole copy of the matrix to a new location, this can be big overhead when working with large matrices - Equal/Controlled expansion on particular/all sides of the matrix,
This will likely be not what you need to do, generally, but here we are taking a look for interest. In this also,
vector<vector>may need frequent copies of whole matrix to new array (almost always actually in this case)
Since, we have talked of possible use case, you may proceed on basis of interest to do this, or have a good read 😃
Trade Off -> Element access using coordinates will not be O(1)
A 2D Matrix is inherently a graph, with each node connected to four adjacent node
- The Nodes So, first we need a node class,
template<typename T> // don't worry if not very familiar with templates
class Graph_Node{
T data; /* Here additional data of any type T can be stored, can be another struct too ! */
Graph_Node* right;
Graph_Node* left;
Graph_Node* up;
Graph_Node* down;
}- The Matrix class
This matrix class will be the actual one that you will be instantiating to have the matrix
And the Matrix class can be this, we can have that (0,0) position by default as
origin(which will be a Node as per our design)
template<typename T> // don't worry if not very familiar with templates
class Matrix{
Graph_Node<T> origin;
}- We are just adding data members here, member functions need to be added, and not really bothered with access specifiers (public, private, protected) Let's add more data members, our matrix class should hold its size too ? So lets have n_rows, and n_cols for number of rows and columns respectively Also, for a better realisation of the corners we will have 4 pointers in the Matrix class ->
template<typename T>
class Matrix{
Graph_Node<T> origin;
Graph_Node<T>* tl_corner, bl_corner, tr_corner, tl_corner; // t is for 'top', b for 'bottom', 'l' for left, and 'r' for right
long n_cols, n_rows; // number of columns, and number of rows
}For most functionality, these are the ones needed data members. There's more possibilities like storing another temporary node pointer for a better access (O(1)) of adjacent elements in the graph, for more you can checkout the Github link at the end of this article.
- Adding push and pop functionality, for rows and columns
So now, here is where we utilize the data members,
Let's first see, how it is logically done ->
You will mostly need to add a row at the bottom of the matrix (at row number = n_rows),
for that, what we can do is
1. Initialise a temporary node with the bottom left corner (bl_corner)
2. Initialise bl_left->down = new Graph_Node;
3. Do step 2, for each temp node, iterating rightwards to the bl_left (ie. using temp = temp->right)
4. Also, we will need to do temp->down->right->left = temp->down; (ie. to set ourselves as the neighbour of the new node)
Hope you got it, if some confusion is left, put it down in the comments, for now lets proceed with the code ->
void Graph_Matrix<T>::pushRow(){ // add a row at downward end
bl_box->down = new Graph_Node<T>;
bl_box->down->up = bl_box;
Graph_Node<T>* prev_new_box = bl_box->down; // a simpler way to `temp->down`
Graph_Node<T>* last_row_iter = bl_box->right != nullptr ? bl_box->right : br_box; // to iterator in last column
dimen_t count{1};
while( last_row_iter != br_box ){
// we also have to initialise the left, right, down pointers of the new node
last_row_iter->down = new Graph_Node<T>;
last_row_iter->down->up = last_row_iter;
last_row_iter->down->left = prev_new_box;
prev_new_box->right = last_row_iter->down;
prev_new_box = last_row_iter->down;
last_row_iter = last_row_iter->right;
}
if( br_box != bl_box ){
br_box->down = Graph_Node<T>;
prev_new_box->right = br_box->down;
prev_new_box->right->left = prev_new_box;
br_box->down->up = br_box;
br_box->down->left = prev_new_box;
}
bl_box = bl_box->down;
br_box = br_box->down; // new bottom right
++n_rows;
}Similar logic is applied for pushColumn, or to push Rows at the top(aka. injectRow()), and columns at left end (aka. injectCol()) of matrix (logically). All you need to think of it is that iterate through a particular column and row, and keep initialising the pointers of each For the detailed code, the github repo can be explored :D
Now, let's talk about another functionality, removing the rows and columns (calling it popRow and popCol)
Let's first see, how we logically remove the last column done ->
You will mostly need to add a row at the bottom of the matrix (at row number = n_rows),
for that, what we can do is
1. Initialise a temporary node with the top_right corner (tr_corner)
2. Iterate through the last column, using temp->down
3. Then for each node you iterate through, delete the temp->up Node (moving downward, keep removing the node you came from)
* We will be managing the edge cases too
* You can also iterate through the second last column, while deleting the right pointers to them, for popping the rightmost column
Again, if you face any problem, or require a clarification, you can utilize the comment box, I will be happy to help with the logic at the least, so here's the code,
void Matrix<T>::popCol(){
if( this->tr_box == this->tl_box ) return; //don't pop out the origin column (x=0)
Graph_Node<T>* temp = this->tr_box;
this->tr_box = this->tr_box->left;
// we have to clear the down pointers of this->tr_box here
while( temp != this->br_box ){
temp->left->right = nullptr;
temp = temp->down;
delete temp->up; //deleting the node we came from
};
this->br_box = this->br_box->left;
delete this->br_box->right;
this->br_box->right = nullptr;
--n_cols;Well, the most basic functionality is done, to get it to work for you (No SEG faults, the pointers are well managed hooray :D) More can be added like path finding algorithms.
You may have noticed, that though it might have took some work.
But here in our matrix, the expansion and column are O(N), and don't cause the overhead of complete copy of a matrix, as in the case of std::vector<std::vector<T>>.
Want to see sample use, see the worldLine simulator -> github.com/AdityaGupta150/worldLineSimulator
All Code in this, and more is available at -> github.com/AdityaGupta150/worldLineSimulator/tree/master/graphMat
- Explore the graph_mat.hpp for the function definitions.