/*
 * Copyright (c) 1992, The Geometry Center
 *                     University of Minnesota 
 *                     1300 South Second Street
 *                     Minneapolis, MN  55454
 *
 * email address: software@geom.umn.edu
 *
 * This software is copyrighted as noted above.  It may be freely copied,
 * modified, and redistributed, provided that the copyright notice is
 * preserved on all copies.
 *
 * There is no warranty or other guarantee of fitness for this software,
 * it is provided solely "as is".  Bug reports or fixes may be sent
 * to the authors, who may or may not act on them as they desire.
 *
 * You may not include this software in a program or other software product
 * without supplying the source, or without informing the end-user that the
 * source is available for no extra charge.
 *
 * If you modify this software, you should include a notice giving the
 * name of the person performing the modification, the date of modification,
 * and the reason for such modification.
 *
 *     The National Science and Technology Research Center for
 *      Computation and Visualization of Geometric Structures
 */

/****** A DARN GOOD .C FILE.  DARN GOOD.  **********/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#import <objc/objc.h>
#include "link_types.h"
#include "link_edit_types.h"
#include "link_edit_global.h"
#include "link.h"
#import "EditView.h"
#include "mf.h"
#import "Link.h"


/*LinkStatus *gnrc;*/

/* This guy is set when LinkAddPointWorldCoords is called, indicating that, hey,
   sure, a point may end up really close to another link, but I'm not putting it
   there; I'm putting in points one at a time, in order (pretty much), one strand
   at a time */
static BOOL isAutomated = NO;
static BOOL isHitAutomated = NO;

void LinkComputeDeviceCoords(LinkStatus *gnrc)
{
  LinkList *lnk;
  LinkPointList *pnt;
  LinkCrossingList *crssng;
  float x_orig,y_orig;

  x_orig = gnrc->origin.dcx; y_orig = gnrc->origin.dcy;
  lnk = gnrc->link.next;
  while(lnk != NULL) {
     pnt = lnk->point.next;
     while(pnt != NULL) {
        pnt->dcx = x_orig + (int) (pnt->x * gnrc->xscale * xppmm);
        pnt->dcy = y_orig - (int) (pnt->y * gnrc->yscale * yppmm);
        crssng = pnt->crossing.next;
        while(crssng != NULL) {
           crssng->dcx = x_orig + (int) (crssng->x * gnrc->xscale * xppmm);
           crssng->dcy = y_orig - (int) (crssng->y * gnrc->yscale * yppmm);
           crssng = crssng->next;
          }
        pnt = pnt->next;
       }
     lnk = lnk->next;
    }
}

void LinkComputePointWorldCoords(LinkStatus *gnrc,LinkPointList *pnt)


{
  pnt->x = (double) (pnt->dcx - gnrc->origin.dcx) /
                     (gnrc->xscale * xppmm); 
  pnt->y = (double) (-pnt->dcy + gnrc->origin.dcy) /
                     (gnrc->yscale * yppmm); 

}

void LinkComputePointDeviceCoords(LinkStatus *gnrc,LinkPointList *pnt)


{
   pnt->dcx = gnrc->origin.dcx + (int) (pnt->x * gnrc->xscale * xppmm);
   pnt->dcy = gnrc->origin.dcy - (int) (pnt->y * gnrc->yscale * yppmm);

}

LinkCrossingList *LinkFindCrossing(LinkStatus *gnrc,float x,float y)

/* Routine checks all crossings of all links */
{
  LinkList *lnk;
  LinkPointList *pnt;
  LinkCrossingList *rtn,*crssng;
  float x_diff,y_diff,dcx,dcy;
  float xtemp,ytemp;

  rtn = NULL;
  lnk = gnrc->link.next;
  while(lnk != NULL) {
     pnt = lnk->point.next;
     x_diff = LINK_X_HIT_RADIUS; y_diff = LINK_Y_HIT_RADIUS;

     while(pnt != NULL) {
        crssng = pnt->crossing.next;
        while(crssng != NULL) {
           dcx = crssng->dcx; dcy = crssng->dcy;
           xtemp = (x > dcx) ? x-dcx:dcx-x; ytemp = (y > dcy) ? y-dcy:dcy-y;
           if(xtemp <= x_diff && ytemp <= y_diff) {
              rtn = crssng; x_diff = xtemp; y_diff = ytemp;
             }
           crssng = crssng->next;
          }
        pnt = pnt->next;
       }
     lnk = lnk->next;
    }
  return(rtn);
}

