tree.c

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