#include <stdio.h>
#define PTS_NODE struct pts_node
#define SEG_NODE struct seg_node
#define BND_NODE struct bnd_node
#define GEO_NODE struct geo_node

#define FOR_ALL_BOUNDARIES(g)    for((g)=geo_list; (g) != NULL; (g) = (g)->next)
#define FOR_ALL_POINTS(g)        for((g) = pts_list; (g) != NULL; (g) = (g)->next)
#define FOR_ALL_SEGMENTS(geo, s) for((s) = (geo)->bnd_list; (s) != NULL; (s) = (s)->next)


PTS_NODE
{
  PTS_NODE *next;
  PTS_NODE *prev;
  int n;
  int x;
  int y;
  float physicalX;
  float physicalY;
};
SEG_NODE
{
  SEG_NODE *next;
  SEG_NODE *prev;
  int n;
  PTS_NODE *pts1;
  PTS_NODE *pts2;

};
BND_NODE
{
  BND_NODE *next;
  BND_NODE *prev;
  SEG_NODE *seg;
};

GEO_NODE
{
  GEO_NODE *next;
  GEO_NODE *prev;
  BND_NODE *bnd_list;
};

PTS_NODE *pts_list = NULL;
PTS_NODE *pts;

SEG_NODE *seg_list = NULL;
SEG_NODE *seg;

BND_NODE *bnd_list = NULL;
BND_NODE *bnd;

GEO_NODE *geo_list = NULL;
GEO_NODE *geo;

/*
 * +---------------------------------------------------------+
 * | Private routines needed to manipulate the geometry data |
 * +---------------------------------------------------------+
 */
void      rm_pnt(float x, float y);
PTS_NODE *last_item();
SEG_NODE *last_seg();
PTS_NODE *find_item(float x, float y);
PTS_NODE *left_insert_item(float x, float y);
void      rigth_insert_item(float x, float y);
void      rm_item(PTS_NODE *this);
void      rm_seg(SEG_NODE *this);
PTS_NODE *find_pnt(float x, float y);
void      rm_pnt(float x, float y);
BND_NODE *add_bnd(SEG_NODE *seg, GEO_NODE *geo);
/*
 * +--------------------------------------------------------+
 * | Public routines needed to manipulate the geometry data |
 * +--------------------------------------------------------+
 */
PTS_NODE *add_pnt(float x, float y);
void      mv_pnt(float x, float y, float xnew, float ynew);
void      add_seg(PTS_NODE *pts1, PTS_NODE *pts2, GEO_NODE *bnd);
GEO_NODE *new_bnd();
void      rm_bnd(GEO_NODE *this);
int       number_of_boundaries();
int       number_of_points();



BND_NODE *add_bnd(SEG_NODE *seg, GEO_NODE *geo)
{
  bnd = (BND_NODE *)malloc(sizeof(BND_NODE));
  if(bnd == NULL)
    printf("out of memory\n");
  bnd->seg = seg;
  bnd->next = geo->bnd_list;
  bnd->prev = NULL;
  if(geo->bnd_list != NULL)
    geo->bnd_list->prev = bnd;
  geo->bnd_list = bnd;
  return bnd_list;
}

PTS_NODE *last_item()
{
  PTS_NODE *p;
  if(pts_list == NULL)
    printf("empty pts\n");
  else{
    FOR_ALL_POINTS( p )
      ;
  }
  return p;
}



SEG_NODE *last_seg()
{
  SEG_NODE *p;
  if(seg_list == NULL)
    printf("empty seg\n");
  else{
    for( p = seg_list; p->next != NULL; p = p->next)
      ;
  }
  return p;
}



PTS_NODE *find_item(float x, float y)
{
  PTS_NODE *p;
  if(pts_list == NULL)
    printf("empty ptst\n");
  else{
    FOR_ALL_POINTS( p ){
      if(p->physicalX == x && p->physicalY == y){
	return p;
      }
    }
    return NULL;
  }
  return NULL;
}



PTS_NODE *left_insert_item(float x, float y)
{
  pts = (PTS_NODE *)malloc(sizeof(PTS_NODE));
  if(pts == NULL)
    printf("out of memory\n");
  pts->physicalX = x;
  pts->physicalY = y;
  pts->n = 0;
  pts->next = pts_list;
  pts->prev = NULL;
  if(pts_list != NULL)
    pts_list->prev = pts;
  pts_list = pts;
  return pts;
}











