BALL  1.4.1
composite.h
Go to the documentation of this file.
00001 // -*- Mode: C++; tab-width: 2; -*-
00002 // vi: set ts=2:
00003 //
00004 
00005 #ifndef BALL_CONCEPT_COMPOSITE_H
00006 #define BALL_CONCEPT_COMPOSITE_H
00007 
00008 #ifndef BALL_COMMON_H
00009 # include <BALL/common.h>
00010 #endif
00011 
00012 #ifndef BALL_CONCEPT_PERSISTENTOBJECT_H
00013 # include <BALL/CONCEPT/persistentObject.h>
00014 #endif
00015 
00016 #ifndef BALL_CONCEPT_COMPARATOR_H
00017 # include <BALL/CONCEPT/comparator.h>
00018 #endif
00019 
00020 #ifndef BALL_CONCEPT_BIDIRECTIONALITERATOR_H
00021 # include <BALL/CONCEPT/bidirectionalIterator.h>
00022 #endif
00023 
00024 #ifndef BALL_CONCEPT_OBJECT_H
00025 # include <BALL/CONCEPT/object.h>
00026 #endif
00027 
00028 #ifndef BALL_CONCEPT_SELECTABLE_H
00029 # include <BALL/CONCEPT/selectable.h>
00030 #endif
00031 
00032 #ifndef BALL_CONCEPT_VISITOR_H
00033 # include <BALL/CONCEPT/visitor.h>
00034 #endif
00035 
00036 #ifndef BALL_CONCEPT_PROCESSOR_H
00037 # include <BALL/CONCEPT/processor.h>
00038 #endif
00039 
00040 #ifndef BALL_CONCEPT_TIMESTAMP_H
00041 # include <BALL/CONCEPT/timeStamp.h>
00042 #endif
00043 
00045 namespace BALL 
00046 {
00069   class BALL_EXPORT Composite
00070     : public PersistentObject,
00071       public Selectable
00072   {
00073     public:
00074 
00078 
00079 #ifndef BALL_KERNEL_PREDICATE_TYPE
00080 #define BALL_KERNEL_PREDICATE_TYPE
00081 
00086     typedef UnaryPredicate<Composite> KernelPredicateType;
00087 #endif
00088 
00091     enum StampType
00092     {
00095       MODIFICATION = 1,
00098       SELECTION = 2,
00101       BOTH = 3
00102     };
00104         
00105     BALL_CREATE_DEEP(Composite)
00106 
00107     static UnaryProcessor<Composite> DEFAULT_PROCESSOR;
00108     static KernelPredicateType DEFAULT_UNARY_PREDICATE;
00109     
00113     
00117     Composite()
00118       ;
00119 
00128     Composite(const Composite& composite, bool deep = true)
00129       ;
00130 
00136     virtual ~Composite() 
00137       ;
00138 
00150     virtual void clear()
00151       ;
00152   
00162     virtual void destroy()
00163       ;
00164 
00177     void destroy(bool virtual_destroy)
00178       ;
00179 
00187     void* clone(Composite& root) const
00188       ;
00189 
00191 
00195     
00201     virtual void persistentWrite(PersistenceManager& pm, const char* name = 0) const;
00202 
00207     virtual void persistentRead(PersistenceManager& pm);
00208 
00210 
00214 
00220     void set(const Composite& composite, bool deep = true) ;
00221 
00226     Composite& operator = (const Composite& composite) ;
00227 
00234     void get(Composite& composite, bool deep = true) const ;
00235 
00240     Size getDegree() const ;
00241 
00246     Size count(const KernelPredicateType& predicate) const ;
00247 
00251     Size countDescendants() const ;
00252 
00258     Size getPathLength(const Composite& composite) const ;
00259 
00264     Size getDepth() const ;
00265 
00270     Size getHeight() const
00271       ;
00272 
00276     Composite& getRoot() ;
00277 
00281     const Composite& getRoot() const ;
00282 
00287     Composite* getLowestCommonAncestor(const Composite& composite)
00288       ;
00289 
00294     const Composite* getLowestCommonAncestor(const Composite& composite) const
00295       ;
00296 
00305     template <typename T>
00306     T* getAncestor(const T& /* dummy */)
00307       ;
00308 
00315     template <typename T>
00316     const T* getAncestor(const T& /* dummy */) const ;
00317 
00325     template <typename T>
00326     T* getPrevious(const T& /* dummy */) ;
00327 
00335     template <typename T>
00336     const T* getPrevious(const T& dummy) const ;
00337 
00345     template <typename T>
00346     T* getNext(const T& /* dummy */) ;
00347 
00355     template <typename T>
00356     const T* getNext(const T& dummy) const ;
00357 
00361     Composite* getParent() ;
00362 
00366     const Composite* getParent() const ;
00367 
00374     Composite* getChild(Index index) ;
00375   
00382     const Composite* getChild(Index index) const ;
00383   
00392     Composite* getSibling(Index index) ;
00393 
00402     const Composite* getSibling(Index index) const ;
00403 
00407     Composite* getFirstChild() ;
00408 
00412     const Composite* getFirstChild() const ;
00413 
00417     Composite* getLastChild() ;
00418 
00422     const Composite* getLastChild() const ;
00423       
00427     const PreciseTime& getModificationTime() const ;
00428 
00432     const PreciseTime& getSelectionTime() const ;
00433 
00443     void stamp(StampType stamp = BOTH) ;
00444       
00450     void prependChild(Composite& composite) ;
00451 
00459     void appendChild(Composite& composite) ;
00460 
00480     static bool insertParent(Composite& parent, Composite& first,  
00481                              Composite& last, bool destroy_parent = true)
00482       ;
00483 
00493     void insertBefore(Composite& composite) ;
00494 
00504     void insertAfter(Composite& composite) ;
00505 
00514     void spliceBefore(Composite& composite) ;
00515 
00524     void spliceAfter(Composite& composite) ;
00525 
00535     void splice(Composite& composite) ;
00536 
00545     bool removeChild(Composite& child) ;
00546 
00547 
00560     Size removeSelected() ;
00561 
00574     Size removeUnselected();
00575 
00584     void replace(Composite& composite) ;
00585 
00594     void swap(Composite& composite) ;
00595 
00604     virtual void select() ;
00605 
00614     virtual void deselect() ;
00616 
00619 
00626     bool operator == (const Composite& composite) const ;
00627 
00631     bool operator != (const Composite& composite) const
00632       ;
00633 
00637     bool isEmpty() const ;
00638 
00642     bool isRoot() const ;
00643   
00646     bool isRootOf(const Composite& composite) const ;
00647   
00650     bool isInterior() const ;
00651   
00654     bool hasChild() const ;
00655   
00658     bool isChildOf(const Composite& composite) const ;
00659   
00662     bool isFirstChild() const ;
00663   
00666     bool isFirstChildOf(const Composite& composite) const ;
00667   
00670     bool isLastChild() const ;
00671   
00674     bool isLastChildOf(const Composite& composite) const ;
00675   
00678     bool hasParent() const ;
00679 
00682     bool isParentOf(const Composite& composite) const ;
00683 
00687     bool hasSibling() const ;
00688       
00691     bool isSiblingOf(const Composite& composite) const ;
00692       
00696     bool hasPreviousSibling() const ;
00697   
00700     bool isPreviousSiblingOf(const Composite& composite) const ;
00701   
00705     bool hasNextSibling() const ;
00706 
00709     bool isNextSiblingOf(const Composite& composite) const ;
00710     
00713     bool isDescendantOf(const Composite& composite) const ;
00714 
00717     template <typename T>
00718     bool hasAncestor(const T& dummy) const  ;
00719 
00722     bool isAncestorOf(const Composite& composite) const ;
00723 
00727     bool isRelatedWith(const Composite& composite) const ;
00728   
00732     bool isHomomorph(const Composite& composite) const ;
00733 
00743     bool containsSelection() const ;
00745 
00751     virtual bool isValid() const ;
00752 
00757     virtual void dump(std::ostream& s = std::cout, Size depth = 0) const
00758       ;
00759 
00761 
00763 
00770     void host(Visitor<Composite>& visitor);
00771 
00776     template <typename T>
00777     bool applyAncestor(UnaryProcessor<T>& processor);
00778 
00783     template <typename T>
00784     bool applyChild(UnaryProcessor<T>& processor);
00785     
00793     template <typename T>
00794     bool applyDescendantPreorder(UnaryProcessor<T>& processor);
00795 
00803     template <typename T>
00804     bool applyDescendantPostorder(UnaryProcessor<T>& processor);
00805   
00813     template <typename T>
00814     bool applyDescendant(UnaryProcessor<T>& processor);
00815     
00822     template <typename T>
00823     bool applyPreorder(UnaryProcessor<T>& processor);
00824     
00831     template <typename T>
00832     bool applyPostorder(UnaryProcessor<T>& processor);
00833 
00840     template <typename T>
00841     bool apply(UnaryProcessor<T>& processor);
00842     
00847     template <typename T>
00848     bool applyLevel(UnaryProcessor<T>& processor, long level);
00850 
00851 
00852   
00853     class BALL_EXPORT AncestorIteratorTraits
00854     {
00855       public:
00856 
00857       BALL_INLINE
00858       AncestorIteratorTraits()
00859         
00860         : bound_(0),
00861           ancestor_(0)
00862       {
00863       }
00864     
00865       BALL_INLINE
00866       AncestorIteratorTraits(const Composite& composite)
00867         
00868         : bound_(const_cast<Composite*>(&composite)),
00869           ancestor_(0)
00870       {
00871       }
00872     
00873       BALL_INLINE
00874       AncestorIteratorTraits(const AncestorIteratorTraits& traits)
00875         
00876         : bound_(traits.bound_),
00877           ancestor_(traits.ancestor_)
00878       {
00879       }
00880     
00881       BALL_INLINE
00882       const AncestorIteratorTraits& operator = (const AncestorIteratorTraits& traits)
00883         
00884       {
00885         bound_ = traits.bound_;
00886         ancestor_ = traits.ancestor_;
00887         return *this;
00888       }
00889 
00890       BALL_INLINE Composite* getContainer()  { return bound_; }
00891 
00892       BALL_INLINE const Composite* getContainer() const  { return bound_; }
00893 
00894       BALL_INLINE bool isSingular() const   { return (bound_ == 0); }
00895 
00896       BALL_INLINE Composite* getPosition()    { return ancestor_; }
00897 
00898       BALL_INLINE Composite* const& getPosition() const  {  return ancestor_; }
00899 
00900       BALL_INLINE bool operator == (const AncestorIteratorTraits& traits) const   { return (ancestor_ == traits.ancestor_); }
00901     
00902       BALL_INLINE bool operator != (const AncestorIteratorTraits& traits) const   { return !(ancestor_ == traits.ancestor_); }
00903 
00904       BALL_INLINE bool isValid() const    { return (bound_ != 0 && ancestor_ != 0); }
00905 
00906       BALL_INLINE void invalidate()   { bound_  = ancestor_ = 0; }
00907       
00908       BALL_INLINE void toBegin()    { ancestor_ = bound_->parent_; }
00909 
00910       BALL_INLINE bool isBegin() const  { return (ancestor_ == bound_->parent_); }
00911 
00912       BALL_INLINE void toEnd()  { ancestor_ = 0;  }
00913 
00914       BALL_INLINE bool isEnd() const  { return (ancestor_ == 0); }
00915 
00916       BALL_INLINE Composite& getData()  { return *ancestor_;  }
00917 
00918       BALL_INLINE const Composite& getData() const  { return *ancestor_; }
00919 
00920       BALL_INLINE void forward()  { ancestor_ = ancestor_->parent_; }
00921 
00922       private:
00923 
00924       Composite* bound_;
00925       Composite* ancestor_;
00926     };
00927 
00928     friend class AncestorIteratorTraits;
00929 
00930     typedef ForwardIterator <Composite, Composite, Composite*, AncestorIteratorTraits>
00931       AncestorIterator;
00932 
00933     AncestorIterator beginAncestor() 
00934     {
00935       return AncestorIterator::begin(*this);
00936     }
00937 
00938     AncestorIterator endAncestor() 
00939     {
00940       return AncestorIterator::end(*this);
00941     }
00942 
00943     typedef ConstForwardIterator<Composite, Composite, Composite*, AncestorIteratorTraits>
00944       AncestorConstIterator;
00945 
00946     AncestorConstIterator beginAncestor() const 
00947     {
00948       return AncestorConstIterator::begin(*this);
00949     }
00950 
00951     AncestorConstIterator endAncestor() const 
00952     {
00953       return AncestorConstIterator::end(*this);
00954     }
00955 
00956     class BALL_EXPORT ChildCompositeIteratorTraits
00957     {
00958       public:
00959 
00960       ChildCompositeIteratorTraits()
00961         
00962         : bound_(0),
00963           child_(0)
00964       {
00965       }
00966       
00967       ChildCompositeIteratorTraits(const Composite& composite)
00968         
00969         : bound_((Composite *)&composite),
00970           child_(0)
00971       {
00972       }
00973     
00974       ChildCompositeIteratorTraits(const ChildCompositeIteratorTraits& traits)
00975         
00976         : bound_(traits.bound_),
00977           child_(traits.child_)
00978       {
00979       }
00980     
00981       const ChildCompositeIteratorTraits& operator = (const ChildCompositeIteratorTraits& traits)
00982         
00983       {
00984         bound_ = traits.bound_;
00985         child_ = traits.child_;
00986         return *this;
00987       }
00988 
00989       BALL_INLINE Composite* getContainer()  {  return bound_; }
00990 
00991       BALL_INLINE const Composite* getContainer() const   { return bound_; }
00992 
00993       BALL_INLINE bool isSingular() const   { return (bound_ == 0); }
00994 
00995       BALL_INLINE Composite* getPosition()  { return child_; }
00996 
00997       BALL_INLINE Composite* const& getPosition() const   { return child_; }
00998 
00999       BALL_INLINE bool operator == (const ChildCompositeIteratorTraits& traits) const  { return (child_ == traits.child_); }
01000     
01001       BALL_INLINE bool operator != (const ChildCompositeIteratorTraits& traits) const  { return !(child_ == traits.child_); }
01002     
01003       BALL_INLINE bool isValid() const  { return (bound_ != 0 && child_ != 0); }
01004 
01005       BALL_INLINE void invalidate()  { bound_ = child_ = 0; }
01006 
01007       BALL_INLINE void toBegin()  { child_ = bound_->first_child_; }
01008 
01009       BALL_INLINE bool isBegin() const  { return (child_ == bound_->first_child_); }
01010 
01011       BALL_INLINE void toEnd()  { child_ = 0; }
01012 
01013       BALL_INLINE bool isEnd() const  { return (child_ == 0); }
01014 
01015       BALL_INLINE void toRBegin()  { child_ = bound_->last_child_; }
01016 
01017       BALL_INLINE bool isRBegin() const  { return (child_ == bound_->last_child_); }
01018 
01019       BALL_INLINE void toREnd()  { child_ = 0; }
01020 
01021       BALL_INLINE bool isREnd() const  { return (child_ == 0); }
01022 
01023       BALL_INLINE Composite& getData()  { return *child_; }
01024 
01025       BALL_INLINE const Composite& getData() const  { return *child_; }
01026 
01027       BALL_INLINE void forward()  { child_ = child_->next_; }
01028 
01029       BALL_INLINE void backward()   
01030       {   
01031         if (child_ == 0) 
01032         { 
01033           // Allow decrementation for past-the-end iterators
01034           child_ = bound_->last_child_; 
01035         }
01036         else  
01037         { 
01038           child_ = child_->previous_; 
01039         } 
01040       }
01041 
01042       private:
01043 
01044       Composite* bound_;
01045       Composite* child_;
01046     };
01047 
01048     friend class ChildCompositeIteratorTraits;
01049 
01050     typedef BidirectionalIterator<Composite, Composite, Composite *, ChildCompositeIteratorTraits>
01051       ChildCompositeIterator;
01052 
01053     ChildCompositeIterator beginChildComposite()
01054       
01055     {
01056       return ChildCompositeIterator::begin(*this);
01057     }
01058 
01059     ChildCompositeIterator endChildComposite()
01060       
01061     {
01062       return ChildCompositeIterator::end(*this);
01063     }
01064 
01065 
01066 
01067     typedef ConstBidirectionalIterator<Composite, Composite, Composite *, ChildCompositeIteratorTraits>
01068       ChildCompositeConstIterator;
01069 
01070     ChildCompositeConstIterator beginChildComposite() const
01071       
01072     {
01073       return ChildCompositeConstIterator::begin(*this);
01074     }
01075 
01076     ChildCompositeConstIterator endChildComposite() const
01077       
01078     {
01079       return ChildCompositeConstIterator::end(*this);
01080     }
01081 
01082 
01083 
01084     typedef std::reverse_iterator<ChildCompositeIterator> ChildCompositeReverseIterator;
01085 
01086     ChildCompositeReverseIterator rbeginChildComposite() 
01087     {
01088       return ChildCompositeReverseIterator(endChildComposite());
01089     }
01090 
01091     ChildCompositeReverseIterator rendChildComposite() 
01092     {
01093       return ChildCompositeReverseIterator(beginChildComposite());
01094     }
01095 
01096 
01097 
01098     typedef std::reverse_iterator<ChildCompositeConstIterator> ChildCompositeConstReverseIterator;
01099 
01100     ChildCompositeConstReverseIterator rbeginChildComposite() const 
01101     {
01102       return ChildCompositeConstReverseIterator(endChildComposite());
01103     }
01104 
01105     ChildCompositeConstReverseIterator rendChildComposite() const 
01106     {
01107       return ChildCompositeConstReverseIterator(beginChildComposite());
01108     }
01109 
01110     class BALL_EXPORT CompositeIteratorTraits
01111     {
01112       public:
01113 
01114       BALL_INLINE CompositeIteratorTraits()
01115         
01116         : bound_(0),
01117           position_(0)
01118       {
01119       }
01120     
01121       CompositeIteratorTraits(const Composite& composite)
01122         
01123         : bound_(const_cast<Composite*>(&composite)),
01124           position_(0)
01125       {
01126       }
01127     
01128       CompositeIteratorTraits(const CompositeIteratorTraits& traits)
01129         
01130         : bound_(traits.bound_),
01131           position_(traits.position_)
01132       {
01133       }
01134 
01135       BALL_INLINE ~CompositeIteratorTraits()  {}
01136     
01137       BALL_INLINE bool isValid() const  
01138       { 
01139         return ((bound_ != 0) && (position_ != 0)); 
01140       }
01141 
01142       BALL_INLINE CompositeIteratorTraits& operator = (const CompositeIteratorTraits& traits) 
01143       {
01144         bound_ = traits.bound_;
01145         position_ = traits.position_;
01146         return *this;
01147       }
01148 
01149       BALL_INLINE Composite* getContainer()   { return bound_; }
01150 
01151       BALL_INLINE const Composite* getContainer() const  { return bound_; }
01152     
01153       BALL_INLINE bool isSingular() const   { return (bound_ == 0); }
01154     
01155       BALL_INLINE Composite* getPosition()  { return position_; }
01156       
01157       BALL_INLINE const Composite* getPosition() const  { return position_; }
01158       BALL_INLINE void setPosition(Composite* position)  { position_ = position; }
01159 
01160 
01161       BALL_INLINE Composite& getData()  { return *position_; }
01162 
01163       BALL_INLINE const Composite& getData() const  { return *position_; }
01164 
01165       BALL_INLINE bool operator == (const CompositeIteratorTraits& traits) const  
01166       { 
01167         return (position_ == traits.position_); 
01168       }
01169     
01170       BALL_INLINE bool operator != (const CompositeIteratorTraits& traits) const  
01171       { 
01172         return !(position_ == traits.position_); 
01173       }
01174     
01175       BALL_INLINE void invalidate()   
01176       { 
01177         bound_ = 0; 
01178         position_ = 0;
01179       }
01180 
01181       BALL_INLINE void toBegin() 
01182       {
01183         position_ = bound_;
01184       }
01185 
01186       BALL_INLINE bool isBegin() const 
01187       {
01188         return (position_ == bound_);
01189       }
01190 
01191       BALL_INLINE void toEnd()  
01192       {
01193         position_ = 0;
01194       }
01195 
01196       BALL_INLINE bool isEnd() const 
01197       {
01198         return (position_ == 0);
01199       }
01200 
01201       BALL_INLINE void toRBegin() 
01202       {
01203         if (bound_ != 0)
01204         {
01205           position_ = findPreviousPosition(0);
01206         }
01207       }
01208 
01209       BALL_INLINE bool isRBegin() const 
01210       {
01211         return (position_ == findPreviousPosition(0));
01212       }
01213     
01214       BALL_INLINE void toREnd() 
01215       { 
01216         position_ = bound_;
01217       }
01218 
01219       BALL_INLINE bool isREnd() const 
01220       {
01221         return (position_ == bound_);
01222       }
01223     
01224       BALL_INLINE void forward() 
01225       {
01226         position_ = findNextPosition(position_);
01227       }
01228 
01229       BALL_INLINE void backward() 
01230       {
01231         position_ = findPreviousPosition(position_);
01232       }
01233 
01234       protected:
01235 
01237       Composite* bound_;
01238 
01240       Composite* position_;
01241 
01242       Composite* findPreviousPosition(Composite* p) const
01243       {
01244         // If we are at the root of the iterator, the 
01245         // decrementing it results in an invalid iterator
01246         // (past-the-end).
01247         if (p == bound_)
01248         {
01249           return 0;
01250         }
01251         // If we decrement a past-the-end-iterator, we
01252         // start at the root and "fall down" on the right
01253         // hand side following the last_child_ pointers
01254         // until we hit bottom.
01255         else if (p == 0)
01256         {
01257           if (bound_->last_child_ == 0)
01258           {
01259             return bound_;
01260           }
01261           else
01262           {
01263             p = bound_->last_child_;
01264           }
01265           while (p->last_child_ != 0)
01266           {
01267             p = p->last_child_;
01268           }
01269         }
01270         // Normally, we just grab the guy to the
01271         // left in the doubly-linked child list.
01272         else if (p->previous_ != 0)
01273         {
01274           p = p->previous_;
01275 
01276           // If the guy to the left hast children,
01277           // we do the drop on the rigth again.
01278           while (p->last_child_ != 0)
01279           {
01280             p = p->last_child_;
01281           }
01282         }
01283         // Finally, if we can't go down and we can't go 
01284         // left, we have to go upwards.
01285         else if (p != bound_)
01286         {
01287           p = p->parent_;
01288         }
01289 
01290         return p;
01291       }
01292 
01293       Composite* findNextPosition(Composite* p) const
01294       {
01295         // If we are in a past-the-end position, we stay put.
01296         if (p == 0)
01297         {
01298           return 0;
01299         }
01300         // Otherwise, we try the first child. If there's one,
01301         // that's our next position.
01302         else 
01303         {
01304           if (p->first_child_ != 0)
01305           {
01306             p = p->first_child_;
01307           }
01308           else 
01309           {
01310             // If we are already in the root node, we are done.
01311             if (p == bound_)
01312             {
01313               return 0;
01314             }
01315             // Otherwise, we try to walk to the right at the current level.
01316             if (p->next_ != 0)
01317             {
01318               p = p->next_;
01319             }
01320             // If that doesn't work out, we'll have to climb up again.
01321             // Now, we either revisit a node we have already been to, or we
01322             // are trying to climb up *beyond* our iteration root (bound_).
01323             // In the latter case, we return a past-the-end-iterator (0).
01324             else
01325             {
01326               // If we could not walk left or right and we are at the root
01327               // again, then we are done with the iteration (this is the
01328               // case if bound_ is a leaf node).
01329               while (p->next_ == 0)
01330               {
01331                 p = p->parent_;
01332                 if ((p == bound_) || (p == 0))
01333                 {
01334                   return 0;
01335                 }
01336               }
01337               p = p->next_;
01338             }
01339           }
01340         }
01341         return p;
01342       }
01343     };
01344 
01345     friend class CompositeIteratorTraits;
01346 
01347     typedef BidirectionalIterator<Composite, Composite, Composite*, CompositeIteratorTraits>
01348       CompositeIterator;
01349 
01350     CompositeIterator beginComposite()  { return CompositeIterator::begin(*this); }
01351 
01352     CompositeIterator endComposite()  { return CompositeIterator::end(*this); }
01353 
01354     typedef ConstBidirectionalIterator<Composite, Composite, Composite*, CompositeIteratorTraits>
01355       CompositeConstIterator;
01356 
01357     CompositeConstIterator beginComposite() const  
01358     { 
01359       return CompositeConstIterator::begin(*this);
01360     }
01361 
01362     CompositeConstIterator endComposite() const 
01363     {
01364       return CompositeConstIterator::end(*this);
01365     }
01366 
01367 
01368     typedef std::reverse_iterator<CompositeIterator> CompositeReverseIterator;
01369 
01370     CompositeReverseIterator rbeginComposite() 
01371     {
01372       return CompositeReverseIterator(endComposite());
01373     }
01374 
01375     CompositeReverseIterator rendComposite() 
01376     {
01377       return CompositeReverseIterator(beginComposite());
01378     }
01379 
01380 
01381     typedef std::reverse_iterator<CompositeConstIterator> CompositeConstReverseIterator;
01382 
01383     CompositeConstReverseIterator rbeginComposite() const 
01384     {
01385       return CompositeConstReverseIterator(endComposite());
01386     }
01387 
01388     CompositeConstReverseIterator rendComposite() const 
01389     {
01390       return CompositeConstReverseIterator(beginComposite());
01391     }
01392 
01393     /*
01394      * This function removes and deletes all composites that are
01395      * supplied in the list of children.
01396      */
01397     void deleteChildrenList_(std::list<Composite*>& composites);
01398 
01399     private:
01400     
01402     Size getHeight_(Size size, Size& max_height) const ;
01403   
01405     Size countDescendants_() const ;
01406 
01408     void clone_(Composite& parent, Composite& stack) const ;
01409 
01410     // \throws Exception::GeneralException
01411     template <typename T>
01412     bool applyLevelNostart_(UnaryProcessor<T>& processor, long level);
01413 
01414     // \throws Exception::GeneralException
01415     template <typename T>
01416     bool applyChildNostart_(UnaryProcessor<T>& processor);
01417 
01418     // \throws Exception::GeneralException
01419     template <typename T>
01420     bool applyPreorderNostart_(UnaryProcessor<T>& processor);
01421 
01422     // \throws Exception::GeneralException
01423     template <typename T>
01424     bool applyDescendantPreorderNostart_(UnaryProcessor<T>& processor);
01425 
01426     // \throws Exception::GeneralException
01427     template <typename T>
01428     bool applyDescendantPostorderNostart_(UnaryProcessor<T>& processor);
01429 
01430 
01431     void updateSelection_();
01432     void determineSelection_();
01433     void select_(bool update_parent = true);
01434     void deselect_(bool update_parent = true);
01435 
01436     // private attributes
01437     
01438     Size            number_of_children_;
01439     Composite*      parent_;
01440     Composite*      previous_;
01441     Composite*      next_;
01442     Composite*      first_child_;
01443     Composite*      last_child_;
01444     unsigned char   properties_;
01445     bool            contains_selection_;
01446     Size            number_of_selected_children_;
01447     Size            number_of_children_containing_selection_;
01448     TimeStamp       selection_stamp_;
01449     TimeStamp       modification_stamp_;
01450   };
01451 
01452   template <typename T>
01453   bool Composite::applyAncestor(UnaryProcessor<T>& processor)
01454   {
01455     if (processor.start() == false)
01456     {
01457       return false;
01458     }
01459 
01460     Processor::Result result;
01461 
01462     for (Composite* composite = parent_; composite != 0; composite = composite->parent_)
01463     {
01464       T* t_ptr;
01465       if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
01466       { 
01467         result = processor(*t_ptr);
01468         if (result <= Processor::BREAK)
01469         {
01470           return (result == Processor::BREAK);
01471         }
01472       }
01473     }
01474 
01475     return processor.finish();
01476   }
01477   
01478   template <typename T>
01479   bool Composite::applyChild(UnaryProcessor<T>& processor)
01480   {
01481     return processor.start() && applyChildNostart_(processor) && processor.finish();
01482   }
01483 
01484   template <typename T>
01485   bool Composite::applyChildNostart_(UnaryProcessor<T>& processor)
01486   {
01487     Processor::Result result = Processor::CONTINUE;
01488 
01489     for (Composite* composite = first_child_;
01490          composite != 0; composite = composite->next_)
01491     {
01492       T* t_ptr;
01493       if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
01494       {
01495         result = processor(*t_ptr);
01496         if (result <= Processor::BREAK)
01497         {
01498           break;
01499         }
01500       }
01501     }
01502 
01503     return (result >= Processor::BREAK);
01504   }
01505  
01506   template <typename T>
01507   bool Composite::applyDescendantPreorder(UnaryProcessor<T>& processor)
01508   {
01509     return processor.start() && applyDescendantPreorderNostart_(processor) && processor.finish();
01510   }
01511 
01512   template <typename T>
01513   bool Composite::applyDescendantPreorderNostart_(UnaryProcessor<T>& processor)
01514   {
01515     Processor::Result result;
01516 
01517     for (Composite* composite = first_child_;
01518          composite != 0; composite = composite->next_)
01519     {
01520       T* t_ptr;
01521       if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
01522       { 
01523         result = processor(*t_ptr);
01524 
01525         if (result <= Processor::BREAK)
01526         {
01527           return (result == Processor::BREAK);
01528         }
01529       }
01530 
01531       if (composite->first_child_ != 0  && composite->applyDescendantPreorderNostart_(processor) == false)
01532       {
01533         return false;
01534       }
01535     }
01536 
01537     return true;
01538   }
01539 
01540   template <typename T>
01541   bool Composite::applyDescendantPostorder(UnaryProcessor<T>& processor)
01542   {
01543     return processor.start() && applyDescendantPostorderNostart_(processor) && processor.finish();
01544   }
01545 
01546   template <typename T>
01547   bool Composite::applyDescendantPostorderNostart_(UnaryProcessor<T>& processor)
01548   {
01549     Processor::Result result;
01550 
01551     for (Composite* composite = first_child_;
01552          composite != 0; composite = composite->next_)
01553     {
01554       if (composite->first_child_ != 0 && 
01555           composite->applyDescendantPostorderNostart_(processor) == false)
01556       {
01557         return false;
01558       }
01559 
01560       T* t_ptr = dynamic_cast<T*>(composite);
01561       if (t_ptr != 0)
01562       {
01563         result = processor(*t_ptr);
01564 
01565         if (result <= Processor::BREAK)
01566         {
01567           return (result == Processor::BREAK);
01568         }
01569       }
01570     }
01571 
01572     return true;
01573   }
01574 
01575   template <typename T>  
01576   bool Composite::applyPostorder(UnaryProcessor<T>& processor)
01577   { 
01578     if (!processor.start() || !applyDescendantPostorderNostart_(processor))
01579     {
01580       return false;
01581     }
01582 
01583     T* t_ptr = dynamic_cast<T*>(this);
01584 
01585     return (t_ptr != 0                            && 
01586             processor(*t_ptr) >= Processor::BREAK && 
01587             processor.finish()                      );
01588   }
01589 
01590   template <typename T>
01591   bool Composite::applyLevel(UnaryProcessor<T>& processor, long level)
01592   {
01593     return processor.start() && applyLevelNostart_(processor, level) && processor.finish();
01594   }
01595 
01596   template <typename T>
01597   bool Composite::applyLevelNostart_(UnaryProcessor<T>& processor, long level)
01598   {
01599     if (level == 0)
01600     {
01601       T* t_ptr = dynamic_cast<T*>(this);
01602       if (t_ptr != 0)
01603       {
01604        Processor::Result result = processor(*t_ptr);
01605 
01606         if (result <= Processor::BREAK)
01607         {
01608           return (result == Processor::BREAK);
01609         }
01610       }
01611     }
01612     else 
01613     {
01614       if (--level == 0)
01615       {
01616         return applyChildNostart_(processor);
01617       }
01618       else 
01619       {
01620         if (level > 0)
01621         {
01622           for (Composite* composite = first_child_;
01623                composite != 0; composite = composite->next_)
01624           {
01625             if (composite->first_child_ != 0 && composite->applyLevelNostart_(processor, level) == false)
01626             {
01627               return false;
01628             }
01629           }
01630         }
01631       }
01632     }
01633     return true;
01634   }
01635 
01636   template <typename T>
01637   bool Composite::applyPreorderNostart_(UnaryProcessor<T>& processor)
01638   {
01639     Processor::Result result;
01640     bool return_value;
01641     T* t_ptr = dynamic_cast<T*>(this);
01642     if (t_ptr != 0)
01643     {
01644       result = processor(*t_ptr);
01645   
01646       if (result <= Processor::BREAK)
01647       {
01648         return_value = (result == Processor::BREAK);
01649       } 
01650       else 
01651       {
01652         return_value =  applyDescendantPreorderNostart_(processor);
01653       }
01654     } 
01655     else 
01656     {
01657       return_value =  applyDescendantPreorderNostart_(processor);
01658     }
01659     
01660     return return_value;
01661   }
01662 
01663   template <typename T>
01664   bool Composite::applyDescendant(UnaryProcessor<T>& processor)
01665   {
01666     return applyDescendantPreorder(processor);
01667   }
01668 
01669   template <typename T>
01670   bool Composite::applyPreorder(UnaryProcessor<T>& processor)
01671   {
01672     return processor.start() && applyPreorderNostart_(processor) && processor.finish();
01673   }
01674 
01675   template <typename T>
01676   BALL_INLINE 
01677   bool Composite::apply(UnaryProcessor<T>& processor)
01678   {
01679     return applyPreorder(processor);
01680   }
01681 
01682   template <typename T>
01683   BALL_INLINE 
01684   T* Composite::getAncestor(const T& /* dummy */)
01685     
01686   {
01687     T* T_ptr = 0;
01688     
01689     for (Composite* composite_ptr = parent_;
01690          composite_ptr != 0; composite_ptr = composite_ptr->parent_)
01691     {
01692       T_ptr = dynamic_cast<T*>(composite_ptr);
01693       if (T_ptr != 0)
01694       {
01695         break;
01696       } 
01697     }
01698     
01699     return T_ptr;
01700   }
01701 
01702   template <typename T>
01703   BALL_INLINE 
01704   const T* Composite::getAncestor(const T& /* dummy */) const
01705     
01706   {
01707     T* t_ptr = 0;
01708     for (Composite* composite_ptr = parent_;
01709          composite_ptr != 0; composite_ptr = composite_ptr->parent_)
01710     {
01711       if ((t_ptr = dynamic_cast<T*>(composite_ptr)) != 0)
01712       {
01713         break;
01714       } 
01715     }
01716     
01717     return const_cast<const T*>(t_ptr);
01718   }
01719 
01720   template <typename T>
01721   BALL_INLINE 
01722   T* Composite::getPrevious(const T& /* dummy */)
01723     
01724   {
01725     // create an iterator bound to the root of the subtree
01726     CompositeIterator it(getRoot().endComposite());
01727 
01728     // set its position to the current composite
01729     it.getTraits().setPosition(this);
01730 
01731     // walk back until we find something  
01732     // or we cannot walk any further
01733     if (+it)
01734     {
01735       do 
01736       {
01737         --it;
01738       } 
01739       while (+it && !RTTI::isKindOf<T>(*it));
01740     }
01741 
01742     // return a NULL pointer if nothing was found
01743     Composite* ptr = 0;
01744     if (+it)
01745     {
01746       ptr = &*it;
01747     }
01748     
01749     return dynamic_cast<T*>(ptr);
01750   }
01751 
01752   template <typename T>
01753   BALL_INLINE 
01754   const T* Composite::getPrevious(const T& dummy) const
01755     
01756   {
01757     // cast away the constness of this and call the non-const method
01758     Composite* nonconst_this = const_cast<Composite*>(this);
01759 
01760     return const_cast<const T*>(nonconst_this->getPrevious(dummy));
01761   }
01762 
01763   template <typename T>
01764   BALL_INLINE 
01765   T* Composite::getNext(const T& /* dummy */)
01766     
01767   {
01768     // create an iterator bound to the root of the subtree
01769     CompositeIterator it(getRoot().beginComposite());
01770 
01771     // set its position to the current composite
01772     it.getTraits().setPosition(this);
01773 
01774     // walk forward until we find something 
01775     // or we cannot walk any further
01776     do 
01777     {
01778       it++;
01779     } 
01780     while (it.isValid() && !RTTI::isKindOf<T>(*it));
01781 
01782 
01783     // return a NULL pointer if nothing was found
01784     Composite* ptr = 0;
01785     if (+it)
01786     {
01787       ptr = &*it;
01788     }
01789     
01790     return dynamic_cast<T*>(ptr);
01791   }
01792 
01793   template <typename T>
01794   BALL_INLINE 
01795   const T* Composite::getNext(const T& dummy) const
01796     
01797   {
01798     // cast away the constness of this and call the non-const method
01799     Composite* nonconst_this = const_cast<Composite*>(this);
01800 
01801     return const_cast<const T*>(nonconst_this->getNext(dummy));
01802   }
01803 
01804   template <typename T>
01805   BALL_INLINE 
01806   bool Composite::hasAncestor(const T& dummy ) const 
01807     
01808   {
01809     return (getAncestor(dummy) != 0); 
01810   }
01811 
01812 # ifndef BALL_NO_INLINE_FUNCTIONS
01813 #   include <BALL/CONCEPT/composite.iC>
01814 # endif
01815 
01816 
01817 } // namespace BALL
01818 
01819 #endif // BALL_CONCEPT_COMPOSITE_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines