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, "\n");
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 it's 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 double d = single_cmp(t, p1);
93 assert(!(d>=0 && to_the_left));
94 if(d<0) to_the_left=1;
99 static actlist_t*last = 0;
102 actlist_splay_dump(a);
107 segment_t*last=0, *s = a->root;
114 d = single_cmp(s, p1);
124 /* 80% hit, average cost per miss ~ 4 nodes */
125 int expected_depth = (int)((double)log2((double)a->size+1))+1;
127 static int misses = 0;
128 static int miss_cost = 0;
129 if(depth <= expected_depth) hits++;
131 miss_cost += depth - expected_depth;
134 fprintf(stderr, "%02.2f%% %f\n", hits / (double)(hits+misses), miss_cost / (double)misses);
138 segment_t*out = last;
139 if(d<0 || (d==0 && LINE_EQ(p2,last)<0)) {
142 assert(cmp(a->list, p1, p2)<0);
146 while(last->right && cmp(last->right, p1, p2)>=0) {
160 printf("[%d]!=[%d]\n", SEGNR(l), SEGNR(last));
161 printf("after tree: [%d]\n", SEGNR(out));
162 actlist_splay_dump(a);
165 double d1 = single_cmp(s,p1);
166 double d2 = cmp(s,p1,p2);
167 int x1 = d1<0?-1:(d1>0?1:0);
168 int x2 = d2<0?-1:(d2>0?1:0);
169 printf("[%d](%d,%d) ", SEGNR(s), x1, x2);
180 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
182 segment_t*last=0, *s = a->list;
185 double d = cmp(s, p1, p2);
197 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
198 //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
200 // rotates segment's left node to the top
201 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
209 assert(s->leftchild);
210 segment_t*p = s->parent;
211 segment_t*n = s->leftchild;
212 segment_t*l = n->rightchild;
213 LINK(n,rightchild,s);
217 if(p->leftchild == s)
219 else if(p->rightchild == s)
226 // rotates segment's right node to the top
227 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
235 assert(s->rightchild);
236 segment_t*p = s->parent;
237 segment_t*n = s->rightchild;
238 segment_t*r = n->leftchild;
240 LINK(s,rightchild,r);
243 if(p->leftchild == s)
245 else if(p->rightchild == s)
253 static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
256 if(parent != s->parent) {
257 fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
260 if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
262 fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
265 (*ss) = (*ss)->right;
266 if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
270 static int actlist_splay_verify(actlist_t*a)
272 segment_t*c = a->list;
273 if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
277 static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down)
281 if(s->leftchild || s->rightchild) {
285 char*o3 = malloc(strlen(up)+3);
286 strcpy(o3, up);strcat(o3, "+-");
287 char*newup = malloc(strlen(up)+3);
288 strcpy(newup, up);strcat(newup, "| ");
289 char*newup2 = malloc(strlen(up)+3);
290 strcpy(newup2, up);strcat(newup2, " ");
291 actlist_splay_dump2(a, s->leftchild, o3, newup2, newup);
292 fprintf(stderr, "%s| \n", up);
297 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
299 char*o3 = malloc(strlen(down)+3);
300 strcpy(o3, down);strcat(o3, "+-");
301 char*newdown = malloc(strlen(down)+3);
302 strcpy(newdown, down);strcat(newdown, "| ");
303 char*newdown2 = malloc(strlen(down)+3);
304 strcpy(newdown2, down);strcat(newdown2, " ");
305 fprintf(stderr, "%s| \n", down);
306 actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2);
312 fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
315 static void actlist_splay_dump(actlist_t*a)
317 actlist_splay_dump2(a, a->root, "", "", "");
321 static void move_to_root(actlist_t*a, segment_t*s)
324 /* this is a textbook implementation of the three splay operations
325 zig, zig-zig and zig-zag */
327 while(a->root != s) {
329 segment_t*p = s->parent;
332 if(a->root->leftchild == s) {
333 rotate_right(a, a->root);
335 rotate_left(a, a->root);
337 assert(a->root == s);
339 segment_t*pp = p->parent;
340 if(p->leftchild == s && pp->leftchild == p) {
343 rotate_right(a, s->parent);
344 } else if(p->rightchild == s && pp->rightchild == p) {
347 rotate_left(a, s->parent);
348 } else if(p->leftchild == s && pp->rightchild == p) {
351 rotate_left(a, s->parent);
352 } else if(p->rightchild == s && pp->leftchild == p) {
355 rotate_right(a, s->parent);
363 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
368 memset(&tmp, 0, sizeof(tmp));
369 segment_t*left=&tmp,*right=&tmp;
373 if(cmp(a->root,p1,p2)<0) {
374 /* we're to the left of the root */
375 if(!a->root->leftchild) {
378 if(cmp(a->root->leftchild,p1,p2)<0) {
379 /* we're also to the left of the root's left child
380 -> rotate right, so that the left child is root */
381 segment_t*s = a->root->leftchild;
382 LINK(a->root, leftchild, s->rightchild);
383 LINK(s, rightchild, a->root);
385 if(!a->root->leftchild) {
389 LINK(right, leftchild, a->root);
391 a->root = a->root->leftchild;
392 } else /* cmp(a->root,p1,p2)>=0 */ {
393 /* we're to the right of the root */
394 if(!a->root->rightchild) {
397 if(cmp(a->root->rightchild,p1,p2)>=0) {
398 /* we're also to the right of the root's right child
399 -> rotate left, so that the right child is root */
400 segment_t*s = a->root->rightchild;
401 LINK(a->root, rightchild, s->leftchild);
402 LINK(s, leftchild, a->root);
404 if(!a->root->rightchild)
407 LINK(left, rightchild, a->root);
409 a->root = a->root->rightchild;
412 LINK(left, rightchild, a->root->leftchild);
413 LINK(right, leftchild, a->root->rightchild);
414 LINK(a->root, leftchild, tmp.rightchild);
415 LINK(a->root, rightchild, tmp.leftchild);
421 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
424 //fprintf(stderr, "insert [%d] after [%d]\n", SEGNR(s), SEGNR(left));
425 //actlist_splay_dump(a);
426 //actlist_dump(a, s->a.y);
431 s->right = left->right;
442 // we insert nodes not trees
443 assert(!s->leftchild);
444 assert(!s->rightchild);
447 move_to_root(a, left);
450 LINK(s,leftchild,a->root);
451 // steal right child from (previous) root
452 LINK(s,rightchild,a->root->rightchild);
453 a->root->rightchild = 0;
455 LINK(s,rightchild,a->root);
458 /*if(cmp(a->root, s->a, s->b) < 0) {
459 LINK(s,rightchild,a->root);
460 // steal left child from (previous) root
461 LINK(s,leftchild,a->root->leftchild);
462 a->root->leftchild = 0;
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;
473 assert(actlist_splay_verify(a));
479 void actlist_delete(actlist_t*a, segment_t*s)
482 assert(actlist_splay_verify(a));
484 assert(actlist_splay_verify(a));
487 s->left->right = s->right;
492 s->right->left = s->left;
494 s->left = s->right = 0;
497 assert(a->root == s);
499 if(!a->root->leftchild) {
500 a->root = a->root->rightchild;
501 } else if(!a->root->rightchild) {
502 a->root = a->root->leftchild;
505 // free up root->left->right
506 segment_t*t = a->root->leftchild;
507 while(t->rightchild) {
508 segment_t*r = t->rightchild;
509 segment_t*l = r->leftchild;
510 LINK(r, leftchild, t);
511 LINK(t, rightchild, l);
514 LINK(a->root,leftchild,t);
515 assert(!a->root->leftchild->rightchild);
516 LINK(a->root->leftchild,rightchild,a->root->rightchild);
517 a->root = a->root->leftchild;
519 // free up root->right->left
520 segment_t*t = a->root->rightchild;
521 while(t->leftchild) {
522 segment_t*l = t->leftchild;
523 segment_t*r = l->rightchild;
524 LINK(l, rightchild, t);
525 LINK(t, leftchild, r);
528 LINK(a->root,rightchild,t);
529 assert(!a->root->rightchild->leftchild);
530 LINK(a->root->rightchild,leftchild,a->root->leftchild);
531 a->root = a->root->rightchild;
536 s->leftchild = s->rightchild = s->parent = 0;
538 assert(actlist_splay_verify(a));
541 int actlist_size(actlist_t*a)
546 segment_t* actlist_leftmost(actlist_t*a)
551 segment_t* actlist_rightmost(actlist_t*a)
553 /* this is only used in checks, so it doesn't matter that it's slow */
554 segment_t*s = a->list;
563 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
565 segment_t*left = actlist_find(a, p1, p2);
566 actlist_insert_after(a, left, s);
570 segment_t* actlist_left(actlist_t*a, segment_t*s)
575 segment_t* actlist_right(actlist_t*a, segment_t*s)
577 if(s) return s->right;
581 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
584 assert(actlist_splay_verify(a));
587 /* test that s1 is to the left of s2- our swap
588 code depends on that */
590 while(s && s!=s2) s = s->right;
594 actlist_delete(a, s1);
595 actlist_insert_after(a, s2, s1);
597 segment_t*s1l = s1->left;
598 segment_t*s1r = s1->right;
599 segment_t*s2l = s2->left;
600 segment_t*s2r = s2->right;
601 if(s1l) s1l->right = s2;
604 if(s2r) s2r->left = s1;
606 if(s2l!=s1) s1->left = s2l;
608 if(s1r!=s2) s2->right = s1r;
618 segment_t*l = s2->leftchild;
619 segment_t*r = s2->rightchild;
620 assert(s1->rightchild == s2); // because s1 < s2
621 segment_t*l1 = s1->leftchild;
622 segment_t*p = s1->parent;
626 if(p->leftchild == s1) p->leftchild=s2;
627 else {assert(p->rightchild == s1);p->rightchild=s2;}
635 } else if(s1->parent==s2) {
641 segment_t*l = s1->leftchild;
642 segment_t*r = s1->rightchild;
643 segment_t*r2 = s2->rightchild;
644 assert(s2->leftchild == s1); // because s1 < s2
645 segment_t*p = s2->parent;
649 if(p->leftchild == s2) p->leftchild=s1;
650 else {assert(p->rightchild == s2);p->rightchild=s1;}
659 segment_t*s1p = s1->parent;
660 segment_t*s1l = s1->leftchild;
661 segment_t*s1r = s1->rightchild;
662 segment_t*s2p = s2->parent;
663 segment_t*s2l = s2->leftchild;
664 segment_t*s2r = s2->rightchild;
667 s2->rightchild = s1r;
670 s1->rightchild = s2r;
673 if(s1p->leftchild == s1) s1p->leftchild=s2;
674 else {assert(s1p->rightchild == s1);s1p->rightchild=s2;}
679 if(s2p->leftchild == s2) s2p->leftchild=s1;
680 else {assert(s2p->rightchild == s2);s2p->rightchild=s1;}
685 if(s1->leftchild) s1->leftchild->parent = s1;
686 if(s2->leftchild) s2->leftchild->parent = s2;
687 if(s1->rightchild) s1->rightchild->parent = s1;
688 if(s2->rightchild) s2->rightchild->parent = s2;
690 assert(actlist_splay_verify(a));