//Cross.h
#ifndef CROSS_LINKED_LIST
#define CROSS_LINKED_LIST

template <typename T>
class Cross
{
public:
	Cross();
	Cross(int m, int n);
	~Cross();

	int Modify(int m, int n, const T& item);
	T Delete(int m, int n);
	int Get(int m, int n, T& item) const;
	
	int Row_count() const;
	int Col_count() const;
	int Count() const;

	struct CrossNode;
	class Iterator
	{
	public:
		Iterator();
		Iterator(const Cross<T>&);
		Iterator(const Cross<T>&, int m, int n);
		const typename Cross<T>::Iterator& 
			operator=(const typename Cross<T>::Iterator&);
		const T& operator*() const;
		const typename Cross<T>::Iterator operator++(int);
		bool operator==(const typename Cross<T>::Iterator& iter) const;
		bool operator!=(const typename Cross<T>::Iterator& iter) const;
		int Row() const;
		int Col() const;
	protected:
		const Cross<T>* _pCross;
		const CrossNode *_pNode;
	};
	friend class Iterator;
	Iterator Row(int m = 0) const;
	Iterator Row_end() const;
protected:
	struct CrossNode
	{
		int row;
		int col;
		T value;
		CrossNode *row_next;
		CrossNode *col_next;
	} **_ppRow, **_ppCol;
	int _row;
	int _col;
	int _count;
};

#endif

//in Cross.cpp
#include <cassert>
#include "Cross.h"

template <typename T>
Cross<T>::Cross()
{
	_row = _col = _count = 0;
	_ppRow = _ppCol = 0;
}

template <typename T>
Cross<T>::Cross(int m,
						int n)
{
	_row = m;
	_col = n;
	_count = 0;
	_ppRow = new CrossNode*[m];
	_ppCol = new CrossNode*[n];
	for (int i = 0; i < m; i++)
		_ppRow[i] = 0;
	for (int j = 0; j < n; j++)
		_ppCol[j] = 0;
}

template <typename T>
Cross<T>::~Cross()
{
	for (int i = 0; i < _row; i++)
	{
		CrossNode *pNode = _ppRow[i];
		CrossNode *pDel;
		while ( pNode )
		{
			pDel = pNode;
			pNode = pNode->row_next;
			delete pDel;
		}
	}
	delete[] _ppRow;
	delete[] _ppCol;
	_ppRow = _ppCol = 0;
	_row = _col = _count = 0;
}

template <typename T>
int Cross<T>::Modify(int m,
							int n,
							const T& item)
{
	CrossNode *p_rnode, *p_rnode_prev;
	CrossNode *p_cnode, *p_cnode_prev;
	p_rnode = _ppRow[m];
	p_cnode = _ppCol[n];
	
	while ( p_rnode && p_rnode->col < n )	//找到行中的适当位置
	{
		p_rnode_prev = p_rnode;				//prev指向插入位置的前一个位置
		p_rnode = p_rnode->row_next;		//rnode可能 >=n, ==0
	}
	while ( p_cnode && p_cnode->row < m )	//列同行一样
	{
		p_cnode_prev = p_cnode;
		p_cnode = p_cnode->col_next;
	}

	if ( p_rnode && p_rnode->col == n)		//结点已经存在（只要判断行即可）
	{
		p_rnode->value = item;
		return 1;
	}
	else									//结点不存在，可能插在中间，也可能在头上
	{
		CrossNode *pNew = new CrossNode;
		pNew->row = m;
		pNew->col = n;
		pNew->value = item;
		pNew->row_next = p_rnode;
		pNew->col_next = p_cnode;
		if ( p_rnode != _ppRow[m] )			//在中间插入
			p_rnode_prev->row_next = pNew;
		else
			_ppRow[m] = pNew;				//在头上插入
		if ( p_cnode != _ppCol[n] )
			p_cnode_prev->col_next = pNew;
		else
			_ppCol[n] = pNew;
		_count++;
		return 1;
	} //if
} //Modify

