Add "next on monitor or empty" workspace parameter (#2198)

* Add "next on monitor or empty" workspace parameter

Implements the following workspace parameter:
r+x/r-x (i.e. r+1): Behaves similar to the "m" parameter, but can also
select empty workspaces and it doesn't wrap around

* Improve code comments

* Implementation V2 for 'r' workspace param

* Rebase to upstream

Should fix CI

* Always set outName

* Include named workspaces

Currently only considers open/active named workspaces

1 files changed, 135 insertions, 2 deletions

diff --git a/src/helpers/MiscFunctions.cpp b/src/helpers/MiscFunctions.cpp
index 5db59a64..dca24552 100644
--- a/src/helpers/MiscFunctions.cpp
+++ b/src/helpers/MiscFunctions.cpp
@@ -2,6 +2,7 @@
 #include "../defines.hpp"
 #include <algorithm>
 #include "../Compositor.hpp"
+#include <set>
 #include <sys/utsname.h>
 #include <iomanip>
 #include <sstream>
@@ -305,7 +306,140 @@ int getWorkspaceIDFromString(const std::string& in, std::string& outName) {
         outName = PLASTWORKSPACE->m_szName;
         return PLASTWORKSPACE->m_iID;
     } else {
-        if ((in[0] == 'm' || in[0] == 'e') && (in[1] == '-' || in[1] == '+') && isNumber(in.substr(2))) {
+        if (in[0] == 'r' && (in[1] == '-' || in[1] == '+') && isNumber(in.substr(2))) {
+            if (!g_pCompositor->m_pLastMonitor) {
+                Debug::log(ERR, "Relative monitor workspace on monitor null!");
+                result = INT_MAX;
+                return result;
+            }
+            result = (int)getPlusMinusKeywordResult(in.substr(1), 0);
+
+            int           remains = (int)result;
+
+            std::set<int> invalidWSes;
+
+            // Collect all the workspaces we can't jump to.
+            for (auto& ws : g_pCompositor->m_vWorkspaces) {
+                if (ws->m_bIsSpecialWorkspace || (ws->m_iMonitorID != g_pCompositor->m_pLastMonitor->ID)) {
+                    // Can't jump to this workspace
+                    invalidWSes.insert(ws->m_iID);
+                }
+            }
+            for (auto& rule : g_pConfigManager->getAllWorkspaceRules()) {
+                const auto PMONITOR = g_pCompositor->getMonitorFromName(rule.monitor);
+                if (!PMONITOR || PMONITOR->ID == g_pCompositor->m_pLastMonitor->ID) {
+                    // Can't be invalid
+                    continue;
+                }
+                // WS is bound to another monitor, can't jump to this
+                invalidWSes.insert(rule.workspaceId);
+            }
+
+            // Prepare all named workspaces in case when we need them
+            std::vector<int> namedWSes;
+            for (auto& ws : g_pCompositor->m_vWorkspaces) {
+                if (ws->m_bIsSpecialWorkspace || (ws->m_iMonitorID != g_pCompositor->m_pLastMonitor->ID) || ws->m_iID >= 0)
+                    continue;
+
+                namedWSes.push_back(ws->m_iID);
+            }
+            std::sort(namedWSes.begin(), namedWSes.end());
+
+            // Just take a blind guess at where we'll probably end up
+            int  predictedWSID = g_pCompositor->m_pLastMonitor->activeWorkspace + remains;
+            int  remainingWSes = 0;
+            char walkDir       = in[1];
+
+            // sanitize. 0 means invalid oob in -
+            predictedWSID = std::max(predictedWSID, 0);
+
+            // Count how many invalidWSes are in between (how bad the prediction was)
+            int  beginID = in[1] == '+' ? g_pCompositor->m_pLastMonitor->activeWorkspace + 1 : predictedWSID;
+            int  endID   = in[1] == '+' ? predictedWSID : g_pCompositor->m_pLastMonitor->activeWorkspace;
+            auto begin   = invalidWSes.upper_bound(beginID - 1); // upper_bound is >, we want >=
+            for (auto it = begin; *it <= endID && it != invalidWSes.end(); it++) {
+                remainingWSes++;
+            }
+
+            // Handle named workspaces. They are treated like always before other workspaces
+            if (g_pCompositor->m_pLastMonitor->activeWorkspace < 0) {
+                // Behaviour similar to 'm'
+                // Find current
+                int currentItem = -1;
+                for (size_t i = 0; i < namedWSes.size(); i++) {
+                    if (namedWSes[i] == g_pCompositor->m_pLastMonitor->activeWorkspace) {
+                        currentItem = i;
+                        break;
+                    }
+                }
+
+                currentItem += remains;
+                currentItem = std::max(currentItem, 0);
+                if (currentItem >= (int)namedWSes.size()) {
+                    // At the seam between namedWSes and normal WSes. Behave like r+[diff] at imaginary ws 0
+                    int diff      = currentItem - (namedWSes.size() - 1);
+                    predictedWSID = diff;
+                    int  beginID  = 1;
+                    int  endID    = predictedWSID;
+                    auto begin    = invalidWSes.upper_bound(beginID - 1); // upper_bound is >, we want >=
+                    for (auto it = begin; *it <= endID && it != invalidWSes.end(); it++) {
+                        remainingWSes++;
+                    }
+                    walkDir = '+';
+                } else {
+                    // We found our final ws.
+                    remainingWSes = 0;
+                    predictedWSID = namedWSes[currentItem];
+                }
+            }
+
+            // Go in the search direction for remainingWSes
+            // The performance impact is directly proportional to the number of open and bound workspaces
+            int finalWSID = predictedWSID;
+            if (walkDir == '-') {
+                int beginID = finalWSID;
+                int curID   = finalWSID;
+                while (--curID > 0 && remainingWSes > 0) {
+                    if (invalidWSes.find(curID) == invalidWSes.end()) {
+                        remainingWSes--;
+                    }
+                    finalWSID = curID;
+                }
+                if (finalWSID <= 0 || invalidWSes.find(finalWSID) != invalidWSes.end()) {
+                    if (namedWSes.size()) {
+                        // Go to the named workspaces
+                        // Need remainingWSes more
+                        int namedWSIdx = namedWSes.size() - remainingWSes;
+                        // Sanitze
+                        namedWSIdx = std::clamp(namedWSIdx, 0, (int)namedWSes.size() - 1);
+                        finalWSID  = namedWSes[namedWSIdx];
+                    } else {
+                        // Couldn't find valid workspace in negative direction, search last first one back up positive direction
+                        walkDir = '+';
+                        // We know, that everything less than beginID is invalid, so don't bother with that
+                        finalWSID     = beginID;
+                        remainingWSes = 1;
+                    }
+                }
+            }
+            if (walkDir == '+') {
+                int curID = finalWSID;
+                while (++curID < INT32_MAX && remainingWSes > 0) {
+                    if (invalidWSes.find(curID) == invalidWSes.end()) {
+                        remainingWSes--;
+                    }
+                    finalWSID = curID;
+                }
+            }
+
+            result                = finalWSID;
+            const auto PWORKSPACE = g_pCompositor->getWorkspaceByID(result);
+            if (PWORKSPACE)
+                outName = g_pCompositor->getWorkspaceByID(result)->m_szName;
+            else
+                outName = std::to_string(finalWSID);
+
+        } else if ((in[0] == 'm' || in[0] == 'e') && (in[1] == '-' || in[1] == '+') && isNumber(in.substr(2))) {
             bool onAllMonitors = in[0] == 'e';
 
             if (!g_pCompositor->m_pLastMonitor) {
@@ -354,7 +488,6 @@ int getWorkspaceIDFromString(const std::string& in, std::string& outName) {
 
             result  = validWSes[currentItem];
             outName = g_pCompositor->getWorkspaceByID(validWSes[currentItem])->m_szName;
-
         } else {
             if (in[0] == '+' || in[0] == '-') {
                 if (g_pCompositor->m_pLastMonitor)