include/basegfx/range/b2dconnectedranges.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #ifndef _BGFX_RANGE_B2DCONNECTEDRANGES_HXX
  21 #define _BGFX_RANGE_B2DCONNECTEDRANGES_HXX
  22
  23 #include <osl/diagnose.h>
  24 #include <basegfx/range/b2drange.hxx>
  25 #include <list>
  26 #include <utility>
  27 #include <algorithm>
  28
  29
  30 namespace basegfx
  31 {
  32     /** Calculate connected ranges from input ranges.
  33
  34         This template constructs a list of connected ranges from the
  35         given input ranges. That is, the output will contain a set of
  36         ranges, itself containing a number of input ranges, which will
  37         be mutually non-intersecting.
  38
  39         Example:
  40         <code>
  41         -------------------
  42         |          -------|
  43         |          |     ||
  44         | ---      |     ||
  45         | | |      -------|        --------
  46         | | +---------    |        |      |
  47         | --+        |    |        |      |
  48         |   |        |    |        --------
  49         |   ----------    |
  50         -------------------
  51         </code
  52
  53         Here, the outer rectangles represent the output
  54         ranges. Contained are the input rectangles that comprise these
  55         output ranges.
  56
  57         @tpl UserData
  58         User data to be stored along with the range, to later identify
  59         which range went into which connected component. Must be
  60         assignable, default- and copy-constructible.
  61      */
  62     template< typename UserData > class B2DConnectedRanges
  63     {
  64     public:
  65         /// Type of the basic entity (rect + user data)
  66         typedef ::std::pair< B2DRange, UserData > ComponentType;
  67         typedef ::std::list< ComponentType >      ComponentListType;
  68
  69         /// List of (intersecting) components, plus overall bounds
  70         struct ConnectedComponents
  71         {
  72             ComponentListType   maComponentList;
  73             B2DRange            maTotalBounds;
  74         };
  75
  76         typedef ::std::list< ConnectedComponents > ConnectedComponentsType;
  77
  78
  79         /// Create the range calculator
  80         B2DConnectedRanges() :
  81             maDisjunctAggregatesList(),
  82             maTotalBounds()
  83         {
  84         }
  85
  86         /** Query total bounds of all added ranges.
  87
  88             @return the union bound rect over all added ranges.
  89          */
  90         B2DRange getBounds() const
  91         {
  92             return maTotalBounds;
  93         }
  94
  95         /** Add an additional range.
  96
  97             This method integrates a new range into the connected
  98             ranges lists. The method has a worst-case time complexity
  99             of O(n^2), with n denoting the number of already added
 100             ranges (typically, for well-behaved input, it is O(n)
 101             though).
 102          */
 103         void addRange( const B2DRange&  rRange,
 104                        const UserData&  rUserData )
 105         {
 106             // check whether fast path is possible: if new range is
 107             // outside accumulated total range, can add it as a
 108             // separate component right away.
 109             const bool bNotOutsideEverything(
 110                 maTotalBounds.overlaps( rRange ) );
 111
 112             // update own global bounds range
 113             maTotalBounds.expand( rRange );
 114
 115             // assemble anything intersecting with rRange into
 116             // this new connected component
 117             ConnectedComponents aNewConnectedComponent;
 118
 119             // as at least rRange will be a member of
 120             // aNewConnectedComponent (will be added below), can
 121             // preset the overall bounds here.
 122             aNewConnectedComponent.maTotalBounds = rRange;
 123
 124
 125             //
 126             //  STAGE 1: Search for intersecting maDisjunctAggregatesList entries
 127             //  =================================================================
 128             //
 129
 130             // if rRange is empty, it will intersect with no
 131             // maDisjunctAggregatesList member. Thus, we can safe us
 132             // the check.
 133             // if rRange is outside all other rectangle, skip here,
 134             // too
 135             if( bNotOutsideEverything &&
 136                 !rRange.isEmpty() )
 137             {
 138                 typename ConnectedComponentsType::iterator aCurrAggregate;
 139                 typename ConnectedComponentsType::iterator aLastAggregate;
 140
 141                 // flag, determining whether we touched one or more of
 142                 // the maDisjunctAggregatesList entries. _If_ we did,
 143                 // we have to repeat the intersection process, because
 144                 // these changes might have generated new
 145                 // intersections.
 146                 bool bSomeAggregatesChanged;
 147
 148                 // loop, until bSomeAggregatesChanged stays false
 149                 do
 150                 {
 151                     // only continue loop if 'intersects' branch below was hit
 152                     bSomeAggregatesChanged = false;
 153
 154                     // iterate over all current members of maDisjunctAggregatesList
 155                     for( aCurrAggregate=maDisjunctAggregatesList.begin(),
 156                              aLastAggregate=maDisjunctAggregatesList.end();
 157                          aCurrAggregate != aLastAggregate; )
 158                     {
 159                         // first check if current component's bounds
 160                         // are empty. This ensures that distinct empty
 161                         // components are not merged into one
 162                         // aggregate. As a matter of fact, they have
 163                         // no position and size.
 164
 165                         if( !aCurrAggregate->maTotalBounds.isEmpty() &&
 166                             aCurrAggregate->maTotalBounds.overlaps(
 167                                 aNewConnectedComponent.maTotalBounds ) )
 168                         {
 169                             // union the intersecting
 170                             // maDisjunctAggregatesList element into
 171                             // aNewConnectedComponent
 172
 173                             // calc union bounding box
 174                             aNewConnectedComponent.maTotalBounds.expand( aCurrAggregate->maTotalBounds );
 175
 176                             // extract all aCurrAggregate components
 177                             // to aNewConnectedComponent
 178                             aNewConnectedComponent.maComponentList.splice(
 179                                 aNewConnectedComponent.maComponentList.end(),
 180                                 aCurrAggregate->maComponentList );
 181
 182                             // remove and delete aCurrAggregate entry
 183                             // from list (we've gutted it's content
 184                             // above). list::erase() will update our
 185                             // iterator with the predecessor here.
 186                             aCurrAggregate = maDisjunctAggregatesList.erase( aCurrAggregate );
 187
 188                             // at least one aggregate changed, need to rescan everything
 189                             bSomeAggregatesChanged = true;
 190                         }
 191                         else
 192                         {
 193                             aCurrAggregate++;
 194                         }
 195                     }
 196                 }
 197                 while( bSomeAggregatesChanged );
 198             }
 199
 200             //
 201             //  STAGE 2: Add newly generated connected component list element
 202             //  =============================================================
 203             //
 204
 205             // add new component to the end of the component list
 206             aNewConnectedComponent.maComponentList.push_back(
 207                 ComponentType( rRange, rUserData ) );
 208
 209             // do some consistency checks (aka post conditions)
 210             OSL_ENSURE( !aNewConnectedComponent.maComponentList.empty(),
 211                         "B2DConnectedRanges::addRange(): empty aggregate list" );
 212             OSL_ENSURE( !aNewConnectedComponent.maTotalBounds.isEmpty() ||
 213                         (aNewConnectedComponent.maTotalBounds.isEmpty() &&
 214                          aNewConnectedComponent.maComponentList.size() == 1),
 215                         "B2DConnectedRanges::addRange(): empty ranges must be solitary");
 216
 217             // add aNewConnectedComponent as a new entry to
 218             // maDisjunctAggregatesList
 219             maDisjunctAggregatesList.push_back( aNewConnectedComponent );
 220         }
 221
 222         /** Apply a functor to each of the disjunct component
 223             aggregates.
 224
 225             @param aFunctor
 226             Functor to apply. Must provide an operator( const ConnectedComponents& ).
 227
 228             @return a copy of the functor, as applied to all aggregates.
 229          */
 230         template< typename UnaryFunctor > UnaryFunctor forEachAggregate( UnaryFunctor aFunctor ) const
 231         {
 232             return ::std::for_each( maDisjunctAggregatesList.begin(),
 233                                     maDisjunctAggregatesList.end(),
 234                                     aFunctor );
 235         }
 236
 237     private:
 238         // default: disabled copy/assignment
 239         B2DConnectedRanges(const B2DConnectedRanges&);
 240         B2DConnectedRanges& operator=( const B2DConnectedRanges& );
 241
 242         /** Current list of disjunct sets of connected components
 243
 244             Each entry corresponds to one of the top-level rectangles
 245             in the drawing above.
 246          */
 247         ConnectedComponentsType maDisjunctAggregatesList;
 248
 249         /** Global bound rect over all added ranges.
 250          */
 251         B2DRange                maTotalBounds;
 252     };
 253 }
 254
 255 #endif /* _BGFX_RANGE_B2DCONNECTEDRANGES_HXX */
 256
 257 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */