/* 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
 */


/*
 * Add edge can be performed on TREE state graph. If the state is FLAT
 * return BadOnFlatGraph error.
 */
int DGL_ADD_EDGE_FUNC (
						dglGraph_s * 	pgraph ,
						dglInt32_t 		nHead,
						dglInt32_t 		nTail,
						dglInt32_t 		nCost,
						dglInt32_t 		nEdge,
						void * pvHeadAttr ,	
						void * pvTailAttr ,	
						void * pvEdgeAttr ,
						dglInt32_t 		nFlags
						)
{
	dglInt32_t *		pHead;
	dglInt32_t *		pTail;
	dglInt32_t *		pEdgeset;
	dglInt32_t *		pEdge;
	DGL_T_NODEITEM_TYPE * 	pHeadNodeItem;
	DGL_T_NODEITEM_TYPE * 	pTailNodeItem;
#if defined(_DGL_V2)
	dglInt32_t *		pinEdgeset;
	dglTreeEdge_s *	pEdgeItem;
	dglTreeEdge_s 	findEdge;
#endif

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

#ifdef DGL_STATS
	{
		clock_t clk = clock();
#endif

	if (
		(pHeadNodeItem = DGL_T_NODEITEM_Add( pgraph->pNodeTree , nHead )) == NULL
		||
		(pTailNodeItem   = DGL_T_NODEITEM_Add( pgraph->pNodeTree , nTail   )) == NULL
	   )
	{
		pgraph->iErrno = DGL_ERR_MemoryExhausted;
		return -pgraph->iErrno;
	}

#ifdef DGL_STATS
		pgraph->clkNodeTree += clock() - clk;
		pgraph->cNodeTree ++;
		pgraph->cNodeTree ++;
	}
#endif

	if ( DGL_T_NODEITEM_NodePTR(pHeadNodeItem) == NULL )
	{
		if ( (pHead = DGL_NODE_ALLOC( pgraph->NodeAttrSize )) == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -1;
		}
		DGL_NODE_STATUS(pHead) = 0;
		DGL_T_NODEITEM_Set_NodePTR(pHeadNodeItem,pHead);
		pgraph->cNode ++;
		pgraph->cHead ++;
	}
	else
	{
		pHead = DGL_T_NODEITEM_NodePTR(pHeadNodeItem);
		if ( !(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) ) pgraph->cHead++;
	}

	if ( DGL_T_NODEITEM_NodePTR(pTailNodeItem) == NULL )
	{
		if ( (pTail = DGL_NODE_ALLOC( pgraph->NodeAttrSize )) == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_NODE_STATUS(pTail) = 0;
		DGL_T_NODEITEM_Set_NodePTR(pTailNodeItem,pTail);
		pgraph->cNode ++;
		pgraph->cTail ++;
	}
	else
	{
		pTail = DGL_T_NODEITEM_NodePTR(pTailNodeItem);
		if ( !(DGL_NODE_STATUS(pTail) & DGL_NS_TAIL) ) pgraph->cTail++;
	}


	DGL_NODE_STATUS(pHead) |= DGL_NS_HEAD;
	DGL_NODE_STATUS(pTail) |= DGL_NS_TAIL;

	if ( DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ) {
		DGL_NODE_STATUS(pHead) &= ~DGL_NS_ALONE;
		pgraph->cAlone --;
	}

	if ( DGL_NODE_STATUS(pTail  ) & DGL_NS_ALONE ) {
		DGL_NODE_STATUS(pTail  ) &= ~DGL_NS_ALONE;
		pgraph->cAlone --;
	}

	DGL_NODE_ID(pHead) = nHead;
	DGL_NODE_ID(pTail) = nTail;

	DGL_NODE_EDGESET_OFFSET(pHead) = -1;
	DGL_NODE_EDGESET_OFFSET(pTail) = -1;

	if ( pvHeadAttr && pgraph->NodeAttrSize ) {
		memcpy( DGL_NODE_ATTR_PTR(pHead), pvHeadAttr, pgraph->NodeAttrSize );
	}

	if ( pvTailAttr && pgraph->NodeAttrSize ) {
		memcpy( DGL_NODE_ATTR_PTR(pTail), pvTailAttr, pgraph->NodeAttrSize );
	}


	/*
	if ( DGL_T_NODEITEM_OutEdgesetPTR(pTailNodeItem) == NULL )
	{
		pEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
		if ( pEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
		DGL_T_NODEITEM_Set_OutEdgesetPTR(pTailNodeItem,pEdgeset);
	}
	*/

	if ( (pEdgeset=DGL_T_NODEITEM_OutEdgesetPTR(pHeadNodeItem)) == NULL )
	{
		pEdgeset = DGL_EDGESET_ALLOC( 1 , pgraph->EdgeAttrSize );
		if ( pEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
		DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem,pEdgeset);
	}
	else
	{
		pEdgeset = DGL_EDGESET_REALLOC( pEdgeset ,
							DGL_EDGESET_EDGECOUNT(pEdgeset) + 1 ,
							pgraph->EdgeAttrSize );

		if ( pEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem,pEdgeset);
	}

#if defined(_DGL_V2)
	/*
	if ( DGL_T_NODEITEM_InEdgesetPTR(pHeadNodeItem) == NULL )
	{
		pinEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
		if ( pinEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
		DGL_T_NODEITEM_Set_InEdgesetPTR(pHeadNodeItem,pinEdgeset);
	}
	*/

	if ( (pinEdgeset=DGL_T_NODEITEM_InEdgesetPTR(pTailNodeItem)) == NULL )
	{
		pinEdgeset = DGL_EDGESET_ALLOC( 1 , pgraph->EdgeAttrSize );
		if ( pinEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
		DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem,pinEdgeset);
	}
	else
	{
		pinEdgeset = DGL_EDGESET_REALLOC( pinEdgeset ,
							DGL_EDGESET_EDGECOUNT(pinEdgeset) + 1 ,
							pgraph->EdgeAttrSize );

		if ( pinEdgeset == NULL ) {
			pgraph->iErrno = DGL_ERR_MemoryExhausted;
			return -pgraph->iErrno;
		}
		DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem,pinEdgeset);
	}

	/*
	 * Set the edge-tree
	 */
	findEdge.nKey = nEdge;

	if ( (pEdgeItem = dglTreeEdgeAdd(pgraph->pEdgeTree, nEdge)) == NULL) {
		pgraph->iErrno = DGL_ERR_MemoryExhausted;
		return -pgraph->iErrno;
	}
	if ( pEdgeItem->pv ) {
		pgraph->iErrno = DGL_ERR_EdgeAlreadyExist;
		return -pgraph->iErrno;
	}
	if ( (pEdgeItem->pv = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL ) {
		pgraph->iErrno = DGL_ERR_MemoryExhausted;
		return -pgraph->iErrno;
	}

	/*
	 * assign edge id
	 */
	pEdgeset[DGL_EDGESET_EDGECOUNT(pEdgeset)+1] = nEdge;
	pinEdgeset[DGL_EDGESET_EDGECOUNT(pinEdgeset)+1] = nEdge;
	++DGL_EDGESET_EDGECOUNT(pEdgeset);
	++DGL_EDGESET_EDGECOUNT(pinEdgeset);

	/*
printf( "add edge: node %ld(%ld,%ld) -> %ld(%ld,%ld)\n",
				DGL_NODE_ID(pHead), DGL_EDGESET_EDGECOUNT(pEdgeset),0,
				DGL_NODE_ID(pTail), 0,DGL_EDGESET_EDGECOUNT(pinEdgeset));
				*/


	pEdge = pEdgeItem->pv;
#endif

#if defined(_DGL_V1)
	pEdge = DGL_EDGESET_EDGE_PTR(pEdgeset, DGL_EDGESET_EDGECOUNT(pEdgeset), pgraph->EdgeAttrSize);
	DGL_EDGESET_EDGECOUNT(pEdgeset) ++;
#endif

	DGL_EDGE_HEADNODE_OFFSET(pEdge) = nHead;		/* will be an offset after flattening */
	DGL_EDGE_TAILNODE_OFFSET(pEdge) = nTail;		/* will be an offset after flattening */
	DGL_EDGE_COST(pEdge)            = nCost;
	DGL_EDGE_ID(pEdge)              = nEdge;

#if !defined(_DGL_V1)
	if (nFlags & DGL_ES_DIRECTED)
		DGL_EDGE_STATUS(pEdge) = DGL_ES_DIRECTED;
	else
		DGL_EDGE_STATUS(pEdge) = 0;
#endif

	pgraph->cEdge ++;
	pgraph->nnCost += (dglInt64_t)nCost;

	if ( pvEdgeAttr && pgraph->EdgeAttrSize ) {
		memcpy( DGL_EDGE_ATTR_PTR(pEdge), pvEdgeAttr, pgraph->EdgeAttrSize );
	}

	/*
	 * If requested add a cost-weighted entry into the edge prioritizer
	 */
#if !defined(_DGL_V1)
	if ( pgraph->nOptions & DGL_GO_EdgePrioritize_COST ) {
		if (dgl_edge_prioritizer_add(pgraph,DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
			return -pgraph->iErrno;
		}
	}
#endif

	if ( nFlags & DGL_STRONGCONNECT ) {
		return DGL_ADD_EDGE_FUNC(pgraph,nTail,nHead,nCost,nEdge,pvHeadAttr,pvTailAttr,pvEdgeAttr,nFlags & ~DGL_STRONGCONNECT);
	}

	return 0;
}

int DGL_DEL_EDGE_FUNC( dglGraph_s * pgraph, dglInt32_t nEdge )
{
#if defined(_DGL_V1)
	pgraph->iErrno = DGL_ERR_NotSupported;
	return -pgraph->iErrno;
#else
	dglTreeEdge_s * pEdgeItem , findEdgeItem;
	dglInt32_t * pEdge;

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

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

	findEdgeItem.nKey = nEdge;
	if ( (pEdgeItem = avl_find( pgraph->pEdgeTree, &findEdgeItem )) == NULL) {
		pgraph->iErrno = DGL_ERR_EdgeNotFound;
        return -pgraph->iErrno;
	}

	pEdge = pEdgeItem->pv;

	if ( DGL_DEL_NODE_INEDGE_FUNC(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
		return -pgraph->iErrno;
	}

	if ( DGL_DEL_NODE_OUTEDGE_FUNC(pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
		return -pgraph->iErrno;
	}

	
	/* 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);
	return 0;
#endif
}

dglInt32_t * DGL_GET_EDGE_FUNC( dglGraph_s * pgraph , dglInt32_t nEdge )
{
#if defined(_DGL_V1)
	pgraph->iErrno = DGL_ERR_NotSupported;
	return NULL;
#else
	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 edge in words of 32 bit */
	register dglTreeEdge_s * ptreeEdge;
	dglTreeEdge_s 	findEdge;
	dglInt32_t		id;

	pgraph->iErrno = 0;
	if ( pgraph->Flags & DGL_GS_FLAT ) {
		cwords = DGL_EDGE_WSIZE(pgraph->EdgeAttrSize);
		/*bot    = pgraph->iEdgeBuffer / DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize);*/
		bot    = pgraph->cEdge;
		top    = 0;
		pos    = 0;
		pref   = (dglInt32_t*)pgraph->pEdgeBuffer;

		/* perform a binary search
	 	*/
		while( top != bot ) {
			pos = top + (bot - top) / 2;
			id = DGL_EDGE_ID(& pref[pos * cwords]);
			if ( id == nEdge ) {
				break;
			}
			else if ( nEdge < id ) {
				bot = pos;
			}
			else if ( nEdge > id ) {
				top = pos + 1;
			}
		}
		if ( top == bot ) {
			return NULL;
		}
		return & pref[ pos * cwords ];
	}
	else {
		findEdge.nKey = nEdge;
		ptreeEdge = avl_find( pgraph->pEdgeTree , &findEdge );
		if ( ptreeEdge && ptreeEdge->pv ) {
			return ptreeEdge->pv;
		}
		return NULL;
	}
#endif
}