/* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
* 
* This software is provided 'as-is', without any express or implied
* warranty. In no event will the authors be held liable for any damages
* arising from the use of this software.
* 
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
* 
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
* 
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
* 
* 3. This notice may not be removed or altered from any source distribution.
*/

/****************************************************************************
*
*  Visual C++ 6.0 created by: Julio Jerez
*
****************************************************************************/
#ifndef __dgGraph__
#define __dgGraph__

#include "dgStdafx.h"
#include "dgRef.h"
#include "dgList.h"


template<class dgNodeData, class dgEdgeData> class dgGraphEdge;
template<class dgNodeData, class dgEdgeData> class dgGraphNode;

template<class dgNodeData, class dgEdgeData>
class dgGraph: public dgList<dgGraphNode<dgNodeData, dgEdgeData> >
{
	public:
//	dgGraph ();
	dgGraph (dgMemoryAllocator* const allocator);
	~dgGraph ();


	typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* AddNode ();
	void DeleteNode (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node);

	void Trace () const;

	#ifdef _DEBUG
	dgInt32 m_counter;
	#endif
};

template<class dgNodeData, class dgEdgeData> 
class dgGraphNode: public dgList<dgGraphEdge<dgNodeData, dgEdgeData> >
{
	public:
	dgGraphNode ();
	~dgGraphNode ();

	typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* AddEdge(typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node);
	void DeleteHalfEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge);
	void DeleteEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge);

	void Trace () const;

#ifdef _DEBUG
	dgInt32 m_index;
#endif

	dgNodeData m_nodeData;
};

template<class dgNodeData, class dgEdgeData> 
class dgGraphEdge
{
	public:
	dgGraphEdge();
	~dgGraphEdge();

	typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* m_node;
	dgEdgeData m_edgeData;
};


/*
template<class dgNodeData, class dgEdgeData>
dgGraph<dgNodeData, dgEdgeData>::dgGraph () 
	:dgList<dgGraphNode<dgNodeData, dgEdgeData> >()
{
#ifdef _DEBUG
	m_counter = 0;
#endif
}
*/

template<class dgNodeData, class dgEdgeData>
dgGraph<dgNodeData, dgEdgeData>::dgGraph (dgMemoryAllocator* const allocator) 
	:dgList<dgGraphNode<dgNodeData, dgEdgeData> >(allocator)
{
#ifdef _DEBUG
	m_counter = 0;
#endif
}


template<class dgNodeData, class dgEdgeData>
dgGraph<dgNodeData, dgEdgeData>::~dgGraph () 
{
}

template<class dgNodeData, class dgEdgeData>
typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* dgGraph<dgNodeData, dgEdgeData>::AddNode ()
{
	typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node = dgGraph<dgNodeData, dgEdgeData>::Append();

	node->GetInfo().SetAllocator(dgGraph<dgNodeData, dgEdgeData>::GetAllocator());
#ifdef _DEBUG
	node->GetInfo().m_index = m_counter;
	m_counter ++;
#endif

	return node;
}

template<class dgNodeData, class dgEdgeData>
void dgGraph<dgNodeData, dgEdgeData>::DeleteNode (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node)
{
	for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link = node->GetInfo().GetFirst(); link; link = link->GetNext()) {	
		typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const twinNode = link->GetInfo().m_node;
		for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link1 = twinNode->GetInfo().GetFirst(); link1; link1 = link1->GetNext()) {	
			if (link1->GetInfo().m_node == node) {
				twinNode->GetInfo().Remove (link1);
				break;
			}
		}
	}
	Remove (node);
}

template<class dgNodeData, class dgEdgeData>
void dgGraph<dgNodeData, dgEdgeData>::Trace () const
{
	for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link = dgGraphNode<dgNodeData, dgEdgeData>::GetFirst(); link; link = link->GetNext()) {	
		link->GetInfo().Trace ();
//		dgTrace (("%d: ", link->GetInfo().m_index));
//		for (dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* edge = link->GetInfo().GetFirst(); edge; edge = edge->GetNext()) {	
//			dgListNode* node;
//			node = edge->GetInfo().m_node;
//			dgTrace (("%d ", node->GetInfo().m_index));
//		}
//		dgTrace (("\n"));
	}
	dgTrace (("\n"));
}


template<class dgNodeData, class dgEdgeData> 
dgGraphNode<dgNodeData, dgEdgeData>::dgGraphNode() 
	:dgList<dgGraphEdge<dgNodeData, dgEdgeData> >(NULL)
{

}


template<class dgNodeData, class dgEdgeData> 
dgGraphNode<dgNodeData, dgEdgeData>::~dgGraphNode() 
{

}

template<class dgNodeData, class dgEdgeData> 
typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* dgGraphNode<dgNodeData, dgEdgeData>::AddEdge (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node)
{
	typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* edge = dgGraphNode<dgNodeData, dgEdgeData>::Append();

	edge->GetInfo().m_node = node;
	return edge;
}

template<class dgNodeData, class dgEdgeData> 
void dgGraphNode<dgNodeData, dgEdgeData>::DeleteHalfEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge)
{
	Remove (edge);
}

template<class dgNodeData, class dgEdgeData> 
void dgGraphNode<dgNodeData, dgEdgeData>::DeleteEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge)
{
	typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node = edge->GetInfo().m_node;
	
	for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* twinEdge = node->GetInfo().GetFirst(); twinEdge; twinEdge = twinEdge->GetNext()) {	
		if (&twinEdge->GetInfo().m_node->GetInfo() == this) {
			node->GetInfo().DeleteHalfEdge(twinEdge);
			break;
		}
	}

	DeleteHalfEdge(edge);
}	

template<class dgNodeData, class dgEdgeData> 
void dgGraphNode<dgNodeData, dgEdgeData>::Trace () const
{
	dgTrace (("%d: ", m_index));
	for (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* edge = typename dgGraph<dgNodeData, dgEdgeData>::GetFirst(); edge; edge = edge->GetNext()) {	
		typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node;
		node = edge->GetInfo().m_node;
		dgTrace (("%d ", node->GetInfo().m_index));
	}
	dgTrace (("\n"));

}


template<class dgNodeData, class dgEdgeData> 
dgGraphEdge<dgNodeData, dgEdgeData>::dgGraphEdge() 
{

}

template<class dgNodeData, class dgEdgeData> 
dgGraphEdge<dgNodeData, dgEdgeData>::~dgGraphEdge() 
{

}



#endif