7 actlist_t* actlist_new()
12 void actlist_destroy(actlist_t*a)
17 void actlist_dump(actlist_t*a, int32_t y)
19 segment_t*s = a->list;
22 if(!s) fprintf(stderr, "(empty)\n");
25 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
28 fprintf(stderr, "?%f<->%f? ", lastx, x);
32 fprintf(stderr, "[%d]", s->nr);
34 if(s) fprintf(stderr, " ");
35 else fprintf(stderr, " y=%d\n", y);
38 void actlist_verify(actlist_t*a, int32_t y)
40 segment_t*s = a->list;
41 assert(!s || !s->left);
46 /* we need to re-evaluate the x of the previous segment. if we
47 try to store it, it might end up being converted to a double,
48 which will make it non-equal to (and possibly larger than) the
49 "long double" the FPU has in its register. This only happens
50 when compiler optimizations are turned on. */
51 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
52 assert(XDIFF(s,l,y) >= 0);
56 assert(!s->left || s->left->right == s);
57 assert(!s->right || s->right->left == s);
62 static inline double single_cmp(segment_t*s, point_t p1)
64 return LINE_EQ(p1, s);
67 static inline double cmp(segment_t*s, point_t p1, point_t p2)
69 double d = LINE_EQ(p1, s);
73 /* We default to always inserting the new segment to the right of the old segment.
74 We do this so that we don't place new segments into the middle of already
75 overlapping lines which may have intersections scheduled.
77 //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);
84 static void actlist_splay_dump(actlist_t*a);
85 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
88 segment_t*t = a->list;
92 /* this check doesn't work out with cmp() because during horizontal
93 processing, both segments ending as well as segments starting will
94 be active in this scanline */
95 //double d = cmp(t, p1, p2);
96 double d = single_cmp(t, p1);
97 if(d>=0 && to_the_left) {
98 actlist_dump(a, p1.y);
99 segment_t*s = a->list;
101 fprintf(stderr, "[%d] %f/%f (%d,%d) -> (%d,%d)\n", s->nr,
102 single_cmp(s,p1), cmp(s,p1,p2),
103 s->a.x, s->a.y, s->b.x, s->b.y);
107 assert(!(d>=0 && to_the_left));
108 if(d<0) to_the_left=1;
113 static actlist_t*last = 0;
116 actlist_splay_dump(a);
121 segment_t*last=0, *s = a->root;
128 d = single_cmp(s, p1);
138 /* 80% hit, average cost per miss ~ 4 nodes */
139 int expected_depth = (int)((double)log2((double)a->size+1))+1;
141 static int misses = 0;
142 static int miss_cost = 0;
143 if(depth <= expected_depth) hits++;
145 miss_cost += depth - expected_depth;
148 fprintf(stderr, "%02.2f%% %f\n", hits / (double)(hits+misses), miss_cost / (double)misses);
152 /* this can be optimized for (is not needed in) normal mode (as opposed to horizontal postprocess mode) */
153 segment_t*out = last;
154 if(d<0 || (d==0 && LINE_EQ(p2,last)<0)) {
157 assert(cmp(a->list, p1, p2)<0);
161 while(last->right && cmp(last->right, p1, p2)>=0) {
175 printf("[%d]!=[%d]\n", SEGNR(l), SEGNR(last));
176 printf("after tree: [%d]\n", SEGNR(out));
177 actlist_splay_dump(a);
180 double d1 = single_cmp(s,p1);
181 double d2 = cmp(s,p1,p2);
182 int x1 = d1<0?-1:(d1>0?1:0);
183 int x2 = d2<0?-1:(d2>0?1:0);
184 printf("[%d](%d,%d) ", SEGNR(s), x1, x2);
195 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
197 segment_t*last=0, *s = a->list;
200 double d = cmp(s, p1, p2);
212 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
213 //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
215 // rotates segment's left node to the top
216 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
224 assert(s->leftchild);
225 segment_t*p = s->parent;
226 segment_t*n = s->leftchild;
227 segment_t*l = n->rightchild;
228 LINK(n,rightchild,s);
232 if(p->leftchild == s)
234 else if(p->rightchild == s)
241 // rotates segment's right node to the top
242 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
250 assert(s->rightchild);
251 segment_t*p = s->parent;
252 segment_t*n = s->rightchild;
253 segment_t*r = n->leftchild;
255 LINK(s,rightchild,r);
258 if(p->leftchild == s)
260 else if(p->rightchild == s)
268 static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
271 if(parent != s->parent) {
272 fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
275 if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
277 fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
280 (*ss) = (*ss)->right;
281 if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
285 static int actlist_splay_verify(actlist_t*a)
287 segment_t*c = a->list;
288 if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
292 static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down)
296 if(s->leftchild || s->rightchild) {
300 char*o3 = malloc(strlen(up)+3);
301 strcpy(o3, up);strcat(o3, "+-");
302 char*newup = malloc(strlen(up)+3);
303 strcpy(newup, up);strcat(newup, "| ");
304 char*newup2 = malloc(strlen(up)+3);
305 strcpy(newup2, up);strcat(newup2, " ");
306 actlist_splay_dump2(a, s->leftchild, o3, newup2, newup);
307 fprintf(stderr, "%s| \n", up);
312 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
314 char*o3 = malloc(strlen(down)+3);
315 strcpy(o3, down);strcat(o3, "+-");
316 char*newdown = malloc(strlen(down)+3);
317 strcpy(newdown, down);strcat(newdown, "| ");
318 char*newdown2 = malloc(strlen(down)+3);
319 strcpy(newdown2, down);strcat(newdown2, " ");
320 fprintf(stderr, "%s| \n", down);
321 actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2);
327 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
330 static void actlist_splay_dump(actlist_t*a)
332 actlist_splay_dump2(a, a->root, "", "", "");
336 static void move_to_root(actlist_t*a, segment_t*s)
339 /* this is a textbook implementation of the three splay operations
340 zig, zig-zig and zig-zag */
342 while(a->root != s) {
344 segment_t*p = s->parent;
347 if(a->root->leftchild == s) {
348 rotate_right(a, a->root);
350 rotate_left(a, a->root);
352 assert(a->root == s);
354 segment_t*pp = p->parent;
355 if(p->leftchild == s && pp->leftchild == p) {
358 rotate_right(a, s->parent);
359 } else if(p->rightchild == s && pp->rightchild == p) {
362 rotate_left(a, s->parent);
363 } else if(p->leftchild == s && pp->rightchild == p) {
366 rotate_left(a, s->parent);
367 } else if(p->rightchild == s && pp->leftchild == p) {
370 rotate_right(a, s->parent);
378 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
383 memset(&tmp, 0, sizeof(tmp));
384 segment_t*left=&tmp,*right=&tmp;
388 if(cmp(a->root,p1,p2)<0) {
389 /* we're to the left of the root */
390 if(!a->root->leftchild) {
393 if(cmp(a->root->leftchild,p1,p2)<0) {
394 /* we're also to the left of the root's left child
395 -> rotate right, so that the left child is root */
396 segment_t*s = a->root->leftchild;
397 LINK(a->root, leftchild, s->rightchild);
398 LINK(s, rightchild, a->root);
400 if(!a->root->leftchild) {
404 LINK(right, leftchild, a->root);
406 a->root = a->root->leftchild;
407 } else /* cmp(a->root,p1,p2)>=0 */ {
408 /* we're to the right of the root */
409 if(!a->root->rightchild) {
412 if(cmp(a->root->rightchild,p1,p2)>=0) {
413 /* we're also to the right of the root's right child
414 -> rotate left, so that the right child is root */
415 segment_t*s = a->root->rightchild;
416 LINK(a->root, rightchild, s->leftchild);
417 LINK(s, leftchild, a->root);
419 if(!a->root->rightchild)
422 LINK(left, rightchild, a->root);
424 a->root = a->root->rightchild;
427 LINK(left, rightchild, a->root->leftchild);
428 LINK(right, leftchild, a->root->rightchild);
429 LINK(a->root, leftchild, tmp.rightchild);
430 LINK(a->root, rightchild, tmp.leftchild);
436 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
439 //fprintf(stderr, "insert [%d] after [%d]\n", SEGNR(s), SEGNR(left));
440 //actlist_splay_dump(a);
441 //actlist_dump(a, s->a.y);
446 s->right = left->right;
457 // we insert nodes not trees
458 assert(!s->leftchild);
459 assert(!s->rightchild);
462 move_to_root(a, left);
464 LINK(s,leftchild,a->root);
465 // steal right child from (previous) root
466 LINK(s,rightchild,a->root->rightchild);
467 a->root->rightchild = 0;
469 LINK(s,rightchild,a->root);
475 assert(actlist_splay_verify(a));
481 void actlist_delete(actlist_t*a, segment_t*s)
484 assert(actlist_splay_verify(a));
486 assert(actlist_splay_verify(a));
489 s->left->right = s->right;
494 s->right->left = s->left;
496 s->left = s->right = 0;
499 assert(a->root == s);
501 if(!a->root->leftchild) {
502 a->root = a->root->rightchild;
503 } else if(!a->root->rightchild) {
504 a->root = a->root->leftchild;
507 // free up root->left->right
508 segment_t*t = a->root->leftchild;
509 while(t->rightchild) {
510 segment_t*r = t->rightchild;
511 segment_t*l = r->leftchild;
512 LINK(r, leftchild, t);
513 LINK(t, rightchild, l);
516 LINK(a->root,leftchild,t);
517 assert(!a->root->leftchild->rightchild);
518 LINK(a->root->leftchild,rightchild,a->root->rightchild);
519 a->root = a->root->leftchild;
521 // free up root->right->left
522 segment_t*t = a->root->rightchild;
523 while(t->leftchild) {
524 segment_t*l = t->leftchild;
525 segment_t*r = l->rightchild;
526 LINK(l, rightchild, t);
527 LINK(t, leftchild, r);
530 LINK(a->root,rightchild,t);
531 assert(!a->root->rightchild->leftchild);
532 LINK(a->root->rightchild,leftchild,a->root->leftchild);
533 a->root = a->root->rightchild;
538 s->leftchild = s->rightchild = s->parent = 0;
540 assert(actlist_splay_verify(a));
543 int actlist_size(actlist_t*a)
548 segment_t* actlist_leftmost(actlist_t*a)
553 segment_t* actlist_rightmost(actlist_t*a)
555 /* this is only used in checks, so it doesn't matter that it's slow */
557 fprintf(stderr, "Warning: actlist_rightmost should not be used\n");
559 segment_t*s = a->list;
568 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
570 segment_t*left = actlist_find(a, p1, p2);
571 actlist_insert_after(a, left, s);
574 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
577 assert(actlist_splay_verify(a));
580 /* test that s1 is to the left of s2- our swap
581 code depends on that */
583 while(s && s!=s2) s = s->right;
587 actlist_delete(a, s1);
588 actlist_insert_after(a, s2, s1);
590 segment_t*s1l = s1->left;
591 segment_t*s1r = s1->right;
592 segment_t*s2l = s2->left;
593 segment_t*s2r = s2->right;
594 if(s1l) s1l->right = s2;
597 if(s2r) s2r->left = s1;
599 if(s2l!=s1) s1->left = s2l;
601 if(s1r!=s2) s2->right = s1r;
611 segment_t*l = s2->leftchild;
612 segment_t*r = s2->rightchild;
613 assert(s1->rightchild == s2); // because s1 < s2
614 segment_t*l1 = s1->leftchild;
615 segment_t*p = s1->parent;
619 if(p->leftchild == s1) p->leftchild=s2;
620 else {assert(p->rightchild == s1);p->rightchild=s2;}
628 } else if(s1->parent==s2) {
634 segment_t*l = s1->leftchild;
635 segment_t*r = s1->rightchild;
636 segment_t*r2 = s2->rightchild;
637 assert(s2->leftchild == s1); // because s1 < s2
638 segment_t*p = s2->parent;
642 if(p->leftchild == s2) p->leftchild=s1;
643 else {assert(p->rightchild == s2);p->rightchild=s1;}
652 segment_t*s1p = s1->parent;
653 segment_t*s1l = s1->leftchild;
654 segment_t*s1r = s1->rightchild;
655 segment_t*s2p = s2->parent;
656 segment_t*s2l = s2->leftchild;
657 segment_t*s2r = s2->rightchild;
660 s2->rightchild = s1r;
663 s1->rightchild = s2r;
666 if(s1p->leftchild == s1) s1p->leftchild=s2;
667 else {assert(s1p->rightchild == s1);s1p->rightchild=s2;}
672 if(s2p->leftchild == s2) s2p->leftchild=s1;
673 else {assert(s2p->rightchild == s2);s2p->rightchild=s1;}
678 if(s1->leftchild) s1->leftchild->parent = s1;
679 if(s2->leftchild) s2->leftchild->parent = s2;
680 if(s1->rightchild) s1->rightchild->parent = s1;
681 if(s2->rightchild) s2->rightchild->parent = s2;
683 assert(actlist_splay_verify(a));