static char *sccs_id= (sccs_id, "@(#)topol.cc	1.2 7/28/92");

#include	"Dictionary.h"
#include	"SortedOList.h"
#include	"ObjFloat.h"
#include	"ObjInt.h"
#include	"ByteArray.h"
#include	"IO/stream.h"
#include	<math.h>

class POINT2 {
public:
   float x, y;
};

class POLYSTRUCT {
public:
   long    npts;
   POINT2  p[1];
};

#define LDELIM          '('
#define RDELIM          ')'
#define DELIM           ','
#define MDELIM          ':'

#define POLY2ALLOC(N) \
(POLYSTRUCT *) malloc((unsigned) (sizeof(POLYSTRUCT) + \
                            (((N)-1) > 0 ? ((N)-1) : 0) \
                            * sizeof(POINT2)))

class EdgeList {
  friend class Edge;
private:
  EdgeList      *next, *prev;
  class Edge    *e;
  long          reversed;
public:
  EdgeList(Edge *e_in, long rev_in):
     e(e_in), reversed(rev_in) { prev = next = NULL; };
  ~EdgeList() {};
};

class Edge: public Object {
  class Node	*to_node, *from_node;
  POLYSTRUCT    *polyline;
  long		oid, left_code, right_code;
  long          next_used, prev_used;
  Edge		*next, *prev;
public:
  Edge(Node *to, Node *from, long the_oid, 
     long left, long right, POLYSTRUCT *polyline_in, Edge *next_in):
     to_node(to), from_node(from), oid(the_oid),
     left_code(left), right_code(right),
     polyline(polyline_in), next(next_in) {
     prev=NULL;
     next_used=prev_used=FALSE;
     if (next_in != NULL) next_in->SetPrev(this);
  };
  ~Edge();
    
  Node *GetOtherNode(Node *n) {
    if (n == from_node) {return(to_node); } else {return(from_node);};
  };

  int AddPoly(long reversed, long *used_again,
              EdgeList **first_el, EdgeList **last_el, int *code);
  void Print(long reversed);
  long GetNextUsed() {return next_used;}
  long GetPrevUsed() {return prev_used;}
  long GetOid() { return oid; }
  long GetLeft() { return left_code; }
  long GetRight() { return right_code; }
  POLYSTRUCT *GetPolyline() { return polyline; }
  Node *GetToNode() { return to_node; }
  Node *GetFromNode() { return from_node; }
  void SetNext(Edge *the_next) { next = the_next; }
  void SetPrev(Edge *the_prev) { prev = the_prev; }
  Edge *GetNext() { return next; }
  Edge *GetPrev() { return prev; }
  void MakeLoop(long forward);
};

class EdgeAngle {
public:
  Edge		*edge;
  long          begins; // Begins (or ends) edge in the node?
  double 	angle;
  EdgeAngle	*next;

  EdgeAngle(Edge *new_e, long begins_in, double new_angle):
     edge(new_e), begins(begins_in), angle(new_angle) {next = NULL;};
};


class Node: public Object {
  EdgeAngle	*first_ea, *prev_ea, *curr_ea, *next_ea, *new_ea;
  ByteArray	*coord;
  int           edge_count;
  Node          *next, *prev;
public:
  Node(ByteArray *node_coord, Node *next_node):
     coord(node_coord), next(next_node) {
     first_ea = NULL;
     edge_count = 0;
     prev=NULL;
     if (next_node != NULL) next_node->SetPrev(this);
  };
  ~Node();
  int GetEdgeCount() { return edge_count; }
  void AddEdge(Edge *new_edge, long begins, double angle);
  void RemoveEdge(Edge *curr_e);
  EdgeAngle *GetNextEdge(Edge *curr_e, long curr_begins);
  void PrintEdgeList();
  void PrintNodes();
  void SetPrev(Node *the_prev) {prev = the_prev;};
  void SetNext(Node *the_next) {next = the_next;};
  Node *GetNext() { return next; };
  Node *GetPrev() { return prev; };
};


// Some global variables

// bool		gMemStatistics= FALSE; // Already in cpath.cc

