Phosphor
Qt6 / Wayland library suite for window-management tools
Loading...
Searching...
No Matches
SplitTree.h
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2026 fuddlesworth
2// SPDX-License-Identifier: LGPL-2.1-or-later
3
4#pragma once
5
6#include "phosphortiles_export.h"
7
8#include "AutotileConstants.h"
9
10#include <QRect>
11#include <QString>
12#include <QStringList>
13#include <QVector>
14
15#include <memory>
16
17namespace PhosphorTiles {
18
25struct PHOSPHORTILES_EXPORT SplitNode
26{
28 bool splitHorizontal = false;
29 std::unique_ptr<SplitNode> first;
30 std::unique_ptr<SplitNode> second;
31 SplitNode* parent = nullptr;
32 QString windowId;
33
34 bool isLeaf() const
35 {
36 return !first && !second;
37 }
38};
39
56class PHOSPHORTILES_EXPORT SplitTree
57{
58public:
65 enum class Edge {
66 Left,
67 Right,
68 Top,
69 Bottom
70 };
71
74
76 SplitTree(SplitTree&& other) noexcept;
77
79 SplitTree& operator=(SplitTree&& other) noexcept;
80
82
83 // Non-copyable (unique_ptr members)
84 SplitTree(const SplitTree&) = delete;
85 SplitTree& operator=(const SplitTree&) = delete;
86
87 // ═══════════════════════════════════════════════════════════════════════
88 // Queries
89 // ═══════════════════════════════════════════════════════════════════════
90
95 const SplitNode* root() const noexcept;
96 SplitNode* root() noexcept;
97
101 bool isEmpty() const noexcept;
102
106 int leafCount() const noexcept;
107
112 int treeHeight() const noexcept;
113
119 const SplitNode* leafForWindow(const QString& windowId) const;
120 SplitNode* leafForWindow(const QString& windowId);
121
126 QStringList leafOrder() const;
127
128 // ═══════════════════════════════════════════════════════════════════════
129 // Mutations
130 // ═══════════════════════════════════════════════════════════════════════
131
141 void insertAtFocused(const QString& windowId, const QString& focusedWindowId, qreal initialRatio = 0.0);
142
151 void insertAtEnd(const QString& windowId, qreal initialRatio = 0.0);
152
163 void insertAtPosition(const QString& windowId, int position, qreal initialRatio = 0.0);
164
169 void remove(const QString& windowId);
170
180 void swap(const QString& windowId1, const QString& windowId2);
181
200 bool swapLeaves(const QString& a, const QString& b);
201
207 void resizeSplit(const QString& windowId, qreal newRatio);
208
220 void resizeSplitNode(SplitNode* node, qreal newRatio);
221
239 const SplitNode* splitOwningEdge(const QString& windowId, Edge edge) const;
240 SplitNode* splitOwningEdge(const QString& windowId, Edge edge);
241
242 // ═══════════════════════════════════════════════════════════════════════
243 // Geometry
244 // ═══════════════════════════════════════════════════════════════════════
245
260 QVector<QRect> applyGeometry(const QRect& area, int innerGap) const;
261
271 bool rebuildFromOrder(const QStringList& tiledWindows,
272 qreal defaultSplitRatio = AutotileDefaults::DefaultSplitRatio);
273
274private:
275 enum class InsertReady {
276 Proceed,
277 Done,
278 Rejected
279 };
283 static constexpr int MaxRuntimeTreeDepth = AutotileDefaults::MaxRuntimeTreeDepth;
284
285 InsertReady prepareInsert(const QString& windowId);
286
288 void insertAtEndRaw(const QString& windowId, qreal initialRatio);
289
291 void insertAtEndImpl(const QString& windowId, qreal initialRatio);
292
293 std::unique_ptr<SplitNode> m_root;
294
295 SplitNode* findLeaf(SplitNode* node, const QString& windowId, int depth = 0) const;
296 const SplitNode* findLeaf(const SplitNode* node, const QString& windowId, int depth = 0) const;
297 SplitNode* leafAtIndex(SplitNode* node, int targetIndex, int& currentIndex, int depth = 0) const;
298 const SplitNode* leafAtIndex(const SplitNode* node, int targetIndex, int& currentIndex, int depth = 0) const;
299 SplitNode* rightmostLeaf(SplitNode* node) const;
300 const SplitNode* rightmostLeaf(const SplitNode* node) const;
301 void collectLeafOrder(const SplitNode* node, QStringList& order, int depth = 0) const;
302 int countLeaves(const SplitNode* node, int depth = 0) const;
303 void applyGeometryRecursive(const SplitNode* node, const QRect& rect, int innerGap, QVector<QRect>& zones,
304 int depth = 0) const;
305
306 static int subtreeHeight(const SplitNode* node, int depth = 0);
307 static void splitLeaf(SplitNode* leaf, const QString& newId, qreal ratio);
308};
309
310} // namespace PhosphorTiles
Algorithm-layer constants for the autotile/tile primitives.
int leafCount() const noexcept
Count the number of leaf nodes (windows).
bool rebuildFromOrder(const QStringList &tiledWindows, qreal defaultSplitRatio=AutotileDefaults::DefaultSplitRatio)
Rebuild tree from a new window order, preserving split ratios where possible.
SplitTree(SplitTree &&other) noexcept
Move constructor.
QStringList leafOrder() const
Get window IDs in depth-first left-to-right order.
bool swapLeaves(const QString &a, const QString &b)
Swap the stored window ids on two existing leaves.
const SplitNode * leafForWindow(const QString &windowId) const
Find the leaf node for a given window ID.
void remove(const QString &windowId)
Remove a window, collapsing its parent and promoting its sibling.
const SplitNode * root() const noexcept
Get the root node of the tree.
void swap(const QString &windowId1, const QString &windowId2)
Swap two windows' positions in the tree.
SplitTree & operator=(const SplitTree &)=delete
Edge
A geometric edge of a window's rectangle.
Definition SplitTree.h:65
void insertAtPosition(const QString &windowId, int position, qreal initialRatio=0.0)
Insert a window by splitting the leaf at a given position.
SplitTree & operator=(SplitTree &&other) noexcept
Move assignment.
bool isEmpty() const noexcept
Check if the tree has no nodes.
int treeHeight() const noexcept
Get the maximum height of the tree.
SplitTree()
Construct an empty tree (no root).
void insertAtFocused(const QString &windowId, const QString &focusedWindowId, qreal initialRatio=0.0)
Insert a window by splitting the focused window's leaf.
SplitTree(const SplitTree &)=delete
const SplitNode * splitOwningEdge(const QString &windowId, Edge edge) const
Find the ancestor split whose division line is collinear with a given edge of a leaf window.
void resizeSplitNode(SplitNode *node, qreal newRatio)
Set the split ratio on a specific internal node.
void resizeSplit(const QString &windowId, qreal newRatio)
Adjust the split ratio of a window's parent node.
void insertAtEnd(const QString &windowId, qreal initialRatio=0.0)
Insert a window by splitting the rightmost leaf.
QVector< QRect > applyGeometry(const QRect &area, int innerGap) const
Compute zone rectangles by recursively splitting the area.
Auto-tiling algorithm defaults.
Definition AutotileConstants.h:36
constexpr qreal DefaultSplitRatio
50/50 split when nothing else specified
Definition AutotileConstants.h:41
constexpr int MaxRuntimeTreeDepth
Maximum recursion depth for split tree operations.
Definition AutotileConstants.h:94
Definition AutotileEngine.h:52
A single node in the binary split tree.
Definition SplitTree.h:26
std::unique_ptr< SplitNode > second
Second child (right or bottom).
Definition SplitTree.h:30
bool splitHorizontal
true = top/bottom, false = left/right
Definition SplitTree.h:28
bool isLeaf() const
Definition SplitTree.h:34
std::unique_ptr< SplitNode > first
First child (left or top).
Definition SplitTree.h:29
SplitNode * parent
Non-owning back-pointer.
Definition SplitTree.h:31
qreal splitRatio
How to divide this node's space (first child fraction).
Definition SplitTree.h:27
QString windowId
Non-empty only for leaf nodes.
Definition SplitTree.h:32