/* jsppmcmap.c - colormap routines
** Last edited on 2007-10-28 19:46:03 by stolfi
**
** adapted from Jef Poskanzer's libppm3.c - ppm utility library part 3
**
** Copyright (C) 1989, 1991 by Jef Poskanzer.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation.  This software is provided "as is" without express or
** implied warranty.
*/

#include <jsppmcmap.h>

#include <jspnm.h>

#define HASH_SIZE 20023

#define ppm_hashpixel(p) ( ( ( (long) p.c[0] * 33023 + (long) p.c[1] * 30013 + (long) p.c[2] * 27011 ) & 0x7fffffff ) % HASH_SIZE )

ppm_cmapx_hist_vector ppm_cmapx_hist_build( rgb_pixel_t** pixels, int cols, int rows, int maxcolors, int* colorsP)
  {
    ppm_cmapx_table cht;
    ppm_cmapx_hist_vector chv;

    cht = ppm_cmapx_table_build( pixels, cols, rows, maxcolors, colorsP );
    if ( cht == (ppm_cmapx_table)NULL )
      { return (ppm_cmapx_hist_vector)NULL; }
    chv = ppm_cmapx_table_to_hist( cht, maxcolors );
    ppm_cmapx_table_free( cht );
    return chv;
  }

void ppm_cmapx_hist_add (ppm_cmapx_hist_vector chv, int* colorsP, int maxcolors, rgb_pixel_t* colorP, int value, int position)
  {
    int i, j;

    /* Search colorhist for the color. */
    for ( i = 0; i < *colorsP; ++i )
	if ( PPM_EQUAL( chv[i].color, *colorP ) )
	    {
	    /* Found it - move to new slot. */
	    if ( position > i )
		{
		for ( j = i; j < position; ++j )
		    chv[j] = chv[j + 1];
		}
	    else if ( position < i )
		{
		for ( j = i; j > position; --j )
		    chv[j] = chv[j - 1];
		}
	    chv[position].color = *colorP;
	    chv[position].value = value;
	    return;
	    }
    if ( *colorsP < maxcolors )
	{
	/* Didn't find it, but there's room to add it; so do so. */
	for ( i = *colorsP; i > position; --i )
	    chv[i] = chv[i - 1];
	chv[position].color = *colorP;
	chv[position].value = value;
	++(*colorsP);
	}
    }

ppm_cmapx_table ppm_cmapx_table_build (rgb_pixel_t** pixels, int cols, int rows, int maxcolors, int* colorsP)
  {
    ppm_cmapx_table cht;
    register rgb_pixel_t* pP;
    ppm_cmapx_list chl;
    int col, row, hash;

    cht = ppm_cmapx_table_alloc( );
    *colorsP = 0;

    /* Go through the entire image, building a hash table of colors. */
    for ( row = 0; row < rows; ++row )
	for ( col = 0, pP = pixels[row]; col < cols; ++col, ++pP )
	    {
	    hash = ppm_hashpixel( *pP );
	    for ( chl = cht[hash]; chl != (ppm_cmapx_list) 0; chl = chl->next )
		if ( PPM_EQUAL( chl->ch.color, *pP ) )
		    break;
	    if ( chl != (ppm_cmapx_list) 0 )
		++(chl->ch.value);
	    else
		{
		if ( ++(*colorsP) > maxcolors )
		    {
		    ppm_cmapx_table_free( cht );
		    return (ppm_cmapx_table) 0;
		    }
		chl = (ppm_cmapx_list) malloc( sizeof(struct ppm_cmapx_list_item) );
		if ( chl == 0 )
		    pm_error( "out of memory computing hash table" );
		chl->ch.color = *pP;
		chl->ch.value = 1;
		chl->next = cht[hash];
		cht[hash] = chl;
		}
	    }
    
    return cht;
  }

