LibreOffice Module sw (master)  1
SwNumberTree.cxx
Go to the documentation of this file.
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 #include <algorithm>
21 #include <functional>
22 #include <SwNumberTree.hxx>
23 #include <osl/diagnose.h>
24 #include <sal/log.hxx>
25 
26 #include <cassert>
27 
28 using std::vector;
29 using std::find;
30 
32  : mChildren(),
33  mpParent( nullptr ),
34  mnNumber( 0 ),
35  mbContinueingPreviousSubTree( false ),
36  mbPhantom( false ),
37  mItLastValid()
38 {
39  mItLastValid = mChildren.end();
40 }
41 
43 {
44  if (GetChildCount() > 0)
45  {
46  if (HasOnlyPhantoms())
47  {
48  delete *mChildren.begin();
49 
50  mChildren.clear();
51  mItLastValid = mChildren.end();
52  }
53  else
54  {
55  OSL_FAIL("lost children!");
56  }
57  }
58 
59  OSL_ENSURE( IsPhantom() || mpParent == nullptr, ": I'm not supposed to have a parent.");
60 
61  mpParent = reinterpret_cast<SwNumberTreeNode *>(0xdeadbeef);
62 
63  OSL_ENSURE(mChildren.empty(), "children left!");
64 }
65 
67 {
68  SwNumberTreeNode * pNew = nullptr;
69 
70  if (! mChildren.empty() &&
71  (*mChildren.begin())->IsPhantom())
72  {
73  OSL_FAIL("phantom already present");
74  }
75  else
76  {
77  pNew = Create();
78  pNew->mbPhantom = true;
79  pNew->mpParent = this;
80 
81  std::pair<tSwNumberTreeChildren::iterator, bool> aInsert =
82  mChildren.insert(pNew);
83 
84  if (! aInsert.second)
85  {
86  OSL_FAIL("insert of phantom failed!");
87 
88  delete pNew;
89  pNew = nullptr;
90  }
91  }
92 
93  return pNew;
94 }
95 
97 {
98  SwNumberTreeNode * pResult = mpParent;
99 
100  if (pResult)
101  while (pResult->mpParent)
102  pResult = pResult->mpParent;
103 
104  return pResult;
105 }
106 
108 {
109  tSwNumberTreeChildren::iterator aIt = mChildren.begin();
110 
111  if (aIt != mChildren.end() && (*aIt)->IsPhantom())
112  {
113  (*aIt)->ClearObsoletePhantoms();
114 
115  if ((*aIt)->mChildren.empty())
116  {
117  // #i60652#
118  // Because <mChildren.erase(aIt)> could destroy the element, which
119  // is referenced by <mItLastValid>, it's needed to adjust
120  // <mItLastValid> before erasing <aIt>.
121  SetLastValid(mChildren.end());
122 
123  delete *aIt;
124  mChildren.erase(aIt);
125  }
126  }
127 }
128 
130 {
131  tSwNumberTreeChildren::const_iterator aValidateIt =
132  GetIterator(pNode);
133 
134  if (aValidateIt != mChildren.end())
135  {
136  OSL_ENSURE((*aValidateIt)->mpParent == this, "wrong parent");
137 
138  tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
139 
140  // -->
141  // improvement:
142  // - Only one time checked for <mChildren.end()>.
143  // - Less checks for each loop run.
144  // correction:
145  // - consider case that current node isn't counted and isn't the first
146  // child of its parent. In this case the number of last counted child
147  // of the previous node determines the start value for the following
148  // children loop, if all children have to be validated and the first
149  // one doesn't restart the counting.
150  SwNumberTree::tSwNumTreeNumber nTmpNumber( 0 );
151  if (aIt != mChildren.end())
152  nTmpNumber = (*aIt)->mnNumber;
153  else
154  {
155  aIt = mChildren.begin();
156  (*aIt)->mbContinueingPreviousSubTree = false;
157 
158  // determine default start value
159  // consider the case that the first child isn't counted.
160  nTmpNumber = (*aIt)->GetStartValue();
161  if ( !(*aIt)->IsCounted() &&
162  ( !(*aIt)->HasCountedChildren() || (*aIt)->IsPhantom() ) )
163  {
164  --nTmpNumber;
165  }
166 
167  // determine special start value for the case that first child
168  // doesn't restart the numbering and the parent node isn't counted
169  // and isn't the first child.
170  const bool bParentCounted( IsCounted() &&
171  ( !IsPhantom() ||
173  if ( !(*aIt)->IsRestart() &&
174  GetParent() && !bParentCounted )
175  {
176  tSwNumberTreeChildren::const_iterator aParentChildIt =
177  GetParent()->GetIterator( this );
178  while ( aParentChildIt != GetParent()->mChildren.begin() )
179  {
180  --aParentChildIt;
181  SwNumberTreeNode* pPrevNode( *aParentChildIt );
182  if ( pPrevNode->GetChildCount() > 0 )
183  {
184  (*aIt)->mbContinueingPreviousSubTree = true;
185  nTmpNumber = (*(pPrevNode->mChildren.rbegin()))->GetNumber();
186  if ( (*aIt)->IsCounted() &&
187  ( !(*aIt)->IsPhantom() ||
188  (*aIt)->HasPhantomCountedParent() ) )
189  {
190  ++nTmpNumber;
191  }
192  break;
193  }
194  else if ( pPrevNode->IsCounted() )
195  {
196  break;
197  }
198  else
199  {
200  // Previous node has no children and is not counted.
201  // Thus, next turn and check for the previous node.
202  }
203  }
204  }
205 
206  (*aIt)->mnNumber = nTmpNumber;
207  }
208 
209  while (aIt != aValidateIt)
210  {
211  ++aIt;
212  (*aIt)->mbContinueingPreviousSubTree = false;
213 
214  // --> only for counted nodes the number
215  // has to be adjusted, compared to the previous node.
216  // this condition is hold also for nodes, which restart the numbering.
217  if ( (*aIt)->IsCounted() )
218  {
219  if ((*aIt)->IsRestart())
220  nTmpNumber = (*aIt)->GetStartValue();
221  else
222  ++nTmpNumber;
223  }
224 
225  (*aIt)->mnNumber = nTmpNumber;
226  }
227 
228  SetLastValid(aIt, true);
229  }
230 }
231 
233 {
234  tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
235 
236  do
237  {
238  if (aIt == mChildren.end())
239  {
240  aIt = mChildren.begin();
241  }
242  else
243  ++aIt;
244 
245  if (aIt != mChildren.end())
246  {
247  SwNumberTree::tSwNumTreeNumber nTmpNumber = 0;
248  SwNumberTreeNode * pPred = (*aIt)->GetPred();
249 
250  // #i64311#
251  // correct consideration of phantoms
252  // correct consideration of restart at a number tree node
253  if ( pPred )
254  {
255  if ( !(*aIt)->IsCounted() )
256  // #i65284#
257  nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() );
258  else
259  {
260  if ( (*aIt)->IsRestart() )
261  nTmpNumber = (*aIt)->GetStartValue();
262  else
263  nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() ) + 1;
264  }
265  }
266  else
267  {
268  if ( !(*aIt)->IsCounted() )
269  nTmpNumber = GetStartValue() - 1;
270  else
271  {
272  if ( (*aIt)->IsRestart() )
273  nTmpNumber = (*aIt)->GetStartValue();
274  else
275  nTmpNumber = GetStartValue();
276  }
277  }
278 
279  (*aIt)->mnNumber = nTmpNumber;
280  }
281  }
282  while (aIt != mChildren.end() && *aIt != pNode);
283 
284  // #i74748# - applied patch from garnier_romain
285  // number tree node has to be validated.
286  SetLastValid( aIt, true );
287 }
288 
290 {
291  if (! IsValid(pNode))
292  {
293  if (IsContinuous())
294  ValidateContinuous(pNode);
295  else
296  ValidateHierarchical(pNode);
297  }
298 }
299 
301  bool bValidate) const
302 {
303  if (mpParent)
304  {
305  mpParent->GetNumberVector_(rVector, bValidate);
306  rVector.push_back(GetNumber(bValidate));
307  }
308 }
309 
311 {
312  if (IsPhantom())
313  return (*mChildren.begin())->GetFirstNonPhantomChild();
314 
315  return this;
316 }
317 
322  SwNumberTreeNode& _rDestNode )
323 {
324  if ( mChildren.empty() )
325  return;
326 
327  // determine first child, which has to move to <_rDestNode>
328  tSwNumberTreeChildren::iterator aItUpper( mChildren.end() );
329  if ((*mChildren.begin())->IsPhantom() &&
330  _rCompareNode.LessThan(*(*mChildren.begin())->GetFirstNonPhantomChild()))
331  {
332  aItUpper = mChildren.begin();
333  }
334  else
335  {
336  aItUpper = mChildren.upper_bound(&_rCompareNode);
337  }
338 
339  // move children
340  if (aItUpper != mChildren.end())
341  {
342  tSwNumberTreeChildren::iterator aIt;
343  for (aIt = aItUpper; aIt != mChildren.end(); ++aIt)
344  (*aIt)->mpParent = &_rDestNode;
345 
346  _rDestNode.mChildren.insert(aItUpper, mChildren.end());
347 
348  // #i60652#
349  // Because <mChildren.erase(aItUpper, mChildren.end())> could destroy
350  // the element, which is referenced by <mItLastValid>, it's needed to
351  // adjust <mItLastValid> before erasing <aIt>.
352  SetLastValid( mChildren.end() );
353 
354  mChildren.erase(aItUpper, mChildren.end());
355 
356  // #i60652#
357  if ( !mChildren.empty() )
358  {
359  SetLastValid( --(mChildren.end()) );
360  }
361  }
362 
363 #ifdef DBG_UTIL
364  IsSane(false);
365  _rDestNode.IsSane(true);
366 #endif
367 }
368 
370 {
371  if (! mChildren.empty())
372  {
373  tSwNumberTreeChildren::iterator aItBegin = mChildren.begin();
374  SwNumberTreeNode * pMyFirst = *mChildren.begin();
375 
376  // #i60652#
377  // Because <mChildren.erase(aItBegin)> could destroy the element,
378  // which is referenced by <mItLastValid>, it's needed to adjust
379  // <mItLastValid> before erasing <aItBegin>.
380  SetLastValid(mChildren.end());
381 
382  if (pMyFirst->IsPhantom())
383  {
384  SwNumberTreeNode * pDestLast = nullptr;
385 
386  if (pDest->mChildren.empty())
387  pDestLast = pDest->CreatePhantom();
388  else
389  pDestLast = *pDest->mChildren.rbegin();
390 
391  pMyFirst->MoveChildren(pDestLast);
392 
393  delete pMyFirst;
394  mChildren.erase(aItBegin);
395 
396  aItBegin = mChildren.begin();
397  }
398 
399  for (auto& rpChild : mChildren)
400  rpChild->mpParent = pDest;
401 
402  pDest->mChildren.insert(mChildren.begin(), mChildren.end());
403  mChildren.clear();
404  // <stl::set.clear()> destroys all existing iterators.
405  // Thus, <mItLastValid> is also destroyed and reset becomes necessary
406  mItLastValid = mChildren.end();
407  }
408 
409  OSL_ENSURE(mChildren.empty(), "MoveChildren failed!");
410 
411 #ifdef DBG_UTIL
412  IsSane(false);
413  pDest->IsSane(false);
414 #endif
415 }
416 
418  const int nDepth )
419 {
420  /*
421  Algorithm:
422 
423  Search first child A that is greater than pChild,
424  A may be the end of children.
425  If nDepth > 0 then
426  {
427  if A is first child then
428  create new phantom child B at beginning of child list
429  else
430  B is A
431 
432  Add child to B with depth nDepth - 1.
433  }
434  else
435  {
436  Insert pNode before A.
437 
438  if A has predecessor B then
439  remove children of B that are greater as A and insert them as
440  children of A.
441  }
442 
443 */
444 
445  if ( nDepth < 0 )
446  {
447  OSL_FAIL( "<SwNumberTreeNode::AddChild(..)> - parameter <nDepth> out of valid range. Serious defect." );
448  return;
449  }
450 
451  if ( pChild->GetParent() != nullptr || pChild->GetChildCount() > 0 )
452  {
453  OSL_FAIL("only orphans allowed.");
454  return;
455  }
456 
457  if (nDepth > 0)
458  {
459  tSwNumberTreeChildren::iterator aInsertDeepIt =
460  mChildren.upper_bound(pChild);
461 
462  OSL_ENSURE(! (aInsertDeepIt != mChildren.end() &&
463  (*aInsertDeepIt)->IsPhantom()), " unexpected phantom");
464 
465  if (aInsertDeepIt == mChildren.begin())
466  {
467  SwNumberTreeNode * pNew = CreatePhantom();
468 
469  SetLastValid(mChildren.end());
470 
471  if (pNew)
472  pNew->AddChild(pChild, nDepth - 1);
473  }
474  else
475  {
476  --aInsertDeepIt;
477  (*aInsertDeepIt)->AddChild(pChild, nDepth - 1);
478  }
479 
480  }
481  else
482  {
483  pChild->PreAdd();
484  std::pair<tSwNumberTreeChildren::iterator, bool> aResult =
485  mChildren.insert(pChild);
486 
487  if (aResult.second)
488  {
489  pChild->mpParent = this;
490  bool bNotification = pChild->IsNotificationEnabled();
491  tSwNumberTreeChildren::iterator aInsertedIt = aResult.first;
492 
493  if (aInsertedIt != mChildren.begin())
494  {
495  tSwNumberTreeChildren::iterator aPredIt = aInsertedIt;
496  --aPredIt;
497 
498  // -->
499  // Move greater children of previous node to new child.
500  // This has to be done recursively on the children levels.
501  // Initialize loop variables <pPrevChildNode> and <pDestNode>
502  // for loop on children levels.
503  SwNumberTreeNode* pPrevChildNode( *aPredIt );
504  SwNumberTreeNode* pDestNode( pChild );
505  while ( pDestNode && pPrevChildNode &&
506  pPrevChildNode->GetChildCount() > 0 )
507  {
508  // move children
509  pPrevChildNode->MoveGreaterChildren( *pChild, *pDestNode );
510 
511  // prepare next loop:
512  // - search of last child of <pPrevChildNode
513  // - If found, determine destination node
514  if ( pPrevChildNode->GetChildCount() > 0 )
515  {
516  tSwNumberTreeChildren::reverse_iterator aIt =
517  pPrevChildNode->mChildren.rbegin();
518  pPrevChildNode = *aIt;
519  // determine new destination node
520  if ( pDestNode->GetChildCount() > 0 )
521  {
522  pDestNode = *(pDestNode->mChildren.begin());
523  if ( !pDestNode->IsPhantom() )
524  {
525  pDestNode = pDestNode->mpParent->CreatePhantom();
526  }
527  }
528  else
529  {
530  pDestNode = pDestNode->CreatePhantom();
531  }
532  }
533  else
534  {
535  // ready -> break loop.
536  break;
537  }
538  }
539  // assure that unnessary created phantoms at <pChild> are deleted.
540  pChild->ClearObsoletePhantoms();
541 
542  if ((*aPredIt)->IsValid())
543  SetLastValid(aPredIt);
544  }
545  else
546  SetLastValid(mChildren.end());
547 
549 
550  if( bNotification )
551  {
552  // invalidation of not counted parent
553  // and notification of its siblings.
554  if ( !IsCounted() )
555  {
556  InvalidateMe();
558  }
560  }
561  }
562  }
563 
564 #ifdef DBG_UTIL
565  IsSane(false);
566 #endif
567 }
568 
570 {
571  /*
572  Algorithm:
573 
574  if pChild has predecessor A then
575  B is A
576  else
577  create phantom child B at beginning of child list
578 
579  Move children of pChild to B.
580  */
581 
582  if (pChild->IsPhantom())
583  {
584  OSL_FAIL("not applicable to phantoms!");
585 
586  return;
587  }
588 
589  tSwNumberTreeChildren::const_iterator aRemoveIt = GetIterator(pChild);
590 
591  if (aRemoveIt != mChildren.end())
592  {
593  SwNumberTreeNode * pRemove = *aRemoveIt;
594 
595  pRemove->mpParent = nullptr;
596 
597  tSwNumberTreeChildren::const_iterator aItPred = mChildren.end();
598 
599  if (aRemoveIt == mChildren.begin())
600  {
601  if (! pRemove->mChildren.empty())
602  {
603  CreatePhantom();
604 
605  aItPred = mChildren.begin();
606  }
607  }
608  else
609  {
610  aItPred = aRemoveIt;
611  --aItPred;
612  }
613 
614  if (! pRemove->mChildren.empty())
615  {
616  pRemove->MoveChildren(*aItPred);
617  (*aItPred)->InvalidateTree();
618  (*aItPred)->NotifyInvalidChildren();
619  }
620 
621  // #i60652#
622  // Because <mChildren.erase(aRemoveIt)> could destroy the element,
623  // which is referenced by <mItLastValid>, it's needed to adjust
624  // <mItLastValid> before erasing <aRemoveIt>.
625  if (aItPred != mChildren.end() && (*aItPred)->IsPhantom())
626  SetLastValid(mChildren.end());
627  else
628  SetLastValid(aItPred);
629 
630  mChildren.erase(aRemoveIt);
631 
633  }
634  else
635  {
636  OSL_FAIL("RemoveChild: failed!");
637  }
638 
639  pChild->PostRemove();
640 }
641 
643 {
644  if (mpParent)
645  {
646  SwNumberTreeNode * pSavedParent = mpParent;
647 
648  pSavedParent->RemoveChild(this);
649 
650  while (pSavedParent && pSavedParent->IsPhantom() &&
651  pSavedParent->HasOnlyPhantoms())
652  pSavedParent = pSavedParent->GetParent();
653 
654  if (pSavedParent)
655  pSavedParent->ClearObsoletePhantoms();
656 
657 #ifdef DBG_UTIL
658  IsSane(false);
659 #endif
660  }
661 }
662 
664 {
665  return mpParent && mpParent->IsValid(this);
666 }
667 
669  const
670 {
671  if (bValidate && mpParent)
672  mpParent->Validate(this);
673 
674  return mnNumber;
675 }
676 
677 
679 {
680  vector<SwNumberTree::tSwNumTreeNumber> aResult;
681 
682  GetNumberVector_(aResult);
683 
684  return aResult;
685 }
686 
687 bool SwNumberTreeNode::IsValid(const SwNumberTreeNode * pChild) const
688 {
689  bool bResult = false;
690 
691  if (mItLastValid != mChildren.end())
692  {
693  if (pChild && pChild->mpParent == this)
694  {
695  bResult = ! (*mItLastValid)->LessThan(*pChild);
696  }
697  }
698 
699  return bResult;
700 }
701 
702 
704 {
705  bool bResult = false;
706 
707  if (GetChildCount() == 1)
708  {
709  tSwNumberTreeChildren::const_iterator aIt = mChildren.begin();
710 
711  bResult = (*aIt)->IsPhantom() && (*aIt)->HasOnlyPhantoms();
712  }
713  else if (GetChildCount() == 0)
714  bResult = true;
715 
716  return bResult;
717 }
718 
720 {
721  return !IsPhantom() ||
723 }
724 
726 {
727  bool bRet( false );
728 
729  OSL_ENSURE( IsPhantom(),
730  "<SwNumberTreeNode::HasPhantomCountedParent()> - wrong usage of method - it's only for phantoms" );
731  if ( IsPhantom() && mpParent )
732  {
733  if ( mpParent == GetRoot() )
734  {
735  bRet = true;
736  }
737  else if ( !mpParent->IsPhantom() )
738  {
739  bRet = mpParent->IsCounted();
740  }
741  else
742  {
744  }
745  }
746 
747  return bRet;
748 }
749 
751 {
752  tSwNumberTreeChildren::const_iterator aIt = mChildren.begin();
753 
754  if ((*aIt)->IsPhantom())
755  ++aIt;
756 
757  return *aIt == pNode;
758 }
759 
761 {
762  bool bResult = true;
763 
764  if (GetParent())
765  {
766  if (GetParent()->IsFirst(this))
767  {
768  SwNumberTreeNode * pNode = GetParent();
769 
770  while (pNode)
771  {
772  if (!pNode->IsPhantom() && pNode->GetParent())
773  {
774  bResult = false;
775  break;
776  }
777 
778  pNode = pNode->GetParent();
779  }
780 
781  // If node isn't the first child, it is the second child and the
782  // first child is a phanton. In this case check, if the first phantom
783  // child have only phanton children
784  if ( bResult &&
785  this != *(GetParent()->mChildren.begin()) &&
786  !(*(GetParent()->mChildren.begin()))->HasOnlyPhantoms() )
787  {
788  bResult = false;
789  }
790  }
791  else
792  bResult = false;
793  }
794 
795  return bResult;
796 }
797 
798 void SwNumberTreeNode::SetLevelInListTree( const int nLevel )
799 {
800  if ( nLevel < 0 )
801  {
802  OSL_FAIL( "<SwNumberTreeNode::SetLevelInListTree(..)> - parameter <nLevel> out of valid range. Serious defect." );
803  return;
804  }
805 
806  OSL_ENSURE( GetParent(),
807  "<SwNumberTreeNode::SetLevelInListTree(..)> - can only be called for number tree nodes in a list tree" );
808  if ( GetParent() )
809  {
810  if ( nLevel != GetLevelInListTree() )
811  {
812  SwNumberTreeNode* pRootTreeNode = GetRoot();
813  OSL_ENSURE( pRootTreeNode,
814  "<SwNumberTreeNode::SetLevelInListTree(..)> - no root tree node found. Serious defect." );
815 
816  RemoveMe();
817  pRootTreeNode->AddChild( this, nLevel );
818  }
819  }
820 }
821 
823 {
824  if (mpParent)
825  return mpParent->GetLevelInListTree() + 1;
826 
827  return -1;
828 }
829 
830 SwNumberTreeNode::tSwNumberTreeChildren::size_type
832 {
833  return mChildren.size();
834 }
835 
836 #ifdef DBG_UTIL
837 void SwNumberTreeNode::IsSane(bool bRecursive) const
838 {
839  vector<const SwNumberTreeNode*> aParents;
840 
841  return IsSane(bRecursive, aParents);
842 }
843 
844 void SwNumberTreeNode::IsSane(bool bRecursive,
845  vector<const SwNumberTreeNode *> rParents)
846  const
847 {
848  assert(find(rParents.begin(), rParents.end(), this) == rParents.end());
849 
850  assert(rParents.empty() || rParents.back() == mpParent);
851 
852  rParents.push_back(this);
853 
854  bool bFirst = true;
855  for (const auto& rpChild : mChildren)
856  {
857  if (rpChild)
858  {
859  if (rpChild->IsPhantom())
860  {
861  SAL_WARN_IF(rpChild->HasOnlyPhantoms(), "sw.core",
862  "HasOnlyPhantoms: is this an error?");
863 
864  assert(bFirst && "found phantom not at first position.");
865  }
866 
867  assert(rpChild->mpParent == this);
868 
869  if (mpParent)
870  {
871  assert(rpChild->IsPhantom() || !rpChild->LessThan(*this));
872  }
873  }
874  else
875  {
876  assert(!"found child that is NULL");
877  }
878 
879  if (bRecursive)
880  {
881  rpChild->IsSane(bRecursive, rParents);
882  }
883 
884  bFirst = false;
885  }
886 
887  rParents.pop_back();
888 }
889 #endif // DBG_UTIL
890 
891 SwNumberTreeNode::tSwNumberTreeChildren::const_iterator
893 {
894  tSwNumberTreeChildren::const_iterator aItResult =
895  mChildren.find(const_cast<SwNumberTreeNode *>(pChild));
896 
897  OSL_ENSURE( aItResult != mChildren.end(),
898  "something went wrong getting the iterator for a child");
899 
900  return aItResult;
901 }
902 
904  const SwNumberTreeNode * pB)
905 {
906  bool bResult = false;
907 
908  if (pA == nullptr && pB != nullptr)
909  bResult = true;
910  else if (pA != nullptr && pB != nullptr)
911  bResult = pA->LessThan(*pB);
912 
913  return bResult;
914 }
915 
917 {
918  SwNumberTreeNode * pResult = nullptr;
919  tSwNumberTreeChildren::const_reverse_iterator aIt = mChildren.rbegin();
920 
921  if (aIt != mChildren.rend())
922  {
923  pResult = (*aIt)->GetLastDescendant();
924 
925  if (! pResult)
926  pResult = *aIt;
927  }
928 
929  return pResult;
930 }
931 
932 bool SwNumberTreeNode::LessThan(const SwNumberTreeNode & rTreeNode) const
933 {
934  return this < &rTreeNode;
935 }
936 
938 {
939  SwNumberTreeNode * pResult = nullptr;
940 
941  if (mpParent)
942  {
943  tSwNumberTreeChildren::const_iterator aIt =
944  mpParent->GetIterator(this);
945 
946  if ( aIt == mpParent->mChildren.begin() )
947  {
948  // #i64311#
949  // root node is no valid predecessor
950  pResult = mpParent->GetParent() ? mpParent : nullptr;
951  }
952  else
953  {
954  --aIt;
955 
956  if ( !bSibling )
957  pResult = (*aIt)->GetLastDescendant();
958  else
959  pResult = (*aIt);
960 
961  if (! pResult)
962  pResult = (*aIt);
963  }
964  }
965 
966  return pResult;
967 }
968 
970  ( const SwNumberTreeNode::tSwNumberTreeChildren::const_iterator& aItValid,
971  bool bValidating ) const
972 {
973  OSL_ENSURE( (aItValid == mChildren.end() || GetIterator(*aItValid) != mChildren.end()),
974  "last-valid iterator");
975 
976  if (
977  bValidating ||
978  aItValid == mChildren.end() ||
979  (mItLastValid != mChildren.end() &&
980  (*aItValid)->LessThan(**mItLastValid))
981  )
982  {
983  mItLastValid = aItValid;
984  // invalidation of children of next not counted is needed
985  if ( GetParent() )
986  {
987  tSwNumberTreeChildren::const_iterator aParentChildIt =
988  GetParent()->GetIterator( this );
989  ++aParentChildIt;
990  if ( aParentChildIt != GetParent()->mChildren.end() )
991  {
992  SwNumberTreeNode* pNextNode( *aParentChildIt );
993  if ( !pNextNode->IsCounted() )
994  {
995  pNextNode->InvalidateChildren();
996  }
997  }
998  }
999  }
1000 
1001  {
1002  if (IsContinuous())
1003  {
1004  tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1005 
1006  if (aIt != mChildren.end())
1007  ++aIt;
1008  else
1009  aIt = mChildren.begin();
1010 
1011  while (aIt != mChildren.end())
1012  {
1013  (*aIt)->InvalidateTree();
1014 
1015  ++aIt;
1016  }
1017 
1018  if (mpParent)
1019  {
1020  mpParent->SetLastValid(mpParent->GetIterator(this), bValidating);
1021  }
1022  }
1023  }
1024 }
1025 
1027 {
1028  // do not call SetInvalid, would cause loop !!!
1029  mItLastValid = mChildren.end();
1030 
1031  for (const auto& rpChild : mChildren)
1032  rpChild->InvalidateTree();
1033 }
1034 
1036 {
1037  if (pChild->IsValid())
1038  {
1039  tSwNumberTreeChildren::const_iterator aIt = GetIterator(pChild);
1040 
1041  if (aIt != mChildren.begin())
1042  --aIt;
1043  else
1044  aIt = mChildren.end();
1045 
1046  SetLastValid(aIt);
1047 
1048  }
1049 }
1050 
1052 {
1053  if (mpParent)
1054  mpParent->Invalidate(this);
1055 }
1056 
1058 {
1059  if (mpParent)
1060  mpParent->Validate(this);
1061 }
1062 
1064 {
1065  if (IsNotifiable())
1066  {
1067  if (! IsPhantom())
1068  NotifyNode();
1069 
1070  for (auto& rpChild : mChildren)
1071  rpChild->Notify();
1072  }
1073 }
1074 
1076 {
1077  if (IsNotifiable())
1078  {
1079  tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1080 
1081  if (aIt == mChildren.end())
1082  aIt = mChildren.begin();
1083  else
1084  ++aIt;
1085 
1086  while (aIt != mChildren.end())
1087  {
1088  (*aIt)->Notify();
1089 
1090  ++aIt;
1091  }
1092  // notification of next not counted node is also needed.
1093  if ( GetParent() )
1094  {
1095  tSwNumberTreeChildren::const_iterator aParentChildIt =
1096  GetParent()->GetIterator( this );
1097  ++aParentChildIt;
1098  if ( aParentChildIt != GetParent()->mChildren.end() )
1099  {
1100  SwNumberTreeNode* pNextNode( *aParentChildIt );
1101  if ( !pNextNode->IsCounted() )
1102  {
1103  pNextNode->NotifyInvalidChildren();
1104  }
1105  }
1106  }
1107 
1108  }
1109 
1110  if (IsContinuous() && mpParent)
1112 }
1113 
1115 {
1116  if (mpParent != nullptr)
1118 }
1119 
1120 // #i81002#
1122  const SwNumberTreeNode& rNode ) const
1123 {
1124  const SwNumberTreeNode* pPrecedingNode( nullptr );
1125 
1126  if ( GetChildCount() > 0 )
1127  {
1128  tSwNumberTreeChildren::const_iterator aUpperBoundIt =
1129  mChildren.upper_bound( const_cast<SwNumberTreeNode*>(&rNode) );
1130  if ( aUpperBoundIt != mChildren.begin() )
1131  {
1132  --aUpperBoundIt;
1133  pPrecedingNode = (*aUpperBoundIt)->GetPrecedingNodeOf( rNode );
1134  }
1135  }
1136 
1137  if ( pPrecedingNode == nullptr && GetRoot() )
1138  {
1139  // <this> node has no children or the given node precedes all its children
1140  // and the <this> node isn't the root node.
1141  // Thus, compare the given node with the <this> node in order to check,
1142  // if the <this> node precedes the given node.
1143  if ( !(rNode.LessThan( *this )) )
1144  {
1145  pPrecedingNode = this;
1146  }
1147  }
1148 
1149  return pPrecedingNode;
1150 }
1151 
1152 void SwNumberTreeNode::NotifyNodesOnListLevel( const int nListLevel )
1153 {
1154  if ( nListLevel < 0 )
1155  {
1156  OSL_FAIL( "<SwNumberTreeNode::NotifyNodesOnListLevel(..)> - invalid list level provided" );
1157  return;
1158  }
1159 
1160  SwNumberTreeNode* pRootNode = GetParent() ? GetRoot() : this;
1161 
1162  pRootNode->NotifyChildrenOnDepth( nListLevel );
1163 }
1164 
1166 {
1167  OSL_ENSURE( nDepth >= 0,
1168  "<SwNumberTreeNode::NotifyChildrenOnDepth(..)> - misusage" );
1169 
1170  for ( const auto& rpChild : mChildren )
1171  {
1172  if ( nDepth == 0 )
1173  {
1174  rpChild->NotifyNode();
1175  }
1176  else
1177  {
1178  rpChild->NotifyChildrenOnDepth( nDepth - 1 );
1179  }
1180  }
1181 }
1182 
1183 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
bool HasPhantomCountedParent() const
virtual void NotifyNode()=0
Notifies the node.
void AddChild(SwNumberTreeNode *pChild, const int nDepth)
Add a child.
bool IsValid() const
Returns if this node is valid.
SwNumberTreeNode * GetLastDescendant() const
Returns the last descendant of a node, if it has children.
bool IsFirst() const
Return if this node if the first non-phantom node in the tree.
virtual bool LessThan(const SwNumberTreeNode &rTreeNode) const
Returns if this node is less than another node.
A tree of numbered nodes.
const SwNumberTreeNode * GetPrecedingNodeOf(const SwNumberTreeNode &rNode) const
determines the node, which is preceding the node
virtual SwNumberTree::tSwNumTreeNumber GetStartValue() const =0
Return start value.
void SetLevelInListTree(const int nLevel)
set level of this node
SwNumberTreeNode * GetPred(bool bSibling=false) const
Returns the greatest descendant of the root that is smaller than this node, aka the predecessor of th...
SwNumberTreeNode * GetParent() const
Returns the parent of this node.
void RemoveChild(SwNumberTreeNode *pChild)
Remove a child.
void ClearObsoletePhantoms()
Removes recursively phantoms that have no children.
virtual bool HasCountedChildren() const =0
bool SwNumberTreeNodeLessThan(const SwNumberTreeNode *pA, const SwNumberTreeNode *pB)
void Validate(const SwNumberTreeNode *pNode) const
Validates a child.
SwNumberTree::tNumberVector GetNumberVector() const
Returns level numbers of this node.
void GetNumberVector_(SwNumberTree::tNumberVector &rVector, bool bValidate=true) const
Calls GetNumberVector_ on parent and adds number of this node at the end.
int GetLevelInListTree() const
Return level of this node.
OSQLColumns::Vector::const_iterator find(const OSQLColumns::Vector::const_iterator &first, const OSQLColumns::Vector::const_iterator &last, const OUString &_rVal, const ::comphelper::UStringMixEqual &_rCase)
SwNumberTreeNode * GetRoot() const
Returns the root node of the tree this node is part of.
tSwNumberTreeChildren::const_iterator GetIterator(const SwNumberTreeNode *pChild) const
tSwNumberTreeChildren mChildren
the children
void InvalidateMe()
Notifies the node.
void NotifyInvalidChildren()
Notifies all invalid children of this node.
void MoveChildren(SwNumberTreeNode *pDest)
Moves all children to a given destination node.
bool mbPhantom
true this node is a phantom false this node is NOT a phantom
bool IsPhantom() const
Return if this node is a phantom.
void SetLastValid(const tSwNumberTreeChildren::const_iterator &aItLastValid, bool bValidating=false) const
Set the last valid child of this node.
void ValidateHierarchical(const SwNumberTreeNode *pNode) const
Validates a child using hierarchical numbering.
virtual void PreAdd()=0
void Invalidate(SwNumberTreeNode const *pChild)
Invalidates a child.
void RemoveMe()
Remove this child from the tree.
SwNumberTreeNode * CreatePhantom()
Creates a phantom.
virtual bool IsContinuous() const =0
Return if this node is counted continuous.
SwNumberTreeNode * mpParent
he parent node
bool IsValid(const SwNumberTreeNode *pChild) const
Returns if a child A this node is valid.
tSwNumberTreeChildren::const_iterator mItLastValid
Iterator to the last valid element.
SwNumberTree::tSwNumTreeNumber GetNumber(bool bValidate=true) const
Returns number of this node.
virtual ~SwNumberTreeNode()
void ValidateMe()
Validates this node.
SwNumberTreeNode * GetFirstNonPhantomChild()
HB, OD : return node, if it isn't a phantom, otherwise return first non-phantom descendant.
void IsSane(bool bRecursive) const
Sanity check.
std::vector< tSwNumTreeNumber > tNumberVector
virtual bool IsCountPhantoms() const =0
Return if phantoms are counted.
void ValidateContinuous(const SwNumberTreeNode *pNode) const
Validates a child using continuous numbering.
void InvalidateChildren()
Invalidation of all children.
void MoveGreaterChildren(SwNumberTreeNode &_rCompareNode, SwNumberTreeNode &_rDestNode)
Moves all children of this node that are greater than a given node to the destination node...
#define SAL_WARN_IF(condition, area, stream)
bool HasOnlyPhantoms() const
Return if all descendants of this node are phantoms.
tSwNumberTreeChildren::size_type GetChildCount() const
Returns how many children this node has got.
void Notify()
Notifies this node (NotifyNode) and all descendants.
virtual SwNumberTreeNode * Create() const =0
Creates a new node of the same class.
void NotifyChildrenOnDepth(const int nDepth)
notification of children nodes on certain depth
virtual void PostRemove()=0
void NotifyInvalidSiblings()
Notifies all invalid siblings of this node.
SwNumberTree::tSwNumTreeNumber mnNumber
the number of the node
void InvalidateTree() const
Invalidate this node and all its descendants.
virtual bool IsCounted() const
Return if this node is counted.
virtual bool IsNotificationEnabled() const =0
Return if the notification is not disabled on global conditions.
void NotifyNodesOnListLevel(const int nListLevel)
notification of all nodes in the list tree on certain list level
virtual bool IsNotifiable() const =0
Return if this node is notifiable.