/*
 * lmap.c   --  Datastructure 'lm_t' and operations.
 *
 * lm_t is a temporary datastructure, used by function 'processImage()'.
 *
 * See the header file lmap.h for comments on 'lm_t', and for comments
 * on the implementation of the lm_t functions.
 *
 */


#include "lmap.h"    /* lm_t, lmElem_t   */

#include "comp.h"    /* comp_t  */
#include  
#include   /* malloc(), free()  */

#include   /* INT_MAX, INT_MIN */



/****************************************************************************
 * Local functions
 ****************************************************************************/

#ifdef DEBUG
# include 
# include 
	static void DBG_print( char const * pFmt, ... ) 
		{
		va_list ap;
		va_start( ap, pFmt );
		vprintf( pFmt, ap );
		va_end( ap );
		}
	static void DBG_dumpUF( lm_t const * pLM )
		{
		printf( "\tUsed: { " );
		label_t k;
		for ( k = pLM->iUsedFirst; k != LABEL_EMPTY; k = pLM->pArr[k].next )
			{ 
			printf( "%u(%d) ", k, pLM->pArr[k].iLine );
			}
		printf( "}  " );

		printf( "Free: { " );
		for ( k = pLM->iFreeFirst; k != LABEL_EMPTY; k = pLM->pArr[k].next )
			{
			printf( "%u ", k );
			}
		printf( "}\n" );
		}
#else /*DEBUG */
# define DBG_print( a, ... )  /*empty replacement value*/
# define DBG_dumpUF( a )      /*empty replacement value*/
#endif /*DEBUG */



#ifdef DEBUG
/* Check that 'lbl' holds a valid label number.  */
static void __checkLabel( lm_t const * pLM, label_t lbl )
	{
	assert( lbl != LABEL_EMPTY );
	assert( lbl < pLM->N );
	}
#else /*DEBUG */
# define __checkLabel( a, b )  /*empty replacement value*/
#endif /*DEBUG */




/* Clear the data for one component */
static void __comp_clear( comp_t * p )
	{
	p->pixels = 0;

	p->bary_x = 0;
	p->bary_y = 0;

	p->min_x = INT_MAX;
	p->min_y = INT_MAX;
	p->max_x = INT_MIN;
	p->max_y = INT_MIN;
	}


static int __min( int a, int b ) { return ( a <= b ? a : b ); }
static int __max( int a, int b ) { return ( a >= b ? a : b ); }



/* 
 * Basic operations on the free and used lists.
 * 
 * The free list only implements stack operations (push, pop).
 * 
 * The used list implements the following operations:
 *    - Insert a given label number at the beginning of the list (push);
 *    - Remove a given label number from the list, where this label number
 *       can sit at any position in the list (remove).
 */

static void freelist_push( lm_t * pLM, label_t i1 )
	{
	__checkLabel( pLM, i1 );

	if ( pLM->iFreeFirst != LABEL_EMPTY ) 
		{ 
		pLM->pArr[ pLM->iFreeFirst ].prev = i1; 
		}
	pLM->pArr[i1].next = pLM->iFreeFirst;
	pLM->pArr[i1].prev = LABEL_EMPTY;
	pLM->iFreeFirst = i1;

	pLM->pArr[i1].uf = 0;  /* Mark label i1 as free */
	}

static label_t freelist_pop( lm_t * pLM ) /*Return popped label.*/
	{
	assert( pLM->iFreeFirst != LABEL_EMPTY ); /*Free list must not be empty.*/
	
	label_t i1 = pLM->iFreeFirst;

	pLM->iFreeFirst = pLM->pArr[i1].next;
	pLM->pArr[ pLM->iFreeFirst ].prev = LABEL_EMPTY;

	return i1;
	}


/* Insert label i1 at the beginning of the used list */
static void usedlist_push( lm_t * pLM, label_t i1 )
	{
	__checkLabel( pLM, i1 );

	if ( pLM->iUsedFirst != LABEL_EMPTY ) 
		{ 
		pLM->pArr[ pLM->iUsedFirst ].prev = i1; 
		}
	pLM->pArr[i1].next = pLM->iUsedFirst;
	pLM->pArr[i1].prev = LABEL_EMPTY;
	pLM->iUsedFirst = i1;
	if ( pLM->iUsedLast == LABEL_EMPTY ) { pLM->iUsedLast = i1; }

	/* Mark label i1 as used. */
	pLM->pArr[i1].uf = 1; 
	}

/* Remove any label i1 from the used list */
static void usedlist_remove( lm_t * pLM, label_t i1 )
	{
	__checkLabel( pLM, i1 );
	assert( pLM->pArr[i1].uf == 1 ); /*Label 'i1' must be in the used list. */
	assert( pLM->iUsedFirst != LABEL_EMPTY ); /*Used list must not be empty.*/
	assert( pLM->iUsedLast  != LABEL_EMPTY ); /*Used list must not be empty.*/

	if ( pLM->pArr[i1].prev == LABEL_EMPTY )
		{
		pLM->iUsedFirst = pLM->pArr[i1].next;
		}
	else
		{
		label_t iPrev = pLM->pArr[i1].prev;
		pLM->pArr[iPrev].next = pLM->pArr[i1].next;
		}

	if ( pLM->pArr[i1].next == LABEL_EMPTY )
		{ 
		pLM->iUsedLast = pLM->pArr[i1].prev;
		}
	else
		{
		label_t iNext = pLM->pArr[i1].next;
		pLM->pArr[iNext].prev = pLM->pArr[i1].prev;
		}
	}




