/*
***** zip.h *****
***** ZIP fastener algorithm implementation *****

This class is implementation of ZIP fastener Algorithm
of multidimensional array representation
CS 691

Created Date: 14 Mar 2004

ZIP Matrix Class:
------------------
ZIP<template> matrix(10,10);
ZIP<template> matrix(10,10,0); //with default value 0

matrix(0,1)=value;
value=matrix(0,1);

matrix>>filename; //read matrix from text file
matrix<<filename; //write matrix to text file

cin>>matrix; //read matrix from std. input
cout<<matrix; //write matrix to std. output

matrix.begin(); //returns start of row major iterator
matrix.end(); //returns end of row major iterator
matrix.cbegin(); //returns start of column major iterator
matrix.cend(); //returns end of column major iterator
matrix.dbegin(); //returns start of diagonal iterator
matrix.dend(); //returns end of diagonal iterator


Row Major Iterator class:
***This is bidirectional iterator***
ZIP<Template>::iterator iteratorName;
ZIP<Template>::iterator iteratorName(oldIteratorName);
ZIP<Template>::iterator iteratorName(ZIPMatrix, initRow, initCol);

*iteratorName; //iterator dereferenced to give the value
iteratorName++;
++iteratorName;
iteratorName--;
--iteratorName;
iterator1==iterator2; //comparison
iterator1!=iterator2; //comparison

Column Major Iterator class:
***This is bidirectional iterator***
ZIP<Template>::citerator iteratorName;
ZIP<Template>::citerator iteratorName(oldIteratorName);
ZIP<Template>::citerator iteratorName(ZIPMatrix, initRow, initCol);

Diagonal Iterator class:
***This is bidirectional iterator***
*** Works only with square matrix ***
ZIP<Template>::diterator iteratorName;
ZIP<Template>::diterator iteratorName(oldIteratorName);
ZIP<Template>::diterator iteratorName(ZIPMatrix, initRow, initCol);

Super Row Iterator class:
***This is bidirectional iterator***
ZIP<Template>::srowiterator iteratorName;
ZIP<Template>::srowiterator iteratorName(oldIteratorName);
ZIP<Template>::srowiterator iteratorName(ZIPMatrix, initRow);
<srowiterator>=<srowiterator>&<scoliterator>

Super Column Iterator class:
***This is bidirectional iterator***
ZIP<Template>::scoliterator iteratorName;
ZIP<Template>::scoliterator iteratorName(oldIteratorName);
ZIP<Template>::scoliterator iteratorName(ZIPMatrix, initRow);
<scoliterator>=<scoliterator>&<srowiterator>
*/

#ifndef __ZIPMatrix
#define __ZIPMatrix

#include<iostream>
#include<fstream>
#include<assert.h>
#include<vector>
#include<iterator>
#include<cstdlib>

#define Z_ROW 1
#define Z_COLUMN 2
#define Z_DIAMETER 3

template <class T, class _Ref, class _Ptr>
class rowIterator;

template <class T, class _Ref, class _Ptr>
class colIterator;

template <class T, class _Ref, class _Ptr>
class diaIterator;

template <class T, class _Ref, class _Ptr>
class srowIterator;

template <class T, class _Ref, class _Ptr>
class scolIterator;

template <class T>
class row2rowIterator;

template <class T>
class col2colIterator;

template <class T, class _Ref, class _Ptr>
class sliceIterator;

class interleaved;


//Defining a main ZIP Class
template <class T>
class ZIP
{
private:
    vector<T> matrix;
    static int* lookuptable;
    static int lookupsize;
    T& indexof(int irow, int icol); //equiv. to matrix(irow,icol)
public:
    int row;
    int col;

    typedef T               value_type;
    typedef size_t          size_type;
    typedef ptrdiff_t       difference_type;

    typedef T&              reference;
    typedef const T&        const_reference;
    typedef T*              pointer;
    typedef const T*        const_pointer;

    //Iterators starts here
    typedef rowIterator<T, T&, T*>  iterator; //row major
    typedef rowIterator<T, const T&, const T*>  const_iterator; //const row major
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator> reverse_iterator; //reverse iterator

    typedef colIterator<T, T&, T*>  citerator; //column major
    typedef colIterator<T, const T&, const T*>  const_citerator; //const column major

    typedef diaIterator<T, T&, T*>  diterator; //diagonal iterator
    typedef diaIterator<T, const T&, const T*>  const_diterator; //const diagonal iterator

    typedef scolIterator<T, T&, T*> scoliterator; //Super column major
    typedef scolIterator<T, const T&, const T*> const_scoliterator;
    typedef srowIterator<T, T&, T*> srowiterator; //Super row major
    typedef srowIterator<T, const T&, const T*> const_srowiterator;
    typedef sliceIterator<T, T&, T*> sliceiterator; //Super column major
    //Iterators ends here

