#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <object_table.h>
#include <polygon.h>
#include <line.h>
#include <utils.h>

#include <linkedlist.h>

struct vertex_node {
  listnode_t node;
  coord_t pos;
};

typedef struct polyfill_entry
{
  listnode_t node;
  int ymin;
  int ymax;
  float xval;
  float slope;
} polyfill_entry_t;

/**
 * Allocate a new polygon.
 *
 * @return the new allocated polygon object.
 */
polygon_t *
polygon_new( void )
{
  polygon_t *polygon = calloc( 1, sizeof(*polygon) );
  polygon->vertexes = list_new();

  OBJECT_TYPE( polygon ) = OBJECT_TYPE_POLYGON;

  return polygon;
}

/**
 * Free memory allocated to polygon.
 *
 * @param an allocated polygon object.
 */
void
polygon_free( polygon_t *polygon )
{
  assert( polygon != NULL );
  list_free( polygon->vertexes );
  free( polygon );
}

static int
edge_cmp( const listnode_t* edge1, const listnode_t *edge2 )
{
  polyfill_entry_t* e1 = (polyfill_entry_t* ) edge1;
  polyfill_entry_t* e2 = (polyfill_entry_t* ) edge2;

  if ( e1->xval < e2->xval )
    return -1;
  else if ( e1->xval == e2->xval )
    return ( e1->ymin < e2->ymin ) ? 1 : -1;
  else
    return 1;
}


static void
edges_sort( linkedlist_t *src )
{
  polyfill_entry_t *node;
  linkedlist_t *dst = list_new();

  for_each_list_element( src, node )
    list_insert_in_order( dst, *node, edge_cmp );

  swap( *src, *dst );

  list_free( dst );
}




/**
 * Add a new vertex to polygon.
 */
void
polygon_add_vertex( polygon_t *p, uint16_t x, uint16_t y )
{
  assert( p != NULL );

  struct vertex_node *node;
  node = list_add( p->vertexes, __typeof__(*node) );

  assert( node != NULL );
  SET_COORD( node->pos, x, y );
}

/**
 * Hace the polygon to have no vertexes.
 */
void
polygon_clear_vertexes( polygon_t *p )
{
  assert( p != NULL );
  list_clear( p->vertexes );
}



/**
 * Return the string representation of this polygon object.
 *
 * @note string is malloc()ated, please free() it later.
 *
 * @param polygon the object to act on.
 *
 * @return string representation.
 */
char *
polygon_str( polygon_t *polygon )
{
  char *s = NULL;
  int r;

  if ( polygon == NULL )
    r = asprintf( &s, "Polygon is NULL!" );
  else
    {
      r = asprintf( &s,
		    "Polygon( depth=%d, color=0x%08x, transp=%0.3f",
		    OBJECT_DEPTH( polygon ),
		    COLOR_TO_ARGB( OBJECT_COLOR( polygon ) ),
		    OBJECT_TRANSP( polygon )
		    );
      char *n;
      struct vertex_node *node;
      for_each_list_element( polygon->vertexes, node )
	{
	  r = asprintf( &n, "%s, p=( %u, %u )", s,
			node->pos.x, node->pos.y );
	  free( s );
	  s = n;
	}

      r = asprintf( &n, "%s )", s );
      free( s );
      s = n;
    }

  if ( r < 0 )
    s = NULL;

  return s;
}

void
polygon_draw_trivial( polygon_t *polygon, surface_t *surface )
{
  assert( surface != NULL );
  assert( surface->buffer != NULL );

  line_t *l = line_new();
  assert( l != NULL );

  object_init( l, OBJECT_COLOR( polygon ), OBJECT_TRANSP( polygon ),
	       OBJECT_DEPTH( polygon ), OBJECT_DRAW_OPTS( polygon ) );

  struct vertex_node *node, *next_node;
  for_each_list_element( polygon->vertexes, node )
    {
      uint16_t x0 = node->pos.x;
      uint16_t y0 = node->pos.y;

      next_node = LIST_NEXT( node );
      if ( LISTNODE( next_node ) == LIST_SENTINEL( polygon->vertexes ) )
	next_node = (struct vertex_node*)LIST_FIRST( polygon->vertexes );

      uint16_t x1 = next_node->pos.x;
      uint16_t y1 = next_node->pos.y;

      SET_RECT( l->r, x0, y0, x1, y1 );
      __line_draw( l, surface );
  }

  object_free( l );

  return;
}

