# include <stdio.h>
# include <stdlib.h>

# include	"ged.h"
# include        "embed_ops.h"

#define		sqr(x)	((x) * (x))
#define		MAXINT	0x7fff

typedef	struct	_vec	{
		int	col_pos;
		int	col_val;
		struct	_vec	*col_next;
	} *vector;

static	int	min_dist;	/* used by closest and search */
static	int	*used_names = NULL;
static	int	fep = FALSE;
static	point *first_ptr = NULL;
static	int	origin_x, origin_y;

/*
  Function definitions.
*/
static int col_access ( vector vec, int col_num );
static void col_delete ( vector *vecp, int value );
static void col_deleteall ( vector *vecp );
static void col_init ( vector *vecp );
static void col_insert ( vector *vecp, int col_num, int value );
void ds_init ( point *htbl[] );
void freec ( cpoint *cptr );
static point *ins_new_pnt ( point *htbl[], int vname, int xco, int yco );

/*---------------------------------------------------------------------------
 *  ds_init -- initialise global data structures
 *---------------------------------------------------------------------------
 */

void ds_init ( point *htbl[] )
{
    point *pptr;
    int    i;

    for (i = 0; i < GSQRD; i++) {
	pptr = htbl[i] = (point *) (malloc(sizeof(point)));
	pptr->nextp = NULL;
	pptr->cplist = NULL;
    }
}

static void col_init ( vector *vecp )
{
	*vecp = NULL;
}

static void col_insert ( vector *vecp, int col_num, int value )
{
	if (*vecp == NULL) {
		*vecp = (vector) malloc (sizeof (**vecp));

		(*vecp)->col_next = NULL;
		(*vecp)->col_val = value;
		(*vecp)->col_pos = col_num;
	}
	else if ((*vecp)->col_pos < col_num)
		col_insert (&(*vecp)->col_next, col_num, value);
	else if ((*vecp)->col_pos == col_num)
		(*vecp)->col_val = value;
	else {
	/* (*vecp)->col_pos > col_num */
		vector tmp = *vecp;

		*vecp = (vector) malloc (sizeof (**vecp));
		(*vecp)->col_next = tmp;
		(*vecp)->col_pos = col_num;
		(*vecp)->col_val = value;
	}
}

static void col_deleteall ( vector *vecp )
{
	if (*vecp == NULL)
		return;
	else {
		vector	tmp = *vecp;
		*vecp = (*vecp)->col_next;
		free ((char *) tmp);
		col_deleteall (vecp);
	}
}

static void col_delete ( vector *vecp, int value )
{
	if (*vecp == NULL)
		return;
	else if ((*vecp)->col_val < value)
		col_delete (&(*vecp)->col_next, value);
	else if ((*vecp)->col_val == value) {
		vector	tmp = *vecp;
		*vecp = (*vecp)->col_next;
		free ((char *) tmp);
	}
	else
	/* (*vecp)->col_pos > col_num */
		return;
}

static int col_access ( vector vec, int col_num )
{
	if (vec == NULL)
		return 0;
	else
	if (vec->col_pos < col_num)
		return col_access (vec->col_next, col_num);
	else
	if (vec->col_pos == col_num)
		return vec->col_val;
	else
	/* vec->col_pos > col_num */
		return 0;
}
/*---------------------------------------------------------------------------
 *  insertp -- insert a point structure into list
 *---------------------------------------------------------------------------
 */

point *insertp(htbl, vname, xco, yco)
	point	*htbl[];
	int	vname, xco, yco;
{
	point *getxy ();
	int	name_exists ();
	void	remove_point (), merge_clists () ;

	point	*old_point, *new_point;

	if (name_exists (htbl, vname)) {
		old_point = getxy (htbl, vname);
		remove_point (htbl, old_point);
		new_point = ins_new_pnt (htbl, vname, xco, yco);
		merge_clists (new_point, old_point);
		freec (old_point->cplist);
		free ((char *) old_point);
		return new_point;
	}
	else
		return ins_new_pnt (htbl, vname, xco, yco);
}

