summaryrefslogtreecommitdiffstats
path: root/src/extras/text/areaallocator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/extras/text/areaallocator.cpp')
-rw-r--r--src/extras/text/areaallocator.cpp296
1 files changed, 296 insertions, 0 deletions
diff --git a/src/extras/text/areaallocator.cpp b/src/extras/text/areaallocator.cpp
new file mode 100644
index 000000000..61f1d5bc6
--- /dev/null
+++ b/src/extras/text/areaallocator.cpp
@@ -0,0 +1,296 @@
+/****************************************************************************
+**
+** Copyright (C) 2016 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtQuick module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "areaallocator_p.h"
+
+#include <QtCore/qglobal.h>
+#include <QtCore/qrect.h>
+#include <QtCore/qpoint.h>
+
+//
+// This file is copied from qtdeclarative/src/quick/scenegraph/util/qsgareaallocator.cpp
+//
+
+QT_BEGIN_NAMESPACE
+
+namespace Qt3DExtras {
+
+namespace
+{
+ enum SplitType
+ {
+ VerticalSplit,
+ HorizontalSplit
+ };
+
+ static const int maxMargin = 2;
+}
+
+struct AreaAllocatorNode
+{
+ AreaAllocatorNode(AreaAllocatorNode *parent);
+ ~AreaAllocatorNode();
+ inline bool isLeaf();
+
+ AreaAllocatorNode *parent;
+ AreaAllocatorNode *left;
+ AreaAllocatorNode *right;
+ int split; // only valid for inner nodes.
+ SplitType splitType;
+ bool isOccupied; // only valid for leaf nodes.
+};
+
+AreaAllocatorNode::AreaAllocatorNode(AreaAllocatorNode *parent)
+ : parent(parent)
+ , left(0)
+ , right(0)
+ , isOccupied(false)
+{
+}
+
+AreaAllocatorNode::~AreaAllocatorNode()
+{
+ delete left;
+ delete right;
+}
+
+bool AreaAllocatorNode::isLeaf()
+{
+ Q_ASSERT((left != 0) == (right != 0));
+ return !left;
+}
+
+
+AreaAllocator::AreaAllocator(const QSize &size) : m_size(size)
+{
+ m_root = new AreaAllocatorNode(0);
+}
+
+AreaAllocator::~AreaAllocator()
+{
+ delete m_root;
+}
+
+QRect AreaAllocator::allocate(const QSize &size)
+{
+ QPoint point;
+ bool result = allocateInNode(size, point, QRect(QPoint(0, 0), m_size), m_root);
+ return result ? QRect(point, size) : QRect();
+}
+
+bool AreaAllocator::deallocate(const QRect &rect)
+{
+ return deallocateInNode(rect.topLeft(), m_root);
+}
+
+bool AreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, AreaAllocatorNode *node)
+{
+ if (size.width() > currentRect.width() || size.height() > currentRect.height())
+ return false;
+
+ if (node->isLeaf()) {
+ if (node->isOccupied)
+ return false;
+ if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) {
+ //Snug fit, occupy entire rectangle.
+ node->isOccupied = true;
+ result = currentRect.topLeft();
+ return true;
+ }
+ // TODO: Reuse nodes.
+ // Split node.
+ node->left = new AreaAllocatorNode(node);
+ node->right = new AreaAllocatorNode(node);
+ QRect splitRect = currentRect;
+ if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) {
+ node->splitType = HorizontalSplit;
+ node->split = currentRect.top() + size.height();
+ splitRect.setHeight(size.height());
+ } else {
+ node->splitType = VerticalSplit;
+ node->split = currentRect.left() + size.width();
+ splitRect.setWidth(size.width());
+ }
+ return allocateInNode(size, result, splitRect, node->left);
+ } else {
+ // TODO: avoid unnecessary recursion.
+ // has been split.
+ QRect leftRect = currentRect;
+ QRect rightRect = currentRect;
+ if (node->splitType == HorizontalSplit) {
+ leftRect.setHeight(node->split - leftRect.top());
+ rightRect.setTop(node->split);
+ } else {
+ leftRect.setWidth(node->split - leftRect.left());
+ rightRect.setLeft(node->split);
+ }
+ if (allocateInNode(size, result, leftRect, node->left))
+ return true;
+ if (allocateInNode(size, result, rightRect, node->right))
+ return true;
+ return false;
+ }
+}
+
+bool AreaAllocator::deallocateInNode(const QPoint &pos, AreaAllocatorNode *node)
+{
+ while (!node->isLeaf()) {
+ // has been split.
+ int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
+ node = cmp < node->split ? node->left : node->right;
+ }
+ if (!node->isOccupied)
+ return false;
+ node->isOccupied = false;
+ mergeNodeWithNeighbors(node);
+ return true;
+}
+
+void AreaAllocator::mergeNodeWithNeighbors(AreaAllocatorNode *node)
+{
+ bool done = false;
+ AreaAllocatorNode *parent = 0;
+ AreaAllocatorNode *current = 0;
+ AreaAllocatorNode *sibling;
+ while (!done) {
+ Q_ASSERT(node->isLeaf());
+ Q_ASSERT(!node->isOccupied);
+ if (node->parent == 0)
+ return; // No neighbors.
+
+ SplitType splitType = SplitType(node->parent->splitType);
+ done = true;
+
+ /* Special case. Might be faster than going through the general code path.
+ // Merge with sibling.
+ parent = node->parent;
+ sibling = (node == parent->left ? parent->right : parent->left);
+ if (sibling->isLeaf() && !sibling->isOccupied) {
+ Q_ASSERT(!sibling->right);
+ node = parent;
+ parent->isOccupied = false;
+ delete parent->left;
+ delete parent->right;
+ parent->left = parent->right = 0;
+ done = false;
+ continue;
+ }
+ */
+
+ // Merge with left neighbor.
+ current = node;
+ parent = current->parent;
+ while (parent && current == parent->left && parent->splitType == splitType) {
+ current = parent;
+ parent = parent->parent;
+ }
+
+ if (parent && parent->splitType == splitType) {
+ Q_ASSERT(current == parent->right);
+ Q_ASSERT(parent->left);
+
+ AreaAllocatorNode *neighbor = parent->left;
+ while (neighbor->right && neighbor->splitType == splitType)
+ neighbor = neighbor->right;
+
+ if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
+ // Left neighbor can be merged.
+ parent->split = neighbor->parent->split;
+
+ parent = neighbor->parent;
+ sibling = neighbor == parent->left ? parent->right : parent->left;
+ AreaAllocatorNode **nodeRef = &m_root;
+ if (parent->parent) {
+ if (parent == parent->parent->left)
+ nodeRef = &parent->parent->left;
+ else
+ nodeRef = &parent->parent->right;
+ }
+ sibling->parent = parent->parent;
+ *nodeRef = sibling;
+ parent->left = parent->right = 0;
+ delete parent;
+ delete neighbor;
+ done = false;
+ }
+ }
+
+ // Merge with right neighbor.
+ current = node;
+ parent = current->parent;
+ while (parent && current == parent->right && parent->splitType == splitType) {
+ current = parent;
+ parent = parent->parent;
+ }
+
+ if (parent && parent->splitType == splitType) {
+ Q_ASSERT(current == parent->left);
+ Q_ASSERT(parent->right);
+
+ AreaAllocatorNode *neighbor = parent->right;
+ while (neighbor->left && neighbor->splitType == splitType)
+ neighbor = neighbor->left;
+
+ if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
+ // Right neighbor can be merged.
+ parent->split = neighbor->parent->split;
+
+ parent = neighbor->parent;
+ sibling = neighbor == parent->left ? parent->right : parent->left;
+ AreaAllocatorNode **nodeRef = &m_root;
+ if (parent->parent) {
+ if (parent == parent->parent->left)
+ nodeRef = &parent->parent->left;
+ else
+ nodeRef = &parent->parent->right;
+ }
+ sibling->parent = parent->parent;
+ *nodeRef = sibling;
+ parent->left = parent->right = 0;
+ delete parent;
+ delete neighbor;
+ done = false;
+ }
+ }
+ } // end while (!done)
+}
+
+} // namespace Qt3DExtras
+
+QT_END_NAMESPACE
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 03:07:33 +0000