juce_RectangleList.h

Go to the documentation of this file.

 /*
  ==============================================================================
 
   This file is part of the JUCE library.
   Copyright (c) 2022 - Raw Material Software Limited
 
   JUCE is an open source library subject to commercial or open-source
   licensing.
 
   By using JUCE, you agree to the terms of both the JUCE 7 End-User License
   Agreement and JUCE Privacy Policy.
 
   End User License Agreement: www.juce.com/juce-7-licence
   Privacy Policy: www.juce.com/juce-privacy-policy
 
   Or: You may also use this code under the terms of the GPL v3 (see
   www.gnu.org/licenses).
 
   JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
   EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
   DISCLAIMED.
 
  ==============================================================================
*/
 
namespace juce
{
 
//==============================================================================
template <typename ValueType>
class RectangleList  final
{
public:
    using RectangleType = Rectangle<ValueType>;
 
    //==============================================================================
    RectangleList() = default;
 
    RectangleList (const RectangleList& other)  : rects (other.rects)
    {
    }
 
    RectangleList (RectangleType rect)
    {
        addWithoutMerging (rect);
    }
 
    RectangleList& operator= (const RectangleList& other)
    {
        rects = other.rects;
        return *this;
    }
 
    RectangleList (RectangleList&& other) noexcept
        : rects (std::move (other.rects))
    {
    }
 
    RectangleList& operator= (RectangleList&& other) noexcept
    {
        rects = std::move (other.rects);
        return *this;
    }
 
    //==============================================================================
    bool isEmpty() const noexcept                               { return rects.isEmpty(); }
 
    int getNumRectangles() const noexcept                       { return rects.size(); }
 
    RectangleType getRectangle (int index) const noexcept       { return rects[index]; }
 
    //==============================================================================
    void clear()
    {
        rects.clearQuick();
    }
 
    void add (RectangleType rect)
    {
        jassert (rect.isFinite()); // You must provide a valid rectangle to this method!
 
        if (! rect.isEmpty())
        {
            if (isEmpty())
            {
                rects.add (rect);
            }
            else
            {
                bool anyOverlaps = false;
 
                for (int j = rects.size(); --j >= 0;)
                {
                    auto& ourRect = rects.getReference (j);
 
                    if (rect.intersects (ourRect))
                    {
                        if (rect.contains (ourRect))
                            rects.remove (j);
                        else if (! ourRect.reduceIfPartlyContainedIn (rect))
                            anyOverlaps = true;
                    }
                }
 
                if (anyOverlaps && ! isEmpty())
                {
                    RectangleList r (rect);
 
                    for (auto& ourRect : rects)
                    {
                        if (rect.intersects (ourRect))
                        {
                            r.subtract (ourRect);
 
                            if (r.isEmpty())
                                return;
                        }
                    }
 
                    rects.addArray (r.rects);
                }
                else
                {
                    rects.add (rect);
                }
            }
        }
    }
 
    void add (ValueType x, ValueType y, ValueType width, ValueType height)
    {
        add (RectangleType (x, y, width, height));
    }
 
    void addWithoutMerging (RectangleType rect)
    {
        jassert (rect.isFinite()); // You must provide a valid rectangle to this method!
 
        if (! rect.isEmpty())
            rects.add (rect);
    }
 
    void add (const RectangleList& other)
    {
        for (auto& r : other)
            add (r);
    }
 