static point *ins_new_pnt ( point *htbl[], int vname, int xco, int yco )
{
	int	getbucket ();
	point	*pptr, *tptr;

	pptr = htbl[getbucket(xco, yco)];
	col_insert ( &used_names, vname, vname );
	tptr = (point *) (malloc(sizeof(point)));
	tptr->name = vname;
	tptr->X = xco;
	tptr->Y = yco;
	tptr->cplist = (cpoint *) (malloc (sizeof (cpoint)));
	tptr->cplist->nextcp = NULL;
	tptr->nextp = pptr->nextp;
	pptr->nextp = tptr;
	return(tptr);
}

/*---------------------------------------------------------------------------
 *  insertc -- insert a cpoint structure into list of connected points
 *---------------------------------------------------------------------------
 */

void insertc(cptr, vname)
	cpoint	*cptr;
	int	vname;
{
	cpoint *tptr;	/* temporary pointer */

	tptr = (cpoint *) (malloc(sizeof(cpoint)));
	tptr->pname = vname;
	tptr->nextcp = cptr->nextcp;
	cptr->nextcp = tptr;
}

void remove_point (htbl, mptr)
	point	*htbl[], *mptr;
{
	int	getbucket ();
	point	*pptr;

	pptr = htbl[getbucket(mptr->X, mptr->Y)];
	while (pptr->nextp != NULL)
		if (pptr->nextp == mptr) {
			pptr->nextp = mptr->nextp;
			mptr->nextp = NULL;
			return;
		}
		else
			pptr = pptr->nextp;
}

void replace_point (htbl, mptr, new_xco, new_yco)
	point	*htbl[], *mptr;
	int	new_xco, new_yco;
{
	int	getbucket ();
	point	*pptr;

	pptr = htbl[getbucket(new_xco, new_yco)];
	mptr->X = new_xco;
	mptr->Y = new_yco;
	mptr->nextp = pptr->nextp;
	pptr->nextp = mptr;
}

/*---------------------------------------------------------------------------
 *  move_point -- moves a point from it's present bucket to the one
 * 		   hashed by the new coordinates
 *---------------------------------------------------------------------------
 */

void move_point (htbl, mptr, new_xco, new_yco)
	point	*htbl[], *mptr;
	int	new_xco, new_yco;
{

	void	remove_point (), replace_point ();

	remove_point (htbl, mptr);
	replace_point (htbl, mptr, new_xco, new_yco);
}

/*---------------------------------------------------------------------------
 *  deletep -- delete a point structure from a list
 *---------------------------------------------------------------------------
 */

void deletep ( point *pptr, int tname )
{
	void	freec (), deletec (), remove_point ();
	int	getbucket ();

	cpoint	*cptr;
	int	i;

	remove_point (hash, pptr);
	col_delete (&used_names, tname);
	freec(pptr->cplist);
	free((char *) pptr);
	for (i = 0; i < GSQRD; i++) {
		pptr = hash[i];
		while (pptr->nextp != NULL) {
			pptr = pptr->nextp;
			cptr = pptr->cplist;
			while (cptr->nextcp != NULL) {
				cptr = cptr->nextcp;
				if (cptr->pname == tname)
					deletec(pptr->cplist, tname);
			}
		}
	}
}

/*---------------------------------------------------------------------------
 *  deletec -- delete a cpoint structure from a list
 *---------------------------------------------------------------------------
 */

void deletec(cptr, vname)
	cpoint	*cptr;
	int	vname;
{
	cpoint *tptr = NULL;

	while (cptr->nextcp != NULL) {		/* find item in list */
		if (cptr->nextcp->pname == vname) {
			tptr = cptr->nextcp;
			cptr->nextcp = tptr->nextcp;
			free((char *) tptr);
			break;
		}
		cptr = cptr->nextcp;
	}
}

/*---------------------------------------------------------------------------
 *  freep -- free space used by "point" structures
 *---------------------------------------------------------------------------
 */

void freep(pptr)
	point *pptr;
{
	point *tptr;

	pptr = pptr->nextp;
	while (pptr != NULL) {
		tptr = pptr->nextp;
		freec(pptr->cplist);
		free((char *) pptr);
		pptr = tptr;
	}
}

/*---------------------------------------------------------------------------
 *  freec -- free space used by "cpoint" structures
 *---------------------------------------------------------------------------
 */

