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