/****************************************************************************
 * Exported functions
 ****************************************************************************/

/*
 * lm_alloc() --
 *
 * User instantiates an lm_t instance, then calls lm_alloc to
 * allocate the internal members of that lm_t instance.
 *
 * Parameter: 
 *   in_nLabels = the number of different labels that the map must store.
 *
 * Returns 0 on failure, 1 on success.
 */
int lm_alloc( 
	lm_t * pLM,
	int    in_nLabels )
	{
	pLM->pArr = (lmElem_t*)malloc( (in_nLabels+1) * sizeof(lmElem_t) );
	if ( pLM->pArr == NULL ) { return 0; }
	pLM->N = in_nLabels+1;
	return 1;
	}

/*
 * lm_free() --
 * Deallocate the internal members of the fl_t instance.
 */
void lm_free( lm_t * pLM )
	{
	free( pLM->pArr );
	}




/* lm_clearDataOfLabel() -- 
 * Clear compData, lblEq, and iLine of the label 'lbl'.  
 */
void lm_clearDataOfLabel(
	lm_t *  pLM,
	label_t lbl )
	{
	__checkLabel( pLM, lbl );

	lmElem_t * p = pLM->pArr + lbl;
		
	__comp_clear( &( p->compData ) );
	p->lblEq = LABEL_EMPTY;
	p->iLine = 0;
	}

/* lm_init() --
 * Initialize lm_t instance for beginning with a new image:
 *  - Each label's comp_t data is made empty
 *  - Each label has empty equivalence (i.e. maps to no other label)
 *  - All labels in the free list; used list empty.
 */
void lm_init( lm_t * pLM )
	{
	label_t k;

	/* Clear compData, lblEq, and iLine  */
	for ( k = 1; k < pLM->N; k++ )  /*element 0 unused.*/
		{
		lm_clearDataOfLabel( pLM, k );
		}

	/* Initialize the free and used lists: All labels are initially in
	 * the free list
     */
	pLM->iFreeFirst = 1;
	pLM->iUsedFirst = LABEL_EMPTY;
	pLM->iUsedLast  = LABEL_EMPTY;
	for ( k = 1; k < pLM->N; k++ )  /*element 0 unused.*/
		{ 
		pLM->pArr[k].prev = ( k > 1        ? k-1 : LABEL_EMPTY );
		pLM->pArr[k].next = ( k < pLM->N-1 ? k+1 : LABEL_EMPTY );
		pLM->pArr[k].uf = 0;
		}
	}





/* lm_getFreeLabel --
 * Take the first free label,
 * remove it from the free list and insert it into the used list.
 * Return this label.
 */
label_t lm_getFreeLabel( lm_t * pLM )
	{
	label_t i1 = freelist_pop( pLM );
	usedlist_push( pLM, i1 );
	return i1;
	}


/* lm_returnLabel() --
 * Remove the label 'i1' from the used list, 
 * and insert it into the free list.
 */
void lm_returnLabel( 
	lm_t *  pLM,
	label_t i1 )
	{
	usedlist_remove( pLM, i1 );
	freelist_push( pLM, i1 );
	}




/* lm_updateLineNr() --
 * Register that label 'lbl' was last used in line number 'in_iLine'.
 *
 * Implementation:
 * We have to keep the used list sorted, 
 *  from new (= large) line numbers at the beginning 
 *  to old (= small) line numbers at the end.
 * Therefore apart from changing the line number of the item 'lbl'
 *  we also move the item 'lbl' to the beginning of the used list.
 */
void lm_updateLineNr( 
	lm_t *  pLM,
	label_t lbl,
	int     in_iLine )
	{
	__checkLabel( pLM, lbl );
	assert( pLM->pArr[lbl].uf );

	/* The new iLine of 'lbl' can't be smaller than its old value. */
	assert( in_iLine >= pLM->pArr[lbl].iLine ); 


	/* Change line number. */
	pLM->pArr[lbl].iLine = in_iLine;

	/* Move item 'lbl' to the beginning of the used list. 
	 *
	 * (As an optimization, we do this only when necessary, namely when
	 * item 'lbl' is not already at the beginning.  This optimization makes
	 * sense because with big solid components, long strings of pixels with 
	 * the same label occur often.)
	 */
	if ( pLM->iUsedFirst != lbl ) 
		{
		/* Assert the correct used-list ordering: The iLine of the new list 
		 * head must not be smaller than that of the previous list head. */
		assert( in_iLine >= pLM->pArr[ pLM->iUsedFirst ].iLine );

		usedlist_remove( pLM, lbl );
		usedlist_push( pLM, lbl ); /*Insert at beginning.*/
		}
	}
	


