path: root/basegfx/inc/basegfx/range/b2dconnectedranges.hxx

/*************************************************************************
 *
 *  OpenOffice.org - a multi-platform office productivity suite
 *
 *  $RCSfile: b2dconnectedranges.hxx,v $
 *
 *  $Revision: 1.4 $
 *
 *  last change: $Author: kz $ $Date: 2005-11-02 13:54:40 $
 *
 *  The Contents of this file are made available subject to
 *  the terms of GNU Lesser General Public License Version 2.1.
 *
 *
 *    GNU Lesser General Public License Version 2.1
 *    =============================================
 *    Copyright 2005 by Sun Microsystems, Inc.
 *    901 San Antonio Road, Palo Alto, CA 94303, USA
 *
 *    This library is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License version 2.1, as published by the Free Software Foundation.
 *
 *    This library is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    Lesser General Public License for more details.
 *
 *    You should have received a copy of the GNU Lesser General Public
 *    License along with this library; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *    MA  02111-1307  USA
 *
 ************************************************************************/

#ifndef _BGFX_RANGE_B2DCONNECTEDRANGES_HXX
#define _BGFX_RANGE_B2DCONNECTEDRANGES_HXX

#ifndef _OSL_DIAGNOSE_H_
#include <osl/diagnose.h>
#endif

#ifndef _BGFX_RANGE_B2DRANGE_HXX
#include <basegfx/range/b2drange.hxx>
#endif

#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()
        {
        }

        /** Query total bounds of all added ranges.

            @return the union bound rect over all added ranges.
         */
        B2DRange getBounds() const
        {
            return 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.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:
        // default: disabled copy/assignment
        B2DConnectedRanges(const B2DConnectedRanges&);
        B2DConnectedRanges& operator=( const B2DConnectedRanges& );

        /** 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;
    };
}

#endif /* _BGFX_RANGE_B2DCONNECTEDRANGES_HXX */