Branch data 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 _BGFX_RANGE_B2DCONNECTEDRANGES_HXX
21 : : #define _BGFX_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 : : !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 : : 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 : : 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 : : // default: disabled copy/assignment
239 : : B2DConnectedRanges(const B2DConnectedRanges&);
240 : : B2DConnectedRanges& operator=( const B2DConnectedRanges& );
241 : :
242 : : /** Current list of disjunct sets of connected components
243 : :
244 : : Each entry corresponds to one of the top-level rectangles
245 : : in the drawing above.
246 : : */
247 : : ConnectedComponentsType maDisjunctAggregatesList;
248 : :
249 : : /** Global bound rect over all added ranges.
250 : : */
251 : : B2DRange maTotalBounds;
252 : : };
253 : : }
254 : :
255 : : #endif /* _BGFX_RANGE_B2DCONNECTEDRANGES_HXX */
256 : :
257 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
