LCOV - code coverage report
Current view: top level - include/basegfx/range - b2dconnectedranges.hxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 0 31 0.0 %
Date: 2015-06-13 12:38:46 Functions: 0 8 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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 INCLUDED_BASEGFX_RANGE_B2DCONNECTEDRANGES_HXX
      21             : #define INCLUDED_BASEGFX_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           0 :     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           0 :         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           0 :         B2DConnectedRanges() :
      81             :             maDisjunctAggregatesList(),
      82           0 :             maTotalBounds()
      83             :         {
      84           0 :         }
      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           0 :         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           0 :                 maTotalBounds.overlaps( rRange ) );
     111             : 
     112             :             // update own global bounds range
     113           0 :             maTotalBounds.expand( rRange );
     114             : 
     115             :             // assemble anything intersecting with rRange into
     116             :             // this new connected component
     117           0 :             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           0 :             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           0 :             if( bNotOutsideEverything &&
     136           0 :                 !rRange.isEmpty() )
     137             :             {
     138           0 :                 typename ConnectedComponentsType::iterator aCurrAggregate;
     139           0 :                 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           0 :                 do
     150             :                 {
     151             :                     // only continue loop if 'intersects' branch below was hit
     152           0 :                     bSomeAggregatesChanged = false;
     153             : 
     154             :                     // iterate over all current members of maDisjunctAggregatesList
     155           0 :                     for( aCurrAggregate=maDisjunctAggregatesList.begin(),
     156           0 :                              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           0 :                         if( !aCurrAggregate->maTotalBounds.isEmpty() &&
     166           0 :                             aCurrAggregate->maTotalBounds.overlaps(
     167             :                                 aNewConnectedComponent.maTotalBounds ) )
     168             :                         {
     169             :                             // union the intersecting
     170             :                             // maDisjunctAggregatesList element into
     171             :                             // aNewConnectedComponent
     172             : 
     173             :                             // calc union bounding box
     174           0 :                             aNewConnectedComponent.maTotalBounds.expand( aCurrAggregate->maTotalBounds );
     175             : 
     176             :                             // extract all aCurrAggregate components
     177             :                             // to aNewConnectedComponent
     178           0 :                             aNewConnectedComponent.maComponentList.splice(
     179             :                                 aNewConnectedComponent.maComponentList.end(),
     180           0 :                                 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           0 :                             aCurrAggregate = maDisjunctAggregatesList.erase( aCurrAggregate );
     187             : 
     188             :                             // at least one aggregate changed, need to rescan everything
     189           0 :                             bSomeAggregatesChanged = true;
     190             :                         }
     191             :                         else
     192             :                         {
     193           0 :                             ++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           0 :             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           0 :             maDisjunctAggregatesList.push_back( aNewConnectedComponent );
     220           0 :         }
     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           0 :         template< typename UnaryFunctor > UnaryFunctor forEachAggregate( UnaryFunctor aFunctor ) const
     231             :         {
     232             :             return ::std::for_each( maDisjunctAggregatesList.begin(),
     233             :                                     maDisjunctAggregatesList.end(),
     234           0 :                                     aFunctor );
     235             :         }
     236             : 
     237             :     private:
     238             :         B2DConnectedRanges(const B2DConnectedRanges&) SAL_DELETED_FUNCTION;
     239             :         B2DConnectedRanges& operator=( const B2DConnectedRanges& ) SAL_DELETED_FUNCTION;
     240             : 
     241             :         /** Current list of disjunct sets of connected components
     242             : 
     243             :             Each entry corresponds to one of the top-level rectangles
     244             :             in the drawing above.
     245             :          */
     246             :         ConnectedComponentsType maDisjunctAggregatesList;
     247             : 
     248             :         /** Global bound rect over all added ranges.
     249             :          */
     250             :         B2DRange                maTotalBounds;
     251             :     };
     252             : }
     253             : 
     254             : #endif // INCLUDED_BASEGFX_RANGE_B2DCONNECTEDRANGES_HXX
     255             : 
     256             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.11