    void subtract (const RectangleType rect)
    {
        if (auto numRects = rects.size())
        {
            const auto x1 = rect.getX();
            const auto y1 = rect.getY();
            const auto x2 = x1 + rect.getWidth();
            const auto y2 = y1 + rect.getHeight();
 
            for (int i = numRects; --i >= 0;)
            {
                auto& r = rects.getReference (i);
 
                const auto rx1 = r.getX();
                const auto ry1 = r.getY();
                const auto rx2 = rx1 + r.getWidth();
                const auto ry2 = ry1 + r.getHeight();
 
                const auto isNotEqual = [&] (const RectangleType newRect)
                {
                    // When subtracting tiny slices from relatively large rectangles, the
                    // subtraction may have no effect (due to limited-precision floating point
                    // maths) and the original rectangle may remain unchanged.
                    // We check that any 'new' rectangle has different dimensions to the rectangle
                    // being tested before adding it to the rects array.
                    // Integer arithmetic is not susceptible to this problem, so there's no need
                    // for this additional equality check when working with integral rectangles.
                    if constexpr (std::is_floating_point_v<ValueType>)
                    {
                        return newRect != r;
                    }
                    else
                    {
                        ignoreUnused (newRect);
                        return true;
                    }
                };
 
                if (rx1 < x2 && x1 < rx2 && ry1 < y2 && y1 < ry2)
                {
                    if (rx1 < x1 && x1 < rx2)
                    {
                        if (y1 <= ry1 && ry2 <= y2 && rx2 <= x2)
                        {
                            r.setWidth (x1 - rx1);
                        }
                        else
                        {
                            if (const RectangleType newRect (rx1, ry1, x1 - rx1, ry2 - ry1); isNotEqual (newRect))
                            {
                                r.setX (x1);
                                r.setWidth (rx2 - x1);
 
                                rects.insert (++i, newRect);
                                ++i;
                            }
                        }
                    }
                    else if (rx1 < x2 && x2 < rx2)
                    {
                        r.setX (x2);
                        r.setWidth (rx2 - x2);
 
                        if (ry1 < y1 || y2 < ry2 || rx1 < x1)
                        {
                            if (const RectangleType newRect (rx1, ry1, x2 - rx1, ry2 - ry1); isNotEqual (newRect))
                            {
                                rects.insert (++i, newRect);
                                ++i;
                            }
                        }
                    }
                    else if (ry1 < y1 && y1 < ry2)
                    {
                        if (x1 <= rx1 && rx2 <= x2 && ry2 <= y2)
                        {
                            r.setHeight (y1 - ry1);
                        }
                        else
                        {
                            if (const RectangleType newRect (rx1, ry1, rx2 - rx1, y1 - ry1); isNotEqual (newRect))
                            {
                                r.setY (y1);
                                r.setHeight (ry2 - y1);
 
                                rects.insert (++i, newRect);
                                ++i;
                            }
                        }
                    }
                    else if (ry1 < y2 && y2 < ry2)
                    {
                        r.setY (y2);
                        r.setHeight (ry2 - y2);
 
                        if (rx1 < x1 || x2 < rx2 || ry1 < y1)
                        {
                            if (const RectangleType newRect (rx1, ry1, rx2 - rx1, y2 - ry1); isNotEqual (newRect))
                            {
                                rects.insert (++i, newRect);
                                ++i;
                            }
                        }
                    }
                    else
                    {
                        rects.remove (i);
                    }
                }
            }
        }
    }
 
    bool subtract (const RectangleList& otherList)
    {
        for (auto& r : otherList)
        {
            if (isEmpty())
                return false;
 
            subtract (r);
        }
 
        return ! isEmpty();
    }
 
    bool clipTo (RectangleType rect)
    {
        jassert (rect.isFinite()); // You must provide a valid rectangle to this method!
 
        bool notEmpty = false;
 
        if (rect.isEmpty())
        {
            clear();
        }
        else
        {
            for (int i = rects.size(); --i >= 0;)
            {
                auto& r = rects.getReference (i);
 
                if (! rect.intersectRectangle (r))
                    rects.remove (i);
                else
                    notEmpty = true;
            }
        }
 
        return notEmpty;
    }
 
    template <typename OtherValueType>
    bool clipTo (const RectangleList<OtherValueType>& other)
    {
        if (isEmpty())
            return false;
 
        RectangleList result;
 
        for (auto& rect : rects)
        {
            for (auto& r : other)
            {
                auto clipped = r.template toType<ValueType>();
 
                if (rect.intersectRectangle (clipped))
                    result.rects.add (clipped);
            }
        }
 
        swapWith (result);
        return ! isEmpty();
    }
 
    bool getIntersectionWith (RectangleType rect, RectangleList& destRegion) const
    {
        jassert (rect.isFinite()); // You must provide a valid rectangle to this method!
 
        destRegion.clear();
 
        if (! rect.isEmpty())
            for (auto r : rects)
                if (rect.intersectRectangle (r))
                    destRegion.rects.add (r);
 
        return ! destRegion.isEmpty();
    }
 
    void swapWith (RectangleList& otherList) noexcept
    {
        rects.swapWith (otherList.rects);
    }
 
    //==============================================================================
    bool containsPoint (Point<ValueType> point) const noexcept
    {
        for (auto& r : rects)
            if (r.contains (point))
                return true;
 
        return false;
    }
 
    bool containsPoint (ValueType x, ValueType y) const noexcept
    {
        return containsPoint (Point<ValueType> (x, y));
    }
 
    bool containsRectangle (RectangleType rectangleToCheck) const
    {
        if (rects.size() > 1)
        {
            RectangleList r (rectangleToCheck);
 
            for (auto& rect : rects)
            {
                r.subtract (rect);
 
                if (r.isEmpty())
                    return true;
            }
        }
        else if (! isEmpty())
        {
            return rects.getReference (0).contains (rectangleToCheck);
        }
 
        return false;
    }
 