LinkList *LinkFindLink(LinkStatus *gnrc,float x,float y)

{
  LinkList *lnk;

  lnk = gnrc->link.next;

  if (isHitAutomated)
    {
      while(lnk != NULL) {
	if(LinkFindPoint(gnrc,lnk,x,y) != NULL) break;
	lnk = lnk->next;
      }
      return lnk;
    }
  while (lnk != NULL) {
    if(LinkFindPoint(gnrc,lnk,x,y) != NULL) break;
    if(LinkFindEdge(gnrc,lnk,x,y) != NULL) break;
    lnk = lnk->next;
  }
  return(lnk);
}

LinkPointList *LinkFindEdge(LinkStatus *gnrc,LinkList *lnk,float x,float y)

/* Returns point representing start of selected edge */

{
  float x_diff,y_diff;
  float xtemp,ytemp;
  float t;           /* Line parameter */
  int d,r0,s0,r1,s1;
  LinkPointList *pnt,*selected_pnt;

  x_diff = LINK_X_HIT_RADIUS; /* Initialize to just too far away */
  y_diff = LINK_Y_HIT_RADIUS;

  if((pnt = lnk->point.next) == NULL) return(NULL);
  selected_pnt = NULL;

  while(pnt->next != NULL) {
     r0 = pnt->dcx; s0 = pnt->dcy;
     r1 = pnt->next->dcx; s1 = pnt->next->dcy;
     d = (r1-r0)*(r1-r0) + (s1-s0)*(s1-s0);

     if(d != 0) {
        t = ((float) ( (x-r0)*(r1-r0) + (y-s0)*(s1-s0) ))/((float) d);
        if((t >= 0.0) && (t <= 1.0)) {

           xtemp = x - r0 - (int) (t*(r1-r0));
           xtemp = (xtemp > 0) ? xtemp:-xtemp;

           ytemp = y - s0 - (int) (t*(s1-s0));
           ytemp = (ytemp > 0) ? ytemp:-ytemp;

           if((xtemp <= x_diff) && (ytemp <= y_diff)) {
              selected_pnt = pnt;
              x_diff = xtemp;
              y_diff = ytemp;
             }
          }
       }
     pnt = pnt->next;
    }

  /* Special case if link is closed */
  if(lnk->closed) {
     r0 = pnt->dcx; s0 = pnt->dcy;
     r1 = lnk->point.next->dcx; s1 = lnk->point.next->dcy;
     d = (r1-r0)*(r1-r0) + (s1-s0)*(s1-s0);

     if(d != 0) {
        t = ((float) ( (x-r0)*(r1-r0) + (y-s0)*(s1-s0) ))/((float) d);
        if((t >= 0.0) && (t <= 1.0)) {

           xtemp = x - r0 - (int) (t*(r1-r0));
           xtemp = (xtemp > 0) ? xtemp:-xtemp;

           ytemp = y - s0 - (int) (t*(s1-s0));
           ytemp = (ytemp > 0) ? ytemp:-ytemp;

           if((xtemp <= x_diff) && (ytemp <= y_diff)) {
              selected_pnt = pnt;
              x_diff = xtemp;
              y_diff = ytemp;
             }
          }
       }
    }

  return(selected_pnt);
}


LinkPointList *LinkFindPoint(LinkStatus *gnrc,LinkList *lnk,float x,float y)

{
  LinkPointList *pnt,*rtn;
  float x_diff,y_diff,dcx,dcy;
  float xtemp,ytemp;

  rtn = NULL;
  pnt = lnk->point.next;
  x_diff = LINK_X_HIT_RADIUS; y_diff = LINK_Y_HIT_RADIUS;

  if (isHitAutomated)
    {
      while (pnt != NULL)
	{
	  if (pnt->dcx == x && pnt->dcy == y)
	    return pnt;
	  pnt = pnt->next;
	}
      return NULL;
    }
  while(pnt != NULL) {
    dcx = pnt->dcx; dcy = pnt->dcy;
    xtemp = (x > dcx) ? x-dcx:dcx-x; ytemp = (y > dcy) ? y-dcy:dcy-y;
    if(xtemp <= x_diff && ytemp <= y_diff) {
      rtn = pnt; x_diff = xtemp; y_diff = ytemp;
    }
    pnt = pnt->next;
  }
  return(rtn);
}


