/* LIBDGL -- a Directed Graph Library implementation
 * Copyright (C) 2002 Roberto Micarelli
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*
 * best view with tabstop=4
 */

int DGL_ADD_NODE_FUNC(
						dglGraph_s *  pgraph,
						dglInt32_t       nId,
						void * 			pvNodeAttr,	
						dglInt32_t 		nFlags
					)
{
	DGL_T_NODEITEM_TYPE * 	pNodeItem;
	dglInt32_t *		pnode;

	if ( pgraph->Flags & DGL_GS_FLAT )
	{
		pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
		return -pgraph->iErrno;
	}

	if ( (pNodeItem = DGL_T_NODEITEM_Add( pgraph->pNodeTree , nId )) == NULL )
	{
		pgraph->iErrno = DGL_ERR_MemoryExhausted;
		return -pgraph->iErrno;
	}

	if ( DGL_T_NODEITEM_NodePTR(pNodeItem) == NULL )
	{
		if ( (pnode = DGL_NODE_ALLOC( pgraph->NodeAttrSize )) == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		memset( pnode, 0, DGL_NODE_SIZEOF(pgraph->NodeAttrSize) );
		DGL_NODE_ID(pnode) = nId;
		DGL_NODE_STATUS(pnode) = DGL_NS_ALONE;
		DGL_T_NODEITEM_Set_NodePTR(pNodeItem,pnode);
		pgraph->cNode ++;
		pgraph->cAlone ++;
	}
	else
	{
		/* node already exists */
		pgraph->iErrno = DGL_ERR_NodeAlreadyExist;
		return -pgraph->iErrno;
	}
	return 0;
}

#if !defined(_DGL_V1)
/*
 * Delete the link from the node's out-edgeset
 */
int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s *  pgraph, dglInt32_t nNode, dglInt32_t nEdge)
{
	DGL_T_NODEITEM_TYPE * pNodeItem , findNodeItem;
	dglInt32_t * pnEdgeset, * pnEdge, * pnNode;
	dglEdgesetTraverser_s	t;

	findNodeItem.nKey = nNode;

	if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) != NULL) {
		pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
		if ( DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE ) {
			return 0;
		}
		if ( (pnEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem)) != NULL ) {
			if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&t,pnEdgeset) >= 0 ) {
				for (
					pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t) ;
					pnEdge ;
					pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
					)
				{
					if (DGL_EDGE_ID(pnEdge) == nEdge)
					{
						register dglInt32_t * pnSet;
						register int i1, i2, c;

						c = pnEdgeset[0];

						if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
							pgraph->iErrno = DGL_ERR_MemoryExhausted;
							return -pgraph->iErrno;
						}

						for(i1 = 0, i2 = 0 ; i2 < c ; i2++) {
							if (pnEdgeset[1 + i2] != nEdge) {
								pnSet[1 + i1++] = pnEdgeset[1 + i2];
							}
						}
						pnSet[0] = i1;

						free(pnEdgeset);
						DGL_T_NODEITEM_Set_OutEdgesetPTR(pNodeItem,pnSet);
						break;
					}
				}
			}
		}
		{ /* check alone status */
			dglInt32_t *pIn, *pOut, *pNode;
			pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
			pIn  = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
			pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
			if	(
				(pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
				(pIn  == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
				)
			{
				if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD) pgraph->cHead--;
				if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL) pgraph->cTail--;
				DGL_NODE_STATUS(pNode) = DGL_NS_ALONE; pgraph->cAlone++;	
			}
		}
	}
	return 0;
}

