| /**************************************************************************** |
| ** |
| ** 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 ¤tRect, 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 |