    bool intersectsRectangle (RectangleType rectangleToCheck) const noexcept
    {
        for (auto& r : rects)
            if (r.intersects (rectangleToCheck))
                return true;
 
        return false;
    }
 
    bool intersects (const RectangleList& other) const noexcept
    {
        for (auto& r : rects)
            if (other.intersectsRectangle (r))
                return true;
 
        return false;
    }
 
    //==============================================================================
    RectangleType getBounds() const noexcept
    {
        if (isEmpty())
            return {};
 
        auto& r = rects.getReference (0);
 
        if (rects.size() == 1)
            return r;
 
        auto minX = r.getX();
        auto minY = r.getY();
        auto maxX = minX + r.getWidth();
        auto maxY = minY + r.getHeight();
 
        for (int i = rects.size(); --i > 0;)
        {
            auto& r2 = rects.getReference (i);
 
            minX = jmin (minX, r2.getX());
            minY = jmin (minY, r2.getY());
            maxX = jmax (maxX, r2.getRight());
            maxY = jmax (maxY, r2.getBottom());
        }
 
        return { minX, minY, maxX - minX, maxY - minY };
    }
 
    void consolidate()
    {
        for (int i = 0; i < rects.size() - 1; ++i)
        {
            auto& r = rects.getReference (i);
            auto rx1 = r.getX();
            auto ry1 = r.getY();
            auto rx2 = rx1 + r.getWidth();
            auto ry2 = ry1 + r.getHeight();
 
            for (int j = rects.size(); --j > i;)
            {
                auto& r2 = rects.getReference (j);
                auto jrx1 = r2.getX();
                auto jry1 = r2.getY();
                auto jrx2 = jrx1 + r2.getWidth();
                auto jry2 = jry1 + r2.getHeight();
 
                // if the vertical edges of any blocks are touching and their horizontals don't
                // line up, split them horizontally..
                if (jrx1 == rx2 || jrx2 == rx1)
                {
                    if (jry1 > ry1 && jry1 < ry2)
                    {
                        r.setHeight (jry1 - ry1);
                        rects.add (RectangleType (rx1, jry1, rx2 - rx1, ry2 - jry1));
                        i = -1;
                        break;
                    }
 
                    if (jry2 > ry1 && jry2 < ry2)
                    {
                        r.setHeight (jry2 - ry1);
                        rects.add (RectangleType (rx1, jry2, rx2 - rx1, ry2 - jry2));
                        i = -1;
                        break;
                    }
                    else if (ry1 > jry1 && ry1 < jry2)
                    {
                        r2.setHeight (ry1 - jry1);
                        rects.add (RectangleType (jrx1, ry1, jrx2 - jrx1, jry2 - ry1));
                        i = -1;
                        break;
                    }
                    else if (ry2 > jry1 && ry2 < jry2)
                    {
                        r2.setHeight (ry2 - jry1);
                        rects.add (RectangleType (jrx1, ry2, jrx2 - jrx1, jry2 - ry2));
                        i = -1;
                        break;
                    }
                }
            }
        }
 
        for (int i = 0; i < rects.size() - 1; ++i)
        {
            auto& r = rects.getReference (i);
 
            for (int j = rects.size(); --j > i;)
            {
                if (r.enlargeIfAdjacent (rects.getReference (j)))
                {
                    rects.remove (j);
                    i = -1;
                    break;
                }
            }
        }
    }
 
    void offsetAll (Point<ValueType> offset) noexcept
    {
        for (auto& r : rects)
            r += offset;
    }
 
    void offsetAll (ValueType dx, ValueType dy) noexcept
    {
        offsetAll (Point<ValueType> (dx, dy));
    }
 
    template <typename ScaleType>
    void scaleAll (ScaleType scaleFactor) noexcept
    {
        for (auto& r : rects)
            r *= scaleFactor;
    }
 
    void transformAll (const AffineTransform& transform) noexcept
    {
        for (auto& r : rects)
            r = r.transformedBy (transform);
    }
 
    //==============================================================================
    Path toPath() const
    {
        Path p;
 
        for (auto& r : rects)
            p.addRectangle (r);
 
        return p;
    }
 
    //==============================================================================
    const RectangleType* begin() const noexcept     { return rects.begin(); }
    const RectangleType* end() const noexcept       { return rects.end(); }
 
    void ensureStorageAllocated (int minNumRectangles)
    {
        rects.ensureStorageAllocated (minNumRectangles);
    }
 
private:
    //==============================================================================
    Array<RectangleType> rects;
};
 
} // namespace juce