int LinkAddPointWorldCoords(LinkStatus *gnrc, float x, float y,
			    BOOL automated, BOOL hitAutomated)
{
  int retvalue;
  LinkPointList pnt;
  pnt.x = x; pnt.y = y;
  LinkComputePointDeviceCoords(gnrc, &pnt);
  isAutomated = automated; isHitAutomated = hitAutomated;
  retvalue = LinkAddPoint(gnrc, pnt.dcx, pnt.dcy);
  isAutomated = isHitAutomated = NO;
  return retvalue;
}

/* Returns 1 if link becomes closed; otherwise 0 */
int LinkAddPoint(LinkStatus *gnrc,float x,float y)

/* Eventually: intelligently add points before, between, or after nodes */

{
  LinkList *lnk, *lnk2;
  float delta_x,delta_y;
  LinkPointList *pnt, *pnt2;

  lnk = gnrc->current_link;
  if(lnk == NULL) { /* Start a new link */ 
    if((lnk = LinkCreateNewLink( gnrc)) == NULL) return 0;
    [globalEditView clearScreen];
    [globalEditView ReDrawLinkTopWindow :gnrc];
    LinkAddPointAfter(gnrc,lnk,x,y);
    return 0;
  }

  /* If point near first point, close link */
  if((pnt = lnk->point.next) != NULL && !(lnk->closed) ) {
     delta_x = x - pnt->dcx;  delta_x = (delta_x < 0) ? -delta_x:delta_x;
     delta_y = y - pnt->dcy;  delta_y = (delta_y < 0) ? -delta_y:delta_y;
     if(delta_x < LINK_X_HIT_RADIUS && delta_y < LINK_Y_HIT_RADIUS) {
        [globalEditView setCurrentPoint:NULL fromLink:lnk];
        if (LinkCloseCurrentLink( gnrc)) return 1;
	else return -1;
      }
   }

  /* If point part of another strand, connect them */
  if (!isAutomated)
    {
      lnk2 = LinkFindLink(gnrc,x,y);
      if (lnk2 != NULL)
	{
	  pnt2 = LinkFindPoint(gnrc,lnk2,x,y);
	  if (pnt2 == NULL) return -1;
	  if (lnk2 != lnk)
	    {
	      if (pnt2->next == NULL)
		LinkReverseArrows(gnrc, lnk2);
	      if (pnt2->previous->previous == NULL)
		LinkJoinLinks(gnrc,lnk,lnk2);
	      else return -1;
	    }
	  return (lnk2 == lnk) ? -1 : 1;
	}
    }

  if (!isAutomated)
    {
      /* else, if edge hit add to interior of edge */
      if((pnt = LinkFindEdge(gnrc,lnk,x,y)) != NULL ) {
	double param;
	LinkPointList *nxt,*new;
	LinkCrossingList *crssng;
	
	/* Compute param value of new point on edge */
	if((nxt = pnt->next) == NULL) nxt = lnk->point.next;
	delta_x = x - pnt->dcx;  delta_x = (delta_x < 0) ? -delta_x:delta_x;
	delta_y = y - pnt->dcy;  delta_y = (delta_y < 0) ? -delta_y:delta_y;
	if(delta_x > delta_y) 
	  param = (double) (x - pnt->dcx) / (double) (nxt->dcx - pnt->dcx);
	else
	  param = (double) (y - pnt->dcy) / (double) (nxt->dcy - pnt->dcy);
	
	/* create new point */
	new = (LinkPointList *) malloc(sizeof(LinkPointList));
	if(new == NULL) {fprintf(stderr,"GULP! Out of space!\n"); return 0;}
	new->x = pnt->x + param*(nxt->x - pnt->x);
	new->y = pnt->y + param*(nxt->y - pnt->y);
	new->z = -1.0;
	new->next = pnt->next;
	new->previous = pnt;
	new->isVertex = 1;
	new->isAnchor = 0;
	
	if(pnt->next != NULL) pnt->next->previous = new;
	pnt->next = new;
	LinkComputePointDeviceCoords(gnrc,new); 
	lnk->num ++;
	
	/* Fix crossing list */
	crssng = pnt->crossing.next;
	while(crssng != NULL) {
	  if(crssng->param > param) break;
	  crssng = crssng->next;
	}
	new->crossing.next = crssng;
	
	crssng = &(pnt->crossing);
	while(crssng->next !=NULL) {
	  if(crssng->next->param > param) break;
	  crssng = crssng->next;
	  crssng->param /= param;
	}
	/* cut off crossing list at break point */
	crssng->next = NULL;
	
	/* fix new crossing list */
	crssng = new->crossing.next;
	while(crssng != NULL) {
	  crssng->param = (crssng->param - param)/(1.0-param);
	  crssng->crossing->partner = new;
	  crssng = crssng->next;
	}
	[globalEditView clearScreen];
	[globalEditView ReDrawLinkTopWindow :gnrc];
	return 0;
      }
    }
  /* else, start new link if current closed */
  if(lnk->closed) {
    if((lnk = LinkCreateNewLink( gnrc)) == NULL) return 0;
     [globalEditView clearScreen];
     [globalEditView ReDrawLinkTopWindow :gnrc];
     LinkAddPointAfter(gnrc,lnk,x,y);
     return 0;
    }

  /* else, add to end of current link */  
  LinkAddPointAfter(gnrc,lnk,x,y);
  return 0;
}