void freec ( cpoint *cptr )
{
	cpoint *tptr;

	while (cptr != NULL) {
		tptr = cptr->nextcp;
		free((char *) cptr);
		cptr = tptr;
	}
}

/*---------------------------------------------------------------------------
 *  getbucket -- gets the bucket of the hash table to which a point
 *                belongs
 *---------------------------------------------------------------------------
 */

int getbucket(xco, yco)
	int xco, yco;
{
	int col, row;	/* 0 <= col <= 90 and 0 <= row <= 9 */

	col = GRID * (int) (((float) xco + 0.5) * GRID / WXMAX);
	if (col == GSQRD)
		col -= GRID;
	row = (int) (((float) yco + 0.5) * GRID / WXMAX);
	if (row == GRID)
		row--;
	return(col + row);
}

/*---------------------------------------------------------------------------
 *  pnt -- controls operations performed on points
 *---------------------------------------------------------------------------
 */

void pnt(xco, yco)
	int	xco, yco;
{
	point	*closest (), *insertp ();

	point	*pptr, *mptr;
	cpoint *tptr;
	int	tname;

/*
	if ((xco > WXMAX) || (yco > WYMAX))
	{
		alarm(3);
		msg("out of drawing area");
	}
*/
	if (xco > WXMAX) xco = WXMAX;
	if (yco > WYMAX) yco = WYMAX;
/*
	if (xco < 0 ) xco = 0;
	if (yco < 0) yco = 0;
*/

	switch (mode ()) {
    	case I_MODE:
		pptr = closest (hash, xco, yco);
		if (pptr != NULL)
			if (abs(xco - pptr->X) < CLOSEST &&
		      	    abs(yco - pptr->Y) < CLOSEST) {
		        	msg ("\007Point exists there already");
		        	break;
			}
		tname = getname();
		(void) insertp (hash, tname, xco, yco);
		draw_marker(xco,yco);
		draw_update();
		break;

	case D_MODE:
		pptr = closest (hash, xco, yco);
		if (pptr == NULL) {
			msg("No point close");
			return;
		}

		tptr = pptr->cplist;
		rub_marker(pptr->X, pptr->Y);
		while (tptr != NULL) {
			/* Get the point */
			mptr = getxy (hash, tptr->pname);
			if (mptr != NULL ) {
				/* now, erase the line */
				rub_line(pptr->X, pptr->Y, mptr->X, mptr->Y);
				/* Redraw the marker on the end */
				draw_marker(mptr->X, mptr->Y);
				}
			/* go to next one */
			tptr = tptr->nextcp;
			}
		draw_update();

		tname = pptr->name;
		deletep(pptr, tname);
		break;

	case M_MODE:
		msg ("Something bad has happened");
		break;
	default:
		msg("\007Must be in insert, delete or move mode");
    }
}

/*---------------------------------------------------------------------------
 *  line -- controls operations performed on lines
 *---------------------------------------------------------------------------
 */

void line(xco, yco)
	int	xco, yco;
{
	point	*closest ();
	void	insertc (), deletec (), set_fep (), clear_fep ();
	int	fep_selected ();

	if ((xco > WXMAX) || (yco > WYMAX))
		return;

	switch (mode ()) {
	case I_MODE:
		if (!fep_selected ()) {
			point	*fptr;
			if ((fptr = closest(hash, xco, yco)) == NULL) {
				msg ("\007");
				break;
			}
			else {
				set_fep (fptr);
				invert_marker(first_ptr->X, first_ptr->Y);
				draw_update();
			}
		}
		else {
			point	*sptr;
			if ((sptr = closest(hash, xco, yco)) == NULL) {
				msg ("\007");
				break;
			}
			else {
				cpoint	*cptr;
				if (sptr->name == first_ptr->name) {
					msg ("\007");
					return;
				}
				cptr = first_ptr->cplist;
				while (cptr->nextcp != NULL) {
					cptr = cptr->nextcp;
					if (cptr->pname == sptr->name) {
						msg ("\007");
						return;
					}
				}
				insertc(first_ptr->cplist, sptr->name);
				insertc(sptr->cplist, first_ptr->name);
				draw_line(sptr->X, sptr->Y, first_ptr->X, first_ptr->Y);
				draw_marker(first_ptr->X, first_ptr->Y);
				draw_update();
				clear_fep ();
			}
		}
		break;

	case D_MODE:
		if (!fep_selected ()) {
			point	*fptr;
			if ((fptr = closest(hash, xco, yco)) == NULL) {
				msg ("\007");
				break;
			}
			else {
				set_fep (fptr);
				invert_marker(first_ptr->X, first_ptr->Y);
				draw_update();
			}
		}
		else {
			point	*sptr;
			if ((sptr = closest(hash, xco, yco)) == NULL) {
				msg ("\007");
				break;
			}
			else {
				cpoint	*cptr;
				if (sptr->name == first_ptr->name) {
					msg ("\007");
					return;
				}
				cptr = first_ptr->cplist;
				while (cptr->nextcp != NULL) {
					cptr = cptr->nextcp;
					if (cptr->pname == sptr->name)
						deletec(first_ptr->cplist,
							sptr->name);
						deletec(sptr->cplist,
							first_ptr->name);
				}
				rub_line(sptr->X, sptr->Y, first_ptr->X, first_ptr->Y);
				draw_marker(sptr->X, sptr->Y);
				draw_marker(first_ptr->X, first_ptr->Y);
				draw_update();
				clear_fep ();
			}
		}
		break;

	default	: msg ("Must be in insert or delete mode");
	}
}

/*---------------------------------------------------------------------------
 *  closest -- returns a pointer to the structure that is closest in
 *	        X and Y coordinates to the coords passed as params
 *---------------------------------------------------------------------------
 */

point *closest(htbl, xco, yco)
	point *htbl[];
	int xco, yco;
{
	int	getbucket ();
	point	*pptr, *tptr, *search();
	int	home, row, col;

	min_dist = MAXINT;

	home = getbucket(xco, yco);
	row = home % GRID;
	col = (int) (home / GRID);

	tptr = pptr = search(htbl, home, xco, yco);
	if ((row != 0) && (col != 0)) {
		tptr = search(htbl, home - (GRID + 1), xco, yco);  /* l dn */
		if (tptr != NULL)
			pptr = tptr;
	}
	if (col != 0) {
		tptr = search(htbl, home - GRID, xco, yco);	   /* l */
		if (tptr != NULL)
			pptr = tptr;
	}
	if ((row != (GRID - 1)) && (col != 0)) {
		tptr = search(htbl, home - (GRID - 1), xco, yco);  /* l up */
		if (tptr != NULL)
			pptr = tptr;
	}
	if (row != (GRID - 1)) {
		tptr = search(htbl, home + 1, xco, yco);	   /* up */
		if (tptr != NULL)
			pptr = tptr;
	}
	if (row != 0) {
		tptr = search(htbl, home - 1, xco, yco);	   /* dn */
		if (tptr != NULL)
			pptr = tptr;
	}
	if ((row != 0) && (col != (GRID - 1))) {
		tptr = search(htbl, home + (GRID - 1), xco, yco);  /* r dn */
		if (tptr != NULL)
			pptr = tptr;
	}
	if (col != (GRID - 1)) {
		tptr = search(htbl, home + GRID, xco, yco);	   /* r */
		if (tptr != NULL)
			pptr = tptr;
	}
	if ((row != (GRID - 1)) && (col != (GRID - 1))) {
		tptr = search(htbl, home + (GRID + 1), xco, yco);  /* r up */
		if (tptr != NULL)
			pptr = tptr;
	}
	return(pptr);
}

/*---------------------------------------------------------------------------
 *  search -- searches a box in the hash table for a point closer
 *	       than the current closest
 *---------------------------------------------------------------------------
 */

point *search(htbl, i, xco, yco)
	point *htbl[];
	int i;
	int xco, yco;
{
	point	*pptr, *tptr = NULL;
	int	dx, dy, dist;

	pptr = htbl[i];

	while (pptr->nextp != NULL) {
		pptr = pptr->nextp;
		dx = xco - pptr->X;
		dy = yco - pptr->Y;
		dist = sqr(dx) + sqr(dy);
		if (dist < min_dist) {
			min_dist = dist;
			tptr = pptr;
		}
	}
	return(tptr);
}

/*---------------------------------------------------------------------------
 *  getname -- returns a unique name
 *---------------------------------------------------------------------------
 */

