#ifndef lint
static char *sccsid = "@(#)hitlist.c	1.2 (Steve Hill) 3/9/90";
#endif

/* hitlist.c
 *
 * Primitive functions for manipulating a linked list of solids.
 * Lists are sorted according to the parameter "t" of the equation
 * of the line that intersects them, and the corresponding point.
 */

#include <stdio.h>

#include "basetype.h"
#include "cartesian.h"
#include "malloc.h"
#include "error.h"
#include "matrix.h"
#include "point.h"
#include "vector.h"
#include "indexlist.h"
#include "ray.h"
#include "quadric.h"
#include "colour.h"
#include "surface.h"
#include "bitmap.h"
#include "pattern.h"
#include "solid.h"
#include "bbox.h"
#include "list.h"
#include "hitlist.h"


/* GetHitInfo
 *
 * Private function that allocates memory for an entry in
 * a hitlist.
 */

static
hit_info_t *
GetHitInfo()
{
	hit_info_t	*i;

	i = (hit_info_t *) malloc(sizeof(hit_info_t));

	if (i == HitInfoNull)
		FatalError(__FILE__, __LINE__, "HitInfo: out of memory");

	return(i);
}


/* HitInfo
 *
 * Allocate and initialise a hitlist enrty.  The point will be
 * freed when the list is, but the solid will not.  The parameter
 * t is used to sort a hitlist.  The point corresponds to this
 * parameter according to the equation of the line that gave this
 * intersection.  The solid should be the solid that is intersected.
 */

hit_info_t *
HitInfo(solid, point, t)
solid_t	*solid;
point_t	*point;
real_t	t;
{
	hit_info_t	*hit_info;

	hit_info = GetHitInfo();

	hit_info->solid = solid;
	hit_info->point = point;
	hit_info->t = t;

	return(hit_info);
}


/* HitInfoCopy
 *
 * Duplicate an entry in a hitlist.  The point is duplicated, but
 * the solid pointer is simply copied.
 */

hit_info_t *
HitInfoCopy(hit_info)
hit_info_t	*hit_info;
{
	hit_info_t	*new ;

	new = GetHitInfo();

	new->point = PointCopy(hit_info->point);
	new->t     = hit_info->t;
	new->solid = hit_info->solid;

	return(new);
}


/* HitInfoPrint
 *
 * Print a hitlist entry to a file.
 */

void
HitInfoPrint(file, hit_info)
FILE		*file;
hit_info_t	*hit_info;
{
	if (hit_info == HitInfoNull)
	{
		fprintf(file, "Null HitInfo\n");
		return;
	}

	SolidPrint(file,  hit_info->solid);
	PointPrint(file, hit_info->point);
	RealPrint(file,  hit_info->t);
}


/* HitInfoFree
 *
 * Free a hitlist entry.  The point is freed, and the memory
 * for the hitinfo is freed.  The solid pointer is not freed.
 */

void
HitInfoFree(hit_info)
hit_info_t	*hit_info;
{
	if (hit_info == HitInfoNull)
		return;

	PointFree(hit_info->point);
	(void) free((char *) hit_info);
}


/* HitListInsert
 *
 * This function can be used to maintain a sorted hitlist.
 * The new entry is inserted in the appropriate place in the
 * list, and a pointer to the new list returned.  The list
 * is sorted according to increasing values of "t".
 */

hit_list_t *
HitListInsert(hit_info, hit_list)
hit_info_t	*hit_info;
hit_list_t	*hit_list;
{
	hit_list_t	*l, *p, *n;

	p = HitListNull;
	l = hit_list;

	while (l != HitListNull && l->elem->t < hit_info->t)
	{
		p = l;
		l = l->ptr;
	}

	n = HitListCons(hit_info, l);
	
	if (p != HitListNull)
	{
		p->ptr = n;
		return(hit_list);
	}
	else
		return(n);
}


/* HitListMerge
 *
 * The two lists are merged, preserving order. The first of the two
 * lists is freed.  The function returns a pointer to the new sorted
 * list.
 */

hit_list_t *
HitListMerge(hit_list1, hit_list2)
hit_list_t	*hit_list1, *hit_list2;
{
	hit_list_t	*l1, *l2;

	l1 = hit_list1;
	l2 = hit_list2;

	while (l1 != HitListNull)
	{
		hit_info_t	*hit_info;

		hit_info = HitInfoCopy((hit_info_t *) l1->elem);
		l2 = HitListInsert(hit_info, l2);
		l1 = l1->ptr;
	}

	HitListFree(hit_list1);

	return(l2);
}


/* HitListPrint
 *
 * Print out a hitlist to a file.
 */

void
HitListPrint(file, hit_list)
FILE		*file;
hit_list_t	*hit_list;
{
	if (hit_list == HitListNull)
	{
		fprintf(file, "Null HitList\n");
		return;
	}

	ListPrint(file, HitInfoPrint, (list_t *) hit_list);
}