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: */
|