//删除一个结点，并返回其中的值
//删除一个不存在的结点会有不确定的结果
template <typename T>
T Cross<T>::Delete(int m, int n)
{
	T del_value;
	CrossNode *p_rnode, *p_rnode_prev;
	CrossNode *p_cnode, *p_cnode_prev;
	p_rnode = _ppRow[m];
	p_cnode = _ppCol[n];

	p_rnode_prev = p_rnode;
	while ( p_rnode && p_rnode->col != n )
	{
		p_rnode_prev = p_rnode;
		p_rnode = p_rnode->row_next;
	}
	p_cnode_prev = p_cnode;
	while ( p_cnode && p_cnode->row != m )
	{
		p_cnode_prev = p_cnode;
		p_cnode = p_cnode->col_next;
	}
	assert( p_rnode && p_rnode->col == n );

	if ( p_rnode == _ppRow[m] )		//删除行链表的头
		_ppRow[m] = p_rnode->row_next;
	else
		p_rnode_prev->row_next = p_rnode->row_next;
	if ( p_cnode == _ppCol[n] )		//删除列链表的头
		_ppCol[n] = p_cnode->col_next;
	else
		p_cnode_prev->col_next = p_cnode->col_next;
	del_value = p_rnode->value;
	delete p_rnode;
	_count--;
	return del_value;
} //Delete

//取得m行n列的值，1表示成功，0表示不存在
template <typename T>
int Cross<T>::Get(int m, int n,
							T& item)	const /*取出的值*/
{
	CrossNode *p_rnode = _ppRow[m];
	while ( p_rnode && p_rnode->col < n )
		p_rnode = p_rnode->row_next;
	if ( p_rnode && p_rnode->col == n )		//找到
	{
		item = p_rnode->value;
		return 1;
	}
	else
		return 0;
}

template <typename T>
inline int Cross<T>::Row_count() const
{
	return _row;
}

template <typename T>
inline int Cross<T>::Col_count() const
{
	return _col;
}

template <typename T>
inline int Cross<T>::Count() const
{
	return _count;
}

template <typename T>
typename Cross<T>::Iterator Cross<T>::Row(int m) const
{
	assert( m >= 0 && m < _row );
	int col = 0;
	if ( _ppRow[m] )
		col = _ppRow[m]->col;
	typename Cross<T>::Iterator iter(*this, m, col);
	return iter;
}

template <typename T>
typename Cross<T>::Iterator Cross<T>::Row_end() const
{
	typename Cross<T>::Iterator iter(*this);
	return iter;
}

template <typename T>
Cross<T>::Iterator::Iterator()
{
	_pCross = 0;
	_pNode = 0;
}

template <typename T>
Cross<T>::Iterator::Iterator(const Cross<T>& cross)
{
	_pCross = &cross;
	_pNode = 0;
}

template <typename T>
Cross<T>::Iterator::Iterator(const Cross<T>& cross, int m, int n)
{
	_pCross = &cross;
	_pNode = _pCross->_ppRow[m];
	while ( _pNode && _pNode->col != n)
		_pNode = _pNode->row_next;
}

template <typename T>
const typename Cross<T>::Iterator& 
Cross<T>::Iterator::operator=(const typename Cross<T>::Iterator& iter)
{
	_pCross = iter._pCross;
	_pNode = iter._pNode;
	return *this;
}

template <typename T>
const T& Cross<T>::Iterator::operator*() const
{
	assert(_pCross && _pNode);
	return _pNode->value;
}

template <typename T>
const typename Cross<T>::Iterator Cross<T>::Iterator::operator++(int)
{
	assert(_pCross && _pNode);
	Iterator temp;
	temp = *this;
	_pNode = _pNode->row_next;
	return temp;
}

template <typename T>
bool Cross<T>::Iterator::operator==(const typename Cross<T>::Iterator& iter) const
{
	return ( _pCross == iter._pCross && _pNode == iter._pNode );
}

template <typename T>
bool Cross<T>::Iterator::operator!=(const typename Cross<T>::Iterator& iter) const
{
	return ( _pCross != iter._pCross || _pNode != iter._pNode );
}

template <typename T>
int Cross<T>::Iterator::Row() const
{
	assert (_pCross && _pNode);
	return _pNode->row;
}

template <typename T>
int Cross<T>::Iterator::Col() const
{
	assert (_pCross && _pNode);
	return _pNode->col;
}