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