composite.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//
// $Id: composite.h,v 1.62.14.1 2007/03/25 21:23:37 oliver Exp $
//
// Author:
//   Nicolas Boghossian
//   Oliver Kohlbacher
//

#ifndef BALL_CONCEPT_COMPOSITE_H
#define BALL_CONCEPT_COMPOSITE_H

#ifndef BALL_COMMON_H
# include <BALL/common.h>
#endif

#ifndef BALL_CONCEPT_PERSISTENTOBJECT_H
# include <BALL/CONCEPT/persistentObject.h>
#endif

#ifndef BALL_CONCEPT_COMPARATOR_H
# include <BALL/CONCEPT/comparator.h>
#endif

#ifndef BALL_CONCEPT_BIDIRECTIONALITERATOR_H
# include <BALL/CONCEPT/bidirectionalIterator.h>
#endif

#ifndef BALL_CONCEPT_OBJECT_H
# include <BALL/CONCEPT/object.h>
#endif

#ifndef BALL_CONCEPT_SELECTABLE_H
# include <BALL/CONCEPT/selectable.h>
#endif

#ifndef BALL_CONCEPT_VISITOR_H
# include <BALL/CONCEPT/visitor.h>
#endif

#ifndef BALL_CONCEPT_PROCESSOR_H
# include <BALL/CONCEPT/processor.h>
#endif

#ifndef BALL_CONCEPT_TIMESTAMP_H
# include <BALL/CONCEPT/timeStamp.h>
#endif