int getname()
{
	int	col_access ();
	void col_insert ();

	int	i;

	i = 1;
	for (;;) {
		if (col_access (used_names, i) == 0) {
			col_insert (&used_names, i, i);
			return (i);
		}
		i++;
	}
}

void release_name (n)
{
	void	col_delete ();

	col_delete (&used_names, n);
}

/*---------------------------------------------------------------------------
 *  getxy -- returns a pointer to structure containing X and Y coords
 *	      of a given name
 *---------------------------------------------------------------------------
 */

point *getxy (htbl, n)
	point	*htbl[];
	int	n;
{
	point *pptr;
	int   i = 0;

	for (i = 0; i < GSQRD; i++) {
		pptr = htbl[i];
		while (pptr->nextp != NULL) {
			pptr = pptr->nextp;
			if (pptr->name == n)
				return(pptr);
		}
	}
	return(NULL);
}

/*---------------------------------------------------------------------------
 *  clean -- free memory malloced for list structures
 *---------------------------------------------------------------------------
 */

void deleteall ()
{
	int i;

	for (i = 0; i < GSQRD; i++) {
		freep(hash[i]);
		hash[i]->nextp = NULL;
	}
	col_deleteall (&used_names);
	col_init (&used_names);
	clear_canvas ();
}

void deleteallinavr ()
{
        int i;

        for (i = 0; i < GSQRD; i++) {
                freep(hash[i]);
                hash[i]->nextp = NULL;
        }
        col_deleteall (&used_names);
        col_init (&used_names);
}

void move_down (xco, yco)
	int xco, yco;
{
	point	*closest ();
	point	*tptr;

	tptr = closest (hash, xco, yco);
	if (tptr == NULL) {
		msg ("Can't find a point close to the cursor");
		return;
	}
	origin_x = tptr->X;
	origin_y = tptr->Y;
	set_fep(tptr);
	invert_marker(tptr->X, tptr->Y);
	draw_update();
}

void move_up (xco, yco)
	int xco, yco;
{
	point	*closest ();
	void	drawgraph (), remove_point (), replace_point ();

	if (fep_selected ()) {
		point	*tptr;
		remove_point (hash, first_ptr);
		tptr = closest (hash, xco, yco);
		if (tptr != NULL)
			if (abs (xco - tptr->X) < CLOSEST &&
		    	    abs (yco - tptr->Y) < CLOSEST) {
				msg ("\007There's a point there already");
				replace_point (hash, first_ptr,
					       origin_x, origin_y);
			}
			else
				replace_point (hash, first_ptr, xco, yco);
		else
			replace_point (hash, first_ptr, xco, yco);
		clear_fep ();
		drawgraph ();
	}
}

void drag (xco, yco)
	int xco, yco;
{
	void	drawgraph (), move_point ();
	cpoint	*tptr;
	point	*mptr;

	if (fep_selected()) {
		rub_marker (first_ptr->X, first_ptr->Y);
        tptr = first_ptr->cplist;
        while (tptr != NULL) {
            /* Get the point */
            mptr = getxy (hash, tptr->pname);
            if (mptr != NULL ) {
                /* now, erase the line */
                rub_line(first_ptr->X, first_ptr->Y, mptr->X, mptr->Y);
                draw_line(xco, yco, mptr->X, mptr->Y);
                /* Redraw the marker on the end */
                draw_marker(mptr->X, mptr->Y);
                }
            /* go to next one */
            tptr = tptr->nextcp;
            }
		move_point (hash, first_ptr, xco, yco);
		invert_marker (xco, yco);
        draw_update();
	}
}

static void set_fep (fptr)
	point	*fptr;
{
	fep = TRUE;
	first_ptr = fptr;
}

void clear_fep ()
{
	fep = FALSE;
	first_ptr = NULL;
}

int fep_selected ()
{
	return fep;
}

point *first_end_point ()
{
	return first_ptr;
}

/*---------------------------------------------------------------------------
 *  name_exists -- true if a point with name n exists in hash
 *---------------------------------------------------------------------------
 */

int name_exists (htbl, n)
	point	*htbl[];
	int	n;
{
	point	*getxy ();

	return (getxy (htbl, n) != NULL);
}

