// 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;  
    }  
}