void LinkAddAnchor(LinkStatus *gnrc, LinkList *lnk, LinkPointList *pnt, float x,float y)

{
  float delta_x,delta_y;

  /* If user selected existing point, make it an anchor */
  if (pnt != NULL)
    {
      pnt->isAnchor = 1;
      [globalEditView clearScreen];
      [globalEditView ReDrawLinkTopWindow :gnrc];
      LinkPrintMessage("You may make another anchor.");
      return;
    }

  /* Otherwise, add anchor onto edge */
  if((pnt = LinkFindEdge(gnrc,lnk,x,y)) != NULL ) {
     double param;
     LinkPointList *nxt,*new;
     LinkCrossingList *crssng;

     /* Compute param value of new point on edge */
     if((nxt = pnt->next) == NULL) nxt = lnk->point.next;
     delta_x = x - pnt->dcx;  delta_x = (delta_x < 0) ? -delta_x:delta_x;
     delta_y = y - pnt->dcy;  delta_y = (delta_y < 0) ? -delta_y:delta_y;
     if(delta_x > delta_y) 
        param = (double) (x - pnt->dcx) / (double) (nxt->dcx - pnt->dcx);
     else
        param = (double) (y - pnt->dcy) / (double) (nxt->dcy - pnt->dcy);

     /* create new point */
     new = (LinkPointList *) malloc(sizeof(LinkPointList));
     if(new == NULL) {fprintf(stderr,"GULP! Out of space!\n"); return;}
     new->x = pnt->x + param*(nxt->x - pnt->x);
     new->y = pnt->y + param*(nxt->y - pnt->y);
     new->z = -1.0;
     new->next = pnt->next;
     new->previous = pnt;
     new->isAnchor = 1;
     new->isVertex = 0;

     if(pnt->next != NULL) pnt->next->previous = new;
     pnt->next = new;
     LinkComputePointDeviceCoords(gnrc,new); 
     lnk->num ++;
     
     /* Fix crossing list */
     crssng = pnt->crossing.next;
     while(crssng != NULL) {
        if(crssng->param > param) break;
        crssng = crssng->next;
       }
     new->crossing.next = crssng;

     crssng = &(pnt->crossing);
     while(crssng->next !=NULL) {
        if(crssng->next->param > param) break;
        crssng = crssng->next;
        crssng->param /= param;
       }
     /* cut off crossing list at break point */
     crssng->next = NULL;

     /* fix new crossing list */
     crssng = new->crossing.next;
     while(crssng != NULL) {
        crssng->param = (crssng->param - param)/(1.0-param);
        crssng->crossing->partner = new;
        crssng = crssng->next;
       }
/*     XClearWindow(dpy,gnrc->TopWindow);*/
     [globalEditView clearScreen];
     [globalEditView ReDrawLinkTopWindow :gnrc];
     LinkPrintMessage("You may make another anchor.");
     return;
   }
}

int LinkAddPointAfter(LinkStatus *gnrc,LinkList *lnk,float x,float y)

