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