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