[gnome-shell] workspace: Sort windows to minimize travel distance

[Florian Müllner <fmuellner src gnome org>]

commit f50cac30051cd69aefa94a2c48378376ead21e63
Author: Sergey Bugaev <bugaevc gmail com>
Date:   Sat Oct 20 16:28:05 2018 +0300

    workspace: Sort windows to minimize travel distance
    
    When transitioning to or from the overview, windows travel
    a certain distance between their real desktop position and
    their place in the overview window grid. The less this travel
    distance is, the smoother, more polished, and less jarring
    the overall transition looks. This is why it makes sense to
    try reordering and repositioning windows to minimize their
    travel distance. That being said, there are other factors
    that impact the quality of the overview layout, such as how
    much the windows get scaled and what portion of the overall
    available space they take up.
    
    The existing code tries to minimize the travel distance by
    sorting the windows in each row by their horizontal position.
    There are, however, two problems with this implementation.
    First, it compares the coordinates of windows' left edges as
    opposed to their centers, which means it yields unexpected
    results when a small window is positioned next to the left
    edge of a large window. Second, it completely disregards
    vertical coordinates, instead assigning windows to the grid
    rows using their monotonically increasing window numbers,
    effectively vertically sorting them by the order they were
    created in.
    
    This commit changes both vertical and horizontal ordering
    to work based on the coordinates of the geometric centers
    of the windows. That is to say, windows are first assigned
    to grid rows based on the vertical coordinates of their
    centers, and subsequently sorted inside each row based on
    the horizontal coordinates of said centers. In my testing,
    this leads to a much more intuitive and visually pleasing
    window placement.
    
    Signed-off-by: Sergey Bugaev <bugaevc gmail com>
    
    https://gitlab.gnome.org/GNOME/gnome-shell/merge_requests/267

 js/ui/workspace.js | 27 +++++++++++++++++++--------
 1 file changed, 19 insertions(+), 8 deletions(-)
---
diff --git a/js/ui/workspace.js b/js/ui/workspace.js
index 7df297e7d3..95369997a0 100644
--- a/js/ui/workspace.js
+++ b/js/ui/workspace.js
@@ -736,10 +736,6 @@ var WindowPositionFlags = {
 // which rows, row sizes and other general state tracking that would make
 // calculating window positions from this information fairly easy.
 //
-// We don't compute some global order of windows right now for optimal
-// travel when animating into the overview; windows are assumed to be
-// in some stable order.
-//
 // After a layout is computed that's considered the best layout, we
 // compute the layout scale to fit it in the area, and then compute
 // slots (sizes and positions) for each thumbnail.
@@ -997,8 +993,13 @@ var UnalignedLayoutStrategy = class extends LayoutStrategy {
     }
 
     _sortRow(row) {
-        // Sort windows horizontally to minimize travel distance
-        row.windows.sort((a, b) => a.realWindow.x - b.realWindow.x);
+        // Sort windows horizontally to minimize travel distance.
+        // This affects in what order the windows end up in a row.
+        row.windows.sort((a, b) => {
+            let aCenter = a.realWindow.x + a.realWindow.width / 2;
+            let bCenter = b.realWindow.x + b.realWindow.width / 2;
+            return aCenter - bCenter;
+        });
     }
 
     computeLayout(windows, layout) {
@@ -1013,13 +1014,23 @@ var UnalignedLayoutStrategy = class extends LayoutStrategy {
         }
 
         let idealRowWidth = totalWidth / numRows;
+
+        // Sort windows vertically to minimize travel distance.
+        // This affects what rows the windows get placed in.
+        let sortedWindows = windows.slice();
+        sortedWindows.sort((a, b) => {
+            let aCenter = a.realWindow.y + a.realWindow.height / 2;
+            let bCenter = b.realWindow.y + b.realWindow.height / 2;
+            return aCenter - bCenter;
+        });
+
         let windowIdx = 0;
         for (let i = 0; i < numRows; i++) {
             let row = this._newRow();
             rows.push(row);
 
-            for (; windowIdx < windows.length; windowIdx++) {
-                let window = windows[windowIdx];
+            for (; windowIdx < sortedWindows.length; windowIdx++) {
+                let window = sortedWindows[windowIdx];
                 let s = this._computeWindowScale(window);
                 let width = window.width * s;
                 let height = window.height * s;