 /*
  * Khoros: $Id: autocolor.c,v 1.5 1992/03/25 17:30:06 dkhoros Exp $
  */

#if !defined(lint) && !defined(SABER)
static char rcsid[] = "Khoros: $Id: autocolor.c,v 1.5 1992/03/25 17:30:06 dkhoros Exp $";
#endif

 /*
  * $Log: autocolor.c,v $
 * Revision 1.5  1992/03/25  17:30:06  dkhoros
 * VirtualPatch5
 *
  */ 

/*
 *----------------------------------------------------------------------
 *
 *            Copyright 1990 University of New Mexico
 *  
 *  Permission to use, copy, modify, distribute, and sell this
 *  software and its documentation for any purpose is hereby
 *  granted without fee, provided that the above copyright
 *  notice appear in all copies and that both that copyright
 *  notice and this permission notice appear in supporting docu-
 *  mentation, and that the name of UNM not be used in advertis-
 *  ing or publicity pertaining to distribution of the software
 *  without specific, written prior permission.  UNM makes no
 *  representations about the suitability of this software for
 *  any purpose.  It is provided "as is" without express or
 *  implied warranty.
 *  
 *  UNM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 *  INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FIT-
 *  NESS, IN NO EVENT SHALL UNM BE LIABLE FOR ANY SPECIAL,
 *  INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
 *  RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 *  ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
 *  OF THIS SOFTWARE.
 *  
 *----------------------------------------------------------------------
 */

#include "unmcopyright.h"	 /* Copyright 1990 by UNM */
#include "xvdisplay.h"
#include "colorspace.h"

/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
   >>>>								<<<<
   >>>>			Autocoloring Routines			<<<<
   >>>>								<<<<
   >>>>			xvd_autocolor()				<<<<
   >>>>								<<<<
   >>>>			xvd_color_cie_diagram()			<<<<
   >>>>			xvd_color_rgb_distance()		<<<<
   >>>>			xvd_color_rgb_triangle()		<<<<
   >>>>			xvd_color_rgb_cube()			<<<<
   >>>>			xvd_color_greyscale()			<<<<
   >>>>			xvd_color_invert()			<<<<
   >>>>			xvd_color_reverse()			<<<<
   >>>>			xvd_color_rainbow()			<<<<
   >>>>			xvd_color_rgb_spiral()			<<<<
   >>>>			xvd_color_hls_spiral()			<<<<
   >>>>			xvd_color_hls_spirals()			<<<<
   >>>>			xvd_color_rgb_spirals()			<<<<
   >>>>			xvd_color_hls_rings()			<<<<
   >>>>			xvd_color_hsv_rings()			<<<<
   >>>>			xvd_color_rgb_random()			<<<<
   >>>>			xvd_color_density_slice()		<<<<
   >>>>			xvd_color_sa_pseudo()			<<<<
   >>>>								<<<<
   >>>>			histogram_min_max()			<<<<
   >>>>								<<<<
   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */



static  void histogram_min_max();

/***********************************************************************
*
*  Routine Name: xvd_autocolor
*
*       Purpose: performs automatic coloring on an image according to
*		 the type of desired auto-coloring algorithm
*
*         Input: xvdisplay -  display structure to be autocolored
*		 type      -  type of desired auto-coloring
*
*        Output: none
*
*    CALLED BY: the application program
*
*    Written By: Mark Young 
*
***********************************************************************/


xvd_autocolor(xvdisplay, type)