void rigth_insert_item(float x, float y)
{
  PTS_NODE *p;

  pts = (PTS_NODE *)malloc(sizeof(PTS_NODE));
  if(pts == NULL)
    printf("out of memory\n");
  pts->physicalX = x;
  pts->physicalY = y;
  pts->n = 1;

  p = last_item();
  pts->prev = p;
  pts->next = NULL;

  p->next = pts;

}



void rm_item(PTS_NODE *this)
{
  PTS_NODE *left;
  PTS_NODE *right;

  left = this->prev;
  right= this->next;
  free(this);
  if(left != NULL)
    left->next = right;
  else
    pts_list = right;
  if(right != NULL)
    right->prev = left;
}



void rm_seg(SEG_NODE *this)
{
  SEG_NODE *left;
  SEG_NODE *right;

  left = this->prev;
  right= this->next;
  if(this->n > 1)
    this->n--;
  else{
    free(this);
    if(left != NULL)
      left->next = right;
    else
      seg_list = right;
    if(right != NULL)
      right->prev = left;
  }
}



void dump_items()
{
  PTS_NODE *p;
  if(pts_list == NULL)
    printf("empty list\n");
  else{
    FOR_ALL_POINTS( p )
      printf("%f -> ", p->x);
  }
  printf("\n");
}



void dump_all()
{
  BND_NODE *p;
  SEG_NODE *s;
  GEO_NODE *g;
  PTS_NODE *p1, *p2;

  printf("There are currently %i boundaries\n", number_of_boundaries());
  printf("There are currently %i points\n", number_of_points());
  printf("Dumping all known boundaries\n");
  FOR_ALL_BOUNDARIES( g ){
    printf("bnd:\n");
    FOR_ALL_SEGMENTS(g, p){
      s = p->seg;
      p1 = s->pts1;
      p2 = s->pts2;
      printf("(%f %f) ->(%f %f) \n", p1->physicalX, p1->physicalY,
  	                             p2->physicalX, p2->physicalY);
    }
  }
  printf("\n");
}


PTS_NODE *find_pnt(float x, float y)
{
  PTS_NODE *p;
  if(pts_list == NULL)
    printf("empty pnt\n");
  else{
    FOR_ALL_POINTS( p ){
      if(p->physicalX == x && p->physicalY == y){
	return p;
      }
    }
    return NULL;
  }
  return NULL;
}






void rm_pnt(float x, float y)
{
  PTS_NODE *p;

  p = find_item(x, y);
  if(p != NULL){
    if(p->n > 1)
      p->n--;
    else
      rm_item(p);
  }
}





/*
 *
 * +-----------------+
 * | Public routines |
 * +-----------------+
 *
 */
/*
 *
 * +------------------------------+
 * | Adds a point to the database |
 * +------------------------------+
 
    Arguments:   x, y - The coordinates of the point
    Returns:     A pointer to the new point
 
    Description: 

 *
 */
PTS_NODE *add_pnt(float x, float y)
{
  PTS_NODE *p;

  p = find_item(x, y);
  if(p == NULL)
    p = left_insert_item(x, y);

  return p;
}
/*
 * +----------------------------------------------------------+
 * | Moves a specific point in the database to a new location |
 * +----------------------------------------------------------+
 
    Arguments:   x, y       - The old location
                 xnew, ynew - The new location
    Returns:     
 
    Description: Finds the point at (x,y) and changes the
                 coordinates to (xnew,ynew)

*/
void mv_pnt(float x, float y, float xnew, float ynew)
{
  PTS_NODE *p;

  p = find_item(x, y);
  if(p != NULL){
    p->physicalX = xnew;
    p->physicalY = ynew;
  }
}

/*
 * +---------------------------------------------+
 * | Removes a complete boundary in the database |
 * +---------------------------------------------+
 
    Arguments:   this - A pointer to the boundary that is removed
    Returns:     
 
    Description: 


 */
