// Sparse Array Assignment.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct node{
int row;
int col;
int value;
node* next_in_row;
node* next_in_col;
};
class MultiLinkedListSparseArray {
private:
char *logfile;
node** rowPtr;
node** colPtr; // used in constructor
node* find_node(node* out);
node* ins_node(node* ins,int col);
node* in_node(node* ins,node* z);
node* get(node* in,int row,int col);
bool exist(node* so,int row,int col);
node* dummy;
int rowd,cold;
//add anything you need
public:
MultiLinkedListSparseArray(int rows, int cols);
~MultiLinkedListSparseArray();
void setCell(int row, int col, int value);
int getCell(int row, int col);
void display();
void log(char *s);
void dump();
};
MultiLinkedListSparseArray::MultiLinkedListSparseArray(int rows,int cols){
rowPtr=new node* [rows+1];
colPtr=new node* [cols+1];
for(int n=0;n<=rows;n++)
rowPtr[n]=NULL;
for(int i=0;i<=cols;i++)
colPtr[i]=NULL;
rowd=rows;cold=cols;
}
MultiLinkedListSparseArray::~MultiLinkedListSparseArray(){
cout<<"array is deleted"<<endl;
for(int i=rowd;i>=0;i--){
for(int j=cold;j>=0;j--){
if(exist(rowPtr[i],i,j))
delete get(rowPtr[i],i,j);
}
} // it stops in the last loop & doesnt show the done word
cout<<"done"<<endl;
delete [] rowPtr;
delete [] colPtr;
delete dummy;
}
void MultiLinkedListSparseArray::log(char *s){
logfile=s;
}
void MultiLinkedListSparseArray::setCell(int row,int col,int value){
if(exist(rowPtr[row],row,col)){
(*get(rowPtr[row],row,col)).value=value;
}
else{
if(rowPtr[row]==NULL){
rowPtr[row]=new node;
(*rowPtr[row]).value=value;
(*rowPtr[row]).row=row;
(*rowPtr[row]).col=col;
(*rowPtr[row]).next_in_row=NULL;
(*rowPtr[row]).next_in_col=NULL;
}
else if((*find_node(rowPtr[row])).col<col){
node* out;
out=find_node(rowPtr[row]);
(*out).next_in_row=new node;
(*((*out).next_in_row)).col=col;
(*((*out).next_in_row)).row=row;
(*((*out).next_in_row)).value=value;
(*((*out).next_in_row)).next_in_row=NULL;
}
else if((*find_node(rowPtr[row])).col>col){
node* ins;
ins=in_node(rowPtr[row],ins_node(rowPtr[row],col));
node* g=(*ins).next_in_row;
(*ins).next_in_row=new node;
(*((*ins).next_in_row)).col=col;
(*(*ins).next_in_row).row=row;
(*(*ins).next_in_row).value=value;
(*(*ins).next_in_row).next_in_row=g;
}
}
}
int MultiLinkedListSparseArray::getCell(int row,int col){
return (*get(rowPtr[row],row,col)).value;
}
void MultiLinkedListSparseArray::display(){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
if(exist(rowPtr[i],i,j))
cout<<(*get(rowPtr[i],i,j)).value<<" ";
else cout<<"0"<<" ";
}
cout<<endl;
}
}
node* MultiLinkedListSparseArray::find_node(node* out)
{
while((*out).next_in_row!=NULL)
out=(*out).next_in_row;
return out;
}
node* MultiLinkedListSparseArray::ins_node(node* ins,int col){
while(!((*ins).col>col))
ins=(*ins).next_in_row;
return ins;
}
node* MultiLinkedListSparseArray::in_node(node* ins,node* z){
while((*ins).next_in_row!=z)
ins=(*ins).next_in_col;
return ins;
}
node* MultiLinkedListSparseArray::get(node* in,int row,int col){
dummy=new node;
dummy->value=0;
while((*in).col!=col){
if((*in).next_in_row==NULL){
return dummy;
}
in=(*in).next_in_row;
}
return in;
}
bool MultiLinkedListSparseArray::exist(node* so,int row,int col){
if(so==NULL)
return false;
else{
while((*so).col!=col){
if((*so).next_in_row==NULL)
return false;
else
so=(*so).next_in_row;
}
return true;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
MultiLinkedListSparseArray a(5, 5);
a.setCell(1, 5, 4);
a.setCell(2, 1, 2);
a.setCell(2, 2, 3);
a.setCell(3, 4, 5);
a.setCell(4, 1, 7);
a.setCell(4, 5, 8);
a.setCell(5, 2, 6);
cout << "X[4, 1] = " << a.getCell(4, 1) << endl;
cout << "X[4, 5] = " << a.getCell(4, 5) << endl;
cout << "X[2, 2] = " << a.getCell(2, 2) << endl;
cout << "X[5, 1] = " << a.getCell(5, 1) << endl;
a.display();
a.setCell(3, 4, 0);
a.setCell(1, 5, 0);
cout<<a.getCell(1,5)<<endl;
a.setCell(2, 2, 0);
a.setCell(5, 2, 0);
a.setCell(4, 5, 0);
//a.setCell(2, 5, 7); // problem WHY????????!!!!!!!!!!!!!!!
a.setCell(5, 3, 8);
a.setCell(2, 3, 5);
a.setCell(2, 5, 3);
a.setCell(2, 1, 0);
a.setCell(4, 2, 4);
a.setCell(4, 2, 2);
a.setCell(4, 2, 0);
a.setCell(4, 1, 0);
a.setCell(2, 3, 0);
a.setCell(2, 5, 0);
a.setCell(5, 3, 0);
a.display();
return 0;
}