DisplayStructure *xvdisplay;
int		 type;
{
	int	  i, j, ncolors;
	XColor	  temp[MAX_PIXELS];

	struct	  xvimage *image = xvdisplay->disp_image;
	XColor	  *xcolors = xvdisplay->xcolors;
	Display	  *display = xvdisplay->display;
	Boolean	  *active  = xvdisplay->active;
	unsigned  long *histogram = xvdisplay->histogram;


	if (image->data_storage_type == VFF_TYP_BIT)
	{
	   xvf_error_wait("Sorry! Cannot color dithered images.",
			  "xvd_autocolor", NULL);
	   return;
	}

	ncolors = 0;
	for (i = 0; i < MAX_PIXELS; i++)
	{
	   if (xvdisplay->active[i] > 0)
	      ncolors++;
	}

	/*
	 *  Find out which type of automatic coloring they wish to
	 *  perform.
	 */
	switch(type)
	{
	   case XVD_RGB_CUBE:
		xvd_color_rgb_cube(xcolors, histogram, active, ncolors);
		break;

	   case XVD_RGB_TRIANGLE:
		xvd_color_rgb_triangle(xcolors, histogram, active, ncolors);
		break;

	   case XVD_RGB_SPIRAL:
		xvd_color_rgb_spiral(xcolors, histogram, active, ncolors);
		break;

	   case XVD_HLS_SPIRAL:
		xvd_color_hls_spiral(xcolors, histogram, active, ncolors);
		break;

	   case XVD_HLS_RINGS:
		xvd_color_hls_rings(xcolors, histogram, active, ncolors);
		break;

	   case XVD_HSV_RINGS:
		xvd_color_hsv_rings(xcolors, histogram, active, ncolors);
		break;

	   case XVD_RGB_DISTANCE:
		xvd_color_rgb_distance(xcolors, histogram, active,  
				   xvdisplay->disp_image, ncolors);
		break;

	   case XVD_RANDOM:
		xvd_color_rgb_random(xcolors, histogram, active, ncolors);
		break;

	   case XVD_RAINBOW:
		xvd_color_rainbow(xcolors, histogram, active, ncolors);
		break;

	   case XVD_CIE_DIAGRAM:
		xvd_color_cie_diagram(xcolors, histogram, active, ncolors);
		break;

	   case XVD_DENSITY_SLICE:
		xvd_color_density_slice(xcolors, histogram, active, ncolors);
		break;

	   case XVD_GREYSCALE:
		xvd_color_greyscale(xcolors, histogram, active, ncolors);
		break;

	   case XVD_SA_PSEUDO:
		xvd_color_sa_pseudo(xcolors, histogram, active, ncolors);
		break;

	   case XVD_INVERT:
		xvd_color_invert(xcolors, histogram, active, ncolors);
		break;

	   case XVD_INVERT_ORIG:
	   case XVD_ORIGINAL:

		/*
		 *  Restore the original colormap that came with the input
		 *  image.  We need to save the X colors in case 
		 *  xvd_load_xcolors fails.
		 *
		 *  If xvd_load_xcolors succeeds we can then restore the saved
		 *  pixel values to the newly loaded color array.  This is
		 *  done since XAllocColor (in create_colormap) may not
		 *  give you the pixel that you request.  Hence, if i request
		 *  pixel 10 the color cell maybe reassigned pixel 40.
		 *  Therefore xvd_load_xcolors reinitializes it back to 10, the
		 *  wrong color cell.
		 */
		for (i = 0; i < MAX_PIXELS; i++)
		   temp[i] = xcolors[i];

		if (!xvd_load_xcolors(xvdisplay))
		{
		   /*
		    *  xvd_load_xcolors failed, so we restore the X color array
		    *  and return.
		    */
		   for (i = 0; i < MAX_PIXELS; i++)
		      xcolors[i] = temp[i];
		   return;
		}

		/*
		 *  xvd_load_xcolors succeed but the X color array pixels may be
		 *  pointing into the unintialized color cells.  Therefore,
		 *  we set the pixel values to the saved one.
		 */
		for (i = 0; i < MAX_PIXELS; i++)
		   xcolors[i].pixel = temp[i].pixel;


		if (type == XVD_INVERT_ORIG)
		   xvd_color_invert(xcolors, histogram, active, ncolors);
		break;

	   default:
		xvf_error_wait("Internal error! Unknown coloring type.",
			       "xvd_autocolor", NULL);
		return;
		break;
	}

	/*
	 *  Store the changed color cells into the current colormap.
	 */
	xvd_update_xcolors(xvdisplay);
}



/************************************************************
*
*  MODULE NAME: xvd_color_cie_diagram
*
*      PURPOSE: auto colors according to the CIE chromaticity
*		diagram.  The routine starts at blue then varies
*		the RB primaries until red is reached.  We then
*		vary the RG primaries until green is reached.  On
*		the last segment the GB primaries are varied until
*		we come back to blue (our original starting place).
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY:  Mark Young & Tom Sauer
*
*
*************************************************************/

