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 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_slideshow.hxx"
26 
27 // must be first
28 #include <canvas/debug.hxx>
29 #include <tools/diagnose_ex.h>
30 #include <canvas/verbosetrace.hxx>
31 
32 #include <rtl/math.hxx>
33 #include <rtl/logfile.hxx>
34 
35 #include <vcl/metaact.hxx>
36 #include <vcl/gdimtf.hxx>
37 #include <basegfx/numeric/ftools.hxx>
38 
39 #include "drawshapesubsetting.hxx"
40 #include "drawshape.hxx"
41 
42 #include <boost/bind.hpp>
43 
44 #include <algorithm>
45 #include <functional>
46 #include <limits>
47 
48 using namespace ::com::sun::star;
49 
50 
51 namespace slideshow
52 {
53     namespace internal
54     {
55 
56         //////////////////////////////////////////////////////////////////////
57         //
58         // Private methods
59         //
60         //////////////////////////////////////////////////////////////////////
61 
62         void DrawShapeSubsetting::ensureInitializedNodeTree() const
63         {
64             ENSURE_OR_THROW( mpMtf,
65                               "DrawShapeSubsetting::ensureInitializedNodeTree(): Invalid mtf" );
66 
67             if( mbNodeTreeInitialized )
68                 return; // done, already initialized.
69 
70             // init doctree vector
71             maActionClassVector.clear();
72             maActionClassVector.reserve( mpMtf->GetActionCount() );
73 
74             // search metafile for text output
75             MetaAction* pCurrAct;
76 
77             sal_Int32 nActionIndex(0);
78             sal_Int32 nLastTextActionIndex(0);
79             for( pCurrAct = mpMtf->FirstAction(); pCurrAct; pCurrAct = mpMtf->NextAction() )
80             {
81                 // check for one of our special text doctree comments
82                 switch( pCurrAct->GetType() )
83                 {
84                     case META_COMMENT_ACTION:
85                     {
86                         MetaCommentAction* pAct = static_cast<MetaCommentAction*>(pCurrAct);
87 
88                         // skip comment if not a special XTEXT comment
89                         if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT", 5 ) == COMPARE_EQUAL )
90                         {
91                             // fill classification vector with NOOPs,
92                             // then insert corresponding classes at
93                             // the given index
94                             maActionClassVector.resize( nActionIndex+1, CLASS_NOOP );
95 
96                             if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_EOC" ) == COMPARE_EQUAL )
97                             {
98                                 // special, because can happen
99                                 // in-between of portions - set
100                                 // character-end classificator at
101                                 // given index (relative to last text
102                                 // action).
103                                 const sal_Int32 nIndex( nLastTextActionIndex + pAct->GetValue() );
104 
105                                 ENSURE_OR_THROW( static_cast< ::std::size_t >(nIndex) < maActionClassVector.size(),
106                                                   "DrawShapeSubsetting::ensureInitializedNodeTree(): sentence index out of range" );
107 
108                                 maActionClassVector[ nIndex ] = CLASS_CHARACTER_CELL_END;
109                             }
110                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_EOW" ) == COMPARE_EQUAL )
111                             {
112                                 // special, because can happen
113                                 // in-between of portions - set
114                                 // word-end classificator at given
115                                 // index (relative to last text
116                                 // action).
117                                 const sal_Int32 nIndex( nLastTextActionIndex + pAct->GetValue() );
118 
119                                 ENSURE_OR_THROW( static_cast< ::std::size_t >(nIndex) < maActionClassVector.size(),
120                                                   "DrawShapeSubsetting::ensureInitializedNodeTree(): sentence index out of range" );
121 
122                                 maActionClassVector[ nIndex ] = CLASS_WORD_END;
123                             }
124                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_EOS" ) == COMPARE_EQUAL )
125                             {
126                                 // special, because can happen
127                                 // in-between of portions - set
128                                 // sentence-end classificator at given
129                                 // index (relative to last text
130                                 // action).
131                                 const sal_Int32 nIndex( nLastTextActionIndex + pAct->GetValue() );
132 
133                                 ENSURE_OR_THROW( static_cast< ::std::size_t >(nIndex) < maActionClassVector.size(),
134                                                   "DrawShapeSubsetting::ensureInitializedNodeTree(): sentence index out of range" );
135 
136                                 maActionClassVector[ nIndex ] = CLASS_SENTENCE_END;
137                             }
138                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_EOL" ) == COMPARE_EQUAL )
139                             {
140                                 maActionClassVector[ nActionIndex ] = CLASS_LINE_END;
141                             }
142                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_EOP" ) == COMPARE_EQUAL )
143                             {
144                                 maActionClassVector[ nActionIndex ] = CLASS_PARAGRAPH_END;
145                             }
146                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_PAINTSHAPE_END" ) == COMPARE_EQUAL )
147                             {
148                                 maActionClassVector[ nActionIndex ] = CLASS_SHAPE_END;
149                             }
150                             else if( pAct->GetComment().CompareIgnoreCaseToAscii( "XTEXT_PAINTSHAPE_BEGIN" ) == COMPARE_EQUAL )
151                             {
152                                 maActionClassVector[ nActionIndex ] = CLASS_SHAPE_START;
153                             }
154                         }
155                         ++nActionIndex;
156                         break;
157                     }
158                     case META_TEXT_ACTION:
159                     case META_TEXTARRAY_ACTION:
160                     case META_STRETCHTEXT_ACTION:
161                         nLastTextActionIndex = nActionIndex;
162                         // fallthrough intended
163                     default:
164                         // comment action and all actions not
165                         // explicitely handled here:
166                         nActionIndex += getNextActionOffset(pCurrAct);
167                         break;
168                 }
169             }
170 
171             mbNodeTreeInitialized = true;
172         }
173 
174         void DrawShapeSubsetting::updateSubsetBounds( const SubsetEntry& rSubsetEntry )
175         {
176             // TODO(F1): This removes too much from non-contiguous subsets
177             mnMinSubsetActionIndex = ::std::min(
178                 mnMinSubsetActionIndex,
179                 rSubsetEntry.mnStartActionIndex );
180             mnMaxSubsetActionIndex = ::std::max(
181                 mnMaxSubsetActionIndex,
182                 rSubsetEntry.mnEndActionIndex );
183         }
184 
185         void DrawShapeSubsetting::updateSubsets()
186         {
187             maCurrentSubsets.clear();
188 
189             if( !maSubsetShapes.empty() )
190             {
191                 if( maSubset.isEmpty() )
192                 {
193                     // non-subsetted node, with some child subsets
194                     // that subtract from it
195                     maCurrentSubsets.push_back( DocTreeNode( 0,
196                                                              mnMinSubsetActionIndex,
197                                                              DocTreeNode::NODETYPE_INVALID ) );
198                     maCurrentSubsets.push_back( DocTreeNode( mnMaxSubsetActionIndex,
199                                                              maActionClassVector.size(),
200                                                              DocTreeNode::NODETYPE_INVALID ) );
201                 }
202                 else
203                 {
204                     // subsetted node, from which some further child
205                     // subsets subtract content
206                     maCurrentSubsets.push_back( DocTreeNode( maSubset.getStartIndex(),
207                                                              mnMinSubsetActionIndex,
208                                                              DocTreeNode::NODETYPE_INVALID ) );
209                     maCurrentSubsets.push_back( DocTreeNode( mnMaxSubsetActionIndex,
210                                                              maSubset.getEndIndex(),
211                                                              DocTreeNode::NODETYPE_INVALID ) );
212                 }
213             }
214             else
215             {
216                 // no further child subsets, simply add our subset (if any)
217                 if( !maSubset.isEmpty() )
218                 {
219                     // subsetted node, without any subset children
220                     maCurrentSubsets.push_back( maSubset );
221                 }
222             }
223         }
224 
225         //////////////////////////////////////////////////////////////////////
226         //
227         // Public methods
228         //
229         //////////////////////////////////////////////////////////////////////
230 
231         DrawShapeSubsetting::DrawShapeSubsetting() :
232             maActionClassVector(),
233             mpMtf(),
234             maSubset(),
235             maSubsetShapes(),
236             mnMinSubsetActionIndex( SAL_MAX_INT32 ),
237             mnMaxSubsetActionIndex(0),
238             maCurrentSubsets(),
239             mbNodeTreeInitialized( false )
240         {
241         }
242 
243         DrawShapeSubsetting::DrawShapeSubsetting( const GDIMetaFileSharedPtr& rMtf ) :
244             maActionClassVector(),
245             mpMtf( rMtf ),
246             maSubset(),
247             maSubsetShapes(),
248             mnMinSubsetActionIndex( SAL_MAX_INT32 ),
249             mnMaxSubsetActionIndex(0),
250             maCurrentSubsets(),
251             mbNodeTreeInitialized( false )
252         {
253             ENSURE_OR_THROW( mpMtf,
254                               "DrawShapeSubsetting::DrawShapeSubsetting(): Invalid metafile" );
255 
256             initCurrentSubsets();
257         }
258 
259         DrawShapeSubsetting::DrawShapeSubsetting( const DocTreeNode&			rShapeSubset,
260                                                   const GDIMetaFileSharedPtr&	rMtf ) :
261             maActionClassVector(),
262             mpMtf( rMtf ),
263             maSubset( rShapeSubset ),
264             maSubsetShapes(),
265             mnMinSubsetActionIndex( SAL_MAX_INT32 ),
266             mnMaxSubsetActionIndex(0),
267             maCurrentSubsets(),
268             mbNodeTreeInitialized( false )
269         {
270             ENSURE_OR_THROW( mpMtf,
271                               "DrawShapeSubsetting::DrawShapeSubsetting(): Invalid metafile" );
272 
273             initCurrentSubsets();
274         }
275 
276         void DrawShapeSubsetting::reset()
277         {
278             maActionClassVector.clear();
279             mpMtf.reset();
280             maSubset.reset();
281             maSubsetShapes.clear();
282             mnMinSubsetActionIndex = SAL_MAX_INT32;
283             mnMaxSubsetActionIndex = 0;
284             maCurrentSubsets.clear();
285             mbNodeTreeInitialized = false;
286         }
287 
288         void DrawShapeSubsetting::reset( const ::boost::shared_ptr< GDIMetaFile >& rMtf )
289         {
290             reset();
291             mpMtf = rMtf;
292 
293             initCurrentSubsets();
294         }
295 
296         void DrawShapeSubsetting::reset( const DocTreeNode&                          rShapeSubset,
297                                          const ::boost::shared_ptr< GDIMetaFile >&   rMtf )
298         {
299             reset();
300             mpMtf = rMtf;
301             maSubset = rShapeSubset;
302 
303             initCurrentSubsets();
304         }
305 
306         void DrawShapeSubsetting::initCurrentSubsets()
307         {
308             // only add subset to vector, if it's not empty - that's
309             // because the vector's content is later literally used
310             // for e.g. painting.
311             if( !maSubset.isEmpty() )
312                 maCurrentSubsets.push_back( maSubset );
313         }
314 
315         DocTreeNode DrawShapeSubsetting::getSubsetNode() const
316         {
317             return maSubset;
318         }
319 
320         bool DrawShapeSubsetting::hasSubsetShapes() const
321         {
322             return !maSubsetShapes.empty();
323         }
324 
325         AttributableShapeSharedPtr DrawShapeSubsetting::getSubsetShape( const DocTreeNode& rTreeNode ) const
326         {
327             RTL_LOGFILE_CONTEXT( aLog, "::presentation::internal::DrawShapeSubsetting::getSubsetShape()" );
328 
329             // subset shape already created for this DocTreeNode?
330             SubsetEntry aEntry;
331 
332             aEntry.mnStartActionIndex 	= rTreeNode.getStartIndex();
333             aEntry.mnEndActionIndex 	= rTreeNode.getEndIndex();
334 
335             ShapeSet::const_iterator aIter;
336             if( (aIter=maSubsetShapes.find( aEntry )) != maSubsetShapes.end() )
337             {
338                 // already created, return found entry
339                 return aIter->mpShape;
340             }
341 
342             return AttributableShapeSharedPtr();
343         }
344 
345         void DrawShapeSubsetting::addSubsetShape( const AttributableShapeSharedPtr& rShape )
346         {
347             RTL_LOGFILE_CONTEXT( aLog, "::presentation::internal::DrawShapeSubsetting::addSubsetShape()" );
348 
349             // subset shape already created for this DocTreeNode?
350             SubsetEntry aEntry;
351             const DocTreeNode& rEffectiveSubset( rShape->getSubsetNode() );
352 
353             aEntry.mnStartActionIndex 	= rEffectiveSubset.getStartIndex();
354             aEntry.mnEndActionIndex 	= rEffectiveSubset.getEndIndex();
355 
356             ShapeSet::const_iterator aIter;
357             if( (aIter=maSubsetShapes.find( aEntry )) != maSubsetShapes.end() )
358             {
359                 // already created, increment use count and return
360 
361                 // safe cast, since set order does not depend on
362                 // mnSubsetQueriedCount
363                 const_cast<SubsetEntry&>(*aIter).mnSubsetQueriedCount++;
364             }
365             else
366             {
367                 // not yet created, init entry
368                 aEntry.mnSubsetQueriedCount = 1;
369                 aEntry.mpShape = rShape;
370 
371                 maSubsetShapes.insert( aEntry );
372 
373                 // update cached subset borders
374                 updateSubsetBounds( aEntry );
375                 updateSubsets();
376             }
377         }
378 
379         bool DrawShapeSubsetting::revokeSubsetShape( const AttributableShapeSharedPtr& rShape )
380         {
381             RTL_LOGFILE_CONTEXT( aLog, "::presentation::internal::DrawShapeSubsetting::revokeSubsetShape()" );
382 
383             // lookup subset shape
384             SubsetEntry aEntry;
385             const DocTreeNode& rEffectiveSubset( rShape->getSubsetNode() );
386 
387             aEntry.mnStartActionIndex 	= rEffectiveSubset.getStartIndex();
388             aEntry.mnEndActionIndex 	= rEffectiveSubset.getEndIndex();
389 
390             ShapeSet::iterator aIter;
391             if( (aIter=maSubsetShapes.find( aEntry )) == maSubsetShapes.end() )
392                 return false; // not found, subset was never queried
393 
394             // last client of the subset revoking?
395             if( aIter->mnSubsetQueriedCount > 1 )
396             {
397                 // no, still clients out there. Just decrement use count
398                 // safe cast, since order does not depend on mnSubsetQueriedCount
399                 const_cast<SubsetEntry&>(*aIter).mnSubsetQueriedCount--;
400 
401                 VERBOSE_TRACE( "Subset summary: shape 0x%X, %d open subsets, revoked subset has refcount %d",
402                                this,
403                                maSubsetShapes.size(),
404                                aIter->mnSubsetQueriedCount );
405 
406                 return false; // not the last client
407             }
408 
409             VERBOSE_TRACE( "Subset summary: shape 0x%X, %d open subsets, cleared subset has range [%d,%d]",
410                            this,
411                            maSubsetShapes.size(),
412                            aEntry.mnStartActionIndex,
413                            aEntry.mnEndActionIndex );
414 
415             // yes, remove from set
416             maSubsetShapes.erase( aIter );
417 
418 
419             // update currently active subset for _our_ shape (the
420             // part of this shape that is visible, i.e. not displayed
421             // in subset shapes)
422             // ======================================================
423 
424             // init bounds
425             mnMinSubsetActionIndex = SAL_MAX_INT32;
426             mnMaxSubsetActionIndex = 0;
427 
428             // TODO(P2): This is quite expensive, when
429             // after every subset effect end, we have to scan
430             // the whole shape set
431 
432             // determine new subset range
433             ::std::for_each( maSubsetShapes.begin(),
434                              maSubsetShapes.end(),
435                              ::boost::bind(&DrawShapeSubsetting::updateSubsetBounds,
436                                            this,
437                                            _1 ) );
438 
439             updateSubsets();
440 
441             return true;
442         }
443 
444         namespace
445         {
446             /** Iterate over all action classification entries in the
447                 given range, pass each element range found to the
448                 given functor.
449 
450                 This method extracts, for each of the different action
451                 classifications, the count and the ranges for each of
452                 them, and calls the provided functor with that
453                 information.
454 
455                 @tpl FunctorT
456                 This is the functor's operator() calling signature,
457                 with eCurrElemClassification denoting the current
458                 classification type the functor is called for,
459                 nCurrElemCount the running total of elements visited
460                 for the given class (starting from 0), and
461                 rCurrElemBegin/rCurrElemEnd the range of the current
462                 element (i.e. the iterators from the start to the end
463                 of this element).
464                 <pre>
465                 bool operator()( IndexClassificator								 eCurrElemClassification
466                 				 sal_Int32										 nCurrElemCount,
467 								 const IndexClassificatorVector::const_iterator& rCurrElemBegin,
468 								 const IndexClassificatorVector::const_iterator& rCurrElemEnd );
469                 </pre>
470                 If the functor returns false, iteration over the
471                 shapes is immediately stopped.
472 
473                 @param io_pFunctor
474                 This functor is called for every shape found.
475 
476                 @param rBegin
477                 Start of range to iterate over
478 
479                 @param rEnd
480                 End of range to iterate over
481 
482                 @return the number of shapes found in the metafile
483              */
484             template< typename FunctorT > void iterateActionClassifications(
485                 FunctorT& 															 io_rFunctor,
486                 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rBegin,
487                 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rEnd )
488             {
489                 sal_Int32 nCurrShapeCount( 0 );
490                 sal_Int32 nCurrParaCount( 0 );
491                 sal_Int32 nCurrLineCount( 0 );
492                 sal_Int32 nCurrSentenceCount( 0 );
493                 sal_Int32 nCurrWordCount( 0 );
494                 sal_Int32 nCurrCharCount( 0 );
495 
496                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastShapeStart(rBegin);
497                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastParaStart(rBegin);
498                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastLineStart(rBegin);
499                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastSentenceStart(rBegin);
500                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastWordStart(rBegin);
501                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aLastCharStart(rBegin);
502 
503                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aNext;
504                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator aCurr( rBegin );
505                 while( aCurr != rEnd )
506                 {
507                     // aNext will hold an iterator to the next element
508                     // (or the past-the-end iterator, if aCurr
509                     // references the last element). Used to pass a
510                     // valid half-open range to the functors.
511                     aNext = aCurr;
512                     ++aNext;
513 
514                     switch( *aCurr )
515                     {
516                         default:
517                             ENSURE_OR_THROW( false,
518                                               "Unexpected type in iterateDocShapes()" );
519                         case DrawShapeSubsetting::CLASS_NOOP:
520                             // ignore NOOP actions
521                             break;
522 
523                         case DrawShapeSubsetting::CLASS_SHAPE_START:
524                             // regardless of ending action
525                             // classifications before: a new shape
526                             // always also starts contained elements
527                             // anew
528                             aLastShapeStart    =
529                             aLastParaStart     =
530                             aLastLineStart     =
531                             aLastSentenceStart =
532                             aLastWordStart     =
533                             aLastCharStart     = aCurr;
534                             break;
535 
536                         case DrawShapeSubsetting::CLASS_SHAPE_END:
537                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_SHAPE_END,
538                                               nCurrShapeCount,
539                                               aLastShapeStart,
540                                               aNext ) )
541                             {
542                                 return;
543                             }
544 
545                             ++nCurrShapeCount;
546                             // FALLTHROUGH intended: shape end also
547                             // ends lines
548                         case DrawShapeSubsetting::CLASS_PARAGRAPH_END:
549                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_PARAGRAPH_END,
550                                               nCurrParaCount,
551                                               aLastParaStart,
552                                               aNext ) )
553                             {
554                                 return;
555                             }
556 
557                             ++nCurrParaCount;
558                             aLastParaStart = aNext;
559                             // FALLTHROUGH intended: para end also
560                             // ends line
561                         case DrawShapeSubsetting::CLASS_LINE_END:
562                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_LINE_END,
563                                               nCurrLineCount,
564                                               aLastLineStart,
565                                               aNext ) )
566                             {
567                                 return;
568                             }
569 
570                             ++nCurrLineCount;
571                             aLastLineStart = aNext;
572 
573                             if( *aCurr == DrawShapeSubsetting::CLASS_LINE_END )
574                             {
575                                 // DON'T fall through here, as a line
576                                 // does NOT end neither a sentence,
577                                 // nor a word. OTOH, all parent
578                                 // structures (paragraph and shape),
579                                 // which itself fall through to this
580                                 // code, DO end word, sentence and
581                                 // character cell.
582 
583                                 // TODO(F1): Maybe a line should end a
584                                 // character cell, OTOH?
585                                 break;
586                             }
587                             // FALLTHROUGH intended
588                         case DrawShapeSubsetting::CLASS_SENTENCE_END:
589                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_SENTENCE_END,
590                                               nCurrSentenceCount,
591                                               aLastSentenceStart,
592                                               aNext ) )
593                             {
594                                 return;
595                             }
596 
597                             ++nCurrSentenceCount;
598                             aLastSentenceStart = aNext;
599                             // FALLTHROUGH intended
600                         case DrawShapeSubsetting::CLASS_WORD_END:
601                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_WORD_END,
602                                               nCurrWordCount,
603                                               aLastWordStart,
604                                               aNext ) )
605                             {
606                                 return;
607                             }
608 
609                             ++nCurrWordCount;
610                             aLastWordStart = aNext;
611                             // FALLTHROUGH intended
612                         case DrawShapeSubsetting::CLASS_CHARACTER_CELL_END:
613                             if( !io_rFunctor( DrawShapeSubsetting::CLASS_CHARACTER_CELL_END,
614                                               nCurrCharCount,
615                                               aLastCharStart,
616                                               aNext ) )
617                             {
618                                 return;
619                             }
620 
621                             ++nCurrCharCount;
622                             aLastCharStart = aNext;
623                             break;
624                     }
625 
626                     aCurr = aNext;
627                 }
628             }
629 
630             DrawShapeSubsetting::IndexClassificator mapDocTreeNode( DocTreeNode::NodeType eNodeType )
631             {
632                 switch( eNodeType )
633                 {
634                     case DocTreeNode::NODETYPE_INVALID:
635                         // FALLTHROUGH intended
636                     default:
637                         OSL_ENSURE(false,
638                                    "DrawShapeSubsetting::mapDocTreeNode(): unexpected node type");
639                         return DrawShapeSubsetting::CLASS_NOOP;
640 
641                     case DocTreeNode::NODETYPE_LOGICAL_SHAPE:
642                         // FALLTHROUGH intended
643                     case DocTreeNode::NODETYPE_FORMATTING_SHAPE:
644                         return DrawShapeSubsetting::CLASS_SHAPE_END;
645 
646                     case DocTreeNode::NODETYPE_FORMATTING_LINE:
647                         return DrawShapeSubsetting::CLASS_LINE_END;
648 
649                     case DocTreeNode::NODETYPE_LOGICAL_PARAGRAPH:
650                         return DrawShapeSubsetting::CLASS_PARAGRAPH_END;
651 
652                     case DocTreeNode::NODETYPE_LOGICAL_SENTENCE:
653                         return DrawShapeSubsetting::CLASS_SENTENCE_END;
654 
655                     case DocTreeNode::NODETYPE_LOGICAL_WORD:
656                         return DrawShapeSubsetting::CLASS_WORD_END;
657 
658                     case DocTreeNode::NODETYPE_LOGICAL_CHARACTER_CELL:
659                         return DrawShapeSubsetting::CLASS_CHARACTER_CELL_END;
660                 };
661             }
662 
663             /// Counts number of class occurrences
664             class CountClassFunctor
665             {
666             public:
667                 CountClassFunctor( DrawShapeSubsetting::IndexClassificator eClass ) :
668                     meClass( eClass ),
669                     mnCurrCount(0)
670                 {
671                 }
672 
673                 bool operator()( DrawShapeSubsetting::IndexClassificator								eCurrElemClassification,
674                 				 sal_Int32																/*nCurrElemCount*/,
675 								 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator&	/*rCurrElemBegin*/,
676 								 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator&	/*rCurrElemEnd*/ )
677                 {
678                     if( eCurrElemClassification == meClass )
679                         ++mnCurrCount;
680 
681                     return true; // never stop, count all occurrences
682                 }
683 
684                 sal_Int32 getCount() const
685                 {
686                     return mnCurrCount;
687                 }
688 
689             private:
690                 DrawShapeSubsetting::IndexClassificator meClass;
691                 sal_Int32								mnCurrCount;
692             };
693         }
694 
695         sal_Int32 DrawShapeSubsetting::implGetNumberOfTreeNodes( const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rBegin,
696                                                                  const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rEnd,
697                                                                  DocTreeNode::NodeType 												  eNodeType ) const
698         {
699             const IndexClassificator eRequestedClass(
700                 mapDocTreeNode( eNodeType ) );
701 
702             // create a counting functor for the requested class of
703             // actions
704             CountClassFunctor aFunctor( eRequestedClass );
705 
706             // count all occurrences in the given range
707             iterateActionClassifications( aFunctor, rBegin, rEnd );
708 
709             return aFunctor.getCount();
710         }
711 
712         sal_Int32 DrawShapeSubsetting::getNumberOfTreeNodes( DocTreeNode::NodeType eNodeType ) const
713         {
714             ensureInitializedNodeTree();
715 
716             return implGetNumberOfTreeNodes( maActionClassVector.begin(),
717                                              maActionClassVector.end(),
718                                              eNodeType );
719         }
720 
721         namespace
722         {
723             /** This functor finds the nth occurrence of a given
724                 action class.
725 
726                 The operator() compares the given index value with the
727                 requested index, as given on the functor's
728                 constructor. Then, the operator() returns false,
729                 denoting that the requested action is found.
730              */
731             class FindNthElementFunctor
732             {
733             public:
734                 FindNthElementFunctor( sal_Int32 								nNodeIndex,
735                                        DrawShapeSubsetting::IndexClassificator	eClass ) :
736                     mnNodeIndex( nNodeIndex ),
737                     meClass( eClass )
738                 {
739                 }
740 
741                 bool operator()( DrawShapeSubsetting::IndexClassificator								eCurrElemClassification,
742                 				 sal_Int32																nCurrElemCount,
743 								 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator&	rCurrElemBegin,
744 								 const DrawShapeSubsetting::IndexClassificatorVector::const_iterator&	rCurrElemEnd )
745                 {
746                     if( eCurrElemClassification == meClass &&
747                         nCurrElemCount == mnNodeIndex )
748                     {
749                         maLastBegin = rCurrElemBegin;
750                         maLastEnd = rCurrElemEnd;
751 
752                         return false; // abort iteration, we've
753                                       // already found what we've been
754                                       // looking for
755                     }
756 
757                     return true; // keep on truckin'
758                 }
759 
760                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator getBeginElement() const
761                 {
762                     return maLastBegin;
763                 }
764 
765                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator getEndElement() const
766                 {
767                     return maLastEnd;
768                 }
769 
770             private:
771                 sal_Int32														mnNodeIndex;
772                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator	maLastBegin;
773                 DrawShapeSubsetting::IndexClassificatorVector::const_iterator	maLastEnd;
774                 DrawShapeSubsetting::IndexClassificator							meClass;
775             };
776 
777             DocTreeNode makeTreeNode( const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rBegin,
778                                       const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rStart,
779                                       const DrawShapeSubsetting::IndexClassificatorVector::const_iterator& rEnd,
780                                       DocTreeNode::NodeType												   eNodeType )
781             {
782                 return DocTreeNode( ::std::distance(rBegin,
783                                                     rStart),
784                                     ::std::distance(rBegin,
785                                                     rEnd),
786                                     eNodeType );
787             }
788         }
789 
790         DocTreeNode DrawShapeSubsetting::implGetTreeNode( const IndexClassificatorVector::const_iterator&	rBegin,
791                                                           const IndexClassificatorVector::const_iterator&	rEnd,
792                                                           sal_Int32											nNodeIndex,
793                                                           DocTreeNode::NodeType								eNodeType ) const
794         {
795             const IndexClassificator eRequestedClass(
796                 mapDocTreeNode( eNodeType ) );
797 
798             // create a nth element functor for the requested class of
799             // actions, and nNodeIndex as the target index
800             FindNthElementFunctor aFunctor( nNodeIndex,
801                                             eRequestedClass );
802 
803             // find given index in the given range
804             iterateActionClassifications( aFunctor, rBegin, rEnd );
805 
806             return makeTreeNode( maActionClassVector.begin(),
807                                  aFunctor.getBeginElement(),
808                                  aFunctor.getEndElement(),
809                                  eNodeType );
810         }
811 
812         DocTreeNode DrawShapeSubsetting::getTreeNode( sal_Int32				nNodeIndex,
813                                                       DocTreeNode::NodeType	eNodeType ) const
814         {
815             ensureInitializedNodeTree();
816 
817             return implGetTreeNode( maActionClassVector.begin(),
818                                     maActionClassVector.end(),
819                                     nNodeIndex,
820                                     eNodeType );
821         }
822 
823         sal_Int32 DrawShapeSubsetting::getNumberOfSubsetTreeNodes( const DocTreeNode&  		rParentNode,
824                                                                    DocTreeNode::NodeType	eNodeType ) const
825         {
826             ensureInitializedNodeTree();
827 
828             // convert from vector indices to vector iterators
829             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aBegin( maActionClassVector.begin() );
830             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aParentBegin( aBegin + rParentNode.getStartIndex() );
831             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aParentEnd( aBegin + rParentNode.getEndIndex() );
832 
833             return implGetNumberOfTreeNodes( aParentBegin,
834                                              aParentEnd,
835                                              eNodeType );
836         }
837 
838         DocTreeNode DrawShapeSubsetting::getSubsetTreeNode( const DocTreeNode& 		rParentNode,
839                                                             sal_Int32				nNodeIndex,
840                                                             DocTreeNode::NodeType	eNodeType ) const
841         {
842             ensureInitializedNodeTree();
843 
844             // convert from vector indices to vector iterators
845             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aBegin( maActionClassVector.begin() );
846             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aParentBegin( aBegin + rParentNode.getStartIndex() );
847             const DrawShapeSubsetting::IndexClassificatorVector::const_iterator aParentEnd( aBegin + rParentNode.getEndIndex() );
848 
849             return implGetTreeNode( aParentBegin,
850                                     aParentEnd,
851                                     nNodeIndex,
852                                     eNodeType );
853         }
854 
855         const VectorOfDocTreeNodes& DrawShapeSubsetting::getActiveSubsets() const
856         {
857             return maCurrentSubsets;
858         }
859 
860     }
861 }
862