ByteArray	*FindP(long oid);
static Dictionary	*node_dict;
Node      *first_node;
Edge      *first_edge;

// The geo-ext POLYSTRUCT input function is used.
// This should be replaced by a nice Poly class or so.
POLYSTRUCT *
poly_in(char *str)
{
   float   coord;
   extern double   atof();
   extern long     atol();
   long         field;
   char    *s;
   int     ct, i;
   POLYSTRUCT   *result;

   if (str == NULL)
      return(NULL);

   for (i = 0, s = str; *s && i < 1 && *s != RDELIM ; ++s)
      if (*s == DELIM || (*s == LDELIM && !i)) {
         field = atol(s + 1);
         ++i;
      }
   if (i < 0)
           return(NULL);
   result = POLY2ALLOC(field);
   result->npts =  field;

   ct = result->npts * 2;  /* two coords for every point */
   for (i = 0; *s && i < ct && *s != RDELIM; ++s) {
      if (*s == DELIM || *s == MDELIM) {
         coord = (float) atof(s + 1);
         if (i % 2)
            (result->p[i/2]).y = coord;
         else
            (result->p[i/2]).x = coord;
         ++i;
      }
   }
   if (i % 2 || i < --ct) {
      free((char *)result);
      printf("Ill formatted POLYSTRUCT2: %s", str);
      return(NULL);
   }
   return(result);
}

long
PointEq(POINT2 p1, POINT2 p2)
{
  return( (p2.x == p1.x) && (p2.y == p1.y));
}

double
Angle(POINT2 p1, POINT2 p2)
{
  double dx, dy;

  dx = (double)(p2.x - p1.x);
  dy = (double)(p2.y - p1.y);
  return(atan2(dy,dx));
}

void ReadData()
{
  char		the_from[1000], the_to[1000], the_polyline[10000];
  long		the_oid, left_code, right_code;
  Node          *from_node, *to_node;
  Edge		*edge;
  ByteArray	*fb, *tb;
  POLYSTRUCT    *pln;
  int           i, n, line_ok;

  while (cin >> the_oid >> left_code >> right_code >> the_polyline) {
    pln = poly_in(the_polyline);
    n=pln->npts;
    line_ok = TRUE;
    if (n < 2) {
      line_ok = FALSE;
    } else {
      for (i=1;i<n;i++) if (!PointEq(pln->p[0],pln->p[i])) break;
      if (i == n) line_ok = FALSE;
    }
    if (!line_ok) {
      cerr << "Not a correct polyline (" << the_oid << "): all points equal\n";
    } else {
      sprintf(the_from,"(%f,%f)",pln->p[0].x,pln->p[0].y);
      sprintf(the_to,"(%f,%f)",pln->p[n-1].x,pln->p[n-1].y);
      fb= new ByteArray(the_from);
      tb= new ByteArray(the_to);

      if ((from_node = (Node *)node_dict->AtKey(fb)) == NULL) {
         from_node = first_node = new Node(fb, first_node);
         node_dict->AtKeyPut(fb, from_node);
      }
      if ((to_node = (Node *)node_dict->AtKey(tb)) == NULL) {
         to_node = first_node = new Node(tb, first_node);
         node_dict->AtKeyPut(tb, to_node);
      }

      edge = first_edge = new Edge(to_node, from_node, the_oid,
			    left_code, right_code, pln, first_edge);

      for (i=1;i<n;i++) if (!PointEq(pln->p[0],pln->p[i])) break;
      if (i < n) from_node->AddEdge(edge, TRUE, Angle(pln->p[0],pln->p[i]));
      for (i=n-2;i>0;i--) if (!PointEq(pln->p[n-1],pln->p[i])) break;
      if (i >= 0 ) to_node->AddEdge(edge, FALSE, Angle(pln->p[n-1],pln->p[i]));
    }
  }
}


Edge::~Edge()
{ 
  if (this == first_edge) first_edge = next;
  if (prev != NULL) prev->SetNext(this->next);
  if (next != NULL) next->SetPrev(this->prev);
  cerr << "Edge removed (oid=" << oid << ")\n";
};
    