{
  LinkPointList *pnt;

  if(lnk == NULL) {
     LinkPrintMessage("No current link!");
     return(0);
    }
  pnt = &(lnk->point);
  while(pnt->next != NULL) pnt = pnt->next;
  pnt->next = (LinkPointList *) malloc(sizeof(LinkPointList));
  if(pnt->next == NULL) {
     LinkPrintMessage("Out of memory!");
     return(0);
    }
  pnt->next->previous = pnt;

  pnt = pnt->next;
  pnt->dcx = x; pnt->dcy = y;
  LinkComputePointWorldCoords(gnrc,pnt);
  pnt->z = -1.0;
  pnt->next = NULL;
  pnt->crossing.next = NULL;
  pnt->isAnchor = 0;
  pnt->isVertex = 1;
  lnk->num ++;
  [globalEditView setCurrentPoint:pnt fromLink:lnk];
  if(pnt->previous == &(lnk->point)) {  /* first point in link */
    [globalEditView linkDrawPoint :gnrc :lnk :pnt];
    }
  else { 
    if(LinkComputeEdgeCrossings(gnrc,lnk,pnt->previous)){ /* crossings added */
      [globalEditView clearScreen];
      [globalEditView ReDrawLinkTopWindow :gnrc];
      }
    else {  /* Just draw edge */
      [globalEditView linkDrawPoint :gnrc :lnk :pnt];
      [globalEditView linkDrawEdge :gnrc :lnk :pnt->previous];
    }
  }
  [globalEditView flushItsWindow];
  return 0;
}

void LinkFreeEdgeCrossings(LinkStatus *gnrc,LinkList *lnk,LinkPointList *pnt)

{
  LinkCrossingList *crssng,*tmp;

  if(pnt == NULL) return;
  /* Free crossing data of pnt and crossing partners */
  crssng = pnt->crossing.next;
  pnt->crossing.next = NULL;
  while(crssng != NULL) {
     tmp = crssng->next;
     LinkFreeCrossing(gnrc,crssng->partner,crssng->crossing);
     free(crssng);
     crssng = tmp;
    }
}

void LinkDeleteAll(LinkStatus *gnrc)

{
  LinkList *lnk,*tmp;
  lnk = gnrc->link.next;
  while(lnk != NULL) {
     tmp = lnk->next;
     LinkDeleteLink(gnrc,lnk);
     lnk = tmp;
    }
  gnrc->num = 0;
}

void LinkDeleteLink(LinkStatus *gnrc,LinkList *lnk)

{
  LinkPointList *pnt,*tmp;
  LinkList *lnk_ptr;
  
  if(lnk == NULL) return;

  if(gnrc->current_link == lnk) {  /* Change current link */
     if(gnrc->link.next != lnk) 
        gnrc->current_link = gnrc->link.next;
     else
        gnrc->current_link = lnk->next;
    }

  /* remove crossings and points */
  pnt = lnk->point.next;
  while(pnt != NULL) {
     LinkFreeEdgeCrossings(gnrc,lnk,pnt);
     pnt = pnt->next; 
    }
  pnt = lnk->point.next;
  while(pnt != NULL) {
     tmp = pnt->next;
     free(pnt);
     pnt = tmp;
    }

  /* remove from list of links */
  lnk_ptr = &(gnrc->link);
  while(lnk_ptr->next != NULL) {
     if(lnk_ptr->next == lnk) {
        lnk_ptr->next = lnk->next;
        break;
       }
     lnk_ptr = lnk_ptr->next;
    }
  free(lnk);
  gnrc->num --;
}

void LinkDeletePoint(LinkStatus *gnrc,LinkList *lnk,LinkPointList *pnt)

/* Routine deletes pnt and recomputes crossings for pnt->previous */
{
  LinkPointList *prev_pnt,*tmp_pnt;

  if(pnt == NULL) return;
  if(lnk->closed && lnk->num < 4) {
     LinkPrintMessage("Too few points on closed link to delete!");
     return;
    }

  /* Free crossings on pnt and pnt->previous */
  LinkFreeEdgeCrossings(gnrc,lnk,pnt);
  prev_pnt = pnt->previous;
  if(lnk->closed && prev_pnt == &(lnk->point)) {
     /* If link is closed recompute crossing from last point */
     prev_pnt = &(lnk->point);
     while(prev_pnt->next != NULL) prev_pnt = prev_pnt->next;
    }
  if(prev_pnt != &(lnk->point))
     LinkFreeEdgeCrossings(gnrc,lnk,prev_pnt);
  

  /* remove pnt from list */
  tmp_pnt = pnt->previous;
  tmp_pnt->next = pnt->next;
  if(pnt->next != NULL) pnt->next->previous = tmp_pnt;
  free(pnt); 
  lnk->num--;

  /* Recompute crossing for prev_pnt */
  if(prev_pnt != &(lnk->point))
     LinkComputeEdgeCrossings(gnrc,lnk,prev_pnt);
}