    //Not real iterator but returns super row & col iterators
    typedef row2rowIterator<T> r2riterator; //Row 2 Row
    typedef col2colIterator<T> c2citerator; //Col 2 Col 

    T& operator () (int irow, int icol); //irow=info. row

    //Constructor for ZIP Class
    ZIP(int nrow, int ncol); //without initialization parameter
    ZIP(int nrow, int ncol, T defaultValue); //with initialization parameter
    
    void operator >> (char * filename); //input filename
    void operator << (char * filename); //output filename
    //begin returns row major iterator
    iterator begin()
    {
        iterator itr(*this, 0, 0);
        return itr;
    }
    iterator end()
    {
        iterator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }
    const_iterator const_begin()
    {
        const_iterator itr(*this, 0, 0);
        return itr;
    }
    const_iterator const_end()
    {
        const_iterator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }
    reverse_iterator rbegin() {return reverse_iterator(end());}
    reverse_iterator rend() {return reverse_iterator(begin());}
    const_reverse_iterator const_rbegin() {return const_reverse_iterator(const_end());}
    const_reverse_iterator const_rend() {return const_reverse_iterator(const_begin());}

    //cbegin returns column major iterator
    citerator cbegin()
    {
        citerator itr(*this, 0, 0);
        return itr;
    }

    citerator cend()
    {
        citerator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }
    const_citerator const_cbegin()
    {
        const_citerator itr(*this, 0, 0);
        return itr;
    }
    const_citerator const_cend()
    {
        const_citerator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }

    //dbegin return diagonal iterator
    diterator dbegin()
    {
        diterator itr(*this, 0, 0);
        return itr;
    }

    diterator dend()
    {
        diterator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }

    const_diterator const_dbegin()
    {
        const_diterator itr(*this, 0, 0);
        return itr;
    }

    const_diterator const_dend()
    {
        const_diterator itr(*this, this->row-1,this->col-1);
        return ++itr;
    }

    //r2rbegin and r2rend return super row iterator
    r2riterator r2rbegin()
    {
        r2riterator itr(*this, 0);
        return itr;
    }

    r2riterator r2rend()
    {
        r2riterator itr(*this, this->row-1);
        return ++itr;
    }

    //c2cbegin and c2cend return super column iterator
    c2citerator c2cbegin()
    {
        c2citerator itr(*this, 0);
        return itr;
    }

    c2citerator c2cend()
    {
        c2citerator itr(*this, this->col-1);
        return ++itr;
    }
    
    friend class rowIterator<T, T&, T*>;
    friend class rowIterator<T, const T&, const T*>;
    friend class colIterator<T, T&, T*>;
    friend class colIterator<T, const T&, const T*>;
    friend class diaIterator<T, T&, T*>;
    friend class diaIterator<T, const T&, const T*>;
    friend class srowIterator<T, T&, T*>;
    friend class srowIterator<T, const T&, const T*>;
    friend class scolIterator<T, T&, T*>;
    friend class scolIterator<T, const T&, const T*>;
    friend class sliceIterator<T, T&, T*>;
    friend class sliceIterator<T, const T&, const T*>;
};

//***** Static lookuptable *****
template <class T>
int* ZIP<T>::lookuptable;

//***** Static size of lookuptable *****
template <class T>
int ZIP<T>::lookupsize;

//***** Constructor for ZIP class *****
template <class T>
ZIP<T>::ZIP(int nrow, int ncol)
        :row(nrow), col(ncol)
{
    int i, index;

    if(nrow>ncol)
	index=nrow;
    else
	index=ncol;

    if((lookuptable==NULL)||(index>lookupsize))
    {
	lookupsize=index+1;
	lookuptable=new int[lookupsize];
	lookuptable[0]=0;
	for(i=1;i<lookupsize;i++)
    	{
       	     lookuptable[i]=(((lookuptable[i-1]|0xAAAAAAAA)+1)&0x55555555);
    	}
    }
    //Resizing vector for new matrix
    matrix.resize(((lookuptable[nrow-1]<<1)+lookuptable[ncol-1])+1);
}

//***** Constructor for ZIP class with default value *****
template <class T>
ZIP<T>::ZIP(int nrow, int ncol, T defaultValue)
        :row(nrow), col(ncol)
{
    int i, index;

    if(nrow>ncol)
	index=nrow;
    else
	index=ncol;

    if((lookuptable==NULL)||(index>lookupsize))
    {
	lookupsize=index+1;
	lookuptable=new int[lookupsize];
	lookuptable[0]=0;
	for(i=1;i<lookupsize;i++)
    	{
       	     lookuptable[i]=(((lookuptable[i-1]|0xAAAAAAAA)+1)&0x55555555);
    	}
    }
    //Resizing vector for new matrix
    matrix.resize(((lookuptable[nrow-1]<<1)+lookuptable[ncol-1])+1,defaultValue);
}