static inline uint16_t
initialize_global_edge( linkedlist_t *global_edge,
			const linkedlist_t *vertexes )
{
  struct vertex_node *node, *next_node;
  uint16_t scanline = UINT16_MAX;

  for_each_list_element( vertexes, node )
    {
      uint16_t x0 = node->pos.x;
      uint16_t y0 = node->pos.y;

      next_node = LIST_NEXT( node );
      if ( LISTNODE( next_node ) == LIST_SENTINEL( vertexes ) )
	next_node = (struct vertex_node*)LIST_FIRST( vertexes );

      uint16_t x1 = next_node->pos.x;
      uint16_t y1 = next_node->pos.y;

      scanline = min( scanline, min( y0, y1 ) );

      if ( ( y1 - y0 ) != 0 )
	{
	  polyfill_entry_t nd;
	  nd.node.next = nd.node.prev = NULL;
	  nd.ymin = min( y0, y1 );
	  nd.ymax = max( y0, y1 );
	  nd.xval = ( y0 < y1 ) ? x0 : x1;
	  nd.slope = ( (float)x1 - (float)x0 ) / ( (float)y1 - (float)y0 );
	  list_insert_in_order( global_edge, nd, edge_cmp );
	}
    }
  return scanline;
}

static inline void
active_from_global_edge( linkedlist_t *active_edge,
			 const linkedlist_t *global_edge,
			 const uint16_t scanline )
{
  polyfill_entry_t *pnode;
  for_each_list_element( global_edge, pnode )
    if ( pnode->ymin == scanline )
      list_insert_in_order( active_edge, *pnode, edge_cmp );
}

static inline void
draw_scanline( const linkedlist_t *active_edge, const uint16_t scanline,
	       const surface_t *surface,
	       const color_t color, const float transp )
{
  polyfill_entry_t *last=NULL, *pnode;
  for_each_list_element( active_edge, pnode )
    {
      if ( last != NULL )
	{
	  line_draw_horizontal( last->xval + 1, pnode->xval + 1, scanline,
				surface, color, transp );
	  last = NULL;
	}
      else
	last = pnode;
    }

}

static inline void
remove_active_edges_with_ymax_equal_scanline( const linkedlist_t *active_edge,
					      const uint16_t scanline )
{
  polyfill_entry_t *pnode;
  for_each_list_element( active_edge, pnode )
    {
      if ( pnode->ymax == scanline )
	{
	  polyfill_entry_t *tmp = LIST_NEXT( LIST_NEXT( pnode ) );

	  list_del( active_edge, pnode );
	  if ( LIST_EMPTY( active_edge ) )
	    break;

	  pnode = LIST_PREV( LIST_PREV( tmp ) );
	}
    }
}

static inline void
remove_global_edges_with_ymin_equal_scanline( const linkedlist_t *global_edge,
					      const uint16_t scanline )
{
  polyfill_entry_t *pnode;
  for_each_list_element( global_edge, pnode )
    {
      if ( pnode->ymin == scanline )
	{
	  polyfill_entry_t *tmp = LIST_NEXT( LIST_NEXT( pnode ) );

	  list_del( global_edge, pnode );
	  if ( LIST_EMPTY( global_edge ) )
	    break;

	  pnode = LIST_PREV( LIST_PREV( tmp ) );
	}
    }
}

static inline void
fill_polygon( linkedlist_t *active_edge, linkedlist_t *global_edge,
	      uint16_t scanline, const surface_t *surface,
	      const color_t color, const float transp )
{
  polyfill_entry_t *pnode;

  while( ! LIST_EMPTY( active_edge ) )
   {
     draw_scanline( active_edge, scanline, surface, color, transp );
     scanline++;

     for_each_list_element( active_edge, pnode )
       pnode->xval += pnode->slope;

     remove_active_edges_with_ymax_equal_scanline( active_edge, scanline );

     active_from_global_edge( active_edge, global_edge, scanline );

     edges_sort( active_edge );

     remove_global_edges_with_ymin_equal_scanline( global_edge, scanline );
  }
}

void
polygon_draw_fill( polygon_t *polygon, surface_t *surface )
{
  assert( surface != NULL );
  assert( surface->buffer != NULL );
  uint16_t scanline;

  linkedlist_t *global_edge = list_new();
  linkedlist_t *active_edge = list_new();

  /*
   * Reference: http://www.cs.rit.edu/~icss571/filling/index.html
   */
  scanline = initialize_global_edge( global_edge, polygon->vertexes );
  active_from_global_edge( active_edge, global_edge, scanline );
  fill_polygon( active_edge, global_edge, scanline, surface,
		OBJECT_COLOR( polygon ), OBJECT_TRANSP( polygon ) );

  list_free( active_edge );
  list_free( global_edge );

  polygon_draw_trivial( polygon, surface );

  return;
}




void
__polygon_draw( polygon_t *polygon, surface_t *surface )
{
  assert( surface != NULL );
  assert( surface->buffer != NULL );


  void (*draw)( polygon_t *, surface_t * ) = NULL;

  if ( OBJECT_DRAW_OPTS( polygon ) & DRAW_FILL )
    draw = polygon_draw_fill;
  else
    draw = polygon_draw_trivial;

  draw( polygon, surface );

  return;

}

void
polygon_draw( polygon_t *polygon, surface_t *surface )
{
  surface_reset_visits( surface );
  __polygon_draw( polygon, surface );
}