void LinkReComputeEdgeCrossings(LinkStatus *gnrc,LinkList *lnk,LinkPointList *pnt)

/* Routine removes all the crossing structures from pnt and all */
/* corresponding crossings on partners and recomputes crossings for pnt. */
/* Over-under relationships are maintained. */ 
{
  LinkCrossingList *crssng,*old_crssng,*tmp;

  if(pnt == NULL) return;
  old_crssng = crssng = pnt->crossing.next;  /* Save old list */
  pnt->crossing.next = NULL;
  while(crssng != NULL) {
     LinkFreeCrossing(gnrc,crssng->partner,crssng->crossing);
     crssng = crssng->next;
    }
  LinkComputeEdgeCrossings(gnrc,lnk,pnt);

  /* Restore over under relationships */
  crssng = pnt->crossing.next;
  while(crssng != NULL) {
     tmp = old_crssng;
     while(tmp != NULL) {
        if(tmp->partner == crssng->partner) { /* restore over-under */
           if(tmp->z > 0.0) {
              crssng->z = 1.0; crssng->crossing->z = -1.0;
             }
           else {
              crssng->z = -1.0; crssng->crossing->z = 1.0;
             }
          }
        tmp = tmp->next;
       }
     crssng = crssng->next;
    }

  /* Free old crossing list */
  crssng = old_crssng;
  while(crssng != NULL) {
     tmp = crssng->next;
     free(crssng);
     crssng = tmp;
    } 
}

void LinkFreeCrossing(LinkStatus *gnrc,LinkPointList *pnt,LinkCrossingList *crssng)
/* Routine removes crssng from the crossing list of pnt */
{
  LinkCrossingList *tmp;

  if(pnt == NULL) return;
  tmp = &(pnt->crossing);
  while(tmp->next != NULL) {
     if(tmp->next == crssng) {
        tmp->next = crssng->next;
        free(crssng);
        break;
       }
     tmp = tmp->next;
    }
}

int LinkComputeEdgeCrossings(LinkStatus *gnrc,LinkList *lnk,LinkPointList *pnt)

/* routine computes all crossings between edge beginning with pnt (on */
/* link lnk) and all other edges on all other links */
/* returns the number of crossings inserted */
/* Note: when reading links over existing links, this routine is */
/* used  when lnk is not actually on the list attached to gnrc! */

{
  LinkList *tmp_lnk;
  LinkPointList *tmp_pnt;
  LinkCrossingList crossing;
  double param,tmp_param;
  int total;

  if(pnt == NULL) return(0);

  tmp_lnk = gnrc->link.next;
  total = 0;
  while(tmp_lnk != NULL) {
    tmp_pnt = tmp_lnk->point.next;
    while(tmp_pnt != NULL)
      {
	if(LinkEdgeCrossEdge(gnrc,lnk,pnt,tmp_lnk,tmp_pnt,&crossing,
			     &param,&tmp_param))
	  {
	    LinkInsertCrossing(gnrc,lnk,pnt,tmp_lnk,tmp_pnt,&crossing,
			       param,tmp_param);
	    total++;
	  }
	tmp_pnt = tmp_pnt->next;
      }
    tmp_lnk = tmp_lnk->next;
  }
  return(total);
}

int LinkInsertCrossing(LinkStatus *gnrc,LinkList *lnk1,
		       LinkPointList *pnt1, LinkList *lnk2,
		       LinkPointList *pnt2,
		       LinkCrossingList *crossing,
		       double param1, double param2)


/* Routine places crossing in the crossing lists of pnt1 and pnt2, in the */
/* position determined by param1 and param2 .  crossing on pnt1 goes on top*/