//***** Operator (row,col) overloaded to find the index of ZIP Matrix *****
template <class T>
T& ZIP<T>::operator() (int irow, int icol)
{
    int index;
    index=(lookuptable[irow]<<1)+lookuptable[icol];
    return matrix[index];
}

//*****Private member to find the index of ZIP Matrix*****
//*****Same as overloaded operator ( )*****
template <class T>
T& ZIP<T>::indexof(int irow, int icol)
{
   int index;
   index=(lookuptable[irow]<<1)+lookuptable[icol];
   return matrix[index];
}

//*****Reading from the file using >> operator*****
template <class T>
void ZIP<T>::operator >> (char * filename)
{
    int i, j;
    fstream inFile;

    //Reading from the file for first matrix
    inFile.open(filename, ios::in);
    if (!inFile)
    {
	cout<<"Cannot open file"<<endl;
	exit(1);
    }

    for(i=0;i<row;i++)
	for(j=0;j<col;j++)
	{
	    inFile>>indexof(i,j);
	}
    inFile.close();
}

//*****Writing matrix to the file using << operator*****
template <class T>
void ZIP<T>::operator << (char * filename)
{
    int i, j;
    fstream outFile;

    //Reading from the file for first matrix
    outFile.open(filename, ios::out);
    if (!outFile)
    {
	cout<<"Cannot open file"<<endl;
	exit(1);
    }

    for(i=0;i<row;i++)
    {
	for(j=0;j<col;j++)
	{
	    outFile<<indexof(i,j)<<" ";
	}
        outFile<<endl;
    }
    outFile.close();
}

//*****Writing to matrix to output stream*****
template <class T>
ostream & operator << (ostream & out, ZIP<T> & mymatrix)
{
    int i, j;
    for(i=0;i<mymatrix.row;i++)
    {
        for(j=0;j<mymatrix.col;j++)
            out<<mymatrix(i,j)<<" ";
        out<<endl;
    }
    return out;
}

//*****Reading from input stream to matrix*****
template <class T>
istream & operator >> (istream & in, ZIP<T> & mymatrix)
{
    int i, j;
    for(i=0;i<mymatrix.row;i++)
    {
        for(j=0;j<mymatrix.col;j++)
            in>>mymatrix(i,j);
    }
    return in;
}
//***** Main ZIP Class ends here *****

//****** Bit interleaved add/subtract class ******
// This class is for bit interleaved "++" and "--" implementation

class interleaved
{
        private:
                int value;
        public:
                interleaved():value(0){}
                interleaved(int newValue):value(newValue){}
                int operator ++(int)
                {
                        int tmp=value;
                        value=(((value|0xAAAAAAAA)+1)&0x55555555);
                        return tmp;
                }
                int & operator ++()
                {
                        value=(((value|0xAAAAAAAA)+1)&0x55555555);
                        return value;
                }
                int operator --(int)
                {
                        int tmp=value;
                        value=((value-1)&0x55555555);
                        return tmp;
                }
                int & operator --()
                {
                        value=((value-1)&0x55555555);
                        return value;
                }
                int operator ()()
                {
                        return value;
                }
                int operator +(interleaved & rhs)
                {
                        return (value<<1)+rhs();
                }
};

//***** Iterator Classes starts here *****
//----------------------------------------
//***** Row Iterator *****
//***** rowIterator Class *****
template <class T, class _Ref, class _Ptr>
class rowIterator
{
        public:
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;

                rowIterator()
                        :currRow(0), currCol(0),
                        zippedRow(0), zippedCol(0),
                        totRow(0), totCol(0),
                        zippedTotCol(0),
                        dataPtr(NULL), startPtr(NULL)
                {} //Just Declaration
                rowIterator(ZIP<T> & zipPtr, int newRow, int newCol)
                        :currRow(newRow), currCol(newCol),
			zippedRow(zipPtr.lookuptable[newRow]), zippedCol(zipPtr.lookuptable[newCol]),
			totRow(zipPtr.row), totCol(zipPtr.col),
			zippedTotCol(zipPtr.lookuptable[zipPtr.col]),
			dataPtr(&zipPtr.indexof(newRow,newCol)), startPtr(&zipPtr.indexof(0,0))
                {} //iterator(zipMatrix, startRow, startCol)

                rowIterator(const rowIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
			zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
			totRow(newValue.totRow), totCol(newValue.totCol),
			zippedTotCol(newValue.zippedTotCol),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }

                pointer operator-> () const { return dataPtr; }