ppm_cmapx_table ppm_cmapx_table_alloc(void)
  {
    ppm_cmapx_table cht;
    int i;

    cht = (ppm_cmapx_table) malloc( HASH_SIZE * sizeof(ppm_cmapx_list) );
    if ( cht == 0 )
	pm_error( "out of memory allocating hash table" );

    for ( i = 0; i < HASH_SIZE; ++i )
	cht[i] = (ppm_cmapx_list) 0;

    return cht;
  }

int ppm_cmapx_table_add(ppm_cmapx_table cht, rgb_pixel_t* colorP, int value)
  {
    register int hash;
    register ppm_cmapx_list chl;

    chl = (ppm_cmapx_list) malloc( sizeof(struct ppm_cmapx_list_item) );
    if ( chl == 0 ) { return -1; }
    hash = ppm_hashpixel( *colorP );
    chl->ch.color = *colorP;
    chl->ch.value = value;
    chl->next = cht[hash];
    cht[hash] = chl;
    return 0;
  }

ppm_cmapx_hist_vector ppm_cmapx_table_to_hist(ppm_cmapx_table cht, int maxcolors)
  {
    ppm_cmapx_hist_vector chv;
    ppm_cmapx_list chl;
    int i, j;

    /* Now collate the hash table into a simple colorhist array. */
    chv = (ppm_cmapx_hist_vector) malloc( maxcolors * sizeof(struct ppm_cmapx_hist_item) );
    /* (Leave room for expansion by caller.) */
    if ( chv == (ppm_cmapx_hist_vector) 0 )
	pm_error( "out of memory generating histogram" );

    /* Loop through the hash table. */
    j = 0;
    for ( i = 0; i < HASH_SIZE; ++i )
	for ( chl = cht[i]; chl != (ppm_cmapx_list) 0; chl = chl->next )
	    {
	    /* Add the new entry. */
	    chv[j] = chl->ch;
	    ++j;
	    }

    /* All done. */
    return chv;
  }

ppm_cmapx_table ppm_cmapx_hist_to_table(ppm_cmapx_hist_vector chv, int colors)
  {
    ppm_cmapx_table cht;
    int i, hash;
    rgb_pixel_t color;
    ppm_cmapx_list chl;

    cht = ppm_cmapx_table_alloc( );

    for ( i = 0; i < colors; ++i )
	{
	color = chv[i].color;
	hash = ppm_hashpixel( color );
	for ( chl = cht[hash]; chl != (ppm_cmapx_list) 0; chl = chl->next )
	    if ( PPM_EQUAL( chl->ch.color, color ) )
		pm_error(
		    "same color found twice - %d %d %d", PPM_GETR(color),
		    PPM_GETG(color), PPM_GETB(color) );
	chl = (ppm_cmapx_list) malloc( sizeof(struct ppm_cmapx_list_item) );
	if ( chl == (ppm_cmapx_list) 0 )
	    pm_error( "out of memory" );
	chl->ch.color = color;
	chl->ch.value = i;
	chl->next = cht[hash];
	cht[hash] = chl;
	}

    return cht;
  }

int ppm_cmapx_table_lookup(ppm_cmapx_table cht, rgb_pixel_t* colorP)
  {
    int hash;
    ppm_cmapx_list chl;

    hash = ppm_hashpixel( *colorP );
    for ( chl = cht[hash]; chl != (ppm_cmapx_list) 0; chl = chl->next )
      { if ( PPM_EQUAL( chl->ch.color, *colorP ) ) { return chl->ch.value; } } 
    return -1;
  }

void ppm_cmapx_hist_free(ppm_cmapx_hist_vector chv)
  {
    free( (char*) chv );
  }

void ppm_cmapx_table_free(ppm_cmapx_table cht)
  {
    int i;
    ppm_cmapx_list chl, chlnext;

    for ( i = 0; i < HASH_SIZE; ++i )
	for ( chl = cht[i]; chl != (ppm_cmapx_list) 0; chl = chlnext )
	    {
	    chlnext = chl->next;
	    free( (char*) chl );
	    }
    free( (char*) cht );
  }