{
  LinkCrossingList *tmp,*nxt;
  LinkCrossingList *crssng1,*crssng2;

  tmp = &(pnt1->crossing);
  while(tmp->next != NULL) {
      if(tmp->next->param > param1) break; 
      tmp = tmp->next;
     }
  nxt = tmp->next;
  tmp->next = (LinkCrossingList *) malloc(sizeof(LinkCrossingList));
  if(tmp->next == NULL) {
     fprintf(stderr,"PANIC! Cannot allocate crossing node!");
     return(0);
    }
  crssng1 = tmp->next;
  crssng1->next = nxt;
  crssng1->partner = pnt2;
  crssng1->param = param1;
  crssng1->x = crossing->x; crssng1->y = crossing->y; crssng1->z = 1.0;
  crssng1->dcx = crossing->dcx; crssng1->dcy = crossing->dcy;

  tmp = &(pnt2->crossing);
  while(tmp->next != NULL) {
      if(tmp->next->param > param2) break;
      tmp = tmp->next;
     }
  nxt = tmp->next;
  tmp->next = (LinkCrossingList *) malloc(sizeof(LinkCrossingList));
  if(tmp->next == NULL) {
     fprintf(stderr,"PANIC! Cannot allocate crossing node!");
     return(0);
    }
  crssng2 = tmp->next;
  crssng2->next = nxt;
  crssng2->partner = pnt1;
  crssng2->param = param2;
  crssng2->x = crossing->x; crssng2->y = crossing->y; crssng2->z = -1.0;
  crssng2->dcx = crossing->dcx; crssng2->dcy = crossing->dcy;

  /* cross reference crossings */
  crssng1->crossing = crssng2;
  crssng2->crossing = crssng1;
  return 14;
}


int LinkEdgeCrossEdge(LinkStatus *gnrc,LinkList *lnk1,
		      LinkPointList *pnt1, LinkList *lnk2,
		      LinkPointList *pnt2, LinkCrossingList *crossing,
		      double *param1,double *param2)


/* Routine returns 1 if a crossing occurs in the xy projections */
/* 0 if not.  If yes, the crossing point is returned in crossing */
{
  double coeff[2][3];
  LinkPointList sample,*nxt1,*nxt2;
  int success;

  if(pnt1 == pnt2) return(0); 
  if(pnt1->next == NULL && lnk1->closed == LINK_NO) return(0);
  if(pnt2->next == NULL && lnk2->closed == LINK_NO) return(0);

  success = 0;
  if((nxt1 = pnt1->next) == NULL) nxt1 = lnk1->point.next;
  if((nxt2 = pnt2->next) == NULL) nxt2 = lnk2->point.next;
  if(pnt1 == nxt2 || pnt2 == nxt1) return(0);

  coeff[0][0] = nxt1->x - pnt1->x; coeff[0][1] = pnt2->x - nxt2->x; 
  coeff[0][2] = pnt2->x - pnt1->x;
  coeff[1][0] = nxt1->y - pnt1->y; coeff[1][1] = pnt2->y - nxt2->y; 
  coeff[1][2] = pnt2->y - pnt1->y;
  if(SolveTwoByTwo(coeff,param1,param2)) {
     if(0.0 < *param1 && *param1 < 1.0 && 0.0 < *param2 && *param2 < 1.0) {
        sample.x = pnt1->x + *param1 * (nxt1->x-pnt1->x);
        sample.y = pnt1->y + *param1 * (nxt1->y-pnt1->y);
        LinkComputePointDeviceCoords(gnrc,&sample);
        crossing->x = sample.x; crossing->y = sample.y;
        crossing->dcx = sample.dcx;  crossing->dcy = sample.dcy;
        success = 1; 
       }
    }
  return(success);
}
void LinkClearData(LinkStatus *gnrc)

{
  LinkList *lnk,*tmp_lnk;
  LinkPointList *pnt,*tmp_pnt;

  lnk = gnrc->link.next;
  while(lnk != NULL) {
     tmp_lnk = lnk->next;
     pnt = lnk->point.next;
        while(pnt != NULL) {
        tmp_pnt = pnt->next;
        free(pnt);
        pnt = tmp_pnt;
       }
     free(lnk);
     lnk = tmp_lnk;
    }
  gnrc->link.next = NULL;
  gnrc->current_link = NULL;
  gnrc->choice[0] = LINK_NO_CHOICE;
  gnrc->num = 0;
}

void LinkReverseArrows(LinkStatus *gnrc,LinkList *lnk)