                rowIterator & operator ++()
                {
                        currCol++; zippedCol++;
                        if (currCol>=totCol)
                        {
                                currCol=0; zippedCol=0;
                                currRow++; zippedRow++;
                        }
                        if (currRow>=totRow&&currCol>0)
                        {
                                currCol--; zippedCol--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                rowIterator operator ++(int)
                {
                        rowIterator tmp = *this;
                        currCol++; zippedCol++;
                        if (currCol>=totCol)
                        {
                                currCol=0; zippedCol=0;
                                currRow++; zippedRow++;
                        }
                        if (currRow>=totRow&&currCol>0)
                        {
                                currCol--; zippedCol--;
                        }

                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }

                bool operator==(const rowIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const rowIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                rowIterator & operator --()
                {
                        currCol--; zippedCol--;
                        if (currCol<0)
                        {
                                currCol=totCol; currCol--;
                                zippedCol=zippedTotCol; zippedCol--;
                                currRow--; zippedRow--;
                        }
                        if (currRow<0)
                        {
                                currRow=0; zippedRow=0;
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                rowIterator operator --(int)
                {
                        rowIterator tmp = *this;
                        currCol--; zippedCol--;
                        if (currCol<0)
                        {
                                currCol=totCol; currCol--;
                                zippedCol=zippedTotCol; zippedCol--;
                                currRow--; zippedRow--;
                        }

                        if (currRow<0)
                        {
                                currRow=0; zippedRow=0;
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                rowIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                rowIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                rowIterator operator+ (difference_type i) const
                {
                        rowIterator tmp = *this; return tmp += i;
                }
                rowIterator operator- (difference_type i) const
                {
                        rowIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (rowIterator x) const
                {
                        return ((currRow*totCol)+currCol)-((x.currRow*x.totCol)+x.currCol);
                }
                bool operator< (const rowIterator& x) const
                {
                        return ((currRow*totCol)+currCol) < ((x.currRow*x.totCol)+x.currCol);
                }
                bool operator> (const rowIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const rowIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const rowIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
        private:
                int currRow, currCol;
                interleaved zippedRow, zippedCol;
                int totRow, totCol;
                interleaved zippedTotCol;
                T * dataPtr, * startPtr;
};

//***** Column Iterator *****
//***** colIterator Class *****
template <class T, class _Ref, class _Ptr>
class colIterator

{
        public:
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;

                colIterator()
                        :currRow(0), currCol(0),
                        zippedRow(0), zippedCol(0),
                        totRow(0), totCol(0),
                        zippedTotRow(0),
                        dataPtr(NULL), startPtr(NULL)
                {} //Just Declaration
                colIterator(ZIP<T> & zipPtr, int newRow, int newCol)
                        :currRow(newRow), currCol(newCol),
                        zippedRow(zipPtr.lookuptable[newRow]), zippedCol(zipPtr.lookuptable[newCol]),
                        totRow(zipPtr.row), totCol(zipPtr.col),
                        zippedTotRow(zipPtr.lookuptable[zipPtr.row]),
                        dataPtr(&zipPtr.indexof(newRow,newCol)), startPtr(&zipPtr.indexof(0,0))
                {} //iterator(zipMatrix, startRow, startCol)
                colIterator(const colIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
                        zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
                        totRow(newValue.totRow), totCol(newValue.totCol),
                        zippedTotRow(newValue.zippedTotRow),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }
                
                pointer operator-> () const { return dataPtr; }

                colIterator & operator ++()
                {
                        currRow++; zippedRow++;
                        if (currRow>=totRow)
                        {
                                currRow=0; zippedRow=0;
                                currCol++; zippedCol++;
                        }
                        if (currCol>=totCol&&currRow>0)
                        {
                                currRow--; zippedRow--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                colIterator operator ++(int)
                {
                        colIterator tmp = *this;
                        currRow++; zippedRow++;
                        if (currRow>=totRow)
                        {
                                currRow=0; zippedRow=0;
                                currCol++; zippedCol++;
                        }
                        if (currCol>=totCol&&currRow>0)
                        {
                                currRow--; zippedRow--;
                        }

                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                bool operator==(const colIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const colIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                colIterator & operator --()
                {
                        currRow--; zippedRow--;
                        if (currRow<0)
                        {
                                currRow=totRow; currRow--;
                                zippedRow=zippedTotRow; zippedRow--;
                                currCol--; zippedCol--;
                        }
                        if (currCol<0)
                        {
                                currCol=0; zippedCol=0;
                                currRow=0; zippedRow=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                colIterator operator --(int)
                {
                        colIterator tmp = *this;
                        currRow--; zippedRow--;
                        if (currRow<0)
                        {
                                currRow=totRow; currRow--;
                                zippedRow=zippedTotRow; zippedRow--;
                                currCol--; zippedCol--;
                        }
                        if (currCol<0)
                        {
                                currRow=0; zippedRow=0;
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                colIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                colIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                colIterator operator+ (difference_type i) const
                {
                        colIterator tmp = *this; return tmp += i;
                }
                colIterator operator- (difference_type i) const
                {
                        colIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (colIterator x) const
                {
                        return ((currCol*totRow)+currRow)-((x.currCol*x.totRow)+x.currRow);
                }
                bool operator< (const colIterator& x) const
                {
                        return ((currCol*totRow)+currRow)<((x.currCol*x.totRow)+x.currRow);
                }
                bool operator> (const colIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const colIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const colIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
        private:
                int currRow, currCol;
                interleaved zippedRow, zippedCol;
                int totRow, totCol;
		interleaved zippedTotRow;
                T * dataPtr, * startPtr;
};

//***** Diagonal Iterator *****
//***** diaIterator Class *****
template <class T, class _Ref, class _Ptr>
class diaIterator

{
        public:
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;

                diaIterator()
                        :currRow(0), currCol(0),
                        zippedRow(0), zippedCol(0),
                        totRow(0), totCol(0),
                        dataPtr(NULL), startPtr(NULL)
                {} //Just Declaration
                diaIterator(ZIP<T> & zipPtr, int newRow, int newCol)
                        :currRow(newRow), currCol(newCol),
                        zippedRow(zipPtr.lookuptable[newRow]), zippedCol(zipPtr.lookuptable[newCol]),
                        totRow(zipPtr.row), totCol(zipPtr.col),
                        dataPtr(&zipPtr.indexof(newRow,newCol)), startPtr(&zipPtr.indexof(0,0))
                {
                        if((currRow!=currCol)||(totRow!=totCol))
                        {
                                cout<<endl<<"Error: Use Diagonal Iterator with Square Matrix only"<<endl;
                                assert((currRow==currCol)&&(totRow==totCol));
                        }
                } //iterator(zipMatrix, startRow, startCol)
                diaIterator(const diaIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
                        zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
                        totRow(newValue.totRow), totCol(newValue.totCol),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }

                pointer operator-> () const { return dataPtr; }
                
                diaIterator & operator ++()
                {
                        currRow++; zippedRow++;
                        currCol++; zippedCol++;
                        if (currRow>totRow||currCol>totCol)
                        {
                                currRow--; zippedRow--;
                                currCol--; zippedCol--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                diaIterator operator ++(int)
                {
                        diaIterator tmp = *this;
                        currRow++; zippedRow++;
                        currCol++; zippedCol++;
                        if (currRow>totRow||currCol>totCol)
                        {
                                currRow--; zippedRow--;
                                currCol--; zippedCol--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                bool operator==(const diaIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const diaIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                diaIterator & operator --()
                {
                        currRow--; zippedRow--;
                        currCol--; zippedCol--;
                        if (currRow<0||currCol<0)
                        {
                                currRow=0; zippedRow=0;
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                diaIterator operator --(int)
                {
                        diaIterator tmp = *this;
                        currRow--; zippedRow--;
                        currCol--; zippedCol--;
                        if (currRow<0||currCol<0)
                        {
                                currRow=0; zippedRow=0;
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                diaIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                diaIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                diaIterator operator+ (difference_type i) const
                {
                        diaIterator tmp = *this; return tmp += i;
                }
                diaIterator operator- (difference_type i) const
                {
                        diaIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (diaIterator x) const
                {
                        return (currRow - x.currRow);
                        //because currRow is always equal to currCol in diagonal matrix
                }
                bool operator< (const diaIterator& x) const
                {
                        return (currRow < x.currRow);
                }
                bool operator> (const diaIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const diaIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const diaIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
        private:
                int currRow, currCol;
                interleaved zippedRow, zippedCol;
                int totRow, totCol;
                T * dataPtr, * startPtr;
};

//****** Super Row Iterator ******
template<class T, class _Ref, class _Ptr>
class srowIterator
{
        public:
                friend class scolIterator<T, _Ref, _Ptr>;
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;
                
                srowIterator()
                        :currRow(0), currCol(0),
                        dataPtr(NULL), startPtr(NULL),
                        zippedRow(0), zippedCol(0), totCol(0)
                {}
                srowIterator(ZIP<T> & zipPtr, int newRow)
                        :currRow(newRow), currCol(0),
                        dataPtr(&zipPtr.indexof(newRow,0)), startPtr(&zipPtr.indexof(0,0)),
                        zippedRow(zipPtr.lookuptable[newRow]), zippedCol(0),
                        totCol(zipPtr.col)
                {} //srowIterator(&zipMatrix, startRow, startCol)
                srowIterator(const srowIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr),
                        zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
                        totCol(newValue.totCol)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }

                pointer operator-> () const { return dataPtr; }
                
                srowIterator & operator ++()
                {
                        currCol++; zippedCol++;
                        if (currCol>totCol)
                        {
                                currCol--; zippedCol--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                srowIterator operator ++(int)
                {
                        srowIterator tmp = *this;
                        currCol++; zippedCol++;
                        if (currCol>totCol)
                        {
                                currCol--; zippedCol--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                bool operator==(const srowIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const srowIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                srowIterator & operator --()
                {
                        currCol--; zippedCol--;
                        if (currCol<0)
                        {
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                srowIterator operator --(int)
                {
                        srowIterator tmp = *this;
                        currCol--; zippedCol--;
                        if (currCol<0)
                        {
                                currCol=0; zippedCol=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                srowIterator operator &(const scolIterator<T, _Ref, _Ptr> & rhs)
                {
                        srowIterator tmp=*this;
                        //Pointing to start of the column
                        tmp.dataPtr=tmp.startPtr;
                        assert(tmp.startPtr==rhs.startPtr);
                        while (tmp.currCol != rhs.currCol)
                        {
                                tmp++;
                        }
                        return tmp;
                }
                srowIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                srowIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                srowIterator operator+ (difference_type i) const
                {
                        srowIterator tmp = *this; return tmp += i;
                }
                srowIterator operator- (difference_type i) const
                {
                        srowIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (srowIterator x) const
                {
                        return (currCol-x.currCol);
                        //Row is fixed in row iterator
                }
                bool operator< (const srowIterator& x) const
                {
                        return (currCol < x.currCol);
                }
                bool operator> (const srowIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const srowIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const srowIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
                //begin() and end()
                //Extra functionality than standard iterator
                srowIterator begin()
                {
                        srowIterator itr(*this);
                        return (itr-currCol);
                }

                srowIterator end()
                {
                        srowIterator itr(*this);
                        return itr+(totCol-currCol);
                }
        private:
                int currRow, currCol;
                T * dataPtr, * startPtr;
                interleaved zippedRow, zippedCol;
                int totCol;
};

//****** Super Column Iterator ******
template<class T, class _Ref, class _Ptr>
class scolIterator

        {
        public:
                friend class srowIterator<T, _Ref, _Ptr>;
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;
                
                scolIterator()
                        :currRow(0), currCol(0),
                        dataPtr(NULL), startPtr(NULL),
                        zippedRow(0), zippedCol(0), totRow(0)
                {}
                scolIterator(ZIP<T> & zipPtr, int newCol)
                        :currRow(0), currCol(newCol),
                        dataPtr(&zipPtr.indexof(0,newCol)), startPtr(&zipPtr.indexof(0,0)),
                        zippedRow(0), zippedCol(zipPtr.lookuptable[newCol]),
                        totRow(zipPtr.row)
                {} //iterator(&zipMatrix, startRow, startCol)
                scolIterator(const scolIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr),
                        zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
                        totRow(newValue.totRow)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }

                pointer operator-> () const { return dataPtr; }
                
                scolIterator & operator ++()
                {
                        currRow++; zippedRow++;
                        if (currRow>totRow)
                        {
                                currRow--; zippedRow--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                scolIterator operator ++(int)
                {
                        scolIterator tmp = *this;
                        currRow++; zippedRow++;
                        if (currRow>totRow)
                        {
                                currRow--; zippedRow--;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                bool operator==(const scolIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const scolIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                scolIterator & operator --()
                {
                        currRow--; zippedRow--;
                        if (currRow<0)
                        {
                                currRow=0; zippedRow=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                scolIterator operator --(int)
                {
                        scolIterator tmp = *this;
                        currRow--; zippedRow--;
                        if (currRow<0)
                        {
                                currRow=0; zippedRow=0;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }

                scolIterator operator &(const srowIterator<T, _Ref, _Ptr> & rhs)
                {
                        scolIterator tmp=*this;
                        //Pointing to start of the column
                        tmp.dataPtr=tmp.startPtr;
                        assert(tmp.startPtr==rhs.startPtr);
                        while (tmp.currRow != rhs.currRow)
                        {
                                tmp++;
                        }
                        return tmp;
                }
                scolIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                scolIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                scolIterator operator+ (difference_type i) const
                {
                        scolIterator tmp = *this; return tmp += i;
                }
                scolIterator operator- (difference_type i) const
                {
                        scolIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (scolIterator x) const
                {
                        return (currRow-x.currRow);
                        //Column is fixed in column iterator
                }
                bool operator< (const scolIterator& x) const
                {
                        return (currRow < x.currRow);
                }
                bool operator> (const scolIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const scolIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const scolIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
                //begin() and end()
                //Extra functionality than standard iterator
                scolIterator begin()
                {
                        scolIterator itr(*this);
                        return (itr-currRow);
                }

                scolIterator end()
                {
                        scolIterator itr(*this);
                        return itr+(totRow-currRow);
                }
        private:
                int currRow, currCol;
                T * dataPtr, * startPtr;
                interleaved zippedRow, zippedCol;
                int totRow;
};

//***** row2row Iterator Class *****
//***** Not a real iterator *****
//This will return the super row iterator
template <class T>
class row2rowIterator
{
        public:
                row2rowIterator()
                        :currRow(0), dataPtr(NULL)
                {} //Just Declaration
                row2rowIterator(ZIP<T> & zipPtr, int newRow)
                        :currRow(newRow), dataPtr(&zipPtr)
                {} //iterator(zipMatrix, startRow, startCol)
                row2rowIterator(const row2rowIterator& newValue)
                        :currRow(newValue.currRow), dataPtr(newValue.dataPtr)
                {}  //copy constructor

                srowIterator<T, T&, T*> operator*() const
                {
                        srowIterator<T, T&, T*> tmp(*dataPtr, currRow);
                        return tmp;
                }

                row2rowIterator & operator ++()
                {
                        currRow++;
                        if (currRow>dataPtr->row)
                        {
                                currRow--;
                        }
                        return *this;
                }
                row2rowIterator operator ++(int)
                {
                        row2rowIterator tmp=*this;
                        currRow++;
                        if (currRow>dataPtr->row)
                        {
                                currRow--;
                        }
                        return tmp;
                }
                bool operator==(const row2rowIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr)&&(currRow==newValue.currRow);
                }

                bool operator!=(const row2rowIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                row2rowIterator & operator --()
                {
                        currRow--;
                        if (currRow<0)
                        {
                                currRow=0;
                        }
                        return *this;
                }
                row2rowIterator operator --(int)
                {
                        row2rowIterator tmp = *this;
                        currRow--;
                        if (currRow<0)
                        {
                                currRow=0;
                        }
                        return tmp;
                }                
        private:
                int currRow;
                ZIP<T> * dataPtr;
};

//***** col2col Iterator Class *****
//***** Not a real iterator *****
//This will return the super row iterator
template <class T>
class col2colIterator
{
        public:
                col2colIterator()
                        :currCol(0), dataPtr(NULL)
                {} //Just Declaration
                col2colIterator(ZIP<T> & zipPtr, int newRow)
                        :currCol(newRow), dataPtr(&zipPtr)
                {} //iterator(zipMatrix, startRow, startCol)
                col2colIterator(const col2colIterator& newValue)
                        :currCol(newValue.currCol), dataPtr(newValue.dataPtr)
                {}  //copy constructor

                scolIterator<T, T&, T*> operator*() const
                {
                        scolIterator<T, T&, T*> tmp(*dataPtr, currCol);
                        return tmp;
                }

                col2colIterator & operator ++()
                {
                        currCol++;
                        if (currCol>dataPtr->col)
                        {
                                currCol--;
                        }
                        return *this;
                }
                col2colIterator operator ++(int)
                {
                        col2colIterator tmp=*this;
                        currCol++;
                        if (currCol>dataPtr->col)
                        {
                                currCol--;
                        }
                        return tmp;
                }
                bool operator==(const col2colIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr)&&(currCol==newValue.currCol);
                }

                bool operator!=(const col2colIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                col2colIterator & operator --()
                {
                        currCol--;
                        if (currCol<0)
                        {
                                currCol=0;
                        }
                        return *this;
                }
                col2colIterator operator --(int)
                {
                        col2colIterator tmp = *this;
                        currCol--;
                        if (currCol<0)
                        {
                                currCol=0;
                        }
                        return tmp;
                }
        private:
                int currCol;
                ZIP<T> * dataPtr;
};

//****** SLICE Row Iterator ******
template<class T, class _Ref, class _Ptr>
class sliceIterator
{
        public:
                typedef T               value_type;
                typedef _Ref            reference;
                typedef _Ptr            pointer;
                typedef ptrdiff_t       difference_type;
                typedef random_access_iterator_tag iterator_category;

                sliceIterator()
                        :currRow(0), currCol(0),
                        dataPtr(NULL), startPtr(NULL),
                        zippedRow(0), zippedCol(0), totCol(0), totRow(0), mode(0)
                {}
                sliceIterator(ZIP<T> & zipPtr, int newValue, int newMode)
                {
                        mode= newMode;
                        totCol=zipPtr.col; totRow=zipPtr.row;
                        dataPtr=&zipPtr.indexof(newValue,0);
                        startPtr=&zipPtr.indexof(0,0);
                        if (mode==1)
                        {
                                currRow=newValue;
                                zippedRow=zipPtr.lookuptable[newValue];
                                currCol=0;
                                zippedCol=0;
                        } else if (mode==2)
                        {
                                currRow=0;
                                zippedRow=0;
                                currCol=newValue;
                                zippedCol=zipPtr.lookuptable[newValue];
                        }else
                        {
                                cout<<"Error: Invalid parameter to slice iterator\n";
                                exit(1);
                        }


                } //srowIterator(&zipMatrix, startRow)
                sliceIterator(const sliceIterator& newValue)
                        :currRow(newValue.currRow), currCol(newValue.currCol),
                        dataPtr(newValue.dataPtr),startPtr(newValue.startPtr),
                        zippedRow(newValue.zippedRow),zippedCol(newValue.zippedCol),
                        totCol(newValue.totCol), totRow(newValue.totRow), mode(newValue.mode)
                {}  //copy constructor

                reference operator*() const
                {
                        return (*dataPtr);
                }

                pointer operator-> () const { return dataPtr; }
                
                sliceIterator & operator ++()
                {
                        switch (mode)
                        {
                        case 1:
                                currCol++; zippedCol++;
                                if (currCol>totCol)
                                {
                                        currCol--; zippedCol--;
                                }
                                break;
                        case 2:
                                currRow++; zippedRow++;
                                if (currRow>totRow)
                                {
                                        currRow--; zippedRow--;
                                }
                                break;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                sliceIterator operator ++(int)
                {
                        sliceIterator tmp = *this;
                        switch (mode)
                        {
                        case 1:
                                currCol++; zippedCol++;
                                if (currCol>totCol)
                                {
                                        currCol--; zippedCol--;
                                }
                                break;
                        case 2:
                                currRow++; zippedRow++;
                                if (currRow>totRow)
                                {
                                        currRow--; zippedRow--;
                                }
                                break;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                bool operator==(const sliceIterator & newValue)
                {
                        return (dataPtr==newValue.dataPtr);
                }

                bool operator!=(const sliceIterator & newValue)
                {
                        return (!(*this == newValue));
                }
                sliceIterator & operator --()
                {
                        switch (mode)
                        {
                        case 1:
                                currCol--; zippedCol--;
                                if (currCol<0)
                                {
                                        currCol=0; zippedCol=0;
                                }
                                break;
                        case 2:
                                currRow--; zippedRow--;
                                if (currRow<0)
                                {
                                        currRow=0; zippedRow=0;
                                }
                                break;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return *this;
                }
                sliceIterator operator --(int)
                {
                        sliceIterator tmp = *this;
                        switch (mode)
                        {
                        case 1:
                                currCol--; zippedCol--;
                                if (currCol<0)
                                {
                                        currCol=0; zippedCol=0;
                                }
                                break;
                        case 2:
                                currRow--; zippedRow--;
                                if (currRow<0)
                                {
                                        currRow=0; zippedRow=0;
                                }
                                break;
                        }
                        this->dataPtr=this->startPtr+(zippedRow+zippedCol);
                        return tmp;
                }
                
                sliceIterator & operator += (difference_type i)
                {
                        if (i >= 0)
                                while (i--) ++*this;
                        else
                                while (i++) --*this;
                        return *this;
                }
                sliceIterator& operator-= (difference_type i)
                {
                        *this += -i; return *this;
                }
                sliceIterator operator+ (difference_type i) const
                {
                        sliceIterator tmp = *this; return tmp += i;
                }
                sliceIterator operator- (difference_type i) const
                {
                        sliceIterator tmp = *this;
                        return tmp -= i;
                }
                difference_type operator- (sliceIterator x) const
                {
                        switch(mode)
                        {
                        case 1:
                                return (currCol-x.currCol);
                        case 2:
                                return (currRow-x.currRow);
                        }
                        //Row is fixed in row iterator
                }
                bool operator< (const sliceIterator& x) const
                {
                        switch(mode)
                        {
                        case 1:
                                return (currCol < x.currCol);
                        case 2:
                                return (currRow < x.currRow);
                        }
                }
                bool operator> (const sliceIterator& x) const
                {
                        return x < *this;
                }
                bool operator>= (const sliceIterator& x) const
                {
                        return !(*this < x);
                }
                bool operator<= (const sliceIterator& x) const
                {
                        return !(*this > x);
                }
                reference operator[] (difference_type i)
                {
                        return *(*this + i);
                }
                //begin() and end()
                //Extra functionality than standard iterator
                sliceIterator begin()
                {
                        sliceIterator itr(*this);
                        switch(mode)
                        {
                        case 1:
                                return (itr-currCol);
                        case 2:
                                return (itr-currRow);
                        }
                }

                sliceIterator end()
                {
                        sliceIterator itr(*this);
                        switch(mode)
                        {
                        case 1:
                                return itr+(totCol-currCol);
                        case 2:
                                return itr+(totRow-currRow);
                        }
                }
                void setmode(int newValue){mode=newValue;}
                int getmode(){return mode;}
                
        private:
                int currRow, currCol;
                T * dataPtr, * startPtr;
                interleaved zippedRow, zippedCol;
                int totCol, totRow;
                int mode;
};


#endif /* __ZIPMatrix */