int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge)
{
	DGL_T_NODEITEM_TYPE * pNodeItem , findNodeItem;
	dglInt32_t * pnEdgeset, * pnEdge, * pnNode;
	dglEdgesetTraverser_s	t;

	findNodeItem.nKey = nNode;

	if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) != NULL) {
		pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
		if ( DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE ) {
			return 0;
		}
		if ( (pnEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem)) != NULL ) {
			if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&t,pnEdgeset) >= 0 ) {
				for (
					pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t) ;
					pnEdge ;
					pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
					)
				{
					if (DGL_EDGE_ID(pnEdge) == nEdge)
					{
						register dglInt32_t * pnSet;
						register int i1, i2, c;

						c = pnEdgeset[0];

						if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
							pgraph->iErrno = DGL_ERR_MemoryExhausted;
							return -pgraph->iErrno;
						}

						for(i1 = 0, i2 = 0 ; i2 < c ; i2++) {
							if (pnEdgeset[1 + i2] != nEdge) {
								pnSet[1 + i1++] = pnEdgeset[1 + i2];
							}
						}
						pnSet[0] = i1;

						free(pnEdgeset);
						DGL_T_NODEITEM_Set_InEdgesetPTR(pNodeItem,pnSet);
						break;
					}
				}
			}
		}
		{ /* check alone status */
			dglInt32_t *pIn, *pOut, *pNode;
			pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
			pIn  = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
			pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
			if	(
				(pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
				(pIn  == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
				)
			{
				if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD) pgraph->cHead--;
				if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL) pgraph->cTail--;
				DGL_NODE_STATUS(pNode) = DGL_NS_ALONE; pgraph->cAlone++;	
			}
		}
	}
	return 0;
}
#endif

int DGL_DEL_NODE_FUNC( dglGraph_s *  pgraph, dglInt32_t nNodeId )
{
#if defined(_DGL_V1)
	pgraph->iErrno = DGL_ERR_NotSupported;
	return -pgraph->iErrno;
#else
	DGL_T_NODEITEM_TYPE * 	pNodeItem, findNodeItem;
	dglInt32_t *		pEdgeset;
	dglInt32_t *		pnode;
	dglInt32_t *		pEdge;
	dglEdgesetTraverser_s	trav;

	dglTreeEdge_s *	pEdgeItem;

	if ( pgraph->Flags & DGL_GS_FLAT )
	{
		pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
		return -pgraph->iErrno;
	}

	if ( pgraph->pNodeTree == NULL ) {
		pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
		return -pgraph->iErrno;
	}

	findNodeItem.nKey = nNodeId;
	if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) == NULL) {
		pgraph->iErrno = DGL_ERR_NodeNotFound;
        return -pgraph->iErrno;
	}

	pnode = DGL_T_NODEITEM_NodePTR(pNodeItem);

	if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE ) goto node_is_alone;

	pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);

	if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&trav,pEdgeset) < 0 ) return -pgraph->iErrno;
	for (
		pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav) ;
		pEdge ;
		pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
		)
	{
		if ( DGL_EDGE_TAILNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode) ) {
			if ( DGL_DEL_NODE_INEDGE_FUNC(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
				return -pgraph->iErrno;
			}
		}
		if ( (pEdgeItem = trav.pvCurrentItem) != NULL ) {
			/* prioritizer sync
			 */
			if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
				if ( dgl_edge_prioritizer_del(pgraph,DGL_EDGE_ID(pEdge),DGL_EDGE_COST(pEdge)) < 0) {
					return -pgraph->iErrno;
				}
			}
			/*
			 */
			pgraph->cEdge--;
			pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);

			avl_delete(pgraph->pEdgeTree, pEdgeItem);
			dglTreeEdgeCancel(pEdgeItem,NULL);
		}
	}
	DGL_EDGESET_T_RELEASE_FUNC(&trav);

	pEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);

	if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&trav,pEdgeset) < 0 ) return -pgraph->iErrno;
	for (
		pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav) ;
		pEdge ;
		pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
		)
	{
		if ( DGL_EDGE_HEADNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode) ) {
			if ( DGL_DEL_NODE_OUTEDGE_FUNC(pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
				return -pgraph->iErrno;
			}
		}
		if ( (pEdgeItem = trav.pvCurrentItem) != NULL ) {
			/* prioritizer sync
			 */
			if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
				if ( dgl_edge_prioritizer_del(pgraph,DGL_EDGE_ID(pEdge),DGL_EDGE_COST(pEdge)) < 0) {
					return -pgraph->iErrno;
				}
			}
			/*
			 */
			pgraph->cEdge--;
			pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);

			avl_delete(pgraph->pEdgeTree, pEdgeItem);
			dglTreeEdgeCancel(pEdgeItem,NULL);
		}
	}
	DGL_EDGESET_T_RELEASE_FUNC(&trav);

	if ( DGL_NODE_STATUS(pnode) & DGL_NS_HEAD  ) pgraph->cHead--;
	if ( DGL_NODE_STATUS(pnode) & DGL_NS_TAIL    ) pgraph->cTail--;

	node_is_alone:
	if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE ) pgraph->cAlone--;
	pgraph->cNode--;

	avl_delete( pgraph->pNodeTree, pNodeItem );
	DGL_T_NODEITEM_Cancel(pNodeItem, NULL);

	return 0;