int
Edge::AddPoly(long reversed, long *used_again, 
              EdgeList **first_el, EdgeList **last_el, int *code)
{
  EdgeList *new_el;

  if ((reversed && prev_used) || (!reversed && next_used)) {
    cerr << "Problem with polyline " << oid NL;
    *used_again = TRUE;
    return (0);
  }

  new_el = new EdgeList(this, reversed);
  if (*first_el == NULL) {
    *first_el = new_el;
  } else {
    (*last_el)->next = new_el;
    new_el->prev = *last_el;
  }
  *last_el = new_el;

  if (reversed) {
     prev_used = TRUE;
     *code = left_code;
  } else {
     next_used = TRUE;
     *code = right_code;
  };
  return(polyline->npts -1);
};

void
Edge::Print(long reversed)
{
  int i, n;

  n=polyline->npts;
  if (! reversed) {
        for (i=0; i<(n-1); i++) {
           cout << polyline->p[i].x << "," << polyline->p[i].y;
	   if (i != (n-2)) cout << ",";
	};
  } else {
        for (i=n-1; i>0; i--) {
           cout << polyline->p[i].x << "," << polyline->p[i].y;
	   if (i != 1) cout << ",";
	};
  };
};

void
Edge::MakeLoop(long forward)
{
  int len, code, code_e;
  long loop_finished, used_again, begins;
  Node *loop_n;
  Edge *loop_e;
  EdgeAngle *loop_ea;
  EdgeList  *first_el, *curr_el, *last_el;  // for storing loop.

  // Create list of edges that form a polygon.
  loop_e = this;
  first_el = last_el = NULL;
  if (forward) { loop_n = to_node; } else { loop_n = from_node; };
  begins = !forward;
  len = 0;
  code = 0;
  used_again = FALSE;
  loop_finished = FALSE;
  while(!((used_again)||(loop_finished))) {
     len += loop_e->AddPoly(begins, &used_again, &first_el, &last_el, &code_e);
     if (code == 0) code=code_e;
     loop_ea = loop_n->GetNextEdge(loop_e, begins);
     loop_e = loop_ea->edge;
     if (loop_ea->begins) {
        loop_n = loop_e->GetToNode();
	begins = FALSE;
     } else { 
        loop_n = loop_e->GetFromNode();
	begins = TRUE;
     };
     if ((loop_e == this)&&(begins != forward)) loop_finished=TRUE;;
  };

  if (!used_again) {
     if (len > 500) {
        cerr << "Polygon has too many points (" << len << ") for Postgres\n";
     } else { // Print polygon
        cout << code << "\t";
        cout << "(" << len << ":";
        while (first_el != NULL) {
           curr_el = first_el;
           loop_e = curr_el->e;
           loop_e->Print(curr_el->reversed);
           if (curr_el != last_el) cout << ", ";
           first_el = curr_el->next;
           delete curr_el;
        }
        cout << ")\n";
     }
  } else { // Error in loop formation
     cerr << "Current edge list: ";
     while (first_el != NULL) {
        curr_el = first_el;
        first_el = curr_el->next;
        loop_e = curr_el->e;
        cerr << loop_e->GetOid() << ", ";
        delete curr_el;
     };
     cerr << "...\n";
  };
};


Node::~Node()
{ 
  Node *other;

  if (edge_count > 1)
        cerr << "Hmm... is this ok? (destruct of node and edge_count > 1)\n";
     
  if (this==first_node) first_node=next;
  cerr << "Node removed\n";
  if (edge_count == 1) {
        other = (first_ea->edge)->GetOtherNode(this);
        other->RemoveEdge(first_ea->edge);
	delete first_ea->edge;
  } else {
	cerr << "Edge was already deleted\n";
  }
  if (prev != NULL) prev->SetNext(this->next);
  if (next != NULL) next->SetPrev(this->prev);
};
    
