1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtQuick module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "areaallocator_p.h"
41
42#include <QtCore/qglobal.h>
43#include <QtCore/qrect.h>
44#include <QtCore/qpoint.h>
45
46//
47// This file is copied from qtdeclarative/src/quick/scenegraph/util/qsgareaallocator.cpp
48//
49
50QT_BEGIN_NAMESPACE
51
52namespace Qt3DExtras {
53
54namespace
55{
56 enum SplitType
57 {
58 VerticalSplit,
59 HorizontalSplit
60 };
61
62 static const int maxMargin = 2;
63}
64
65struct AreaAllocatorNode
66{
67 AreaAllocatorNode(AreaAllocatorNode *parent);
68 ~AreaAllocatorNode();
69 inline bool isLeaf();
70
71 AreaAllocatorNode *parent;
72 AreaAllocatorNode *left;
73 AreaAllocatorNode *right;
74 int split; // only valid for inner nodes.
75 SplitType splitType;
76 bool isOccupied; // only valid for leaf nodes.
77};
78
79AreaAllocatorNode::AreaAllocatorNode(AreaAllocatorNode *parent)
80 : parent(parent)
81 , left(0)
82 , right(0)
83 , isOccupied(false)
84{
85}
86
87AreaAllocatorNode::~AreaAllocatorNode()
88{
89 delete left;
90 delete right;
91}
92
93bool AreaAllocatorNode::isLeaf()
94{
95 Q_ASSERT((left != 0) == (right != 0));
96 return !left;
97}
98
99
100AreaAllocator::AreaAllocator(const QSize &size) : m_size(size)
101{
102 m_root = new AreaAllocatorNode(0);
103}
104
105AreaAllocator::~AreaAllocator()
106{
107 delete m_root;
108}
109
110QRect AreaAllocator::allocate(const QSize &size)
111{
112 QPoint point;
113 bool result = allocateInNode(size, result&: point, currentRect: QRect(QPoint(0, 0), m_size), node: m_root);
114 return result ? QRect(point, size) : QRect();
115}
116
117bool AreaAllocator::deallocate(const QRect &rect)
118{
119 return deallocateInNode(pos: rect.topLeft(), node: m_root);
120}
121
122bool AreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, AreaAllocatorNode *node)
123{
124 if (size.width() > currentRect.width() || size.height() > currentRect.height())
125 return false;
126
127 if (node->isLeaf()) {
128 if (node->isOccupied)
129 return false;
130 if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) {
131 //Snug fit, occupy entire rectangle.
132 node->isOccupied = true;
133 result = currentRect.topLeft();
134 return true;
135 }
136 // TODO: Reuse nodes.
137 // Split node.
138 node->left = new AreaAllocatorNode(node);
139 node->right = new AreaAllocatorNode(node);
140 QRect splitRect = currentRect;
141 if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) {
142 node->splitType = HorizontalSplit;
143 node->split = currentRect.top() + size.height();
144 splitRect.setHeight(size.height());
145 } else {
146 node->splitType = VerticalSplit;
147 node->split = currentRect.left() + size.width();
148 splitRect.setWidth(size.width());
149 }
150 return allocateInNode(size, result, currentRect: splitRect, node: node->left);
151 } else {
152 // TODO: avoid unnecessary recursion.
153 // has been split.
154 QRect leftRect = currentRect;
155 QRect rightRect = currentRect;
156 if (node->splitType == HorizontalSplit) {
157 leftRect.setHeight(node->split - leftRect.top());
158 rightRect.setTop(node->split);
159 } else {
160 leftRect.setWidth(node->split - leftRect.left());
161 rightRect.setLeft(node->split);
162 }
163 if (allocateInNode(size, result, currentRect: leftRect, node: node->left))
164 return true;
165 if (allocateInNode(size, result, currentRect: rightRect, node: node->right))
166 return true;
167 return false;
168 }
169}
170
171bool AreaAllocator::deallocateInNode(const QPoint &pos, AreaAllocatorNode *node)
172{
173 while (!node->isLeaf()) {
174 // has been split.
175 int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
176 node = cmp < node->split ? node->left : node->right;
177 }
178 if (!node->isOccupied)
179 return false;
180 node->isOccupied = false;
181 mergeNodeWithNeighbors(node);
182 return true;
183}
184
185void AreaAllocator::mergeNodeWithNeighbors(AreaAllocatorNode *node)
186{
187 bool done = false;
188 AreaAllocatorNode *parent = 0;
189 AreaAllocatorNode *current = 0;
190 AreaAllocatorNode *sibling;
191 while (!done) {
192 Q_ASSERT(node->isLeaf());
193 Q_ASSERT(!node->isOccupied);
194 if (node->parent == 0)
195 return; // No neighbors.
196
197 SplitType splitType = SplitType(node->parent->splitType);
198 done = true;
199
200 /* Special case. Might be faster than going through the general code path.
201 // Merge with sibling.
202 parent = node->parent;
203 sibling = (node == parent->left ? parent->right : parent->left);
204 if (sibling->isLeaf() && !sibling->isOccupied) {
205 Q_ASSERT(!sibling->right);
206 node = parent;
207 parent->isOccupied = false;
208 delete parent->left;
209 delete parent->right;
210 parent->left = parent->right = 0;
211 done = false;
212 continue;
213 }
214 */
215
216 // Merge with left neighbor.
217 current = node;
218 parent = current->parent;
219 while (parent && current == parent->left && parent->splitType == splitType) {
220 current = parent;
221 parent = parent->parent;
222 }
223
224 if (parent && parent->splitType == splitType) {
225 Q_ASSERT(current == parent->right);
226 Q_ASSERT(parent->left);
227
228 AreaAllocatorNode *neighbor = parent->left;
229 while (neighbor->right && neighbor->splitType == splitType)
230 neighbor = neighbor->right;
231
232 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
233 // Left neighbor can be merged.
234 parent->split = neighbor->parent->split;
235
236 parent = neighbor->parent;
237 sibling = neighbor == parent->left ? parent->right : parent->left;
238 AreaAllocatorNode **nodeRef = &m_root;
239 if (parent->parent) {
240 if (parent == parent->parent->left)
241 nodeRef = &parent->parent->left;
242 else
243 nodeRef = &parent->parent->right;
244 }
245 sibling->parent = parent->parent;
246 *nodeRef = sibling;
247 parent->left = parent->right = 0;
248 delete parent;
249 delete neighbor;
250 done = false;
251 }
252 }
253
254 // Merge with right neighbor.
255 current = node;
256 parent = current->parent;
257 while (parent && current == parent->right && parent->splitType == splitType) {
258 current = parent;
259 parent = parent->parent;
260 }
261
262 if (parent && parent->splitType == splitType) {
263 Q_ASSERT(current == parent->left);
264 Q_ASSERT(parent->right);
265
266 AreaAllocatorNode *neighbor = parent->right;
267 while (neighbor->left && neighbor->splitType == splitType)
268 neighbor = neighbor->left;
269
270 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
271 // Right neighbor can be merged.
272 parent->split = neighbor->parent->split;
273
274 parent = neighbor->parent;
275 sibling = neighbor == parent->left ? parent->right : parent->left;
276 AreaAllocatorNode **nodeRef = &m_root;
277 if (parent->parent) {
278 if (parent == parent->parent->left)
279 nodeRef = &parent->parent->left;
280 else
281 nodeRef = &parent->parent->right;
282 }
283 sibling->parent = parent->parent;
284 *nodeRef = sibling;
285 parent->left = parent->right = 0;
286 delete parent;
287 delete neighbor;
288 done = false;
289 }
290 }
291 } // end while (!done)
292}
293
294} // namespace Qt3DExtras
295
296QT_END_NAMESPACE
297

source code of qt3d/src/extras/text/areaallocator.cpp