Dynamic Programming in Window Management
After my junior year of college, I thought it was fitting to revisit my window manager,
berry, and apply some of the concepts I had learned over the past year.
Last winter, I took an algorithms class and was interested in using dynamic programming to make
efficient algorithms that improved the usability of my window manager.
The Problem
The goal of this project is smart window placement. When a new window is created, where should it be placed for maximum efficiency? A natural definition of efficiency in this case is any place on the screen in which the new window does not overlap with existing windows.
Algorithm I: Maximal Square
Our first step is to think of a way to represent the computer screen. A 2-D matrix is a natural first step, where each cell represents the pixel at that location. For simplicity, cells that overlap with a window will be marked as 0, whereas empty pixels will be marked as 1.
Given a simple 5x5 screen with one window, we could visualize it with a matrix \(M\) as such:
\[M = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}\]In order to intuitively place at new window we want to find the largest unoccupied submatrix within \(M\). There is an elegant dynamic programming solution which runs in linear time with respect to the matrix dimensions.
First, let us construct a new matrix, \(OPT\) that has dimensions identical to that of \(M\). Each value of \({OPT}\) will represent the largest submatrix that can be created with that cell as the bottom righthand corner of the square.
We initialize the first row and column of \(OPT\) to the values in the first row and column of \(M\) - the largest square you can make in one dimension is just the value at that cell (either 0 or 1).
Initially, \(M\) and \(OPT\) appear as below:
\[M=\begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} OPT = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & - & - & - & - \\ 1 & - & - & - & - \\ 1 & - & - & - & - \\ 1 & - & - & - & - \end{bmatrix}\]The next step is to find the value at the intersection of the second row and column of \(OPT\). There are two general cases to consider here. If the value of \(M\) is 0, then the value in \(OPT\) must also be 0 since that cell cannot be part of square. If the value of \(M\) is 1, then the value of \(OPT\) depends on that of its neighbors. More specifically, the value of \(OPT[i, j]\) depends on that of \(OPT[i-1, j]\), \(OPT[i, j-1]\), and \(OPT[i-1, j-1]\). If all three values are the same, then \(OPT[i, j]\) can now extend all three of those squares, making a square with an area one greater than all of those neighbors. If the values are different, \(OPT[i, j]\) can extend only the square with the smallest area, as the smallest area square must be contained in the others.
This leads to the following function with which to determine \(OPT[i, j]\)
\[OPT[i,j] = \begin{cases} 0 & \text{if } M[i, j] = 0 \\ MIN(OPT[i-1,j], OPT[i,j-1], OPT[i-1,j-1]) + 1 & \text{ otherwise } \\ \end{cases}\]Given that this function relies on the values of \(OPT[i-1, j]\) and \(OPT[i-1,j-1]\) we can fill in the values of \(OPT\) by traversing left to right, top to bottom. This yields the following algorithm which returns the largest possible square submatrix in a given matrix \(M\).
MAXIMAL_SUBSQUARE(M):
create a matrix OPT with dimensions of M
initialize first row and col of OPT to that of M
max = 0
for i in each row of OPT:
for j in each col of OPT:
if M[i, j] == 0:
OPT[i, j] = 0
else:
OPT[i, j] = MIN(OPT[i-1,j], OPT[i,j-1], OPT[i-1,j-1]) + 1
max = MAX(max, OPT[i, j])
return max
The given algorithm runs in \(O(nm)\) where \(n\) and \(m\) are the dimensions of the given matrix.
In practice, however, the given algorithm does only an adequate job of intuitively placing windows
on a given desktop.
In particular, MAXIMAL_SUBSQUARE ignores the dimensions of the given window to be created
and may in fact place windows over one another if the returned max is less than the width or height
of the new window.
Additionally, MAXIMAL_SUBSQUARE cannot detect large free rectangular regions which might be a good
fit for the new window.
Algorithm II: Modified Maximal Rectangle
There is a well known linear time dynamic programming algorithm which finds the area of the largest rectangle in a given matrix \(M\). In its most general state, however, the algorithm will not work for our use case. To see why, consider the following matrix:
\[M = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{bmatrix}\]The largest rectangle in this matrix has area 5 and is created using only the bottom row of \(M\). But it is unlikely that a newly created window will have such wide dimensions, even if it requests an area less than or equal to 5. Instead, we need an algorithm that will find the best region to fit a window of dimension \(x\) and \(y\).
However, this algorithm might help us reach a more optimal solution. The first step in the maximal rectangle problem is creating an \(OPT\) matrix where each row represents the free space \textit{above} that given pixel. To see how this works, consider a matrix with only two rows:
\[M = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}\]When constructing an \(OPT\) matrix, the first row is the same. But the second row is now a summary of how much free space exists in all rows above it. So for the given \(M\), we would construct the following \(OPT\):
\[M = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} \implies OPT = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 2 & 2 & 0 \end{bmatrix}\]This leads to the following piecewise function with which to develop \(OPT\):
\[OPT[i,j] = \begin{cases} 0 & \text{ if } M[i,j] = 0 \\ OPT[i-1,j] + 1 & \text{ otherwise } \end{cases}\]This yields the following algorithm which will populate \(OPT\)
HISTOGRAM(M):
create a matrix OPT with dimensions of M
initialize first row of OPT to that of M
for i in each row of OPT:
for j in each col of OPT:
if M[i, j] = 0:
OPT[i, j] = 0
else:
OPT[i, j] = 1 + OPT[i-1, j]
return OPT
Now there is a question of where does our window fit within \(OPT\)? My initial thought was to use a sliding window algorithm. But the solution is even more simple. We can simple traverse \(OPT\) until we find a sequence of cells in which the height is greater than or equal to the height of our new window. This has the distinct advantage of not depending on the width of the window we are trying to place.
The following traceback algorithm will place a window at the first location which meets the size requirement.
TRACEBACK(OPT, x, y):
count = 0
for i in each row of OPT:
for j in each col of OPT:
while OPT[i, j] >= y
i++
count++
if count == x
return i, j
return -1, there is not enough free space
Implementation
The first step in implementation is creating a matrix which represents the current workspace. Originally I had planned to use two matrices: a boolean matrix \(M\) which represents used and unused pixels, and an integer matrix \(OPT\) which is used to find optimal window placement. Soon after I started programming, however, I realized that we only actually need one matrix - \(OPT\). The contents of \(M\) are only used to initially build \(OPT\), and we never need to revisit its state after \(OPT\) has been created.
berry stores windows in a linked list, so we can traverse all active clients and add them to the matrix.
Additionally, I realized that a full 1920x1080 matrix is probably overkill for this problem.
So I added a constant, PLACE_RES, which groups pixels together.
By default, PLACE_RES is set to 10.
static void
client_place(struct client *c)
{
uint16_t opt[height][width];
for (struct client *tmp = f_list[curr_ws]; tmp != NULL; tmp = tmp->next) {
if (tmp != c) {
struct client_geom *geom = &tmp->geom;
for (int i = geom->y / PLACE_RES; i < (geom->y / PLACE_RES) + (geom->height / PLACE_RES); i++) {
for (int j = geom->x / PLACE_RES; k < (geom->x / PLACE_RES) + (geom->width / PLACE_RES); j++) {
opt[i][j] = 0;
}
}
}
}
The next step is filling in \(OPT\) using the formula stated above:
...
for (int i = 1; i < height; i++) {
for (int j = 0; j < width; j++) {
if (opt[i][j] != 0)
opt[i][j] = opt[i-1][j] + 1
}
}
Now there is the matter of finding the best place to put our new window. Originally I had planned to traverse \(OPT\) like we have been this whole time, from the top row down and left to right. But this has the consequence of finding a space which perfectly fits the client inside of it. Although this might seem space efficient it tends to shove windows into the corners and leave gaps between windows which are too small to be useful anyway. Instead, I decided to traverse bottom to top, left to right. This gives us the advantage of being able to center, both vertically and horizontally, our client inside the given space. I implemented it as follows:
int count = 1;
int min_height = INT_MAX;
for (int i = height - 1; i >= 0; i--) {
for (int j = 0; j < width; j++) {
while (j < widt && opt[i][j] >= c->geom.height / PLACE_RES) {
min_height = MIN(min_height, opt[i][j]);
count++;
j++;
}
if (count >= c->geom.width / PLACE_RES) {
client_center_in_rect(c, (j - count) * PLACE_RES, (i - min_height) * PLACE_RES,
count * PLACE_RES, min_height * PLACE_RES);
return;
}
count = 0;
}
}
Results
The algorithm ended up working just as I had wanted. Now \verb|berry| is able to intuitively place windows in large open spaces, which is especially useful for one-off tasks or running quick terminal commands.
If you are interested in seeing the full implementation, the project is available on my github.
The respective function, client_place, can be found here.