void rm_bnd(GEO_NODE *this)
{
  GEO_NODE *left;
  GEO_NODE *right;
  BND_NODE *p;
  SEG_NODE *s;
  PTS_NODE *p1, *p2;

  left = this->prev;
  right= this->next;

  FOR_ALL_SEGMENTS(this, p){
    s = p->seg;
    p1 = s->pts1;
    p2 = s->pts2;
    rm_seg(s);
    rm_pnt(p1->physicalX, p1->physicalY);
    rm_pnt(p2->physicalX, p2->physicalY);
  }
  free(this);
  if(left != NULL)
    left->next = right;
  else
    geo_list = right;
  if(right != NULL)
    right->prev = left;
}
/*
 * +--------------------------------+
 * | Adds a segment to the database |
 * +--------------------------------+
 
    Arguments:   pts1, pts2 - The two points making up this segment
                 bnd        - The boundary that the segment is added to
    Returns:     A pointer to a segment
 
    Description: 

 *
 */
void add_seg(PTS_NODE *pts1, PTS_NODE *pts2, GEO_NODE *bnd)
{
  SEG_NODE *seg;

  seg = (SEG_NODE *)malloc(sizeof(SEG_NODE));
  if(seg == NULL)
    printf("out of memory\n");
  seg->n = 1;
  seg->pts1 = pts1;
  seg->pts2 = pts2;
  pts1->n++;
  pts2->n++;
  seg->next = seg_list;
  seg->prev = NULL;
  if(seg_list != NULL)
    seg_list->prev = seg;
  seg_list = seg;
  add_bnd(seg, bnd);

}

/*
 * +-------------------------------------+
 * | Adds a new boundary to the database |
 * +-------------------------------------+
 
    Arguments:
    Returns:     A pointer to the new boundary
 
    Description: 

 */
GEO_NODE *new_bnd()
{

  geo = (GEO_NODE *)malloc(sizeof(GEO_NODE));
  if(geo == NULL)
    printf("out of memory\n");
  geo->bnd_list = bnd_list;
  geo->next = geo_list;
  geo->prev = NULL;
  if(geo_list != NULL)
    geo_list->prev = geo;
  geo_list = geo;

  return geo_list;
}
/*
 * +-------------------------------------------------+
 * | Counts the number of boundaries in the database |
 * +-------------------------------------------------+
 
    Arguments:
    Returns:     The number of boundaries
 
    Description: 

 */
int number_of_boundaries()
{
  int i;
  GEO_NODE *g;
  i = 0;
  FOR_ALL_BOUNDARIES( g )
    i++;
  return i;

}
/*
 * +---------------------------------------------+
 * | Counts the number of points in the database |
 * +---------------------------------------------+
 
    Arguments:
    Returns:     The number of points
 
    Description: 

 */
int number_of_points()
{
  int i;
  PTS_NODE *p;
  i = 0;
  FOR_ALL_POINTS( p )
    i++;
  return i;
}


/*
 *
 * +--------------------+
 * | Simple test driver |
 * +--------------------+
 *
 */

main()
{
  PTS_NODE *p1, *p2;
  SEG_NODE *s1;
  GEO_NODE *g;

  g = new_bnd();
  p1 = add_pnt(1.,2.);
  p2 = add_pnt(2.,2.);
  add_seg(p1, p2, g);

  p1 = add_pnt(2.,2.);
  p2 = add_pnt(2.,3.);
  add_seg(p1, p2, g);

  p1 = add_pnt(2.,2.);
  p2 = add_pnt(2.,3.);
  add_seg(p1, p2, g);

  g = new_bnd();
  p1 = add_pnt(10.,2.);
  p2 = add_pnt(20.,2.);
  add_seg(p1, p2, g);

  p1 = add_pnt(20.,2.);
  p2 = add_pnt(20.,3.);
  add_seg(p1, p2, g);

  p1 = add_pnt(20.,2.);
  p2 = add_pnt(20.,3.);
  add_seg(p1, p2, g);

  dump_all();

  rm_bnd(g);
  dump_all();
/*
  add_pnt(3.,2.);
  add_pnt(4.,2.);
  dump_items();
  rm_pnt(4.,2.);
  dump_items();
  rm_pnt(3.,2.);
  dump_items();
*/
}