We forgot to count the dock in LeastOverlap
[dana/openbox.git] / openbox / keytree.c
1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
2
3    keytree.c for the Openbox window manager
4    Copyright (c) 2006        Mikael Magnusson
5    Copyright (c) 2003-2007   Dana Jansens
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    See the COPYING file for a copy of the GNU General Public License.
18 */
19
20 #include "keyboard.h"
21 #include "translate.h"
22 #include "actions.h"
23 #include <glib.h>
24
25 void tree_destroy(KeyBindingTree *tree)
26 {
27     KeyBindingTree *c;
28
29     while (tree) {
30         tree_destroy(tree->next_sibling);
31         c = tree->first_child;
32         if (c == NULL) {
33             GList *it;
34             GSList *sit;
35             for (it = tree->keylist; it != NULL; it = it->next)
36                 g_free(it->data);
37             g_list_free(tree->keylist);
38             for (sit = tree->actions; sit != NULL; sit = sit->next)
39                 actions_act_unref(sit->data);
40             g_slist_free(tree->actions);
41         }
42         g_slice_free(KeyBindingTree, tree);
43         tree = c;
44     }
45 }
46
47 KeyBindingTree *tree_build(GList *keylist)
48 {
49     GList *it;
50     KeyBindingTree *ret = NULL, *p;
51
52     if (g_list_length(keylist) <= 0)
53         return NULL; /* nothing in the list.. */
54
55     for (it = g_list_last(keylist); it; it = g_list_previous(it)) {
56         GList *kit;
57
58         p = ret;
59         ret = g_slice_new0(KeyBindingTree);
60
61         for (kit = it; kit != NULL; kit = g_list_previous(kit))
62             ret->keylist = g_list_prepend(ret->keylist,
63                                           g_strdup(kit->data)); /* deep copy */
64         ret->first_child = p;
65         if (p != NULL) p->parent = ret;
66         translate_key(it->data, &ret->state, &ret->key);
67     }
68     return ret;
69 }
70
71 void tree_assimilate(KeyBindingTree *node)
72 {
73     KeyBindingTree *a, *b, *tmp, *last;
74
75     if (keyboard_firstnode == NULL) {
76         /* there are no nodes at this level yet */
77         keyboard_firstnode = node;
78     } else {
79         a = keyboard_firstnode;
80         last = a;
81         b = node;
82         while (a) {
83             last = a;
84             /* check b->key != 0 for key bindings that didn't get translated */
85             if (!(a->state == b->state && a->key == b->key && b->key != 0)) {
86                 a = a->next_sibling;
87             } else {
88                 tmp = b;
89                 b = b->first_child;
90                 g_slice_free(KeyBindingTree, tmp);
91                 a = a->first_child;
92             }
93         }
94         /* check b->key != 0, and save key bindings that didn't get translated
95            as siblings here */
96         if (!(last->state == b->state && last->key == b->key && b->key != 0)) {
97             last->next_sibling = b;
98             b->parent = last->parent;
99         } else {
100             last->first_child = b->first_child;
101             last->first_child->parent = last;
102             g_slice_free(KeyBindingTree, b);
103         }
104     }
105 }
106
107 KeyBindingTree *tree_find(KeyBindingTree *search, gboolean *conflict)
108 {
109     KeyBindingTree *a, *b;
110
111     *conflict = FALSE;
112
113     a = keyboard_firstnode;
114     b = search;
115     while (a && b) {
116         /* check b->key != 0 for key bindings that didn't get translated, and
117            don't make them conflict with anything else so that they can all
118            live together in peace and harmony */
119         if (!(a->state == b->state && a->key == b->key && b->key != 0)) {
120             a = a->next_sibling;
121         } else {
122             if ((a->first_child == NULL) == (b->first_child == NULL)) {
123                 if (a->first_child == NULL) {
124                     /* found it! (return the actual node, not the search's) */
125                     return a;
126                 }
127             } else {
128                 *conflict = TRUE;
129                 return NULL; /* the chain status' don't match (conflict!) */
130             }
131             b = b->first_child;
132             a = a->first_child;
133         }
134     }
135     return NULL; /* it just isn't in here */
136 }
137
138 gboolean tree_chroot(KeyBindingTree *tree, GList *keylist)
139 {
140     guint key, state;
141     translate_key(keylist->data, &state, &key);
142     while (tree != NULL && !(tree->state == state && tree->key == key))
143         tree = tree->next_sibling;
144     if (tree != NULL) {
145         if (keylist->next == NULL) {
146             tree->chroot = TRUE;
147             return TRUE;
148         } else
149             return tree_chroot(tree->first_child, keylist->next);
150     }
151     return FALSE;
152 }