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