/*
** Part 3
*/

#include <stdio.h>

struct rgb {int r, g, b;};

extern int pals, colors;
extern long colorerr [256];
extern struct rgb cmap [256], palette [32];

struct adjcell {
   unsigned char color;
   int dist;
};

/* Select and set palette */
setpalette ()
{
   char *calloc ();
   struct adjcell **adj;
   static marked [256];
   int color, color2, r, g, b, len, dup, unmarked, marks;
   int mindist, mincolor, distance, colperpal, i, pal, radius;
   struct adjcell *p;
   struct rgb *rgbp;

   /* Clear marked array */
   for (color = 0; color < colors; color++)
      marked [color] = 0;
   marks = 0;

   /* Always assign background */
   palette [0] = cmap [0];
   pals = 1;
   if (!marked [0]) {
      marked [0] = -1;
      marks++;
   }
   printf ("Colours after removing background colour = %d\n", colors-marks);

   /* Mark off colors that are never used */
   calcremap ();
   scanpic ();
   for (color = 0; color < colors; color++)
      if ((colorerr [color] == 0L) && !marked [color]) {
         marked [color] = -1;
         marks++;
      }
   printf ("Colours after removing no-error  colours = %d\n", colors-marks);

   /* Mark off duplicates */
   for (color = 0; color < colors; color++)
      if (!marked [color]) {
         r = cmap [color].r;
         g = cmap [color].g;
         b = cmap [color].b;
         for (color2 = color+1; color2 < colors; color2++)
            if (!marked [color2]) {
               rgbp = &cmap [color2];
               if ((r == rgbp->r) && (g == rgbp->g) && (b == rgbp->b)) {
                  marked [color2] = -1;
                  marks++;
               }
            }
      }
   printf ("Colours after removing duplicate colours = %d\n", colors-marks);

   pals = 16;
   unmarked = colors - marks;
   colperpal = unmarked / (pals - 1);
   if (colperpal == 0)
      colperpal = 1;
   printf ("Colours per palette colour = %d\n", colperpal);

   /* Select and set palette based on sorted lists */
   /* Create sorted-by-distance list of colors for each colors */
   /* Leave out marked colors */
   printf ("Sorting colour\n");
   adj = (struct adjcell **) calloc (colors, sizeof (struct adjcell *));
   if (adj == NULL)
      fatalerr ("Out of memory");
   for (color = 0; color < colors; color ++) {
      if (marked [color])
         adj [color] = NULL;
      else {
         adj [color] = (struct adjcell *)
                       calloc (unmarked, sizeof (struct adjcell));
         if (adj [color] == NULL)
            fatalerr ("Out of memory");
         len = 0;
         r = cmap [color].r;
         g = cmap [color].g;
         b = cmap [color].b;
         for (color2 = 0; color2 < colors; color2 ++)
            if (!marked [color2])
               insertheap (
                  color2,
                  rgberr (
                     r, g, b,
                     cmap [color2].r,
                     cmap [color2].g,
                     cmap [color2].b),
                  &len,
                  adj [color]);
         heapsort (len, adj [color]);
      }
      printf ("%d\n\x1BM", color);
   }
   printf ("   ");                     /* Erase sorting count */
   printf ("\x1B[1F\x1B[40K\n\x1BM");  /* Erase sorting message */

   /* Select and set palette based on sorted lists */
   for (pal = 1; pal < pals; pal ++) {
      radius = 0;
      mincolor = 0;
      mindist = 32000;
      if (marks >= colors)
         goto noassign;
      /* Pick the best color to assign to the palette */
      for (color = 1; color < colors; color ++)
         if (!marked [color]) {
            distance = 0;
            p = adj [color];
            for (i = 0; i < colperpal; i ++) {
               while (marked [p->color])
                  p ++;
               distance += p->dist;
               p ++;
            }
            if (distance < mindist) {
               mindist = distance;
               mincolor = color;
            }
         }
      /* Mark off mincolor and the colors around it */
      p = adj [mincolor];
      radius = 0;
      for (i = 0; i < colperpal; i++) {
         while (marked [p->color])
            p ++;
         marked [p->color] = -1;
         marks++;
         if (p->dist > radius)
            radius = p->dist;
         p ++;
      }
      noassign:
      palette [pal] = cmap [mincolor];
      printf ("Palette %3d = colour %3d, radius = %3d\n\x1BM",
               pal, mincolor, radius);
   }

   /* Free up some memory */
   for (color = 0; color < colors; color++)
      if (adj [color] != NULL)
         free (adj [color]);
   free (adj);

   printf ("\x1B[4F");   /* Move to first line of stats */
   printf ("\x1B[J");    /* Erase to end of display */
}

/* Insert a value into a heap */
insertheap (color, dist, len, adjline)
int *len;
struct adjcell *adjline;
{
   struct adjcell *heap = adjline - 1;
   struct adjcell *p, *q, temp;
   int i;

   i = ++(*len);
   heap [i].color = color;
   heap [i].dist = dist;
   while ((i > 1) && ((p=heap+i)->dist > (q=heap+(i>>1))->dist)) {
      temp = *p;
      *p = *q;
      *q = temp;
      i >>= 1;
   }
}

/* Rearrange heap into sorted list */
heapsort (last, adjline)
struct adjcell *adjline;
{
   struct adjcell *h = adjline - 1;
   struct adjcell *q, temp;
   int n = last;
   int i;

   for (i = n; i >= 2; i--) {
      q = h + last;
      temp = *adjline;
      *adjline = *q;
      *q = temp;
      last --;
      pushdown (last, h, 1);
   }
}

/* Part of heapsort */
pushdown (last, h, start)
struct adjcell *h;
{
   struct adjcell *p, *q, temp;
   int i = start;
   int j = i;
   int last2 = last >> 1;

   while ((i <= last2) && (i == j)) {
      j = i << 1;
      if (j < last) {
         if (h [j].dist < h [j + 1].dist)
            j++;
      }
      if ((p=h+i)->dist < (q=h+j)->dist) {
         temp = *p;
         *p = *q;
         *q = temp;
         i = j;
      }
   }
}