/* See jsppm_xtable.h
** Last edited on 2009-01-07 03:13:15 by stolfi
**
** Copied 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 <affirm.h>
#include <stdint.h>

#include <jspnm.h>

#include <jsppm_xhist.h>
#include <jsppm_xtable.h>

#define HASH_SIZE 20023

uint32_t ppm_xtable_hash_pixel(ppm_pixel_t *p);
  /* Computes a hash index for an RGB pixel. */

uint32_t ppm_xtable_hash_pixel(ppm_pixel_t *p)
  { uint32_t r = p->c[0];
    uint32_t g = p->c[1];
    uint32_t b = p->c[2];
    return ((r * 33023 + g * 30013 + b * 27011) & 0x7fffffff) % HASH_SIZE;
  }

ppm_xtable ppm_xtable_build
  ( pnm_sample_t **samples,
    int chns, 
    int cols, 
    int rows, 
    int maxcolors, 
    int *colorsP )
  {
    ppm_xtable cht;
    ppm_xbucket chl;
    int col, row, hash;

    cht = ppm_xtable_alloc( );
    *colorsP = 0;

    /* Go through the entire image, building a hash table of colors. */
    for (row = 0; row < rows; ++row)
      { pnm_sample_t *sP = samples[row];
        for (col = 0; col < cols; ++col)
          { /* Grab a pixel {p}, expanding/truncating to 3 samples: */ 
            ppm_pixel_t p;
            if (chns > 0) { p.c[0] = *sP; sP++; } else {p.c[0] = 0; }
            if (chns > 1) { p.c[1] = *sP; sP++; } else {p.c[1] = p.c[0]; }
            if (chns > 2) { p.c[2] = *sP; sP++; } else {p.c[2] = p.c[0]; }
            if (chns > 3) { sP += (chns-3); }
            hash = ppm_xtable_hash_pixel(&p);
            for (chl = cht[hash]; chl != (ppm_xbucket)NULL; chl = chl->next)
              { if (ppm_equal(&(chl->ch.color), &p)) break; }
            if (chl != (ppm_xbucket)NULL) 
              { ++(chl->ch.value); }
            else
              { if (++(*colorsP) > maxcolors)
                  { ppm_xtable_free(cht);
                    return (ppm_xtable)NULL;
                  }
                chl = (ppm_xbucket)pnm_malloc(sizeof(struct ppm_xbucket_item));
                chl->ch.color = p;
                chl->ch.value = 1;
                chl->next = cht[hash];
                cht[hash] = chl;
              }
          }
      }
    return cht;
  }

ppm_xtable ppm_xtable_alloc(void)
  {
    ppm_xtable cht;
    int i;

    cht = (ppm_xtable)pnm_malloc(HASH_SIZE * sizeof(ppm_xbucket));

    for (i = 0; i < HASH_SIZE; ++i) { cht[i] = (ppm_xbucket)NULL; }

    return cht;
  }

int ppm_xtable_add(ppm_xtable cht, ppm_pixel_t* colorP, int value)
  {
    register int hash;
    register ppm_xbucket chl;

    chl = (ppm_xbucket)pnm_malloc(sizeof(struct ppm_xbucket_item));
    hash = ppm_xtable_hash_pixel(colorP);
    chl->ch.color = *colorP;
    chl->ch.value = value;
    chl->next = cht[hash];
    cht[hash] = chl;
    return 0;
  }

ppm_xhist_vector ppm_xtable_to_xhist(ppm_xtable cht, int maxcolors)
  {
    ppm_xhist_vector chv;
    ppm_xbucket chl;
    int i, j;

    /* Now collate the hash table into a simple colorhist array. */
    chv = (ppm_xhist_vector)pnm_malloc(maxcolors * sizeof(struct ppm_xhist_item));

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

ppm_xtable ppm_xhist_to_xtable(ppm_xhist_vector chv, int colors)
  {
    ppm_xtable cht;
    int i, hash;
    ppm_pixel_t color;
    ppm_xbucket chl;

    cht = ppm_xtable_alloc();

    for (i = 0; i < colors; ++i)
      { color = chv[i].color;
        hash = ppm_xtable_hash_pixel(&color);
        for (chl = cht[hash]; chl != (ppm_xbucket)NULL; chl = chl->next)
          { if (ppm_equal(&(chl->ch.color), &color))
              { pnm_error
                  ( "same color found twice - %u %u %u", 
                    color.c[0], color.c[1], color.c[2]
                  );
              }
          }
        chl = (ppm_xbucket)pnm_malloc( sizeof(struct ppm_xbucket_item));
        chl->ch.color = color;
        chl->ch.value = i;
        chl->next = cht[hash];
        cht[hash] = chl;
      }

    return cht;
  }

int ppm_xtable_lookup(ppm_xtable cht, ppm_pixel_t* colorP)
  {
    int hash;
    ppm_xbucket chl;
    hash = ppm_xtable_hash_pixel(colorP);
    for (chl = cht[hash]; chl != (ppm_xbucket)NULL; chl = chl->next)
      { if (ppm_equal(&(chl->ch.color), colorP))
          { return chl->ch.value; }
      }
    return -1;
  }

void ppm_xtable_free(ppm_xtable cht)
  {
    int i;
    ppm_xbucket chl, chlnext;
    for (i = 0; i < HASH_SIZE; ++i)
      { for (chl = cht[i]; chl != (ppm_xbucket)NULL; chl = chlnext)
          { chlnext = chl->next;
            free(chl);
          }
      }
    free(cht);
  }