void
Node::AddEdge(Edge *new_edge, long begins, double angle)
{ 
  edge_count++;
  new_ea = new EdgeAngle(new_edge, begins, angle);
  if (first_ea == NULL) 
	first_ea = new_ea;
  else { // put in right place;
	if (angle < first_ea->angle) {
	   new_ea->next = first_ea;
	   first_ea = new_ea;
	} else {
	   curr_ea = first_ea;
	   next_ea = curr_ea->next;
	   while ((next_ea!= NULL) && (next_ea->angle < angle)) {
	      curr_ea = next_ea;
	      next_ea = curr_ea->next;
	   }
	   new_ea->next = next_ea;
	   curr_ea->next = new_ea;
        }
  }
};

void
Node::RemoveEdge(Edge *curr_e)
{
  curr_ea = first_ea;
  while ((curr_ea != NULL) && (curr_ea->edge != curr_e)) {
    prev_ea = curr_ea;
    curr_ea = curr_ea->next; 
  }
  if (curr_ea == NULL) // Not found!
    cerr << "Edge not in list\n";
  else { // Edge found
    if (curr_ea == first_ea)
      first_ea = curr_ea->next;
    else {
      prev_ea->next = curr_ea->next;
    }
    edge_count--;
  }
};

EdgeAngle *
Node::GetNextEdge(Edge *curr_e, long curr_begins)
{
  EdgeAngle *result;

  curr_ea = first_ea;
  while ((curr_ea != NULL) &&
    !((curr_ea->edge == curr_e) && (curr_ea->begins == curr_begins)))
    curr_ea = curr_ea->next; 
  if (curr_ea == NULL) {
    result = NULL; // Not found!
  } else {
    if (curr_ea->next != NULL) {
      result=curr_ea->next;
    } else {
      result=first_ea;
    };
  };
  return(result);
};


void
Node::PrintEdgeList()
{
  curr_ea = first_ea;
  while (curr_ea != NULL) {
    cerr << curr_ea->edge << " begins=" << curr_ea->begins;
    cerr << " Angle=" << curr_ea->angle;
    curr_ea = curr_ea->next;
  }
};

void
Node::PrintNodes()
{
  cerr << this << "node coord" << coord << " edge_count="<<edge_count;
  cerr.flush();
  this->PrintEdgeList();
  if (next != NULL) next->PrintNodes();
};


int topol_main(int argc, char *argv[])
{
  Node *curr_node, *next_node;
  Edge *curr_edge, *next_edge;
  long removed;

  if (argc != 1) {
    cerr << "Usage: " << argv[0] NL;
    exit(1);
  }

cerr << "\nReading Data...\n"; cerr.flush();
  node_dict= new Dictionary;
  first_node=NULL;
  first_edge=NULL;
  ReadData();

cerr << "\nRemoving dangling edges...\n"; cerr.flush();
  removed = TRUE;
  while (removed) {
cerr << "\nTHE BIG FILTER LOOP\n"; cerr.flush();
     removed = FALSE;
     curr_node = first_node;
     while (curr_node != NULL) {
        next_node=curr_node->GetNext();
        if (curr_node->GetEdgeCount() < 2) {
           delete curr_node;
           removed=TRUE;
        }
        curr_node=next_node;
     }
  }

// first_node->PrintNodes();
cerr << "\nCreating polygons...\n"; cerr.flush();
  curr_edge = first_edge;
  while (curr_edge != NULL) {
     if (!curr_edge->GetNextUsed()) curr_edge->MakeLoop(TRUE);
     if (!curr_edge->GetPrevUsed()) curr_edge->MakeLoop(FALSE);
     curr_edge=curr_edge->GetNext();
  }

cerr << "\nChecking the use of all Edges...\n"; cerr.flush();
  curr_edge = first_edge;
  while (curr_edge != NULL) {
     if (!curr_edge->GetNextUsed())
	cerr << "Next side of edge " << curr_edge->GetOid() << " not used\n";
     if (!curr_edge->GetPrevUsed()) 
	cerr << "Prev side of edge " << curr_edge->GetOid() << " not used\n";
     curr_edge=curr_edge->GetNext();
  }

  exit(0);
}