namespace BALL 
{
  class BALL_EXPORT Composite
    : public PersistentObject,
      public Selectable
  {
    public:


#ifndef BALL_KERNEL_PREDICATE_TYPE
#define BALL_KERNEL_PREDICATE_TYPE

    typedef UnaryPredicate<Composite> KernelPredicateType;
#endif

    enum StampType
    {
      MODIFICATION = 1,
      SELECTION = 2,
      BOTH = 3
    };
        
    BALL_CREATE_DEEP(Composite)

    static UnaryProcessor<Composite> DEFAULT_PROCESSOR;
    static KernelPredicateType DEFAULT_UNARY_PREDICATE;
    
    
    Composite()
      ;

    Composite(const Composite& composite, bool deep = true)
      ;

    virtual ~Composite() 
      ;

    virtual void clear()
      ;
  
    virtual void destroy()
      ;

    void destroy(bool virtual_destroy)
      ;

    void* clone(Composite& root) const
      ;


    
    virtual void persistentWrite(PersistenceManager& pm,
        const char* name = 0) const
      throw(Exception::GeneralException);

    virtual void persistentRead(PersistenceManager& pm)
      throw(Exception::GeneralException);



    void set(const Composite& composite, bool deep = true) ;

    Composite& operator = (const Composite& composite) ;

    void get(Composite& composite, bool deep = true) const ;

    Size getDegree() const ;

    Size count(const KernelPredicateType& predicate) const ;

    Size countDescendants() const ;

    Size getPathLength(const Composite& composite) const ;

    Size getDepth() const ;

    Size getHeight() const
      ;

    Composite& getRoot() ;

    const Composite& getRoot() const ;

    Composite* getLowestCommonAncestor(const Composite& composite)
      ;

    const Composite* getLowestCommonAncestor(const Composite& composite) const
      ;

    template <typename T>
    T* getAncestor(const T& /* dummy */)
      ;

    template <typename T>
    const T* getAncestor(const T& /* dummy */) const ;

    template <typename T>
    T* getPrevious(const T& /* dummy */) ;

    template <typename T>
    const T* getPrevious(const T& dummy) const ;

    template <typename T>
    T* getNext(const T& /* dummy */) ;

    template <typename T>
    const T* getNext(const T& dummy) const ;

    Composite* getParent() ;

    const Composite* getParent() const ;

    Composite* getChild(Index index) ;
  
    const Composite* getChild(Index index) const ;
  
    Composite* getSibling(Index index) ;

    const Composite* getSibling(Index index) const ;

    Composite* getFirstChild() ;

    const Composite* getFirstChild() const ;

    Composite* getLastChild() ;

    const Composite* getLastChild() const ;
      
    const PreciseTime& getModificationTime() const ;

    const PreciseTime& getSelectionTime() const ;

    void stamp(StampType stamp = BOTH) ;
      
    void prependChild(Composite& composite) ;

    void appendChild(Composite& composite) ;

    static bool insertParent(Composite& parent, Composite& first,  
                             Composite& last, bool destroy_parent = true)
      ;

    void insertBefore(Composite& composite) ;

    void insertAfter(Composite& composite) ;

    void spliceBefore(Composite& composite) ;

    void spliceAfter(Composite& composite) ;

    void splice(Composite& composite) ;

    bool removeChild(Composite& child) ;


    Size removeSelected() ;

    Size removeUnselected();

    void replace(Composite& composite) ;

    void swap(Composite& composite) ;

    virtual void select() ;

    virtual void deselect() ;


    bool operator == (const Composite& composite) const ;

    bool operator != (const Composite& composite) const
      ;

    bool isEmpty() const ;

    bool isRoot() const ;
  
    bool isRootOf(const Composite& composite) const ;
  
    bool isInterior() const ;
  
    bool hasChild() const ;
  
    bool isChildOf(const Composite& composite) const ;
  
    bool isFirstChild() const ;
  
    bool isFirstChildOf(const Composite& composite) const ;
  
    bool isLastChild() const ;
  
    bool isLastChildOf(const Composite& composite) const ;
  
    bool hasParent() const ;

    bool isParentOf(const Composite& composite) const ;

    bool hasSibling() const ;
      
    bool isSiblingOf(const Composite& composite) const ;
      
    bool hasPreviousSibling() const ;
  
    bool isPreviousSiblingOf(const Composite& composite) const ;
  
    bool hasNextSibling() const ;

    bool isNextSiblingOf(const Composite& composite) const ;
    
    bool isDescendantOf(const Composite& composite) const ;

    template <typename T>
    bool hasAncestor(const T& dummy) const  ;

    bool isAncestorOf(const Composite& composite) const ;

    bool isRelatedWith(const Composite& composite) const ;
  
    bool isHomomorph(const Composite& composite) const ;

    bool containsSelection() const ;

    virtual bool isValid() const ;

    virtual void dump(std::ostream& s = std::cout, Size depth = 0) const
      ;



    void host(Visitor<Composite>& visitor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyAncestor(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyChild(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);
    
    template <typename T>
    bool applyDescendantPreorder(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyDescendantPostorder(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);
  
    template <typename T>
    bool applyDescendant(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);
    
    template <typename T>
    bool applyPreorder(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);
    
    template <typename T>
    bool applyPostorder(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool apply(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);
    
    template <typename T>
    bool applyLevel(UnaryProcessor<T>& processor, long level)
      throw(Exception::GeneralException);


  
    class BALL_EXPORT AncestorIteratorTraits
    {
      public:

      BALL_INLINE
      AncestorIteratorTraits()
        
        : bound_(0),
          ancestor_(0)
      {
      }
    
      BALL_INLINE
      AncestorIteratorTraits(const Composite& composite)
        
        : bound_(const_cast<Composite*>(&composite)),
          ancestor_(0)
      {
      }
    
      BALL_INLINE
      AncestorIteratorTraits(const AncestorIteratorTraits& traits)
        
        : bound_(traits.bound_),
          ancestor_(traits.ancestor_)
      {
      }
    
      BALL_INLINE
      const AncestorIteratorTraits& operator = (const AncestorIteratorTraits& traits)
        
      {
        bound_ = traits.bound_;
        ancestor_ = traits.ancestor_;
        return *this;
      }

      BALL_INLINE Composite* getContainer()  { return bound_; }

      BALL_INLINE const Composite* getContainer() const  { return bound_; }

      BALL_INLINE bool isSingular() const   { return (bound_ == 0); }

      BALL_INLINE Composite* getPosition()    { return ancestor_; }

      BALL_INLINE Composite* const& getPosition() const  {  return ancestor_; }

      BALL_INLINE bool operator == (const AncestorIteratorTraits& traits) const   { return (ancestor_ == traits.ancestor_); }
    
      BALL_INLINE bool operator != (const AncestorIteratorTraits& traits) const   { return !(ancestor_ == traits.ancestor_); }

      BALL_INLINE bool isValid() const    { return (bound_ != 0 && ancestor_ != 0); }

      BALL_INLINE void invalidate()   { bound_  = ancestor_ = 0; }
      
      BALL_INLINE void toBegin()    { ancestor_ = bound_->parent_; }

      BALL_INLINE bool isBegin() const  { return (ancestor_ == bound_->parent_); }

      BALL_INLINE void toEnd()  { ancestor_ = 0;  }

      BALL_INLINE bool isEnd() const  { return (ancestor_ == 0); }

      BALL_INLINE Composite& getData()  { return *ancestor_;  }

      BALL_INLINE const Composite& getData() const  { return *ancestor_; }

      BALL_INLINE void forward()  { ancestor_ = ancestor_->parent_; }

      private:

      Composite* bound_;
      Composite* ancestor_;
    };

    friend class AncestorIteratorTraits;

    typedef ForwardIterator <Composite, Composite, Composite*, AncestorIteratorTraits>
      AncestorIterator;

    AncestorIterator beginAncestor() 
    {
      return AncestorIterator::begin(*this);
    }

    AncestorIterator endAncestor() 
    {
      return AncestorIterator::end(*this);
    }

    typedef ConstForwardIterator<Composite, Composite, Composite*, AncestorIteratorTraits>
      AncestorConstIterator;

    AncestorConstIterator beginAncestor() const 
    {
      return AncestorConstIterator::begin(*this);
    }

    AncestorConstIterator endAncestor() const 
    {
      return AncestorConstIterator::end(*this);
    }

    class BALL_EXPORT ChildCompositeIteratorTraits
    {
      public:

      ChildCompositeIteratorTraits()
        
        : bound_(0),
          child_(0)
      {
      }
      
      ChildCompositeIteratorTraits(const Composite& composite)
        
        : bound_((Composite *)&composite),
          child_(0)
      {
      }
    
      ChildCompositeIteratorTraits(const ChildCompositeIteratorTraits& traits)
        
        : bound_(traits.bound_),
          child_(traits.child_)
      {
      }
    
      const ChildCompositeIteratorTraits& operator = (const ChildCompositeIteratorTraits& traits)
        
      {
        bound_ = traits.bound_;
        child_ = traits.child_;
        return *this;
      }

      BALL_INLINE Composite* getContainer()  {  return bound_; }

      BALL_INLINE const Composite* getContainer() const   { return bound_; }

      BALL_INLINE bool isSingular() const   { return (bound_ == 0); }

      BALL_INLINE Composite* getPosition()  { return child_; }

      BALL_INLINE Composite* const& getPosition() const   { return child_; }

      BALL_INLINE bool operator == (const ChildCompositeIteratorTraits& traits) const  { return (child_ == traits.child_); }
    
      BALL_INLINE bool operator != (const ChildCompositeIteratorTraits& traits) const  { return !(child_ == traits.child_); }
    
      BALL_INLINE bool isValid() const  { return (bound_ != 0 && child_ != 0); }

      BALL_INLINE void invalidate()  { bound_ = child_ = 0; }

      BALL_INLINE void toBegin()  { child_ = bound_->first_child_; }

      BALL_INLINE bool isBegin() const  { return (child_ == bound_->first_child_); }

      BALL_INLINE void toEnd()  { child_ = 0; }

      BALL_INLINE bool isEnd() const  { return (child_ == 0); }

      BALL_INLINE void toRBegin()  { child_ = bound_->last_child_; }

      BALL_INLINE bool isRBegin() const  { return (child_ == bound_->last_child_); }

      BALL_INLINE void toREnd()  { child_ = 0; }

      BALL_INLINE bool isREnd() const  { return (child_ == 0); }

      BALL_INLINE Composite& getData()  { return *child_; }

      BALL_INLINE const Composite& getData() const  { return *child_; }

      BALL_INLINE void forward()  { child_ = child_->next_; }

      BALL_INLINE void backward()   
      {   
        if (child_ == 0) 
        { 
          // Allow decrementation for past-the-end iterators
          child_ = bound_->last_child_; 
        }
        else  
        { 
          child_ = child_->previous_; 
        } 
      }

      private:

      Composite* bound_;
      Composite* child_;
    };

    friend class ChildCompositeIteratorTraits;

    typedef BidirectionalIterator<Composite, Composite, Composite *, ChildCompositeIteratorTraits>
      ChildCompositeIterator;

    ChildCompositeIterator beginChildComposite()
      
    {
      return ChildCompositeIterator::begin(*this);
    }

    ChildCompositeIterator endChildComposite()
      
    {
      return ChildCompositeIterator::end(*this);
    }



    typedef ConstBidirectionalIterator<Composite, Composite, Composite *, ChildCompositeIteratorTraits>
      ChildCompositeConstIterator;

    ChildCompositeConstIterator beginChildComposite() const
      
    {
      return ChildCompositeConstIterator::begin(*this);
    }

    ChildCompositeConstIterator endChildComposite() const
      
    {
      return ChildCompositeConstIterator::end(*this);
    }



    typedef std::reverse_iterator<ChildCompositeIterator> ChildCompositeReverseIterator;

    ChildCompositeReverseIterator rbeginChildComposite() 
    {
      return ChildCompositeReverseIterator(endChildComposite());
    }

    ChildCompositeReverseIterator rendChildComposite() 
    {
      return ChildCompositeReverseIterator(beginChildComposite());
    }



    typedef std::reverse_iterator<ChildCompositeConstIterator> ChildCompositeConstReverseIterator;

    ChildCompositeConstReverseIterator rbeginChildComposite() const 
    {
      return ChildCompositeConstReverseIterator(endChildComposite());
    }

    ChildCompositeConstReverseIterator rendChildComposite() const 
    {
      return ChildCompositeConstReverseIterator(beginChildComposite());
    }

    class BALL_EXPORT CompositeIteratorTraits
    {
      public:

      BALL_INLINE CompositeIteratorTraits()
        
        : bound_(0),
          position_(0)
      {
      }
    
      CompositeIteratorTraits(const Composite& composite)
        
        : bound_(const_cast<Composite*>(&composite)),
          position_(0)
      {
      }
    
      CompositeIteratorTraits(const CompositeIteratorTraits& traits)
        
        : bound_(traits.bound_),
          position_(traits.position_)
      {
      }

      BALL_INLINE ~CompositeIteratorTraits()  {}
    
      BALL_INLINE bool isValid() const  
      { 
        return ((bound_ != 0) && (position_ != 0)); 
      }

      BALL_INLINE CompositeIteratorTraits& operator = (const CompositeIteratorTraits& traits) 
      {
        bound_ = traits.bound_;
        position_ = traits.position_;
        return *this;
      }

      BALL_INLINE Composite* getContainer()   { return bound_; }

      BALL_INLINE const Composite* getContainer() const  { return bound_; }
    
      BALL_INLINE bool isSingular() const   { return (bound_ == 0); }
    
      BALL_INLINE Composite* getPosition()  { return position_; }
      
      BALL_INLINE const Composite* getPosition() const  { return position_; }
      BALL_INLINE void setPosition(Composite* position)  { position_ = position; }


      BALL_INLINE Composite& getData()  { return *position_; }

      BALL_INLINE const Composite& getData() const  { return *position_; }

      BALL_INLINE bool operator == (const CompositeIteratorTraits& traits) const  
      { 
        return (position_ == traits.position_); 
      }
    
      BALL_INLINE bool operator != (const CompositeIteratorTraits& traits) const  
      { 
        return !(position_ == traits.position_); 
      }
    
      BALL_INLINE void invalidate()   
      { 
        bound_ = 0; 
        position_ = 0;
      }

      BALL_INLINE void toBegin() 
      {
        position_ = bound_;
      }

      BALL_INLINE bool isBegin() const 
      {
        return (position_ == bound_);
      }

      BALL_INLINE void toEnd()  
      {
        position_ = 0;
      }

      BALL_INLINE bool isEnd() const 
      {
        return (position_ == 0);
      }

      BALL_INLINE void toRBegin() 
      {
        if (bound_ != 0)
        {
          position_ = findPreviousPosition(0);
        }
      }

      BALL_INLINE bool isRBegin() const 
      {
        return (position_ == findPreviousPosition(0));
      }
    
      BALL_INLINE void toREnd() 
      { 
        position_ = bound_;
      }

      BALL_INLINE bool isREnd() const 
      {
        return (position_ == bound_);
      }
    
      BALL_INLINE void forward() 
      {
        position_ = findNextPosition(position_);
      }

      BALL_INLINE void backward() 
      {
        position_ = findPreviousPosition(position_);
      }

      protected:

      Composite* bound_;

      Composite* position_;

      Composite* findPreviousPosition(Composite* p) const
      {
        // If we are at the root of the iterator, the 
        // decrementing it results in an invalid iterator
        // (past-the-end).
        if (p == bound_)
        {
          return 0;
        }
        // If we decrement a past-the-end-iterator, we
        // start at the root and "fall down" on the right
        // hand side following the last_child_ pointers
        // until we hit bottom.
        else if (p == 0)
        {
          if (bound_->last_child_ == 0)
          {
            return bound_;
          }
          else
          {
            p = bound_->last_child_;
          }
          while (p->last_child_ != 0)
          {
            p = p->last_child_;
          }
        }
        // Normally, we just grab the guy to the
        // left in the doubly-linked child list.
        else if (p->previous_ != 0)
        {
          p = p->previous_;

          // If the guy to the left hast children,
          // we do the drop on the rigth again.
          while (p->last_child_ != 0)
          {
            p = p->last_child_;
          }
        }
        // Finally, if we can't go down and we can't go 
        // left, we have to go upwards.
        else if (p != bound_)
        {
          p = p->parent_;
        }

        return p;
      }

      Composite* findNextPosition(Composite* p) const
      {
        // If we are in a past-the-end position, we stay put.
        if (p == 0)
        {
          return 0;
        }
        // Otherwise, we try the first child. If there's one,
        // that's our next position.
        else 
        {
          if (p->first_child_ != 0)
          {
            p = p->first_child_;
          }
          else 
          {
            // If we are already in the root node, we are done.
            if (p == bound_)
            {
              return 0;
            }
            // Otherwise, we try to walk to the right at the current level.
            if (p->next_ != 0)
            {
              p = p->next_;
            }
            // If that doesn't work out, we'll have to climb up again.
            // Now, we either revisit a node we have already been to, or we
            // are trying to climb up *beyond* our iteration root (bound_).
            // In the latter case, we return a past-the-end-iterator (0).
            else
            {
              // If we could not walk left or right and we are at the root
              // again, then we are done with the iteration (this is the
              // case if bound_ is a leaf node).
              while (p->next_ == 0)
              {
                p = p->parent_;
                if ((p == bound_) || (p == 0))
                {
                  return 0;
                }
              }
              p = p->next_;
            }
          }
        }
        return p;
      }
    };

    friend class CompositeIteratorTraits;

    typedef BidirectionalIterator<Composite, Composite, Composite*, CompositeIteratorTraits>
      CompositeIterator;

    CompositeIterator beginComposite()  { return CompositeIterator::begin(*this); }

    CompositeIterator endComposite()  { return CompositeIterator::end(*this); }

    typedef ConstBidirectionalIterator<Composite, Composite, Composite*, CompositeIteratorTraits>
      CompositeConstIterator;

    CompositeConstIterator beginComposite() const  
    { 
      return CompositeConstIterator::begin(*this);
    }

    CompositeConstIterator endComposite() const 
    {
      return CompositeConstIterator::end(*this);
    }


    typedef std::reverse_iterator<CompositeIterator> CompositeReverseIterator;

    CompositeReverseIterator rbeginComposite() 
    {
      return CompositeReverseIterator(endComposite());
    }

    CompositeReverseIterator rendComposite() 
    {
      return CompositeReverseIterator(beginComposite());
    }


    typedef std::reverse_iterator<CompositeConstIterator> CompositeConstReverseIterator;

    CompositeConstReverseIterator rbeginComposite() const 
    {
      return CompositeConstReverseIterator(endComposite());
    }

    CompositeConstReverseIterator rendComposite() const 
    {
      return CompositeConstReverseIterator(beginComposite());
    }

    /*
     * This function removes and deletes all composites that are
     * supplied in the list of children.
     */
    void deleteChildrenList_(std::list<Composite*>& composites);

    private:
    
    Size getHeight_(Size size, Size& max_height) const ;
  
    Size countDescendants_() const ;

    void clone_(Composite& parent, Composite& stack) const ;

    template <typename T>
    bool applyLevelNostart_(UnaryProcessor<T>& processor, long level)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyChildNostart_(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyPreorderNostart_(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyDescendantPreorderNostart_(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);

    template <typename T>
    bool applyDescendantPostorderNostart_(UnaryProcessor<T>& processor)
      throw(Exception::GeneralException);


    void updateSelection_() ;
    void determineSelection_() ;
    void select_(bool update_parent = true) ;
    void deselect_(bool update_parent = true) ;

    // private attributes
    
    Size            number_of_children_;
    Composite*      parent_;
    Composite*      previous_;
    Composite*      next_;
    Composite*      first_child_;
    Composite*      last_child_;
    unsigned char   properties_;
    bool            contains_selection_;
    Size            number_of_selected_children_;
    Size            number_of_children_containing_selection_;
    TimeStamp       selection_stamp_;
    TimeStamp       modification_stamp_;
  };

  template <typename T>
  bool Composite::applyAncestor(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    if (processor.start() == false)
    {
      return false;
    }

    Processor::Result result;

    for (Composite* composite = parent_; composite != 0; composite = composite->parent_)
    {
      T* t_ptr;
      if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
      { 
        result = processor(*t_ptr);
        if (result <= Processor::BREAK)
        {
          return (result == Processor::BREAK);
        }
      }
    }

    return processor.finish();
  }
  
  template <typename T>
  bool Composite::applyChild(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return processor.start() && applyChildNostart_(processor) && processor.finish();
  }

  template <typename T>
  bool Composite::applyChildNostart_(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    Processor::Result result = Processor::CONTINUE;

    for (Composite* composite = first_child_;
         composite != 0; composite = composite->next_)
    {
      T* t_ptr;
      if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
      {
        result = processor(*t_ptr);
        if (result <= Processor::BREAK)
        {
          break;
        }
      }
    }

    return (result >= Processor::BREAK);
  }
 
  template <typename T>
  bool Composite::applyDescendantPreorder(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return processor.start() && applyDescendantPreorderNostart_(processor) && processor.finish();
  }

  template <typename T>
  bool Composite::applyDescendantPreorderNostart_(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    Processor::Result result;

    for (Composite* composite = first_child_;
         composite != 0; composite = composite->next_)
    {
      T* t_ptr;
      if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
      { 
        result = processor(*t_ptr);

        if (result <= Processor::BREAK)
        {
          return (result == Processor::BREAK);
        }
      }

      if (composite->first_child_ != 0  && composite->applyDescendantPreorderNostart_(processor) == false)
      {
        return false;
      }
    }

    return true;
  }

  template <typename T>
  bool Composite::applyDescendantPostorder(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return processor.start() && applyDescendantPostorderNostart_(processor) && processor.finish();
  }

  template <typename T>
  bool Composite::applyDescendantPostorderNostart_(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    Processor::Result result;

    for (Composite* composite = first_child_;
         composite != 0; composite = composite->next_)
    {
      if (composite->first_child_ != 0 && 
          composite->applyDescendantPostorderNostart_(processor) == false)
      {
        return false;
      }

      T* t_ptr = dynamic_cast<T*>(composite);
      if (t_ptr != 0)
      {
        result = processor(*t_ptr);

        if (result <= Processor::BREAK)
        {
          return (result == Processor::BREAK);
        }
      }
    }

    return true;
  }

  template <typename T>  
  bool Composite::applyPostorder(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  { 
    if (!processor.start() || !applyDescendantPostorderNostart_(processor))
    {
      return false;
    }

    T* t_ptr = dynamic_cast<T*>(this);

    return (t_ptr != 0                            && 
            processor(*t_ptr) >= Processor::BREAK && 
            processor.finish()                      );
  }

  template <typename T>
  bool Composite::applyLevel(UnaryProcessor<T>& processor, long level)
    throw(Exception::GeneralException)
  {
    return processor.start() && applyLevelNostart_(processor, level) && processor.finish();
  }

  template <typename T>
  bool Composite::applyLevelNostart_(UnaryProcessor<T>& processor, long level)
    throw(Exception::GeneralException)
  {
    if (level == 0)
    {
      T* t_ptr = dynamic_cast<T*>(this);
      if (t_ptr != 0)
      {
       Processor::Result result = processor(*t_ptr);

        if (result <= Processor::BREAK)
        {
          return (result == Processor::BREAK);
        }
      }
    }
    else 
    {
      if (--level == 0)
      {
        return applyChildNostart_(processor);
      }
      else 
      {
        if (level > 0)
        {
          for (Composite* composite = first_child_;
               composite != 0; composite = composite->next_)
          {
            if (composite->first_child_ != 0 && composite->applyLevelNostart_(processor, level) == false)
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  template <typename T>
  bool Composite::applyPreorderNostart_(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    Processor::Result result;
    bool return_value;
    T* t_ptr = dynamic_cast<T*>(this);
    if (t_ptr != 0)
    {
      result = processor(*t_ptr);
  
      if (result <= Processor::BREAK)
      {
        return_value = (result == Processor::BREAK);
      } 
      else 
      {
        return_value =  applyDescendantPreorderNostart_(processor);
      }
    } 
    else 
    {
      return_value =  applyDescendantPreorderNostart_(processor);
    }
    
    return return_value;
  }

  template <typename T>
  bool Composite::applyDescendant(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return applyDescendantPreorder(processor);
  }

  template <typename T>
  bool Composite::applyPreorder(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return processor.start() && applyPreorderNostart_(processor) && processor.finish();
  }

  template <typename T>
  BALL_INLINE 
  bool Composite::apply(UnaryProcessor<T>& processor)
    throw(Exception::GeneralException)
  {
    return applyPreorder(processor);
  }

  template <typename T>
  BALL_INLINE 
  T* Composite::getAncestor(const T& /* dummy */)
    
  {
    T* T_ptr = 0;
    
    for (Composite* composite_ptr = parent_;
         composite_ptr != 0; composite_ptr = composite_ptr->parent_)
    {
      T_ptr = dynamic_cast<T*>(composite_ptr);
      if (T_ptr != 0)
      {
        break;
      } 
    }
    
    return T_ptr;
  }

  template <typename T>
  BALL_INLINE 
  const T* Composite::getAncestor(const T& /* dummy */) const
    
  {
    T* t_ptr = 0;
    for (Composite* composite_ptr = parent_;
         composite_ptr != 0; composite_ptr = composite_ptr->parent_)
    {
      if ((t_ptr = dynamic_cast<T*>(composite_ptr)) != 0)
      {
        break;
      } 
    }
    
    return const_cast<const T*>(t_ptr);
  }

  template <typename T>
  BALL_INLINE 
  T* Composite::getPrevious(const T& /* dummy */)
    
  {
    // create an iterator bound to the root of the subtree
    CompositeIterator it(getRoot().endComposite());

    // set its position to the current composite
    it.getTraits().setPosition(this);

    // walk back until we find something  
    // or we cannot walk any further
    if (+it)
    {
      do 
      {
        --it;
      } 
      while (+it && !RTTI::isKindOf<T>(*it));
    }

    // return a NULL pointer if nothing was found
    Composite* ptr = 0;
    if (+it)
    {
      ptr = &*it;
    }
    
    return dynamic_cast<T*>(ptr);
  }

  template <typename T>
  BALL_INLINE 
  const T* Composite::getPrevious(const T& dummy) const
    
  {
    // cast away the constness of this and call the non-const method
    Composite* nonconst_this = const_cast<Composite*>(this);

    return const_cast<const T*>(nonconst_this->getPrevious(dummy));
  }

  template <typename T>
  BALL_INLINE 
  T* Composite::getNext(const T& /* dummy */)
    
  {
    // create an iterator bound to the root of the subtree
    CompositeIterator it(getRoot().beginComposite());

    // set its position to the current composite
    it.getTraits().setPosition(this);

    // walk forward until we find something 
    // or we cannot walk any further
    do 
    {
      it++;
    } 
    while (it.isValid() && !RTTI::isKindOf<T>(*it));


    // return a NULL pointer if nothing was found
    Composite* ptr = 0;
    if (+it)
    {
      ptr = &*it;
    }
    
    return dynamic_cast<T*>(ptr);
  }

  template <typename T>
  BALL_INLINE 
  const T* Composite::getNext(const T& dummy) const
    
  {
    // cast away the constness of this and call the non-const method
    Composite* nonconst_this = const_cast<Composite*>(this);

    return const_cast<const T*>(nonconst_this->getNext(dummy));
  }

  template <typename T>
  BALL_INLINE 
  bool Composite::hasAncestor(const T& dummy ) const 
    
  {
    return (getAncestor(dummy) != 0); 
  }

# ifndef BALL_NO_INLINE_FUNCTIONS
#   include <BALL/CONCEPT/composite.iC>
# endif


} // namespace BALL

#endif // BALL_CONCEPT_COMPOSITE_H