xvd_color_cie_diagram(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int   i, j,
	      num_per_range,	/* number to color per range*/
	      num_ranges = 3;	/* there is three sides to the diagram */
	float factor;		/* saturation factor used in coloring */

	num_per_range = ncolors/num_ranges;
	if (num_per_range < 2)
	{
	   xvf_error_wait("Sorry! The image doesn't contain enough colors.\
 A minimum of 6 colors is needed for this color algorithm.",
			  "xvd_color_cie_diagram", NULL);
	   return;
	}
	factor = MAX_INTEN/((float) num_per_range -1);

	/*
	 *  Start at blue and vary RB primary until red is reached.  This
	 *  is done by increasing the red value while decreasing blue.
	 */
	i = j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   = j * factor;
	      xcolors[i].green = 0;
	      xcolors[i].blue  = MAX_INTEN - j * factor;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}

	/*
	 *  Start at red and vary RG primary until green is reached.  This
	 *  is done by increasing the green value while decreasing red.
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   = MAX_INTEN - j * factor;
	      xcolors[i].green = j * factor;
	      xcolors[i].blue  = 0;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}

	/*
	 *  Start at green and vary GB primary until blue is reached (our
	 *  original starting point).  This is done by increasing the blue
	 *  value while decreasing green.  Since this is the last leg we
	 *  include any remainder points from ncolors/3. 
	 */
	num_per_range += (ncolors - (num_per_range * num_ranges));
      	factor = MAX_INTEN/((float) num_per_range -1);

	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   = 0;
	      xcolors[i].green = MAX_INTEN - j * factor;
	      xcolors[i].blue  = j * factor;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_distance
*
*      PURPOSE: This routine auto colors the
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young & Tom Sauer
*
*
*************************************************************/