/*---------------------------------------------------------------------------
 *  change_clists -- replaces each occurrence of old in the connect lists
 *		      of htbl, with new
 *---------------------------------------------------------------------------
 */

void change_clists (htbl, old, new)
	point	*htbl[];
	int	old, new;
{
	int	j;
	point	*pptr;
	cpoint	*cptr;

	for (j = 0; j < GSQRD; j++) {
		pptr = htbl[j];
		while (pptr->nextp != NULL) {
			pptr = pptr->nextp;
			cptr = pptr->cplist;
			if (in_clist (old, cptr))
				deletec (cptr, old);
				if ((pptr->name != new) &&
					!in_clist (new, cptr))
					insertc (cptr, new);
		}
	}
}

/*---------------------------------------------------------------------------
 *  collapse -- coincident points in htbl are collapsed to a single point
 *---------------------------------------------------------------------------
 */

void collapse (htbl)
	point	*htbl[];
{
	point	*closest ();
	int	coincident ();
	void	change_clists (), remove_point (), release_name (),
		freec ();

	int	i;
	point	*new_point;

	for (i = 0; i < GSQRD; i++) {
		new_point = htbl[i];
		while (new_point->nextp != NULL) {
			point	*prev_point = new_point,
				*close;
			new_point = new_point->nextp;
			remove_point (htbl, new_point);
			close = closest (htbl, new_point->X, new_point->Y);
			if (close != NULL) {
				if (coincident (new_point, close)) {
					change_clists (htbl, new_point->name,
						close->name);
					merge_clists (close, new_point);
					release_name (new_point->name);
					freec (new_point->cplist);
					free ((char *) new_point);
					new_point = prev_point;
				}
			}
			else {
				replace_point (htbl, new_point,
					new_point->X, new_point->Y);
				new_point = prev_point->nextp;
			}
		}
	}
}

/*---------------------------------------------------------------------------
 *  transform -- new and old are coincident points (not necessarily in the
 *		 same hash table). new is transformed, so that it has
 * 		 the same name and coordinates as old.
 *---------------------------------------------------------------------------
 */

void transform (htbl, new, old)
	point *htbl[], **new, *old;
{
	point	*tptr;
	int	name = (*new)->name;

	if (getbucket (old->X, old->Y) != getbucket ((*new)->X, (*new)->Y)) {
		remove_point (htbl, *new);
		tptr = insertp (htbl, old->name, old->X, old->Y);
		tptr->cplist = (*new)->cplist;
		free ((char *) (*new));
		*new = tptr;
	}
	else {
		(*new)->name = old->name;
		(*new)->X = old->X;
		(*new)->Y = old->Y;
	}
	release_name (name);
}

/*---------------------------------------------------------------------------
 *  coincident -- two points are coincident if they are with CLOSEST units
 *		   of each other (X and Y coordinates)
 *---------------------------------------------------------------------------
 */

int coincident (a, b)
	point	*a, *b;
{
	return (abs (a->X - b->X) < CLOSEST) && (abs (a->Y - b->Y) < CLOSEST);
}

int in_clist (n, list)
	int	n;
	cpoint	*list;
{
	while (list->nextcp != NULL) {
		list = list->nextcp;
		if (list->pname == n)
			return TRUE;
	}
	return FALSE;
}

void merge_clists (dst, src)
	point	*dst, *src;
{
	cpoint	*dst_cl, *src_cl;

	dst_cl = dst->cplist;
	src_cl = src->cplist;
	while (src_cl->nextcp != NULL) {
		src_cl = src_cl->nextcp;
		if (!in_clist (src_cl->pname, dst_cl))
			insertc (dst_cl, src_cl->pname);
	}
}

point	*find_point (list, target_name)
	point	*list;
	int	target_name;
{
	while (list->nextp != NULL) {
		list = list->nextp;
		if (list->name == target_name)
			return list;
	}
	return NULL;
}

void add_to_graph (htbl, new)
	point	*htbl[], *new;
{
	void	merge_clists ();
	point	*find_point ();

	point	*bucket, *pptr;

	bucket = htbl[getbucket (new->X, new->Y)];
	if ((pptr = find_point (bucket, new->name)) != NULL)
		merge_clists (pptr, new);
	else {
		new->nextp = bucket->nextp;
		bucket->nextp = new;
	}
}