tree.c

   1 #include <float.h>
   2 #include <limits.h>
   3 #include <math.h>
   4 #include "bspwm.h"
   5 #include "desktop.h"
   6 #include "ewmh.h"
   7 #include "history.h"
   8 #include "monitor.h"
   9 #include "query.h"
  10 #include "settings.h"
  11 #include "stack.h"
  12 #include "tag.h"
  13 #include "window.h"
  14 #include "tree.h"
  15
  16 void arrange(monitor_t *m, desktop_t *d)
  17 {
  18     if (d->root == NULL)
  19         return;
  20
  21     PRINTF("arrange %s %s\n", m->name, d->name);
  22
  23     xcb_rectangle_t rect = m->rectangle;
  24     int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap);
  25     rect.x += m->left_padding + wg;
  26     rect.y += m->top_padding + wg;
  27     rect.width -= m->left_padding + m->right_padding + wg;
  28     rect.height -= m->top_padding + m->bottom_padding + wg;
  29     apply_layout(m, d, d->root, rect, rect);
  30 }
  31
  32 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
  33 {
  34     if (n == NULL)
  35         return;
  36
  37     n->rectangle = rect;
  38
  39     if (is_leaf(n)) {
  40
  41         if (is_floating(n->client) && n->client->border_width != d->border_width) {
  42             int ds = 2 * (d->border_width - n->client->border_width);
  43             n->client->floating_rectangle.width += ds;
  44             n->client->floating_rectangle.height += ds;
  45         }
  46
  47         if ((borderless_monocle && is_tiled(n->client) && d->layout == LAYOUT_MONOCLE) ||
  48                 n->client->fullscreen)
  49             n->client->border_width = 0;
  50         else
  51             n->client->border_width = d->border_width;
  52
  53         xcb_rectangle_t r;
  54         if (!n->client->fullscreen) {
  55             if (!n->client->floating) {
  56                 /* tiled clients */
  57                 if (d->layout == LAYOUT_TILED)
  58                     r = rect;
  59                 else if (d->layout == LAYOUT_MONOCLE)
  60                     r = root_rect;
  61                 else
  62                     return;
  63                 int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap);
  64                 int bleed = wg + 2 * n->client->border_width;
  65                 r.width = (bleed < r.width ? r.width - bleed : 1);
  66                 r.height = (bleed < r.height ? r.height - bleed : 1);
  67                 n->client->tiled_rectangle = r;
  68             } else {
  69                 /* floating clients */
  70                 r = n->client->floating_rectangle;
  71             }
  72         } else {
  73             /* fullscreen clients */
  74             r = m->rectangle;
  75         }
  76
  77         window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
  78         window_border_width(n->client->window, n->client->border_width);
  79         window_draw_border(n, n == d->focus, m == mon);
  80
  81     } else {
  82         xcb_rectangle_t first_rect;
  83         xcb_rectangle_t second_rect;
  84
  85         if (n->first_child->vacant || n->second_child->vacant) {
  86             first_rect = second_rect = rect;
  87         } else {
  88             unsigned int fence;
  89             if (n->split_type == TYPE_VERTICAL) {
  90                 fence = rect.width * n->split_ratio;
  91                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
  92                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
  93             } else if (n->split_type == TYPE_HORIZONTAL) {
  94                 fence = rect.height * n->split_ratio;
  95                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
  96                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
  97             }
  98         }
  99
 100         apply_layout(m, d, n->first_child, first_rect, root_rect);
 101         apply_layout(m, d, n->second_child, second_rect, root_rect);
 102     }
 103 }
 104
 105 void insert_node(monitor_t *m, desktop_t *d, node_t *n, node_t *f)
 106 {
 107     if (d == NULL || n == NULL)
 108         return;
 109
 110     PRINTF("insert node %X\n", n->client->window);
 111
 112     /* n: new leaf node */
 113     /* c: new container node */
 114     /* f: focus or insertion anchor */
 115     /* p: parent of focus */
 116     /* g: grand parent of focus */
 117
 118     if (f == NULL)
 119         f = d->root;
 120
 121     if (f == NULL) {
 122         d->root = n;
 123         if (is_visible(d, n))
 124             d->focus = n;
 125     } else {
 126         node_t *c = make_node();
 127         node_t *p = f->parent;
 128         if (p != NULL && f->split_mode == MODE_AUTOMATIC
 129                 && (p->first_child->vacant || p->second_child->vacant)) {
 130             f = p;
 131             p = f->parent;
 132         }
 133         n->parent = c;
 134         c->birth_rotation = f->birth_rotation;
 135         switch (f->split_mode) {
 136             case MODE_AUTOMATIC:
 137                 if (p == NULL) {
 138                     c->first_child = n;
 139                     c->second_child = f;
 140                     if (m->rectangle.width > m->rectangle.height)
 141                         c->split_type = TYPE_VERTICAL;
 142                     else
 143                         c->split_type = TYPE_HORIZONTAL;
 144                     f->parent = c;
 145                     d->root = c;
 146                 } else {
 147                     node_t *g = p->parent;
 148                     c->parent = g;
 149                     if (g != NULL) {
 150                         if (is_first_child(p))
 151                             g->first_child = c;
 152                         else
 153                             g->second_child = c;
 154                     } else {
 155                         d->root = c;
 156                     }
 157                     c->split_type = p->split_type;
 158                     c->split_ratio = p->split_ratio;
 159                     p->parent = c;
 160                     int rot;
 161                     if (is_first_child(f)) {
 162                         c->first_child = n;
 163                         c->second_child = p;
 164                         rot = 90;
 165                     } else {
 166                         c->first_child = p;
 167                         c->second_child = n;
 168                         rot = 270;
 169                     }
 170                     if (!is_floating(n->client))
 171                         rotate_tree(p, rot);
 172                     n->birth_rotation = rot;
 173                 }
 174                 break;
 175             case MODE_MANUAL:
 176                 if (p != NULL) {
 177                     if (is_first_child(f))
 178                         p->first_child = c;
 179                     else
 180                         p->second_child = c;
 181                 }
 182                 c->split_ratio = f->split_ratio;
 183                 c->parent = p;
 184                 f->parent = c;
 185                 f->birth_rotation = 0;
 186                 switch (f->split_dir) {
 187                     case DIR_LEFT:
 188                         c->split_type = TYPE_VERTICAL;
 189                         c->first_child = n;
 190                         c->second_child = f;
 191                         break;
 192                     case DIR_RIGHT:
 193                         c->split_type = TYPE_VERTICAL;
 194                         c->first_child = f;
 195                         c->second_child = n;
 196                         break;
 197                     case DIR_UP:
 198                         c->split_type = TYPE_HORIZONTAL;
 199                         c->first_child = n;
 200                         c->second_child = f;
 201                         break;
 202                     case DIR_DOWN:
 203                         c->split_type = TYPE_HORIZONTAL;
 204                         c->first_child = f;
 205                         c->second_child = n;
 206                         break;
 207                 }
 208                 if (d->root == f)
 209                     d->root = c;
 210                 f->split_mode = MODE_AUTOMATIC;
 211                 break;
 212         }
 213         if (f->vacant)
 214             update_vacant_state(p);
 215     }
 216     if (n->client->sticky)
 217         m->num_sticky++;
 218     put_status();
 219 }
 220
 221 void pseudo_focus(desktop_t *d, node_t *n)
 222 {
 223     d->focus = n;
 224     if (n != NULL)
 225         stack(n);
 226 }
 227
 228 void focus_node(monitor_t *m, desktop_t *d, node_t *n)
 229 {
 230     if (mon->desk != d || n == NULL)
 231         clear_input_focus();
 232
 233     if (m->num_sticky > 0 && d != m->desk) {
 234         node_t *a = first_extrema(m->desk->root);
 235         sticky_still = false;
 236         while (a != NULL) {
 237             node_t *b = next_leaf(a, m->desk->root);
 238             if (a->client->sticky)
 239                 transfer_node(m, m->desk, a, m, d, d->focus);
 240             a = b;
 241         }
 242         sticky_still = true;
 243         if (n == NULL && d->focus != NULL && is_visible(d, d->focus))
 244             n = d->focus;
 245     }
 246
 247     if (n != NULL && d->focus != NULL && n != d->focus && d->focus->client->fullscreen) {
 248         set_fullscreen(d->focus, false);
 249         arrange(m, d);
 250     }
 251
 252     if (mon != m) {
 253         for (desktop_t *cd = mon->desk_head; cd != NULL; cd = cd->next)
 254             window_draw_border(cd->focus, true, false);
 255         for (desktop_t *cd = m->desk_head; cd != NULL; cd = cd->next)
 256             if (cd != d)
 257                 window_draw_border(cd->focus, true, true);
 258         if (d->focus == n)
 259             window_draw_border(n, true, true);
 260     }
 261
 262     if (d->focus != n) {
 263         window_draw_border(d->focus, false, true);
 264         window_draw_border(n, true, true);
 265     }
 266
 267     focus_desktop(m, d);
 268     pseudo_focus(d, n);
 269
 270     if (n == NULL) {
 271         history_add(m, d, NULL);
 272         ewmh_update_active_window();
 273         return;
 274     }
 275
 276     PRINTF("focus node %X\n", n->client->window);
 277
 278     n->client->urgent = false;
 279
 280     if (!is_visible(d, n))
 281         tag_node(m, d, n, d, n->client->tags_field | d->tags_field);
 282     history_add(m, d, n);
 283     set_input_focus(n);
 284
 285     if (focus_follows_pointer) {
 286         xcb_window_t win = XCB_NONE;
 287         query_pointer(&win, NULL);
 288         if (win != n->client->window)
 289             enable_motion_recorder();
 290         else
 291             disable_motion_recorder();
 292     }
 293
 294     ewmh_update_active_window();
 295 }
 296
 297 void update_current(void)
 298 {
 299     focus_node(mon, mon->desk, mon->desk->focus);
 300 }
 301
 302 node_t *make_node(void)
 303 {
 304     node_t *n = malloc(sizeof(node_t));
 305     n->parent = n->first_child = n->second_child = NULL;
 306     n->split_ratio = split_ratio;
 307     n->split_mode = MODE_AUTOMATIC;
 308     n->split_type = TYPE_VERTICAL;
 309     n->birth_rotation = 0;
 310     n->client = NULL;
 311     n->vacant = false;
 312     return n;
 313 }
 314
 315 client_t *make_client(xcb_window_t win)
 316 {
 317     client_t *c = malloc(sizeof(client_t));
 318     snprintf(c->class_name, sizeof(c->class_name), "%s", MISSING_VALUE);
 319     c->border_width = BORDER_WIDTH;
 320     c->window = win;
 321     c->floating = c->transient = c->fullscreen = c->locked = c->sticky = c->urgent = false;
 322     c->icccm_focus = false;
 323     xcb_icccm_get_wm_protocols_reply_t protocols;
 324     if (xcb_icccm_get_wm_protocols_reply(dpy, xcb_icccm_get_wm_protocols(dpy, win, ewmh->WM_PROTOCOLS), &protocols, NULL) == 1) {
 325         if (has_proto(WM_TAKE_FOCUS, &protocols))
 326             c->icccm_focus = true;
 327         xcb_icccm_get_wm_protocols_reply_wipe(&protocols);
 328     }
 329     c->num_states = 0;
 330     xcb_ewmh_get_atoms_reply_t wm_state;
 331     if (xcb_ewmh_get_wm_state_reply(ewmh, xcb_ewmh_get_wm_state(ewmh, win), &wm_state, NULL) == 1) {
 332         for (unsigned int i = 0; i < wm_state.atoms_len && i < MAX_STATE; i++)
 333             ewmh_wm_state_add(c, wm_state.atoms[i]);
 334         xcb_ewmh_get_atoms_reply_wipe(&wm_state);
 335     }
 336     return c;
 337 }
 338
 339 bool is_visible(desktop_t *d, node_t *n)
 340 {
 341     return (d->tags_field & n->client->tags_field) != 0;
 342 }
 343
 344 bool is_leaf(node_t *n)
 345 {
 346     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
 347 }
 348
 349 bool is_tiled(client_t *c)
 350 {
 351     if (c == NULL)
 352         return false;
 353     return (!c->floating && !c->fullscreen);
 354 }
 355
 356 bool is_floating(client_t *c)
 357 {
 358     if (c == NULL)
 359         return false;
 360     return (c->floating && !c->fullscreen);
 361 }
 362
 363 bool is_first_child(node_t *n)
 364 {
 365     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
 366 }
 367
 368 bool is_second_child(node_t *n)
 369 {
 370     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
 371 }
 372
 373 void change_split_ratio(node_t *n, value_change_t chg)
 374 {
 375     n->split_ratio = pow(n->split_ratio,
 376             (chg == CHANGE_INCREASE ? (1 / growth_factor) : growth_factor));
 377 }
 378
 379 void reset_mode(coordinates_t *loc)
 380 {
 381     if (loc->node != NULL) {
 382         loc->node->split_mode = MODE_AUTOMATIC;
 383         window_draw_border(loc->node, loc->desktop->focus == loc->node, mon == loc->monitor);
 384     } else if (loc->desktop != NULL) {
 385         for (node_t *a = first_extrema(loc->desktop->root); a != NULL; a = next_leaf(a, loc->desktop->root)) {
 386             a->split_mode = MODE_AUTOMATIC;
 387             window_draw_border(a, loc->desktop->focus == a, mon == loc->monitor);
 388         }
 389     }
 390 }
 391
 392 node_t *brother_tree(node_t *n)
 393 {
 394     if (n == NULL || n->parent == NULL)
 395         return NULL;
 396     if (is_first_child(n))
 397         return n->parent->second_child;
 398     else
 399         return n->parent->first_child;
 400 }
 401
 402 node_t *closest_visible(desktop_t *d, node_t *n)
 403 {
 404     if (n == NULL)
 405         return NULL;
 406     node_t *prev = prev_leaf(n, d->root);
 407     node_t *next = next_leaf(n, d->root);
 408     while (prev != NULL || next != NULL) {
 409         if (prev != NULL) {
 410             if (is_visible(d, prev))
 411                 return prev;
 412             else
 413                 prev = prev_leaf(prev, d->root);
 414         }
 415         if (next != NULL) {
 416             if (is_visible(d, next))
 417                 return next;
 418             else
 419                 next = next_leaf(next, d->root);
 420         }
 421     }
 422     return NULL;
 423 }
 424
 425 node_t *first_extrema(node_t *n)
 426 {
 427     if (n == NULL)
 428         return NULL;
 429     else if (n->first_child == NULL)
 430         return n;
 431     else
 432         return first_extrema(n->first_child);
 433 }
 434
 435 node_t *second_extrema(node_t *n)
 436 {
 437     if (n == NULL)
 438         return NULL;
 439     else if (n->second_child == NULL)
 440         return n;
 441     else
 442         return second_extrema(n->second_child);
 443 }
 444
 445 node_t *next_leaf(node_t *n, node_t *r)
 446 {
 447     if (n == NULL)
 448         return NULL;
 449     node_t *p = n;
 450     while (is_second_child(p) && p != r)
 451         p = p->parent;
 452     if (p == r)
 453         return NULL;
 454     return first_extrema(p->parent->second_child);
 455 }
 456
 457 node_t *prev_leaf(node_t *n, node_t *r)
 458 {
 459     if (n == NULL)
 460         return NULL;
 461     node_t *p = n;
 462     while (is_first_child(p) && p != r)
 463         p = p->parent;
 464     if (p == r)
 465         return NULL;
 466     return second_extrema(p->parent->first_child);
 467 }
 468
 469 node_t *next_visible_leaf(desktop_t *d, node_t *n, node_t *r)
 470 {
 471     node_t *next = next_leaf(n, r);
 472     if (next == NULL || is_visible(d, next))
 473         return next;
 474     else
 475         return next_visible_leaf(d, next, r);
 476 }
 477
 478 node_t *prev_visible_leaf(desktop_t *d, node_t *n, node_t *r)
 479 {
 480     node_t *prev = prev_leaf(n, r);
 481     if (prev == NULL || is_visible(d, prev))
 482         return prev;
 483     else
 484         return prev_visible_leaf(d, prev, r);
 485 }
 486
 487 /* bool is_adjacent(node_t *a, node_t *r) */
 488 /* { */
 489 /*     node_t *f = r->parent; */
 490 /*     node_t *p = a; */
 491 /*     bool first_child = is_first_child(r); */
 492 /*     while (p != r) { */
 493 /*         if (p->parent->split_type == f->split_type && is_first_child(p) == first_child) */
 494 /*             return false; */
 495 /*         p = p->parent; */
 496 /*     } */
 497 /*     return true; */
 498 /* } */
 499
 500 /* Returns true if *b* is adjacent to *a* in the direction *dir* */
 501 bool is_adjacent(node_t *a, node_t *b, direction_t dir)
 502 {
 503     switch (dir) {
 504         case DIR_RIGHT:
 505             return (a->rectangle.x + a->rectangle.width) == b->rectangle.x;
 506             break;
 507         case DIR_DOWN:
 508             return (a->rectangle.y + a->rectangle.height) == b->rectangle.y;
 509             break;
 510         case DIR_LEFT:
 511             return (b->rectangle.x + b->rectangle.width) == a->rectangle.x;
 512             break;
 513         case DIR_UP:
 514             return (b->rectangle.y + b->rectangle.height) == a->rectangle.y;
 515             break;
 516     }
 517     return false;
 518 }
 519
 520 node_t *find_fence(node_t *n, direction_t dir)
 521 {
 522     node_t *p;
 523
 524     if (n == NULL)
 525         return NULL;
 526
 527     p = n->parent;
 528
 529     while (p != NULL) {
 530         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
 531                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
 532                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
 533                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 534             return p;
 535         p = p->parent;
 536     }
 537
 538     return NULL;
 539 }
 540
 541
 542 node_t *nearest_neighbor(desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 543 {
 544     if (n == NULL || n->client->fullscreen
 545             || (d->layout == LAYOUT_MONOCLE && is_tiled(n->client)))
 546         return NULL;
 547
 548     node_t *nearest = NULL;
 549     if (history_aware_focus)
 550         nearest = nearest_from_history(d, n, dir, sel);
 551     if (nearest == NULL)
 552         nearest = nearest_from_distance(d, n, dir, sel);
 553     return nearest;
 554 }
 555
 556 node_t *nearest_from_history(desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 557 {
 558     if (n == NULL || !is_tiled(n->client))
 559         return NULL;
 560
 561     node_t *target = find_fence(n, dir);
 562     if (target == NULL)
 563         return NULL;
 564     if (dir == DIR_UP || dir == DIR_LEFT)
 565         target = target->first_child;
 566     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 567         target = target->second_child;
 568
 569     node_t *nearest = NULL;
 570     int min_rank = INT_MAX;
 571
 572     for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 573         if (a->vacant || !is_adjacent(n, a, dir) || a == n)
 574             continue;
 575         if (!node_matches(n, a, sel))
 576             continue;
 577
 578         int rank = history_rank(d, a);
 579         if (rank >= 0 && rank < min_rank) {
 580             nearest = a;
 581             min_rank = rank;
 582         }
 583     }
 584
 585     return nearest;
 586 }
 587
 588 node_t *nearest_from_distance(desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 589 {
 590     if (n == NULL)
 591         return NULL;
 592
 593     node_t *target = NULL;
 594
 595     if (is_tiled(n->client)) {
 596         target = find_fence(n, dir);
 597         if (target == NULL)
 598             return NULL;
 599         if (dir == DIR_UP || dir == DIR_LEFT)
 600             target = target->first_child;
 601         else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 602             target = target->second_child;
 603     } else {
 604         target = d->root;
 605     }
 606
 607     node_t *nearest = NULL;
 608     direction_t dir2;
 609     xcb_point_t pt;
 610     xcb_point_t pt2;
 611     get_side_handle(n->client, dir, &pt);
 612     get_opposite(dir, &dir2);
 613     double ds = DBL_MAX;
 614
 615     for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 616         if (a == n ||
 617                 !is_visible(d, a) ||
 618                 !node_matches(n, a, sel) ||
 619                 is_tiled(a->client) != is_tiled(n->client) ||
 620                 (is_tiled(a->client) && !is_adjacent(n, a, dir)))
 621             continue;
 622
 623         get_side_handle(a->client, dir2, &pt2);
 624         double ds2 = distance(pt, pt2);
 625         if (ds2 < ds) {
 626             ds = ds2;
 627             nearest = a;
 628         }
 629     }
 630
 631     return nearest;
 632 }
 633
 634 void get_opposite(direction_t src, direction_t *dst)
 635 {
 636     switch (src) {
 637         case DIR_RIGHT:
 638             *dst = DIR_LEFT;
 639             break;
 640         case DIR_DOWN:
 641             *dst = DIR_UP;
 642             break;
 643         case DIR_LEFT:
 644             *dst = DIR_RIGHT;
 645             break;
 646         case DIR_UP:
 647             *dst = DIR_DOWN;
 648             break;
 649     }
 650 }
 651
 652 int tiled_area(node_t *n)
 653 {
 654     if (n == NULL)
 655         return -1;
 656     xcb_rectangle_t rect = n->client->tiled_rectangle;
 657     return rect.width * rect.height;
 658 }
 659
 660 node_t *find_biggest(desktop_t *d, node_t *c, client_select_t sel)
 661 {
 662     if (d == NULL)
 663         return NULL;
 664
 665     node_t *r = NULL;
 666     int r_area = tiled_area(r);
 667
 668     for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 669         if (!is_visible(d, f) || !is_tiled(f->client) || !node_matches(c, f, sel))
 670             continue;
 671         int f_area = tiled_area(f);
 672         if (r == NULL) {
 673             r = f;
 674             r_area = f_area;
 675         } else if (f_area > r_area) {
 676             r = f;
 677             r_area = f_area;
 678         }
 679     }
 680
 681     return r;
 682 }
 683
 684 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 685 {
 686     if (n == NULL)
 687         return;
 688
 689     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 690             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 691         change_split_ratio(n, CHANGE_INCREASE);
 692     else
 693         change_split_ratio(n, CHANGE_DECREASE);
 694 }
 695
 696 void rotate_tree(node_t *n, int deg)
 697 {
 698     if (n == NULL || is_leaf(n) || deg == 0)
 699         return;
 700
 701     node_t *tmp;
 702
 703     if ((deg == 90 && n->split_type == TYPE_HORIZONTAL)
 704             || (deg == 270 && n->split_type == TYPE_VERTICAL)
 705             || deg == 180) {
 706         tmp = n->first_child;
 707         n->first_child = n->second_child;
 708         n->second_child = tmp;
 709         n->split_ratio = 1.0 - n->split_ratio;
 710     }
 711
 712     if (deg != 180) {
 713         if (n->split_type == TYPE_HORIZONTAL)
 714             n->split_type = TYPE_VERTICAL;
 715         else if (n->split_type == TYPE_VERTICAL)
 716             n->split_type = TYPE_HORIZONTAL;
 717     }
 718
 719     rotate_tree(n->first_child, deg);
 720     rotate_tree(n->second_child, deg);
 721 }
 722
 723 void rotate_brother(node_t *n)
 724 {
 725     rotate_tree(brother_tree(n), n->birth_rotation);
 726 }
 727
 728 void unrotate_tree(node_t *n, int rot)
 729 {
 730     if (rot == 0)
 731         return;
 732     rotate_tree(n, 360 - rot);
 733 }
 734
 735 void unrotate_brother(node_t *n)
 736 {
 737     unrotate_tree(brother_tree(n), n->birth_rotation);
 738 }
 739
 740 void flip_tree(node_t *n, flip_t flp)
 741 {
 742     if (n == NULL || is_leaf(n))
 743         return;
 744
 745     node_t *tmp;
 746
 747     if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL)
 748             || (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
 749         tmp = n->first_child;
 750         n->first_child = n->second_child;
 751         n->second_child = tmp;
 752         n->split_ratio = 1.0 - n->split_ratio;
 753     }
 754
 755     flip_tree(n->first_child, flp);
 756     flip_tree(n->second_child, flp);
 757 }
 758
 759 int balance_tree(node_t *n)
 760 {
 761     if (n == NULL || n->vacant) {
 762         return 0;
 763     } else if (is_leaf(n)) {
 764         return 1;
 765     } else {
 766         int b1 = balance_tree(n->first_child);
 767         int b2 = balance_tree(n->second_child);
 768         int b = b1 + b2;
 769         if (b1 > 0 && b2 > 0)
 770             n->split_ratio = (double) b1 / b;
 771         return b;
 772     }
 773 }
 774
 775 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
 776 {
 777     if (d == NULL || n == NULL)
 778         return;
 779
 780     PRINTF("unlink node %X\n", n->client->window);
 781
 782     node_t *p = n->parent;
 783
 784     if (p == NULL) {
 785         d->root = NULL;
 786         d->focus = NULL;
 787     } else {
 788         if (n == d->focus) {
 789             d->focus = history_get_node(d, n);
 790             if (d->focus == NULL)
 791                 d->focus = closest_visible(d, n);
 792         }
 793
 794         node_t *b;
 795         node_t *g = p->parent;
 796
 797         if (is_first_child(n)) {
 798             b = p->second_child;
 799             if (!n->vacant)
 800                 unrotate_tree(b, n->birth_rotation);
 801         } else {
 802             b = p->first_child;
 803             if (!n->vacant)
 804                 unrotate_tree(b, n->birth_rotation);
 805         }
 806
 807         b->parent = g;
 808
 809         if (g != NULL) {
 810             if (is_first_child(p))
 811                 g->first_child = b;
 812             else
 813                 g->second_child = b;
 814         } else {
 815             d->root = b;
 816         }
 817
 818         b->birth_rotation = p->birth_rotation;
 819         n->parent = NULL;
 820         free(p);
 821         update_vacant_state(b->parent);
 822     }
 823     if (n->client->sticky)
 824         m->num_sticky--;
 825     put_status();
 826 }
 827
 828 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
 829 {
 830     if (n == NULL)
 831         return;
 832
 833     PRINTF("remove node %X\n", n->client->window);
 834
 835     unlink_node(m, d, n);
 836     history_remove(d, n);
 837     remove_stack_node(n);
 838     free(n->client);
 839     free(n);
 840
 841     num_clients--;
 842     ewmh_update_client_list();
 843
 844     if (mon->desk == d)
 845         update_current();
 846 }
 847
 848 void destroy_tree(node_t *n)
 849 {
 850     if (n == NULL)
 851         return;
 852     node_t *first_tree = n->first_child;
 853     node_t *second_tree = n->second_child;
 854     if (n->client != NULL)
 855         free(n->client);
 856     free(n);
 857     destroy_tree(first_tree);
 858     destroy_tree(second_tree);
 859 }
 860
 861 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2)
 862 {
 863     if (n1 == NULL || n2 == NULL || n1 == n2 || (d1 != d2 && (n1->client->sticky || n2->client->sticky)))
 864         return false;
 865
 866     PRINTF("swap nodes %X %X", n1->client->window, n2->client->window);
 867
 868     node_t *pn1 = n1->parent;
 869     node_t *pn2 = n2->parent;
 870     bool n1_first_child = is_first_child(n1);
 871     bool n2_first_child = is_first_child(n2);
 872     int br1 = n1->birth_rotation;
 873     int br2 = n2->birth_rotation;
 874
 875     if (pn1 != NULL) {
 876         if (n1_first_child)
 877             pn1->first_child = n2;
 878         else
 879             pn1->second_child = n2;
 880     }
 881
 882     if (pn2 != NULL) {
 883         if (n2_first_child)
 884             pn2->first_child = n1;
 885         else
 886             pn2->second_child = n1;
 887     }
 888
 889     n1->parent = pn2;
 890     n2->parent = pn1;
 891     n1->birth_rotation = br2;
 892     n2->birth_rotation = br1;
 893
 894     if (n1->vacant != n2->vacant) {
 895         update_vacant_state(n1->parent);
 896         update_vacant_state(n2->parent);
 897     }
 898
 899     if (d1 != d2) {
 900         if (d1->root == n1)
 901             d1->root = n2;
 902         if (d1->focus == n1)
 903             d1->focus = n2;
 904         if (d2->root == n2)
 905             d2->root = n1;
 906         if (d2->focus == n2)
 907             d2->focus = n1;
 908
 909         if (m1 != m2) {
 910             fit_monitor(m1, n2->client);
 911             fit_monitor(m2, n1->client);
 912         }
 913
 914         ewmh_set_wm_desktop(n1, d2);
 915         ewmh_set_wm_desktop(n2, d1);
 916         history_swap_nodes(m1, d1, n1, m2, d2, n2);
 917
 918         if (m1->desk != d1 && m2->desk == d2) {
 919             window_show(n1->client->window);
 920             window_hide(n2->client->window);
 921         } else if (m1->desk == d1 && m2->desk != d2) {
 922             window_hide(n1->client->window);
 923             window_show(n2->client->window);
 924         }
 925
 926         tag_node(m1, d1, n2, d2, n2->client->tags_field);
 927         tag_node(m2, d2, n1, d1, n1->client->tags_field);
 928
 929         update_input_focus();
 930     }
 931
 932     return true;
 933 }
 934
 935 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd)
 936 {
 937     if (ns == NULL || ns == nd || (sticky_still && ns->client->sticky))
 938         return false;
 939
 940     PRINTF("transfer node %X\n", ns->client->window);
 941
 942     bool focused = (ns == mon->desk->focus);
 943     bool active = (ns == ds->focus);
 944
 945     if (focused)
 946         clear_input_focus();
 947
 948     unlink_node(ms, ds, ns);
 949     insert_node(md, dd, ns, nd);
 950
 951     if (md != ms)
 952         fit_monitor(md, ns->client);
 953
 954     if (ds != dd) {
 955         ewmh_set_wm_desktop(ns, dd);
 956         if (!ns->client->sticky) {
 957             if (ds == ms->desk && dd != md->desk)
 958                 window_hide(ns->client->window);
 959             else if (ds != ms->desk && dd == md->desk)
 960                 window_show(ns->client->window);
 961         }
 962     }
 963
 964     history_transfer_node(md, dd, ns);
 965     stack_under(ns);
 966
 967     if (ds == dd) {
 968         if (focused)
 969             focus_node(md, dd, ns);
 970         else if (active)
 971             pseudo_focus(dd, ns);
 972     } else {
 973         if (focused)
 974             update_current();
 975         else if (ns == mon->desk->focus)
 976             update_input_focus();
 977     }
 978
 979     tag_node(md, dd, ns, ds, ns->client->tags_field);
 980     arrange(ms, ds);
 981     if (ds != dd)
 982         arrange(md, dd);
 983
 984     return true;
 985 }
 986
 987 node_t *closest_node(desktop_t *d, node_t *n, cycle_dir_t dir, client_select_t sel)
 988 {
 989     if (n == NULL)
 990         return NULL;
 991
 992     node_t *f = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
 993     if (f == NULL)
 994         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 995
 996     while (f != n) {
 997         if (node_matches(n, f, sel))
 998             return f;
 999         f = (dir == CYCLE_PREV ? prev_leaf(f, d->root) : next_leaf(f, d->root));
1000         if (f == NULL)
1001             f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
1002     }
1003     return NULL;
1004 }
1005
1006 void circulate_leaves(monitor_t *m, desktop_t *d, circulate_dir_t dir)
1007 {
1008     if (d == NULL || d->root == NULL || d->focus == NULL || is_leaf(d->root))
1009         return;
1010     node_t *p = d->focus->parent;
1011     bool focus_first_child = is_first_child(d->focus);
1012     node_t *head, *tail;
1013     for (head = first_extrema(d->root); head != NULL && !is_visible(d, head); head = next_leaf(head, d->root))
1014         ;
1015     for (tail = second_extrema(d->root); tail != NULL && !is_visible(d, tail); tail = prev_leaf(tail, d->root))
1016         ;
1017     if (head == tail)
1018         return;
1019     if (dir == CIRCULATE_FORWARD)
1020         for (node_t *s = tail, *f = prev_visible_leaf(d, s, d->root); f != NULL; s = prev_visible_leaf(d, f, d->root), f = prev_visible_leaf(d, s, d->root))
1021             swap_nodes(m, d, f, m, d, s);
1022     else
1023         for (node_t *f = head, *s = next_visible_leaf(d, f, d->root); s != NULL; f = next_visible_leaf(d, s, d->root), s = next_visible_leaf(d, f, d->root))
1024             swap_nodes(m, d, f, m, d, s);
1025     if (focus_first_child)
1026         focus_node(m, d, p->first_child);
1027     else
1028         focus_node(m, d, p->second_child);
1029 }
1030
1031 void update_vacant_state(node_t *n)
1032 {
1033     if (n == NULL)
1034         return;
1035
1036     PUTS("update vacant state");
1037
1038     /* n is not a leaf */
1039     node_t *p = n;
1040
1041     while (p != NULL) {
1042         p->vacant = (p->first_child->vacant && p->second_child->vacant);
1043         p = p->parent;
1044     }
1045 }