1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "neato.h"
15#include <stdio.h>
16#include "mem.h"
17#include "info.h"
18
19
20Info_t *nodeInfo; /* Array of node info */
21static Freelist pfl;
22
23void infoinit()
24{
25 freeinit(&pfl, sizeof(PtItem));
26}
27
28/* compare:
29 * returns -1 if p < q
30 * 0 if p = q
31 * 1 if p > q
32 * if q if NULL, returns -1
33 * Ordering is by angle from -pi/2 to 3pi/4.
34 * For equal angles (which should not happen in our context)
35 * ordering is by closeness to origin.
36 */
37static int compare(Point * o, PtItem * p, PtItem * q)
38{
39 double x0;
40 double y0;
41 double x1;
42 double y1;
43 double a, b;
44
45 if (q == NULL)
46 return -1;
47 if ((p->p.x == q->p.x) && (p->p.y == q->p.y))
48 return 0;
49
50 x0 = ((double) (p->p.x)) - ((double) (o->x));
51 y0 = ((double) (p->p.y)) - ((double) (o->y));
52 x1 = ((double) (q->p.x)) - ((double) (o->x));
53 y1 = ((double) (q->p.y)) - ((double) (o->y));
54 if (x0 >= 0.0) {
55 if (x1 < 0.0)
56 return -1;
57 else if (x0 > 0.0) {
58 if (x1 > 0.0) {
59 a = y1 / x1;
60 b = y0 / x0;
61 if (b < a)
62 return -1;
63 else if (b > a)
64 return 1;
65 else if (x0 < x1)
66 return -1;
67 else
68 return 1;
69 } else { /* x1 == 0.0 */
70 if (y1 > 0.0)
71 return -1;
72 else
73 return 1;
74 }
75 } else { /* x0 == 0.0 */
76 if (x1 > 0.0) {
77 if (y0 <= 0.0)
78 return -1;
79 else
80 return 1;
81 } else { /* x1 == 0.0 */
82 if (y0 < y1) {
83 if (y1 <= 0.0)
84 return 1;
85 else
86 return -1;
87 } else {
88 if (y0 <= 0.0)
89 return -1;
90 else
91 return 1;
92 }
93 }
94 }
95 } else {
96 if (x1 >= 0.0)
97 return 1;
98 else {
99 a = y1 / x1;
100 b = y0 / x0;
101 if (b < a)
102 return -1;
103 else if (b > a)
104 return 1;
105 else if (x0 > x1)
106 return -1;
107 else
108 return 1;
109 }
110 }
111}
112
113#if 0 /* not used */
114static void printV(PtItem * vp)
115{
116 if (vp == NULL) {
117 fprintf(stderr, "<empty>\n");
118 return;
119 }
120
121 while (vp != NULL) {
122 fprintf(stderr, "(%.16f,%.16f)\n", vp->p.x, vp->p.y);
123 vp = vp->next;
124 }
125}
126
127static void error(Info_t * ip, Site * s, double x, double y)
128{
129 fprintf(stderr,
130 "Unsorted vertex list for site %d (%.16f,%.16f), pt (%f,%f)\n",
131 s->sitenbr, s->coord.x, s->coord.y, x, y);
132 printV(ip->verts);
133}
134#endif
135
136#if 0 /* not used */
137static int sorted(Point * origin, PtItem * vp)
138{
139 PtItem *next;
140
141 if (vp == NULL)
142 return 1;
143 next = vp->next;
144
145 while (next != NULL) {
146 if (compare(origin, vp, next) <= 0) {
147 vp = next;
148 next = next->next;
149 } else {
150 fprintf(stderr, "(%.16f,%.16f) > (%.16f,%.16f)\n",
151 vp->p.x, vp->p.y, next->p.x, next->p.y);
152 return 0;
153 }
154 }
155
156 return 1;
157
158}
159#endif
160
161void addVertex(Site * s, double x, double y)
162{
163 Info_t *ip;
164 PtItem *p;
165 PtItem *curr;
166 PtItem *prev;
167 Point *origin = &(s->coord);
168 PtItem tmp;
169 int cmp;
170
171 ip = nodeInfo + (s->sitenbr);
172 curr = ip->verts;
173
174 tmp.p.x = x;
175 tmp.p.y = y;
176
177 cmp = compare(origin, &tmp, curr);
178 if (cmp == 0)
179 return;
180 else if (cmp < 0) {
181 p = (PtItem *) getfree(&pfl);
182 p->p.x = x;
183 p->p.y = y;
184 p->next = curr;
185 ip->verts = p;
186 return;
187 }
188
189 prev = curr;
190 curr = curr->next;
191 while ((cmp = compare(origin, &tmp, curr)) > 0) {
192 prev = curr;
193 curr = curr->next;
194 }
195 if (cmp == 0)
196 return;
197 p = (PtItem *) getfree(&pfl);
198 p->p.x = x;
199 p->p.y = y;
200 prev->next = p;
201 p->next = curr;
202
203 /* This test should be unnecessary */
204 /* if (!sorted(origin,ip->verts)) */
205 /* error (ip,s,x,y); */
206
207}
208