// chain-code.c         Section: 12.2
//      Copyright 1994, Center for Computer Vision and Visualization,
//      University of Florida.  All rights reserved.

// Chain Code extraction.

#include "chain-code.h"
#include "IntDI.h"
#include "DDTempl.h"
#include "IntConv.h"


// Delta function, as an array:

static IA_Point<int> delta[] = {
    IA_Point<int>(  0,  1 ),
    IA_Point<int>( -1,  1 ),
    IA_Point<int>( -1,  0 ),
    IA_Point<int>( -1, -1 ),
    IA_Point<int>(  0, -1 ),
    IA_Point<int>(  1, -1 ),
    IA_Point<int>(  1,  0 ),
    IA_Point<int>(  1,  1 )
};



// This code is directly fromRobert H. Forsman <thoth@cis.ufl.edu>
//   with minor comments from <rjj@cis.ufl.edu>
/* calculate the lookup table for a robust chain-code follower */

//#include	<stdio.h> 

int code( int prev, int val )
//    prev	direction we're coming from, [0..7]
//    val	census value [1..511]
{
    char	bits[9];
    int	i;

    if (! (val&(1<<8)))
	return 0;

    for (i=0; i<8; i++) {
	bits[i] = val&1;
	val >>=1;
    }
    bits[8] = bits[0];

    for (i=0; i<=6; i++) {	/* start looking at 3 oclock and go */
				/* counterclockwise looking for a pixel. */
#if 1
	// Proceed clockwise around the figure.
	// The most mysterious point in this algorithm is why don\'t
	//   we have to consider the point that is at (prev+8+3)%8
	//   as the starting point.  After tracing the boundary of
	//   a few figures you will convince yourself that it is
	//   simply impossible for that point to have data in it.
	// If it *had* had data, then it would have been choosen
	//   at the previous step in the algorithm, and the direction
	//   to this point would be different.
	int	dir = (prev+8+2-i) % 8;
#else
	// Proceed counterclockwise around the figure.
	int	dir = (prev+6+i) % 8;
#endif
	if (bits[dir])
	    return dir+1;
    }
    return -1;
}


IA_Array<u_char>
chain_code( const IA_Image<IA_Point<int>,IA_Bit> & source,
	    IA_Point<int> & x0 )
{
    // Declare the template.  We have to use IDDT since u_char < 511
    static int censusVals[] = { 8, 4, 2,  16, 256, 1,  32, 64, 128 };

    IA_DDTemplate<IA_Image<IA_Point<int>,int> >
	t( 2,
	   IA_Image<IA_Point<int>,int>(
	       IA_boxy_pset( IA_Point<int>( -1, -1 ),
			     IA_Point<int>(  1,  1 ) ),
	       censusVals, (unsigned int) 9 ) );

    // Now calculate the census image
    IA_Image<IA_Point<int>,int>
	n( linear_product( IA_Image<IA_Point<int>,int>( source ), t ) );


    // We are ready for the heart of the algorithm,
    //   however we still have to initialize the loop variables.

    // Calculate the lexicographically minimum point with a 1 value
    //   which is returned thru the reference argument x0
    x0 = source.restrict( IA_Set<IA_Bit>(IA_Bit(1)) )
	       .domain()
	       .min();
    IA_Point<int>
	x = x0;

    int 
	direction = 0,                  // Clockwise search
	firstDir  = code( direction,    // First dir to look + 1
			  n( x0 )   ),
	i         = 0;

    if (firstDir == 0) {
	return IA_Array<u_char>( 0 );   // Zero length chain
    }

    // An interesting problem is how much space to allocate for the
    //   result.  We could just calculate the result twice, but 
    //   instead I\'ll use the resizable array property of IA_Array<T>

    int csize = source.domain().card();
    IA_Array<u_char> c( csize );  // Should be over kill...

    while ( 1 ) {
	direction = code( direction, n( x ) ) - 1;

	if ( ( direction == firstDir ) && ( x == x0 ) && ( i != 0 ) ) {
	    break;
	};

	// Assign to c, but check if we need to resize c first.
	if ( i == csize ) {
	    csize += csize;  // Double the length
	    c.resize( csize );
	}
	c[ i ] = direction;
	x += delta[ direction ];
	i++;
    }
    return c.resize( i );
}



IA_Image<IA_Point<int>,IA_Bit>
chain_code_image( const IA_Array<u_char> & chain_code,
		  const IA_Set<IA_Point<int> > & cc_domain,
		  const IA_Point<int> & start ) {

    IA_Image<IA_Point<int>,IA_Bit>
	cc_image( cc_domain, IA_Bit( 0 ) );

    IA_Point<int> x( start );
    for( int i=0; i<chain_code.len(); i++ ) {
	cc_image[ x ] = IA_Bit( 1 );
	x += delta[ chain_code( i ) ];
    }
    return cc_image;
}

double
chain_code_correlation( const IA_Array<u_char> & chain_1,
			const IA_Array<u_char> & chain_2 ) {

    // ~thoth/class/cap6657/proj8.c
    return 0;
}