/* lm_addEquiv() --
 * Register the equivalence that label 'from' maps to label 'to'.
 */
void lm_addEquiv( 
	lm_t *  pLM,
	label_t from, 
	label_t to )
	{
	__checkLabel( pLM, from );

	label_t * pEq = &( pLM->pArr[from].lblEq );

	/* Check old value of lblEq */
	assert( (*pEq == LABEL_EMPTY) || (*pEq == to) );

	*pEq = to;
	}


/* lm_getEquiv()  -- 
 * Retrieve equivalence.
 * Returns LABEL_EMPTY if 'from' does not map to any other component.
 */
label_t lm_getEquiv(
	lm_t *  pLM,
	label_t from )
	{
	__checkLabel( pLM, from );

	return pLM->pArr[from].lblEq;
	}




/* lm_addPixelToComp() --
 * Add to the comp_t of with label 'lbl' the data for the single
 * pixel at location in_x, in_y.
 */
void lm_addPixelToComp( 
	lm_t *  pLM,
	label_t lbl,
	int     in_x, 
	int     in_y )
	{
	__checkLabel( pLM, lbl );

	comp_t * pC = &( pLM->pArr[lbl].compData );

	pC->pixels += 1;

	pC->bary_x += (double)in_x;
	pC->bary_y += (double)in_y;

	pC->min_x = __min( pC->min_x, in_x );
	pC->min_y = __min( pC->min_y, in_y );
	pC->max_x = __max( pC->max_x, in_x );
	pC->max_y = __max( pC->max_y, in_y );
	}

/* lm_mergeCompIntoComp() --
 * Merge component lblSrc into lblDst (i.e. add the comp_t data for
 * component lblSrc into the comp_t of component lblDst),
 * then clear the entry for label 'lblSrc' in the component list.
 */
void lm_mergeCompIntoComp( 
	lm_t *  pLM,
	label_t lblDst, 
	label_t lblSrc )
	{
	__checkLabel( pLM, lblDst );
	__checkLabel( pLM, lblSrc );

	comp_t * pDst = &( pLM->pArr[lblDst].compData );
	comp_t * pSrc = &( pLM->pArr[lblSrc].compData );

	pDst->pixels += pSrc->pixels;

	pDst->bary_x += pSrc->bary_x;
	pDst->bary_y += pSrc->bary_y;

	pDst->min_x = __min( pDst->min_x, pSrc->min_x );
	pDst->min_y = __min( pDst->min_y, pSrc->min_y );
	pDst->max_x = __max( pDst->max_x, pSrc->max_x );
	pDst->max_y = __max( pDst->max_y, pSrc->max_y );

	__comp_clear( pSrc );
	}



/*
 * Finalize the center-of-mass computation for the component with
 * label 'lbl',
 * and then write this final comp_t for label 'lbl' to output.
 */
void lm_outComp( 
	lm_t *  pLM,
	label_t lbl,
	void    (*usrOutComp)( comp_t const * ) )
	{
	__checkLabel( pLM, lbl );
	
	comp_t * pC = &( pLM->pArr[lbl].compData );
	
	pC->bary_x /= (double)(pC->pixels);
	pC->bary_y /= (double)(pC->pixels);

	usrOutComp( pC );
	}




/*
 * lm_purgeOldLabels -- 
 *   Purge from lm_t all labels that have a line number smaller than in_iY.
 *
 * Writes the comp_t for the purged labels to the output, using the
 * user-defined function 'usrOutComp()'.
 *
 * Implementation: 
 * Since the used list is always kept sorted on iLine from new (=large) 
 * line numbers at the beginning to old (=small) line numbers at the end, 
 * we don't need to SEARCH the used list for the labels to be removed.
 * We can simply remove labels from the END of the used list.
 */
void lm_purgeOldLabels(
	lm_t *            pLM,     
	int               in_iY,                            /*Line Number. */
	void              (*usrOutComp)( comp_t const * ) ) /*Callback fn. */
	{
	DBG_dumpUF( pLM );

#ifdef DEBUG 
	/* Assert the condition that the used list is sorted on 
	 * line number (iLine), from large to small. 
	 */
	int iLinePrev = INT_MAX; 
	label_t j;
	for ( j = pLM->iUsedFirst; j != LABEL_EMPTY; j = pLM->pArr[j].next )
		{
		assert( pLM->pArr[j].iLine <= iLinePrev );
		iLinePrev = pLM->pArr[j].iLine;
		}
#endif

	label_t kRem;
	while ( kRem = pLM->iUsedLast,
	        (kRem != LABEL_EMPTY) && (pLM->pArr[kRem].iLine < in_iY) )
		{
		DBG_print( "\tPurge label %u\n", kRem );

		if ( pLM->pArr[kRem].compData.pixels > 0 )
			{
			DBG_print( "\tComponent %u --> out\n", kRem );
			lm_outComp( pLM, kRem, usrOutComp );
			}

		lm_clearDataOfLabel( pLM, kRem ); /*Init for reuse of label.*/

		lm_returnLabel( pLM, kRem );
		}
	}