Method Insert

Source/Engine/Utilities/RectPack.h:157–215

    /// <returns>The node that contains inserted an item or null if failed to find a free space.</returns>
    template<class... Args>
    NodeType* Insert(Size width, Size height, Args&&... args)
    {
        NodeType* result = nullptr;
        const Size paddedWidth = width + BordersPadding;
        const Size paddedHeight = height + BordersPadding;

        // Search free nodes from back to front and find the one that fits requested item size
        // TODO: FreeNodes are sorted so use Binary Search to quickly find the first tile that might have enough space for insert
        for (int32 i = FreeNodes.Count() - 1; i >= 0; i--)
        {
            NodeType* freeNode = FreeNodes.Get()[i];
            if (paddedWidth > freeNode->Width || paddedHeight > freeNode->Height)
            {
                // Not enough space
                continue;
            }

            // Check if there will be some remaining space left in this node
            if (freeNode->Width != width || freeNode->Height != height)
            {
                // Subdivide this node into up to 2 additional nodes
                const Size remainingWidth = freeNode->Width - paddedWidth;
                const Size remainingHeight = freeNode->Height - paddedHeight;

                // Split the remaining area around this node into two children
                SizeRect bigger, smaller;
                if (remainingHeight <= remainingWidth)
                {
                    // Split vertically
                    smaller = SizeRect(freeNode->X, freeNode->Y + paddedHeight, width, remainingHeight);
                    bigger = SizeRect(freeNode->X + paddedWidth, freeNode->Y, remainingWidth, freeNode->Height);
                }
                else
                {
                    // Split horizontally
                    smaller = SizeRect(freeNode->X + paddedWidth, freeNode->Y, remainingWidth, height);
                    bigger = SizeRect(freeNode->X, freeNode->Y + paddedHeight, freeNode->Width, remainingHeight);
                }
                if (smaller.W * smaller.H > bigger.W * bigger.H)
                    Swap(bigger, smaller);
                if (bigger.W * bigger.H > BordersPadding)
                    AddFreeNode(Nodes.Add(NodeType(bigger.X, bigger.Y, bigger.W, bigger.H)));
                if (smaller.W * smaller.H > BordersPadding)
                    AddFreeNode(Nodes.Add(NodeType(smaller.X, smaller.Y, smaller.W, smaller.H)));

                // Shrink to the actual area
                freeNode->Width = width;
                freeNode->Height = height;
            }

            // Insert into this node
            result = freeNode;
            FreeNodes.RemoveAtKeepOrder(i);
            result->OnInsert(Forward<Args>(args)...);
            break;
        }

        return result;