#endif
}

dglInt32_t * DGL_GET_NODE_FUNC( dglGraph_s * pgraph , dglInt32_t nodeid )
{
	register dglInt32_t 		top;	/* top of table */
	register dglInt32_t 		pos;	/* current position to compare */
	register dglInt32_t 		bot;	/* bottom of table */
	register dglInt32_t *	pref;
	register int			cwords; /* size of a node in words of 32 bit */
	register dglTreeNode_s * ptreenode;
	dglTreeNode_s 	findnode;
	dglInt32_t		id;

	pgraph->iErrno = 0;
	if ( pgraph->Flags & DGL_GS_FLAT ) {
		cwords = DGL_NODE_WSIZE(pgraph->NodeAttrSize);
		/*bot    = pgraph->iNodeBuffer / DGL_NODE_SIZEOF(pgraph->NodeAttrSize);*/
		bot    = pgraph->cNode;
		top    = 0;
		pos    = 0;
		pref   = (dglInt32_t*)pgraph->pNodeBuffer;

		/* perform a binary search
	 	*/
		while( top != bot ) {
			pos = top + (bot - top) / 2;
			id = DGL_NODE_ID(& pref[pos * cwords]);
			if ( id == nodeid ) {
				break;
			}
			else if ( nodeid < id ) {
				bot = pos;
			}
			else if ( nodeid > id ) {
				top = pos + 1;
			}
		}
		if ( top == bot ) {
			return NULL;
		}
		return & pref[ pos * cwords ];
	}
	else {
		findnode.nKey = nodeid;
		ptreenode = avl_find( pgraph->pNodeTree , &findnode );
		if ( ptreenode && ptreenode->pv ) {
			return ptreenode->pv;
		}
		return NULL;
	}
}

/*
 * if graph is FLAT retrieve the edge area from the pEdgeBuffer
 * if graph is TREE retrieve the node from the pNodeTree avl and return pv field
 */
dglInt32_t * DGL_GET_NODE_OUTEDGESET_FUNC( dglGraph_s * pgraph , dglInt32_t * pnode )
{
	DGL_T_NODEITEM_TYPE * ptreenode, findnode;
	dglInt32_t * pEdgeset;

	pgraph->iErrno = 0;

	if ( pnode == NULL ) {
		pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
		return NULL;
	}

	if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
		pgraph->iErrno = DGL_ERR_NodeIsAComponent;
		return NULL;
	}

	if ( pgraph->Flags & DGL_GS_FLAT ) {
		pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
		return pEdgeset;
	}
	else {
		findnode.nKey = DGL_NODE_ID(pnode);
		ptreenode = avl_find( pgraph->pNodeTree , &findnode );
		if ( ptreenode && DGL_T_NODEITEM_OutEdgesetPTR(ptreenode) ) {
			return DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
		}
		return NULL;
	}
}

dglInt32_t * DGL_GET_NODE_INEDGESET_FUNC( dglGraph_s * pgraph , dglInt32_t * pnode )
{
#if defined(_DGL_V1)
	pgraph->iErrno = DGL_ERR_NotSupported;
	return NULL;
#endif

#if defined(_DGL_V2)
	DGL_T_NODEITEM_TYPE * 	ptreenode, findnode;
	dglInt32_t * 	pEdgeset;

	pgraph->iErrno = 0;

	if ( pnode == NULL ) {
		pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
		return NULL;
	}

	if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
		pgraph->iErrno = DGL_ERR_NodeIsAComponent;
		return NULL;
	}

	if ( pgraph->Flags & DGL_GS_FLAT ) {
		pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
		pEdgeset += DGL_EDGESET_WSIZE(DGL_EDGESET_EDGECOUNT(pEdgeset), pgraph->EdgeAttrSize);
		return pEdgeset;
	}
	else {
		findnode.nKey = DGL_NODE_ID(pnode);
		ptreenode = avl_find( pgraph->pNodeTree , &findnode );
		if ( ptreenode && DGL_T_NODEITEM_InEdgesetPTR(ptreenode) ) {
			return DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
		}
		return NULL;
	}
#endif
}