Adding upstream version 1:7.0.4.upstream/1%7.0.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 240 insertions, 0 deletions

diff --git a/include/basegfx/range/b2dconnectedranges.hxx b/include/basegfx/range/b2dconnectedranges.hxx
new file mode 100644
index 000000000..0d7a81481
--- /dev/null
+++ b/include/basegfx/range/b2dconnectedranges.hxx
@@ -0,0 +1,240 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   Licensed to the Apache Software Foundation (ASF) under one or more
+ *   contributor license agreements. See the NOTICE file distributed
+ *   with this work for additional information regarding copyright
+ *   ownership. The ASF licenses this file to you under the Apache
+ *   License, Version 2.0 (the "License"); you may not use this file
+ *   except in compliance with the License. You may obtain a copy of
+ *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#pragma once
+
+#include <osl/diagnose.h>
+#include <basegfx/range/b2drange.hxx>
+#include <list>
+#include <utility>
+#include <algorithm>
+
+
+namespace basegfx
+{
+    /** Calculate connected ranges from input ranges.
+
+        This template constructs a list of connected ranges from the
+        given input ranges. That is, the output will contain a set of
+        ranges, itself containing a number of input ranges, which will
+        be mutually non-intersecting.
+
+        Example:
+        <code>
+        -------------------
+        |          -------|
+        |          |     ||
+        | ---      |     ||
+        | | |      -------|        --------
+        | | +---------    |        |      |
+        | --+        |    |        |      |
+        |   |        |    |        --------
+        |   ----------    |
+        -------------------
+        </code
+
+        Here, the outer rectangles represent the output
+        ranges. Contained are the input rectangles that comprise these
+        output ranges.
+
+        @tpl UserData
+        User data to be stored along with the range, to later identify
+        which range went into which connected component. Must be
+        assignable, default- and copy-constructible.
+     */
+    template< typename UserData > class B2DConnectedRanges
+    {
+    public:
+        /// Type of the basic entity (rect + user data)
+        typedef ::std::pair< B2DRange, UserData > ComponentType;
+        typedef ::std::list< ComponentType >      ComponentListType;
+
+        /// List of (intersecting) components, plus overall bounds
+        struct ConnectedComponents
+        {
+            ComponentListType   maComponentList;
+            B2DRange            maTotalBounds;
+        };
+
+        typedef ::std::list< ConnectedComponents > ConnectedComponentsType;
+
+
+        /// Create the range calculator
+        B2DConnectedRanges() :
+            maDisjunctAggregatesList(),
+            maTotalBounds()
+        {
+        }
+
+        /** Add an additional range.
+
+            This method integrates a new range into the connected
+            ranges lists. The method has a worst-case time complexity
+            of O(n^2), with n denoting the number of already added
+            ranges (typically, for well-behaved input, it is O(n)
+            though).
+         */
+        void addRange( const B2DRange&  rRange,
+                       const UserData&  rUserData )
+        {
+            // check whether fast path is possible: if new range is
+            // outside accumulated total range, can add it as a
+            // separate component right away.
+            const bool bNotOutsideEverything(
+                maTotalBounds.overlaps( rRange ) );
+
+            // update own global bounds range
+            maTotalBounds.expand( rRange );
+
+            // assemble anything intersecting with rRange into
+            // this new connected component
+            ConnectedComponents aNewConnectedComponent;
+
+            // as at least rRange will be a member of
+            // aNewConnectedComponent (will be added below), can
+            // preset the overall bounds here.
+            aNewConnectedComponent.maTotalBounds = rRange;
+
+
+            //  STAGE 1: Search for intersecting maDisjunctAggregatesList entries
+
+
+            // if rRange is empty, it will intersect with no
+            // maDisjunctAggregatesList member. Thus, we can safe us
+            // the check.
+            // if rRange is outside all other rectangle, skip here,
+            // too
+            if( bNotOutsideEverything &&
+                !rRange.isEmpty() )
+            {
+                typename ConnectedComponentsType::iterator aCurrAggregate;
+                typename ConnectedComponentsType::iterator aLastAggregate;
+
+                // flag, determining whether we touched one or more of
+                // the maDisjunctAggregatesList entries. _If_ we did,
+                // we have to repeat the intersection process, because
+                // these changes might have generated new
+                // intersections.
+                bool bSomeAggregatesChanged;
+
+                // loop, until bSomeAggregatesChanged stays false
+                do
+                {
+                    // only continue loop if 'intersects' branch below was hit
+                    bSomeAggregatesChanged = false;
+
+                    // iterate over all current members of maDisjunctAggregatesList
+                    for( aCurrAggregate=maDisjunctAggregatesList.begin(),
+                             aLastAggregate=maDisjunctAggregatesList.end();
+                         aCurrAggregate != aLastAggregate; )
+                    {
+                        // first check if current component's bounds
+                        // are empty. This ensures that distinct empty
+                        // components are not merged into one
+                        // aggregate. As a matter of fact, they have
+                        // no position and size.
+
+                        if( !aCurrAggregate->maTotalBounds.isEmpty() &&
+                            aCurrAggregate->maTotalBounds.overlaps(
+                                aNewConnectedComponent.maTotalBounds ) )
+                        {
+                            // union the intersecting
+                            // maDisjunctAggregatesList element into
+                            // aNewConnectedComponent
+
+                            // calc union bounding box
+                            aNewConnectedComponent.maTotalBounds.expand( aCurrAggregate->maTotalBounds );
+
+                            // extract all aCurrAggregate components
+                            // to aNewConnectedComponent
+                            aNewConnectedComponent.maComponentList.splice(
+                                aNewConnectedComponent.maComponentList.end(),
+                                aCurrAggregate->maComponentList );
+
+                            // remove and delete aCurrAggregate entry
+                            // from list (we've gutted it's content
+                            // above). list::erase() will update our
+                            // iterator with the predecessor here.
+                            aCurrAggregate = maDisjunctAggregatesList.erase( aCurrAggregate );
+
+                            // at least one aggregate changed, need to rescan everything
+                            bSomeAggregatesChanged = true;
+                        }
+                        else
+                        {
+                            ++aCurrAggregate;
+                        }
+                    }
+                }
+                while( bSomeAggregatesChanged );
+            }
+
+
+            //  STAGE 2: Add newly generated connected component list element
+
+
+            // add new component to the end of the component list
+            aNewConnectedComponent.maComponentList.push_back(
+                ComponentType( rRange, rUserData ) );
+
+            // do some consistency checks (aka post conditions)
+            OSL_ENSURE( !aNewConnectedComponent.maComponentList.empty(),
+                        "B2DConnectedRanges::addRange(): empty aggregate list" );
+            OSL_ENSURE( !aNewConnectedComponent.maTotalBounds.isEmpty() ||
+                         aNewConnectedComponent.maComponentList.size() == 1,
+                        "B2DConnectedRanges::addRange(): empty ranges must be solitary");
+
+            // add aNewConnectedComponent as a new entry to
+            // maDisjunctAggregatesList
+            maDisjunctAggregatesList.push_back( aNewConnectedComponent );
+        }
+
+        /** Apply a functor to each of the disjunct component
+            aggregates.
+
+            @param aFunctor
+            Functor to apply. Must provide an operator( const ConnectedComponents& ).
+
+            @return a copy of the functor, as applied to all aggregates.
+         */
+        template< typename UnaryFunctor > UnaryFunctor forEachAggregate( UnaryFunctor aFunctor ) const
+        {
+            return ::std::for_each( maDisjunctAggregatesList.begin(),
+                                    maDisjunctAggregatesList.end(),
+                                    aFunctor );
+        }
+
+    private:
+        B2DConnectedRanges(const B2DConnectedRanges&) = delete;
+        B2DConnectedRanges& operator=( const B2DConnectedRanges& ) = delete;
+
+        /** Current list of disjunct sets of connected components
+
+            Each entry corresponds to one of the top-level rectangles
+            in the drawing above.
+         */
+        ConnectedComponentsType maDisjunctAggregatesList;
+
+        /** Global bound rect over all added ranges.
+         */
+        B2DRange                maTotalBounds;
+    };
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */