5 actlist_t* actlist_new()
10 void actlist_destroy(actlist_t*a)
15 void actlist_dump(actlist_t*a, int32_t y)
17 segment_t*s = a->list;
22 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
25 fprintf(stderr, "?%f<->%f? ", lastx, x);
29 fprintf(stderr, "[%d]", s->nr);
31 if(s) fprintf(stderr, " ");
32 else fprintf(stderr, "\n");
35 void actlist_verify(actlist_t*a, int32_t y)
37 segment_t*s = a->list;
38 assert(!s || !s->left);
43 /* we need to re-evaluate the x of the previous segment. if we
44 try to store it, it might end up being converted to a double,
45 which will make it non-equal to (and possibly larger than) the
46 "long double" the FPU has in it's register. This only happens
47 when compiler optimizations are turned on. */
48 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
49 assert(XDIFF(s,l,y) >= 0);
53 assert(!s->left || s->left->right == s);
54 assert(!s->right || s->right->left == s);
59 static inline double cmp(segment_t*s, point_t p1, point_t p2)
61 double d = LINE_EQ(p1, s);
65 /* We default to always inserting the new segment to the right of the old segment.
66 We do this so that we don't place new segments into the middle of already
67 overlapping lines which may have intersections scheduled.
69 //fprintf(stderr, "Notice: actlist_find: both points (%d,%d) and (%d,%d) exactly on segment [%d]\n", p1.x, p1.y, p2.x, p2.y, s->nr);
75 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
77 /* this runs in O(n) right now, and should be optimized using a splay
78 tree to run in ammortized O(log(n))
79 (update: currently only 2.5% of the algorithm's running time is spent here,
80 so maybe we don't need to bother)
82 segment_t*last=0, *s = a->list;
85 double d = cmp(s, p1, p2);
96 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);};printf("%08x->%s now %08x\n", node, __STRING(side), child);
98 // rotates segment's left node to the top
99 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
107 assert(s->leftchild);
108 segment_t*p = s->parent;
109 segment_t*n = s->leftchild;
110 segment_t*l = s->rightchild;
111 LINK(n,rightchild,s);
115 if(p->leftchild == s)
117 else if(p->rightchild == s)
124 // rotates segment's right node to the top
125 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
133 assert(s->rightchild);
134 segment_t*p = s->parent;
135 segment_t*n = s->rightchild;
136 segment_t*r = n->leftchild;
138 LINK(s,rightchild,r);
141 if(p->leftchild == s)
143 else if(p->rightchild == s)
150 static void move_to_root(actlist_t*a, segment_t*s)
152 /* this is a textbook implementation of the three splay operations
153 zig, zig-zig and zig-zag */
154 while(a->root != s) {
156 segment_t*p = s->parent;
159 if(a->root->leftchild == s) {
160 rotate_right(a, a->root);
162 rotate_left(a, a->root);
164 assert(a->root == s);
166 segment_t*pp = p->parent;
167 if(p->leftchild == s && p->parent->leftchild == p->parent) {
171 } else if(p->rightchild == s && p->parent->rightchild == p->parent) {
175 } else if(p->leftchild == s && p->parent->rightchild == p->parent) {
179 } else if(p->rightchild == s && p->parent->leftchild == p->parent) {
188 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
193 memset(&tmp, 0, sizeof(tmp));
194 segment_t*left=&tmp,*right=&tmp;
197 if(cmp(a->root,p1,p2)<0) {
198 /* we're to the left of the root */
199 if(!a->root->leftchild)
201 if(cmp(a->root->leftchild,p1,p2)<0) {
202 /* we're also to the left of the root's left child
203 -> rotate right, so that the left child is root */
204 segment_t*s = a->root->leftchild;
205 LINK(a->root, leftchild, s->rightchild);
206 LINK(s, rightchild, a->root);
208 if(!a->root->leftchild)
211 LINK(right, leftchild, a->root);
213 a->root = a->root->leftchild;
214 } else /* cmp(a->root,p1,p2)>=0 */ {
215 /* we're to the right of the root */
216 if(!a->root->rightchild)
218 if(cmp(a->root->rightchild,p1,p2)>=0) {
219 /* we're also to the right of the root's right child
220 -> rotate left, so that the right child is root */
221 segment_t*s = a->root->rightchild;
222 LINK(a->root, rightchild, s->leftchild);
223 LINK(s, leftchild, a->root);
225 if(!a->root->rightchild)
228 LINK(left, rightchild, a->root);
230 a->root = a->root->rightchild;
233 LINK(left, rightchild, a->root->leftchild);
234 LINK(right, leftchild, a->root->rightchild);
235 LINK(a->root, leftchild, tmp.rightchild);
236 LINK(a->root, rightchild, tmp.leftchild);
241 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
245 s->right = left->right;
256 // we insert nodes not trees
257 assert(!s->leftchild);
258 assert(!s->rightchild);
261 //if(actlist_splay(a, s->a, s->b) < 0) {
262 if(cmp(a->root, s->a, s->b) < 0) {
263 printf("new node %08x, link root (%08x) to the right\n", s, a->root);
264 LINK(s,rightchild,a->root);
265 // steal left child from (previous) root
266 LINK(s,leftchild,a->root->leftchild);
267 a->root->leftchild = 0;
269 printf("new node %08x, link root (%08x) to the left\n", s, a->root);
270 LINK(s,leftchild,a->root);
271 // steal right child from (previous) root
272 LINK(s,rightchild,a->root->rightchild);
273 a->root->rightchild = 0;
283 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
285 segment_t*left = actlist_find(a, p1, p2);
286 actlist_insert_after(a, left, s);
289 void actlist_delete(actlist_t*a, segment_t*s)
292 s->left->right = s->right;
297 s->right->left = s->left;
299 s->left = s->right = 0;
302 printf("delete %08x\n", s);
304 assert(a->root == s);
306 if(!a->root->leftchild) {
307 printf("shift %08x->rightchild (%08x) to root\n", a->root, a->root->rightchild);
308 a->root = a->root->rightchild;
309 } else if(!a->root->rightchild) {
310 printf("shift %08x->leftchild (%08x) to root\n", a->root, a->root->leftchild);
311 a->root = a->root->leftchild;
313 printf("freeing up %08x->left->right\n", a->root);
314 // free up root->left->right
315 segment_t*t = a->root->leftchild;
316 while(t->rightchild) {
317 segment_t*r = t->rightchild;
318 segment_t*l = r->leftchild;
319 LINK(r, leftchild, t);
320 LINK(t, rightchild, l);
323 LINK(a->root,leftchild,t);
324 assert(!a->root->leftchild->rightchild);
325 LINK(a->root->leftchild,rightchild,a->root->right);
326 a->root = a->root->leftchild;
330 s->leftchild = s->rightchild = s->parent = 0;
333 int actlist_size(actlist_t*a)
338 segment_t* actlist_leftmost(actlist_t*a)
343 segment_t* actlist_rightmost(actlist_t*a)
345 /* this is only used in checks, so it doesn't matter that it's slow */
346 segment_t*s = a->list;
355 segment_t* actlist_left(actlist_t*a, segment_t*s)
360 segment_t* actlist_right(actlist_t*a, segment_t*s)
362 if(s) return s->right;
366 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
368 // for splaying this needs to be rewritten (can't use insert_after)
369 actlist_delete(a, s1);
370 actlist_insert_after(a, s2, s1);