xvd_color_rgb_distance(xcolors, histogram, active, image, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
struct	 xvimage *image;
int      ncolors;
{
	int	i, size;
	float	variance[MAX_PIXELS], mean[MAX_PIXELS], intensity[MAX_PIXELS];
	float   tvar, tmean, rms, sum, value, imin, vmin, mmin, max,
		vfact, mfact, ifact;

	sum = rms = 0.0;
	for (i = 0; i < MAX_PIXELS; i++)
	{
	   if (active[i] > 0)
	   {
	      value = histogram[i] * i;
	      sum  += value;
	      rms  += value * value;
	   }
	}

	size  = image->row_size * image->col_size;
	tmean = sum/size;
	tvar  = (rms/size) - (tmean * tmean);

	for (i = 0; i < MAX_PIXELS; i++)
	{
	   if (active[i] > 0)
	   {
	      intensity[i] = i;
	      mean[i]      = (histogram[i] * i) - tmean;
	      variance[i]  = (histogram[i] * i * histogram[i] * i) - tvar;
	   }
	}

	histogram_min_max(histogram, active, variance, &vmin, &max);
	vfact = 65535/(max - vmin);
	vmin  = fabs((double) vmin);

	histogram_min_max(histogram, active, mean, &mmin, &max);
	mfact = 65535/(max - mmin);
	mmin  = fabs((double) mmin);

	histogram_min_max(histogram, active, intensity, &imin, &max);
	ifact = 65535/(max - imin);
	imin  = fabs((double) imin);

	for (i = 0; i < MAX_PIXELS; i++)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red    = (mmin + mean[i]) * mfact;
	      xcolors[i].blue   = (imin + intensity[i]) * ifact;
	      xcolors[i].green	= (vmin + variance[i]) * vfact;
	      xcolors[i].flags  = DoRed | DoGreen | DoBlue;
	   }
	   else
	      xcolors[i].flags = NULL;

	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_triangle
*
*      PURPOSE: Procedure is as follows:
*		We will try to follow the edges of the color triangle.
*		This is done by setting a value of one color to maximum
*		intensity, setting another to zero, then letting the other
*		color range from zero to maximum intensity.  Then set the
*		ranging color to zero, and let the other color range.  The
*		repeat setting other colors to max.  Hence we get:
*
*		Range1 - red (max), 	green (0), 	blue (range)
*		Range2 - red (max), 	green (range), 	blue (0)
*		Range3 - red (range),	green (max),	blue (0)
*		Range4 - red (0),	green (max),	blue(range)
*		Range5 - red (range),	green (0),	blue(max)
*		Range6 - red (0),	green (range),	blue(0)	
*
*		Hence our factor is MAX/(ncolors/6)
*		and to make it look better, when each color saturated we go
*		from MAX to low to MAX.
*
*		Lastly, Range 6 is larger as since ncolors/6 may not be an
*		even number, it has ncolor/6 + the remainer so that we paint
*		a total of ncolor colors
*
*		Note: this is clumsy and is not as pleasing as it should be
*		      Perhaps using the heat color scale would be cleaner.
*
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Eric A. Engquist
*
*   MODIFIED BY:  Mark Young   (modified for khoros).
*
*
*************************************************************/

xvd_color_rgb_triangle(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int	i, j,		/* famous loop variables */
		num_per_range,	/* number to color per range*/
		num_ranges = 6;	/* Each plane (R, G or B has 2 ranges */
	float factor;		/* saturation factor used in auto_color */

	num_per_range = ncolors/num_ranges;	/* ncolors per range */
	if (num_per_range < 2)
	{
	   xvf_error_wait("Sorry! The image doesn't contain enough colors.\
 A minimum of 12 colors is needed for this color algorithm.",
			  "xvd_color_rgb_cube", NULL);
	   return;
	}
      	factor = MAX_INTEN/((float) num_per_range -1);

	/*
	 * Color the first range
	 * Paint in increasing intensity
	 */
	i = j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = MAX_INTEN;
		xcolors[i].green = 0;
		xcolors[i].blue  = j * factor;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Color the second range
	 * Paint in decreasing intensity
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = MAX_INTEN;
		xcolors[i].green = MAX_INTEN - j * factor;
		xcolors[i].blue  = 0;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Color the third range
	 * Paint in increasing intensity
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = j * factor;
		xcolors[i].green = MAX_INTEN;
		xcolors[i].blue  = 0;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * color the fourth range
	 * Paint in decreasing intensity
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = 0;
		xcolors[i].green = MAX_INTEN;
		xcolors[i].blue  = MAX_INTEN - j * factor;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * color the fifth range
	 * Paint in increasing intensity
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = j * factor;
		xcolors[i].green = 0;
		xcolors[i].blue  = MAX_INTEN;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Now do the last range in decreasing intensity
	 * The size of this range is ncolors/6 + any
	 * remainer as ncolors/6 does not always have
	 * an even remainer
	 */
	num_per_range += (ncolors - (num_per_range * num_ranges));
      	factor = MAX_INTEN/((float) num_per_range -1);
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = 0;
		xcolors[i].green = MAX_INTEN - j * factor;
		xcolors[i].blue  = MAX_INTEN;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_cube
*
*      PURPOSE: "xvd_color_rgb_cube" is a modified version of Eric Engquist's
*		"color_rgb_triangle".  The difference is that this routine
*		follows the outline of the rgb cube as one continuous
*		path, rather than Eric's disjoint path.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Eric A. Engquist & Mark Young
*
*   MODIFIED BY:
*
*
*************************************************************/

xvd_color_rgb_cube(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int	i, j,		/* famous loop variables */
		num_per_range,	/* number to color per range*/
		num_ranges = 6;	/* Each plane (R, G or B has 2 ranges */
	float factor;		/* saturation factor used in auto_color */

	num_per_range = ncolors/num_ranges;	/* ncolors per range */
	if (num_per_range < 2)
	{
	   xvf_error_wait("Sorry! The image doesn't contain enough colors.\
 A minimum of 12 colors is needed for this color algorithm.",
			  "xvd_color_rgb_cube", NULL);
	   return;
	}
      	factor = MAX_INTEN/((float) num_per_range -1);

	/*
	 * Start at blue and go to magenta.
	 * Color the first range (start at blue and increase red)
	 */
	i = j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = j * factor;
		xcolors[i].green = 0;
		xcolors[i].blue  = MAX_INTEN;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Start at megenta and go to red.
	 * Color the second range (set red at max and decrease blue)
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = MAX_INTEN;
		xcolors[i].green = 0;
		xcolors[i].blue  = MAX_INTEN - j * factor;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Start at red and go to yellow.
	 * Color the third range (set red at max and increase green)
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = MAX_INTEN;
		xcolors[i].green = j * factor;
		xcolors[i].blue  = 0;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Start at yellow and go to green.
	 * Color the fourth range (set green at max and decrease red)
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = MAX_INTEN - j * factor;
		xcolors[i].green = MAX_INTEN;
		xcolors[i].blue  = 0;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Start at green and go to cyan.
	 * Color the fifth range (set green at max and increase blue)
	 */
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = 0;
		xcolors[i].green = MAX_INTEN;
		xcolors[i].blue  = j * factor;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}

	/*
	 * Start at cyan and go to blue.
	 * Color the last range (set blue at max and decrease green)
	 *
	 * Now do the last range in decreasing intensity
	 * The size of this range is ncolors/6 + any
	 * remainer as ncolors/6 does not always have
	 * an even remainer
	 */
	num_per_range += (ncolors - (num_per_range * num_ranges));
      	factor = MAX_INTEN/((float) num_per_range -1);
	j = 0;
	while (i < MAX_PIXELS && j < num_per_range)
	{
	   if (active[i] > 0)
	   {
		xcolors[i].red   = 0;
		xcolors[i].green = MAX_INTEN - j * factor;
		xcolors[i].blue  = MAX_INTEN;
	        xcolors[i].flags = DoRed | DoGreen | DoBlue;
		j++;
	    }
	    else
	        xcolors[i].flags = NULL;

	    i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_greyscale
*
*      PURPOSE: This routine colors an image using a linear
*		greyscale.  It starts at 0 and increases the
*		RGB values to max intensity (MAX_INTEN) for the
*		screen.  The increasing factor is computed by
*		the following formula:
*
*				MAX_INTEN / (ncolors -1)
*
*		This gives us a black beginning value and
*		a white end value.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_greyscale(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int   i, j;
	float factor;

	/*
	 *  make sure that the colors are linearized between black (0,0,0)
	 *  and white (MAX, MAX, MAX).
	 */
	factor = MAX_INTEN / ((float) ncolors -1);

	i = j = 0;
	while (i < MAX_PIXELS && j < ncolors)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   =
	      xcolors[i].green = 
	      xcolors[i].blue  = j * factor;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_invert
*
*      PURPOSE: This routine inverts an image using the current
*		colors.  It takes each of three color values
*		in the xcolor array and subtracts it from the
*		max intensity (MAX_INTEN).  This is done for
*		the first ncolors.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_invert(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int   i, j;

	i = j = 0;
	while (i < MAX_PIXELS && j < ncolors)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   = MAX_INTEN - xcolors[i].red;
	      xcolors[i].green = MAX_INTEN - xcolors[i].green;
	      xcolors[i].blue  = MAX_INTEN - xcolors[i].blue;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_reverse
*
*      PURPOSE: This routine reverses an image using the current
*		colors.  It takes each of three color values
*		in the xcolor array and swaps them with it's
*		corresponding partner at the other end of the
*		xcolor array.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_reverse(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int   i, j, l;
	XColor temp;

	i = 0; j = MAX_PIXELS-1;
	for (l = 0; l < ncolors/2; l++)
	{
	   while (active[i] == 0 && i < MAX_PIXELS)
	      i++;

	   while (active[j] == 0 && j > 0)
	      j--;

	   temp = xcolors[i];
	   xcolors[i].red   = xcolors[j].red;
	   xcolors[i].green = xcolors[j].green;
	   xcolors[i].blue  = xcolors[j].blue;
	   xcolors[j].red   = temp.red;
	   xcolors[j].green = temp.green;
	   xcolors[j].blue  = temp.blue;

	   xcolors[i].flags =
	   xcolors[j].flags = DoRed | DoGreen | DoBlue;
	   i++; j--;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rainbow
*
*      PURPOSE: This routine colors an image using rainbow
*		colors.  The idea is from Philip R. Thompson
*		(phils@athena.mit.edu).  In his xim3c program
*		he used a technique of setting the saturation and
*		value to max, and then varing the hue for the number
*		of desired steps.  For each (hsv) he would then convert
*		it to (rgb) for the desired rainbow affect.
*
*		This is done for the first ncolors which is what we
*		use as our step.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_rainbow(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j;
	float    hue, saturation, value;

	l = j = 0;
	saturation = value = 1.0;

	while (l < MAX_PIXELS && j < ncolors)
	{
	   if (active[l] > 0)
	   {
	      hue = ((float) j)/ncolors;
	      HSV_to_RGB(hue, saturation, value, xcolors[l]);
	      xcolors[l].flags = DoRed | DoGreen | DoBlue;

	      j++;
	   }
	   else
	      xcolors[l].flags = NULL;

	   l++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_hls_spiral
*
*      PURPOSE: This routine colors an image using a spiral
*		thru the rgb color cube.  The idea is done by
*		converting HSL to RGB.  This is a variant of
*		xvd_color_rainbow() routine.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_hls_spiral(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j;
	float    hue, light, saturation;

	l = j = 0;
	while (l < MAX_PIXELS && j < ncolors)
	{
	   if (active[l] > 0)
	   {
	      hue   = ((float) j)/ncolors;
	      light = ((float) j)/ncolors;

	      saturation = ((float) 2*j)/ncolors;
	      if (saturation > 1.0)
		  saturation = 2.0 - saturation;

	      HLS_to_RGB(hue, light, saturation, xcolors[l]);
	      xcolors[l].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[l].flags = NULL;

	   l++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_spiral
*
*      PURPOSE: This routine colors an image using a spiral
*		thru the rgb color cube.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_rgb_spiral(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j;
	float    hue, light, saturation;

	l = j = 0;
	while (l < MAX_PIXELS && j < ncolors)
	{
	   if (active[l] > 0)
	   {
	      hue   = ((float) j)/ncolors;
	      light = ((float) j)/ncolors;
	      saturation = ((float) 2*j)/ncolors;
	      if (saturation > 1.0)
		  saturation = 2.0 - saturation;

	      HLS_to_RGB(hue, light, saturation, xcolors[l]);
	      xcolors[l].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[l].flags = NULL;

	   l++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_hls_rings
*
*      PURPOSE: This routine colors an image by dividing into
*		different rings.  Each ring is then colored
*		by varying the hue around the ring (0.0 - 1.0).
*		The number of points in the ring varies according
*		to the number of points in the array.  And the number
*		of points in each ring varies according to which
*		ring.
*
*		The number of rings is based on the 
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_hls_rings(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j, i, num, iter;
	float    hue, light, saturation, sat, intv;

	l = j = 0;

	num = log((double) ncolors)/log(2.0) - 1.0;
	if (num > 0)
	{
	   intv = 1.0/num;
	   iter = ncolors/num;
	}
	else
	{
	   intv = 0.5;
	   iter = 1.0;
	}

	light = intv;
	saturation = 2*intv;

	while (l < MAX_PIXELS && j < ncolors)
	{
	   i = 0;
	   while (i < iter && l < MAX_PIXELS)
	   {
	      if (active[l] > 0)
	      {
		 hue = ((float) i)/iter;

		 if (saturation > 1.0)
		    sat = 2.0 - saturation;
		 else
		    sat = saturation;

	         HLS_to_RGB(hue, light, sat, xcolors[l]);
	         xcolors[l].flags = DoRed | DoGreen | DoBlue;
		 i++; j++;
	      }
	      else
		 xcolors[l].flags = NULL;

	      l++;
	   }
	   light      += intv;
	   saturation += 2*intv;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_hsv_rings
*
*      PURPOSE: This routine colors an image by dividing into
*		different rings.  Each ring is then colored
*		by varying the hue around the ring (0.0 - 1.0).
*		The number of points in the ring varies according
*		to the number of points in the array.  And the number
*		of points in each ring varies according to which
*		ring.
*
*		The number of rings is based on the 
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_hsv_rings(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j, i, num, iter;
	float    hue, value, saturation, intv;

	l = j = 0;

	num = log((double) ncolors)/log(2.0) - 1.0;
	if (num > 0)
	{
	   intv = 1.0/num;
	   iter = ncolors/num;
	}
	else
	{
	   intv = 0.5;
	   iter = 1.0;
	}

	saturation = value = intv;
	while (l < MAX_PIXELS && j < ncolors)
	{
	   i = 0;
	   while (i < iter && l < MAX_PIXELS)
	   {
	      if (active[l] > 0)
	      {
		 hue = ((float) i)/iter;
	         HSV_to_RGB(hue, value, saturation, xcolors[l]);
	         xcolors[l].flags = DoRed | DoGreen | DoBlue;
		 i++; j++;
	      }
	      else
		 xcolors[l].flags = NULL;

	      l++;
	   }
	   value      += intv;
	   saturation += intv;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_hls_spirals
*
*      PURPOSE: This routine colors an image by spiraling several
*		times thru the hls color cube.  The idea is done by
*		converting HSL to RGB.  This is a variant of
*		xvd_color_hls_spiral() routine.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_hls_spirals(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j;
	float    hue, light, saturation;

	l = j = 0;
	while (l < MAX_PIXELS && j < ncolors)
	{
	   if (active[l] > 0)
	   {
	      hue   = ((float) j)/ncolors;
	      light = ((float) j)/ncolors;

	      saturation = ((float) 2*j)/ncolors;
	      if (saturation > 1.0)
		  saturation = 2.0 - saturation;

	      HLS_to_RGB(hue, light, saturation, xcolors[l]);
	      xcolors[l].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[l].flags = NULL;

	   l++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_spirals
*
*      PURPOSE: This routine colors an image using by spiraling several
*		times thru the rgb color cube.
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_rgb_spirals(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      l, j;
	float    hue, light, saturation;

	l = j = 0;
	while (l < MAX_PIXELS && j < ncolors)
	{
	   if (active[l] > 0)
	   {
	      hue   = ((float) j)/ncolors;
	      light = ((float) j)/ncolors;
	      saturation = ((float) 2*j)/ncolors;
	      if (saturation > 1.0)
		  saturation = 2.0 - saturation;

	      HLS_to_RGB(hue, light, saturation, xcolors[l]);
	      xcolors[l].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[l].flags = NULL;

	   l++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_rgb_random
*
*      PURPOSE: colors the image using a random function.  Each
*		red, green, blue component is assigned a uniform
*		gaussian random number between 0 and 65536.
*		
*
*       OUTPUT: changes the xcolor array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY: Mark Young
*
*
*************************************************************/

xvd_color_rgb_random(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int      i, j;
	float	 urng();


	i = j = 0;
	while (i < MAX_PIXELS && j < ncolors)
	{
	   if (active[i] > 0)
	   {
	      xcolors[i].red   = urng() * MAX_INTEN;
	      xcolors[i].green = urng() * MAX_INTEN;
	      xcolors[i].blue  = urng() * MAX_INTEN;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      j++;
	   }
	   else
	      xcolors[i].flags = NULL;

	   i++;
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_density_slice
*
*      PURPOSE:
*
*       OUTPUT:
*
*    CALLED BY:  xvd_autocolor
*
*   WRITTEN BY:  Mark Young
*
*
*************************************************************/

xvd_color_density_slice(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	float	 hfact, value, max;
	int	 i, j, l, num, index[MAX_PIXELS];
	unsigned long temp, hist[MAX_PIXELS];

	int	 num_per_range,		/* number to color per range  */
		 num_ranges = 6;	/* r-o-y-g-b-i-v  (6 ranges) */
	float	 factor;		/* saturation factor used in coloring */

	num_per_range = ncolors/num_ranges;
	if (num_per_range < 2)
	{
	   xvf_error_wait("Sorry! The image doesn't contain enough colors.\
 A minimum of 4 colors is needed for this color algorithm.",
			  "xvd_color_density_slice", NULL);
	   return;
	}
	factor = MAX_INTEN/((float) num_per_range -1);

	/*
	 *  Copy the histogram into a temporary array and initialize
	 *  the index array.
	 */
	for (i = 0; i < MAX_PIXELS; i++)
	{
	   if (active[i] > 0)
	      hist[i]  = histogram[i];
	   else
	      hist[i]  = 0;

	   index[i] = i;
	}

	/*
	 *  Sort the histogram into ascending order.  The index array
	 *  is used to tell us which color the histogram came from.
	 */
	for (i = 0; i < MAX_PIXELS -1; i++)
	{
	   num = i;
	   for (j = i +1; j < MAX_PIXELS; j++)
	   {
	      if (hist[j] < hist[num]) num = j;
	   }

	   if (i != num)
	   {
	      temp = index[i];
	      index[i] = index[num];
	      index[num] = temp;

	      temp = hist[i];
	      hist[i] = hist[num];
	      hist[num] = temp;
	   }
	}
	max   = hist[MAX_PIXELS -1];
	hfact = max/((float) ncolors -1);
	i = MAX_PIXELS - ncolors;

	/*
	 *  Start at blue and vary BG primary until green is reached.  This
	 *  is done by increasing the green value while decreasing blue.
	 */
	j = 0;

	value = hfact;
	while (i < MAX_PIXELS && value <= (max/2))
	{
	   if (hist[i] < value)
	   {
	      l = index[i];
	      xcolors[l].red   = 0;
	      xcolors[l].green = j * factor;
	      xcolors[l].blue  = MAX_INTEN - j * factor;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      i++;
	   }
	   else
	   {
	      value += hfact;
	      xcolors[i].flags = NULL;
	      j++;
	   }
	}

	/*
	 *  Start at green and vary RG primary until red is reached.  This
	 *  is done by increasing the red value while decreasing green.
	 */
	j = 0;
	value = hfact;
	while (i < MAX_PIXELS)
	{
	   if (hist[i] < value)
	   {
	      l = index[i];
	      xcolors[l].red   = j * factor;
	      xcolors[l].green = MAX_INTEN - j * factor;
	      xcolors[l].blue  = 0;
	      xcolors[i].flags = DoRed | DoGreen | DoBlue;
	      i++;
	   }
	   else
	   {
	      xcolors[i].flags = NULL;
	      value += hfact;
	      j++;
	   }
	}
}



/************************************************************
*
*  MODULE NAME: xvd_color_sa_pseudo
*
*      PURPOSE: This a pseudo color based on an article in
*		Scientific American.  The pseudocolor is designed
*		to convert a grey scale image and convert it to
*		color image of the same intensity.  The algorithm
*		takes the intensity and maps that to corresponding
*		red, green, blue that has been choosen more for it's
*		aesthetics than it's quantative value.  The article
*		was discovered by Joe Fogler who typed in the and added
*		a few corrections to make the pseudo color even more
*		aestically pleasing.
*
*       OUTPUT:
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY:  Original author unknown, Joe Fogler
*
*
*************************************************************/

typedef struct
{
	int num;
	unsigned char red, green, blue;
} SAElem;

static SAElem elems[] = {
	{ 3, 0, 0, 51 },
	{ 5, 0, 0, 86 },
	{ 5, 0, 0, 102 },
	{ 5, 0, 0, 117 },
	{ 5, 0, 0, 127 },
	{ 4, 0, 0, 137 },
	{ 5, 0, 0, 148 },
	{ 5, 0, 0, 158 },
	{ 5, 0, 0, 163 },
	{ 5, 0, 14, 168 },
	{ 5, 0, 28, 168 },
	{ 5, 0, 42, 168 },
	{ 5, 0, 56, 168 },
	{ 5, 0, 79, 158 },
	{ 5, 0, 94, 153 },
	{ 5, 0, 109, 148 },
	{ 4, 0, 119, 143 },
	{ 5, 0, 126, 139 },
	{ 5, 0, 132, 132 },
	{ 5, 0, 137, 126 },
	{ 5, 0, 143, 119 },
	{ 5, 0, 148, 96 },
	{ 5, 0, 153, 64 },
	{ 5, 0, 158, 32 },
	{ 5, 0, 163, 0 },
	{ 5, 109, 163, 0 },
	{ 4, 153, 158, 0 },
	{ 5, 173, 161, 0 },
	{ 5, 189, 157, 0 },
	{ 5, 203, 156, 1 },
	{ 5, 213, 156, 1 },
	{ 5, 223, 156, 1 },
	{ 5, 234, 156, 1 },
	{ 5, 234, 164, 1 },
	{ 5, 234, 172, 1 },
	{ 5, 234, 176, 1 },
	{ 4, 234, 176, 1 },
	{ 5, 234, 191, 1 },
	{ 5, 228, 198, 1 },
	{ 5, 228, 205, 1 },
	{ 5, 228, 209, 1 },
	{ 5, 228, 213, 1 },
	{ 5, 228, 217, 1 },
	{ 5, 228, 224, 1 },
	{ 5, 228, 228, 1 },
	{ 5, 234, 234, 52 },
	{ 5, 236, 236, 147 },
	{ 4, 241, 241, 157 },
	{ 5, 246, 246, 173 },
	{ 5, 250, 250, 184 },
	{ 5, 252, 252, 197 },
	{ 5, 254, 254, 216 },
	{ 3, 255, 255, 240 },
};

xvd_color_sa_pseudo(xcolors, histogram, active, ncolors)

XColor   *xcolors;
unsigned long *histogram;
Boolean  *active;
int      ncolors;
{
	int	i, j, l, num;


	l = 0;
	num = XtNumber(elems);
	for (i = 0; i < num; i++)
	{
	   for (j = 0; j < elems[i].num; j++)
	   {
	      xcolors[l].red   = elems[i].red*256;
	      xcolors[l].green = elems[i].green*256;
	      xcolors[l].blue  = elems[i].blue*256;
	      l++;
	   }
	}
}



/************************************************************
*
*  MODULE NAME: histogram_min_max
*
*      PURPOSE: find the minimum and maximum values for the
*		incoming values array.  The min & max values
*		are for those indexes that have a histogram
*		count of greater than zero.
*
*       OUTPUT: finds the 'min' & 'max' for the values array.
*
*    CALLED BY: xvd_autocolor
*
*   WRITTEN BY:  Mark Young
*
*
*************************************************************/

static void histogram_min_max(histogram, active, values, min, max)

unsigned long *histogram;
Boolean  *active;
float	 *values, *min, *max;
{
	int i, j = 0;

	while (j < MAX_PIXELS && histogram[j] == 0)
	   j++;

	*min = *max = values[j];
	for (i = j +1; i < MAX_PIXELS; i++)
	{
	    if (active[i] > 0)
	    {
	       if (*min > values[i])
		  *min = values[i];
	       else if (*max < values[i])
		  *max = values[i];
	    }
	}
}
