tree.c

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