+#endif
+
+#ifdef SPLAY
+
+#define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
+ //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
+
+// rotates segment's left node to the top
+static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
+{
+ /* s n
+ / \
+ n -> s
+ \ /
+ l l
+ */
+ assert(s->leftchild);
+ segment_t*p = s->parent;
+ segment_t*n = s->leftchild;
+ segment_t*l = n->rightchild;
+ LINK(n,rightchild,s);
+ LINK(s,leftchild,l);
+ n->parent = p;
+ if(p) {
+ if(p->leftchild == s)
+ p->leftchild = n;
+ else if(p->rightchild == s)
+ p->rightchild = n;
+ } else {
+ a->root = n;
+ }
+ return n;
+}
+// rotates segment's right node to the top
+static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
+{
+ /* s n
+ \ /
+ n -> s
+ / \
+ r r
+ */
+ assert(s->rightchild);
+ segment_t*p = s->parent;
+ segment_t*n = s->rightchild;
+ segment_t*r = n->leftchild;
+ LINK(n,leftchild,s);
+ LINK(s,rightchild,r);
+ n->parent = p;
+ if(p) {
+ if(p->leftchild == s)
+ p->leftchild = n;
+ else if(p->rightchild == s)
+ p->rightchild = n;
+ } else {
+ a->root = n;
+ }
+ return n;
+}
+
+static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
+{
+ if(!s) return 1;
+ if(parent != s->parent) {
+ fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
+ return 0;
+ }
+ if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
+ if(s != *ss) {
+ fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
+ return 0;
+ }
+ (*ss) = (*ss)->right;
+ if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
+ return 1;
+}
+
+static int actlist_splay_verify(actlist_t*a)
+{
+ segment_t*c = a->list;
+ if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
+ if(c) return 0;
+ return 1;
+}
+static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down)
+{
+ if(!s) return;
+
+ if(s->leftchild || s->rightchild) {
+ int t;
+
+ if(s->leftchild) {
+ char*o3 = malloc(strlen(up)+3);
+ strcpy(o3, up);strcat(o3, "+-");
+ char*newup = malloc(strlen(up)+3);
+ strcpy(newup, up);strcat(newup, "| ");
+ char*newup2 = malloc(strlen(up)+3);
+ strcpy(newup2, up);strcat(newup2, " ");
+ actlist_splay_dump2(a, s->leftchild, o3, newup2, newup);
+ fprintf(stderr, "%s| \n", up);
+ free(newup);
+ free(newup2);
+ free(o3);
+ }
+ fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
+ if(s->rightchild) {
+ char*o3 = malloc(strlen(down)+3);
+ strcpy(o3, down);strcat(o3, "+-");
+ char*newdown = malloc(strlen(down)+3);
+ strcpy(newdown, down);strcat(newdown, "| ");
+ char*newdown2 = malloc(strlen(down)+3);
+ strcpy(newdown2, down);strcat(newdown2, " ");
+ fprintf(stderr, "%s| \n", down);
+ actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2);
+ free(newdown);
+ free(newdown2);
+ free(o3);
+ }
+ } else {
+ fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
+ }
+}
+static void actlist_splay_dump(actlist_t*a)
+{
+ actlist_splay_dump2(a, a->root, "", "", "");
+}
+
+
+static void move_to_root(actlist_t*a, segment_t*s)
+{
+ if(!s) return;
+ /* this is a textbook implementation of the three splay operations
+ zig, zig-zig and zig-zag */
+ int nr=0;
+ while(a->root != s) {
+ assert(s->parent);
+ segment_t*p = s->parent;
+ if(p == a->root) {
+ // zig
+ if(a->root->leftchild == s) {
+ rotate_right(a, a->root);
+ } else {
+ rotate_left(a, a->root);
+ }
+ assert(a->root == s);
+ } else {
+ segment_t*pp = p->parent;
+ if(p->leftchild == s && pp->leftchild == p) {
+ // zig-zig (left)
+ rotate_right(a, pp);
+ rotate_right(a, s->parent);
+ } else if(p->rightchild == s && pp->rightchild == p) {
+ // zig-zig (right)
+ rotate_left(a, pp);
+ rotate_left(a, s->parent);
+ } else if(p->leftchild == s && pp->rightchild == p) {
+ // zig-zag (left)
+ rotate_right(a, p);
+ rotate_left(a, s->parent);
+ } else if(p->rightchild == s && pp->leftchild == p) {
+ // zig-zag (right)
+ rotate_left(a, p);
+ rotate_right(a, s->parent);
+ } else {
+ assert(0);
+ }
+ }
+ }
+}
+
+static void actlist_splay(actlist_t*a, point_t p1, point_t p2)
+{
+ if(!a->list) return;
+
+ segment_t tmp;
+ memset(&tmp, 0, sizeof(tmp));
+ segment_t*left=&tmp,*right=&tmp;
+
+ int c = 0;
+ while(1) {
+ if(cmp(a->root,p1,p2)<0) {
+ /* we're to the left of the root */
+ if(!a->root->leftchild) {
+ c = -1;break;
+ }
+ if(cmp(a->root->leftchild,p1,p2)<0) {
+ /* we're also to the left of the root's left child
+ -> rotate right, so that the left child is root */
+ segment_t*s = a->root->leftchild;
+ LINK(a->root, leftchild, s->rightchild);
+ LINK(s, rightchild, a->root);
+ a->root = s;
+ if(!a->root->leftchild) {
+ c = -1;break;
+ }
+ }
+ LINK(right, leftchild, a->root);
+ right = a->root;
+ a->root = a->root->leftchild;
+ } else /* cmp(a->root,p1,p2)>=0 */ {
+ /* we're to the right of the root */
+ if(!a->root->rightchild) {
+ c = 1;break;
+ }
+ if(cmp(a->root->rightchild,p1,p2)>=0) {
+ /* we're also to the right of the root's right child
+ -> rotate left, so that the right child is root */
+ segment_t*s = a->root->rightchild;
+ LINK(a->root, rightchild, s->leftchild);
+ LINK(s, leftchild, a->root);
+ a->root = s;
+ if(!a->root->rightchild)
+ c = 1;break;
+ }
+ LINK(left, rightchild, a->root);
+ left = a->root;
+ a->root = a->root->rightchild;
+ }
+ }
+ LINK(left, rightchild, a->root->leftchild);
+ LINK(right, leftchild, a->root->rightchild);
+ LINK(a->root, leftchild, tmp.rightchild);
+ LINK(a->root, rightchild, tmp.leftchild);
+ a->root->parent = 0;
+}
+
+#endif