/* Routine reverses the order of points in the linked list */
/* NOTE:  this routine is rather complicated due to the way */
/* crossing information is stored.  An edge is implicitly referenced */
/* as its first vertex, and crossing data for the edge is stored on a list at */
/* that vertex.  When reversing arrows the point representing the */
/* edge changes, and so all the crossing data must be transfered, */
/* references updated, crossing param changed, and the list of crossings */
/* themselves reversed! */
{
  LinkPointList *pnt,*tmp,*nxt_pnt;
  LinkCrossingList *crssng,*this_crssng,*nxt_crssng,*prev_crssng;
  LinkCrossingList *tmp_crssng;

  if(lnk == NULL) return;

  /* reverse point list */

  /* Do first point */
  if((pnt = lnk->point.next) == NULL) return; 

  /* save crossinglist for while loop*/
  crssng = pnt->crossing.next;

  if(lnk->closed) {  /* assign crossing list of last point to pnt */
     tmp = pnt;
     while(tmp->next != NULL) tmp = tmp->next;
     pnt->crossing.next = tmp->crossing.next;

     /* fix list: change param and reverse crossing order */
     if((this_crssng = pnt->crossing.next) != NULL) {
        this_crssng->param = 1.0 - this_crssng->param;
        /* fix reference to this_crssng pnt */
        this_crssng->crossing->partner = pnt;

        if((nxt_crssng = this_crssng->next) != NULL) {
           this_crssng->next = NULL;
           prev_crssng = this_crssng;
           this_crssng = nxt_crssng;
           while(this_crssng != NULL) {
              this_crssng->param = 1.0 - this_crssng->param;
              /* fix reference to this_crssng pnt */
              this_crssng->crossing->partner = pnt;

              nxt_crssng = this_crssng->next;
              this_crssng->next = prev_crssng;
              prev_crssng = this_crssng;
              this_crssng = nxt_crssng;

             }
           pnt->crossing.next = prev_crssng;

          }
       }
    }
  else {   /* No crossing list at this point */
     pnt->crossing.next = NULL;
    }

  nxt_pnt = pnt->next;
  pnt->previous = pnt->next;
  pnt->next = NULL;

  /* Remaining points : nxt_pnt is next point after current pnt*/
  /* crssng is the previous point's crossing list */

  while(nxt_pnt != NULL) {
     pnt = nxt_pnt;
     nxt_pnt = nxt_pnt->next; 
     /* re-asssign crossing lists */
     tmp_crssng = pnt->crossing.next;
     pnt->crossing.next = crssng;

     /* fix list: change param and reverse crossing order */
     if((this_crssng = pnt->crossing.next) != NULL) {
        this_crssng->param = 1.0 - this_crssng->param;
        /* fix reference to this_crssng pnt */
        this_crssng->crossing->partner = pnt;

        if((nxt_crssng = this_crssng->next) != NULL) {
           this_crssng->next = NULL;
           prev_crssng = this_crssng;
           this_crssng = nxt_crssng;
           while(this_crssng != NULL) {
              this_crssng->param = 1.0 - this_crssng->param;
              /* fix reference to this_crssng pnt */
              this_crssng->crossing->partner = pnt;

              nxt_crssng = this_crssng->next;
              this_crssng->next = prev_crssng;
              prev_crssng = this_crssng;
              this_crssng = nxt_crssng;

             }
           pnt->crossing.next = prev_crssng;

          }
       }

     crssng = tmp_crssng;

     tmp = pnt->next;
     pnt->next = pnt->previous;
     pnt->previous = tmp;
    }
  /* Fix last point */
  pnt->previous = &(lnk->point);
  lnk->point.next = pnt;
  
}

void LinkJoinLinks(LinkStatus *gnrc, LinkList *first,LinkList *second)
{
  LinkPointList *pnt;
  LinkList *lnk;

  if(first->closed || second->closed) return;
  if(second->point.next == NULL) return;

  pnt = &(first->point);
  while(pnt->next != NULL) pnt = pnt->next;

  /* Update number of points in each link */
  first->num += second->num;

  /* Attach second to first */
  pnt->next = second->point.next;
  second->point.next->previous = pnt;

  /* remove second from list of links */
  lnk = &(gnrc->link);
  while(lnk->next != second) lnk = lnk->next; 
  lnk->next = second->next;
  free(second);

  /* compute new crossings */
  LinkComputeEdgeCrossings(gnrc,first,pnt);
}

void LinkPrintMessage(char *s)

{
  [currentLinkObj printMessage:s];
}
