4 #include "../../config.h"
9 actlist_t* actlist_new()
14 void actlist_destroy(actlist_t*a)
19 void actlist_dump(actlist_t*a, int32_t y)
21 segment_t*s = a->list;
24 if(!s) fprintf(stderr, "(empty)\n");
27 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
30 fprintf(stderr, "?%f<->%f? ", lastx, x);
34 fprintf(stderr, "[%d]", s->nr);
36 if(s) fprintf(stderr, " ");
37 else fprintf(stderr, " y=%d\n", y);
40 void actlist_verify(actlist_t*a, int32_t y)
42 segment_t*s = a->list;
43 assert(!s || !s->left);
48 /* we need to re-evaluate the x of the previous segment. if we
49 try to store it, it might end up being converted to a double,
50 which will make it non-equal to (and possibly larger than) the
51 "long double" the FPU has in its register. This only happens
52 when compiler optimizations are turned on. */
53 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
54 assert(XDIFF(s,l,y) >= 0);
58 assert(!s->left || s->left->right == s);
59 assert(!s->right || s->right->left == s);
64 static inline double single_cmp(segment_t*s, point_t p1)
66 return LINE_EQ(p1, s);
69 static inline double cmp(segment_t*s, point_t p1, point_t p2)
71 double d = LINE_EQ(p1, s);
75 /* We default to always inserting the new segment to the right of the old segment.
76 We do this so that we don't place new segments into the middle of already
77 overlapping lines which may have intersections scheduled.
79 //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);
86 static void actlist_splay_dump(actlist_t*a);
87 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
90 segment_t*t = a->list;
94 /* this check doesn't work out with cmp() because during horizontal
95 processing, both segments ending as well as segments starting will
96 be active in this scanline */
97 //double d = cmp(t, p1, p2);
98 double d = single_cmp(t, p1);
99 if(d>=0 && to_the_left) {
100 actlist_dump(a, p1.y);
101 segment_t*s = a->list;
103 fprintf(stderr, "[%d] %f/%f (%d,%d) -> (%d,%d)\n", s->nr,
104 single_cmp(s,p1), cmp(s,p1,p2),
105 s->a.x, s->a.y, s->b.x, s->b.y);
109 assert(!(d>=0 && to_the_left));
110 if(d<0) to_the_left=1;
115 static actlist_t*last = 0;
118 actlist_splay_dump(a);
123 segment_t*last=0, *s = a->root;
130 d = single_cmp(s, p1);
140 /* 80% hit, average cost per miss ~ 4 nodes */
141 int expected_depth = (int)((double)log2((double)a->size+1))+1;
143 static int misses = 0;
144 static int miss_cost = 0;
145 if(depth <= expected_depth) hits++;
147 miss_cost += depth - expected_depth;
150 fprintf(stderr, "%02.2f%% %f\n", hits / (double)(hits+misses), miss_cost / (double)misses);
154 /* this can be optimized for (is not needed in) normal mode (as opposed to horizontal postprocess mode) */
155 segment_t*out = last;
156 if(d<0 || (d==0 && LINE_EQ(p2,last)<0)) {
159 assert(cmp(a->list, p1, p2)<0);
163 while(last->right && cmp(last->right, p1, p2)>=0) {
177 printf("[%d]!=[%d]\n", SEGNR(l), SEGNR(last));
178 printf("after tree: [%d]\n", SEGNR(out));
179 actlist_splay_dump(a);
182 double d1 = single_cmp(s,p1);
183 double d2 = cmp(s,p1,p2);
184 int x1 = d1<0?-1:(d1>0?1:0);
185 int x2 = d2<0?-1:(d2>0?1:0);
186 printf("[%d](%d,%d) ", SEGNR(s), x1, x2);
197 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
199 segment_t*last=0, *s = a->list;
202 double d = cmp(s, p1, p2);
214 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
215 //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
217 // rotates segment's left node to the top
218 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
226 assert(s->leftchild);
227 segment_t*p = s->parent;
228 segment_t*n = s->leftchild;
229 segment_t*l = n->rightchild;
230 LINK(n,rightchild,s);
234 if(p->leftchild == s)
236 else if(p->rightchild == s)
243 // rotates segment's right node to the top
244 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
252 assert(s->rightchild);
253 segment_t*p = s->parent;
254 segment_t*n = s->rightchild;
255 segment_t*r = n->leftchild;
257 LINK(s,rightchild,r);
260 if(p->leftchild == s)
262 else if(p->rightchild == s)
270 static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
273 if(parent != s->parent) {
274 fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
277 if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
279 fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
282 (*ss) = (*ss)->right;
283 if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
287 static int actlist_splay_verify(actlist_t*a)
289 segment_t*c = a->list;
290 if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
294 static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down)
298 if(s->leftchild || s->rightchild) {
302 char*o3 = malloc(strlen(up)+3);
303 strcpy(o3, up);strcat(o3, "+-");
304 char*newup = malloc(strlen(up)+3);
305 strcpy(newup, up);strcat(newup, "| ");
306 char*newup2 = malloc(strlen(up)+3);
307 strcpy(newup2, up);strcat(newup2, " ");
308 actlist_splay_dump2(a, s->leftchild, o3, newup2, newup);
309 fprintf(stderr, "%s| \n", up);
314 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
316 char*o3 = malloc(strlen(down)+3);
317 strcpy(o3, down);strcat(o3, "+-");
318 char*newdown = malloc(strlen(down)+3);
319 strcpy(newdown, down);strcat(newdown, "| ");
320 char*newdown2 = malloc(strlen(down)+3);
321 strcpy(newdown2, down);strcat(newdown2, " ");
322 fprintf(stderr, "%s| \n", down);
323 actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2);
329 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
332 static void actlist_splay_dump(actlist_t*a)
334 actlist_splay_dump2(a, a->root, "", "", "");
338 static void move_to_root(actlist_t*a, segment_t*s)
341 /* this is a textbook implementation of the three splay operations
342 zig, zig-zig and zig-zag */
344 while(a->root != s) {
346 segment_t*p = s->parent;
349 if(a->root->leftchild == s) {
350 rotate_right(a, a->root);
352 rotate_left(a, a->root);
354 assert(a->root == s);
356 segment_t*pp = p->parent;
357 if(p->leftchild == s && pp->leftchild == p) {
360 rotate_right(a, s->parent);
361 } else if(p->rightchild == s && pp->rightchild == p) {
364 rotate_left(a, s->parent);
365 } else if(p->leftchild == s && pp->rightchild == p) {
368 rotate_left(a, s->parent);
369 } else if(p->rightchild == s && pp->leftchild == p) {
372 rotate_right(a, s->parent);
380 static void actlist_splay(actlist_t*a, point_t p1, point_t p2)
385 memset(&tmp, 0, sizeof(tmp));
386 segment_t*left=&tmp,*right=&tmp;
390 if(cmp(a->root,p1,p2)<0) {
391 /* we're to the left of the root */
392 if(!a->root->leftchild) {
395 if(cmp(a->root->leftchild,p1,p2)<0) {
396 /* we're also to the left of the root's left child
397 -> rotate right, so that the left child is root */
398 segment_t*s = a->root->leftchild;
399 LINK(a->root, leftchild, s->rightchild);
400 LINK(s, rightchild, a->root);
402 if(!a->root->leftchild) {
406 LINK(right, leftchild, a->root);
408 a->root = a->root->leftchild;
409 } else /* cmp(a->root,p1,p2)>=0 */ {
410 /* we're to the right of the root */
411 if(!a->root->rightchild) {
414 if(cmp(a->root->rightchild,p1,p2)>=0) {
415 /* we're also to the right of the root's right child
416 -> rotate left, so that the right child is root */
417 segment_t*s = a->root->rightchild;
418 LINK(a->root, rightchild, s->leftchild);
419 LINK(s, leftchild, a->root);
421 if(!a->root->rightchild)
424 LINK(left, rightchild, a->root);
426 a->root = a->root->rightchild;
429 LINK(left, rightchild, a->root->leftchild);
430 LINK(right, leftchild, a->root->rightchild);
431 LINK(a->root, leftchild, tmp.rightchild);
432 LINK(a->root, rightchild, tmp.leftchild);
438 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
441 //fprintf(stderr, "insert [%d] after [%d]\n", SEGNR(s), SEGNR(left));
442 //actlist_splay_dump(a);
443 //actlist_dump(a, s->a.y);
448 s->right = left->right;
459 // we insert nodes not trees
460 assert(!s->leftchild);
461 assert(!s->rightchild);
464 move_to_root(a, left);
466 LINK(s,leftchild,a->root);
467 // steal right child from (previous) root
468 LINK(s,rightchild,a->root->rightchild);
469 a->root->rightchild = 0;
471 LINK(s,rightchild,a->root);
477 assert(actlist_splay_verify(a));
483 void actlist_delete(actlist_t*a, segment_t*s)
486 assert(actlist_splay_verify(a));
488 assert(actlist_splay_verify(a));
491 s->left->right = s->right;
496 s->right->left = s->left;
498 s->left = s->right = 0;
501 assert(a->root == s);
503 if(!a->root->leftchild) {
504 a->root = a->root->rightchild;
505 } else if(!a->root->rightchild) {
506 a->root = a->root->leftchild;
511 if(((ptroff_t)s)&16) {
513 // free up root->left->right
514 segment_t*t = a->root->leftchild;
515 while(t->rightchild) {
516 segment_t*r = t->rightchild;
517 segment_t*l = r->leftchild;
518 LINK(r, leftchild, t);
519 LINK(t, rightchild, l);
522 LINK(a->root,leftchild,t);
523 assert(!a->root->leftchild->rightchild);
524 LINK(a->root->leftchild,rightchild,a->root->rightchild);
525 a->root = a->root->leftchild;
527 // free up root->right->left
528 segment_t*t = a->root->rightchild;
529 while(t->leftchild) {
530 segment_t*l = t->leftchild;
531 segment_t*r = l->rightchild;
532 LINK(l, rightchild, t);
533 LINK(t, leftchild, r);
536 LINK(a->root,rightchild,t);
537 assert(!a->root->rightchild->leftchild);
538 LINK(a->root->rightchild,leftchild,a->root->leftchild);
539 a->root = a->root->rightchild;
544 s->leftchild = s->rightchild = s->parent = 0;
546 assert(actlist_splay_verify(a));
549 int actlist_size(actlist_t*a)
554 segment_t* actlist_leftmost(actlist_t*a)
559 segment_t* actlist_rightmost(actlist_t*a)
561 /* this is only used in checks, so it doesn't matter that it's slow */
563 fprintf(stderr, "Warning: actlist_rightmost should not be used\n");
565 segment_t*s = a->list;
574 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
576 segment_t*left = actlist_find(a, p1, p2);
577 actlist_insert_after(a, left, s);
580 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
583 assert(actlist_splay_verify(a));
586 /* test that s1 is to the left of s2- our swap
587 code depends on that */
589 while(s && s!=s2) s = s->right;
593 actlist_delete(a, s1);
594 actlist_insert_after(a, s2, s1);
596 segment_t*s1l = s1->left;
597 segment_t*s1r = s1->right;
598 segment_t*s2l = s2->left;
599 segment_t*s2r = s2->right;
600 if(s1l) s1l->right = s2;
603 if(s2r) s2r->left = s1;
605 if(s2l!=s1) s1->left = s2l;
607 if(s1r!=s2) s2->right = s1r;
617 segment_t*l = s2->leftchild;
618 segment_t*r = s2->rightchild;
619 assert(s1->rightchild == s2); // because s1 < s2
620 segment_t*l1 = s1->leftchild;
621 segment_t*p = s1->parent;
625 if(p->leftchild == s1) p->leftchild=s2;
626 else {assert(p->rightchild == s1);p->rightchild=s2;}
634 } else if(s1->parent==s2) {
640 segment_t*l = s1->leftchild;
641 segment_t*r = s1->rightchild;
642 segment_t*r2 = s2->rightchild;
643 assert(s2->leftchild == s1); // because s1 < s2
644 segment_t*p = s2->parent;
648 if(p->leftchild == s2) p->leftchild=s1;
649 else {assert(p->rightchild == s2);p->rightchild=s1;}
658 segment_t*s1p = s1->parent;
659 segment_t*s1l = s1->leftchild;
660 segment_t*s1r = s1->rightchild;
661 segment_t*s2p = s2->parent;
662 segment_t*s2l = s2->leftchild;
663 segment_t*s2r = s2->rightchild;
666 s2->rightchild = s1r;
669 s1->rightchild = s2r;
672 if(s1p->leftchild == s1) s1p->leftchild=s2;
673 else {assert(s1p->rightchild == s1);s1p->rightchild=s2;}
678 if(s2p->leftchild == s2) s2p->leftchild=s1;
679 else {assert(s2p->rightchild == s2);s2p->rightchild=s1;}
684 if(s1->leftchild) s1->leftchild->parent = s1;
685 if(s2->leftchild) s2->leftchild->parent = s2;
686 if(s1->rightchild) s1->rightchild->parent = s1;
687 if(s2->rightchild) s2->rightchild->parent = s2;
689 assert(actlist_splay_verify(a));