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