Composite.h

Go to the documentation of this file.

#ifndef _OCRA_COMPOSITE_H_
#define _OCRA_COMPOSITE_H_

#ifdef _MSC_VER
# pragma once
#endif

#include "ocra/optim/ocra_assert.h"

#include <boost/noncopyable.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/has_nothrow_constructor.hpp>

#include <vector>
#include <algorithm>
#include <iosfwd>
#include <stdexcept>

namespace ocra
{
  template<class ComponentDerived, class CompositeDerived, class ParenthoodInfo> class Component;
  template<class ComponentDerived, class CompositeDerived, class ParenthoodInfo> class Composite;


  struct NoInfo {};


  // ------------------------------------------------------------
  // --- PARENTHOOD ---------------------------------------------
  // ------------------------------------------------------------


  template<class ComponentDerived, class CompositeDerived, class ParenthoodInfo = NoInfo>
  class Parenthood
    : boost::noncopyable
  {
  public:
    typedef Parenthood<ComponentDerived, CompositeDerived, ParenthoodInfo>    parenthood_t;
    typedef ComponentDerived                                                  component_t;
    typedef CompositeDerived                                                  parent_t;

  private:
    // Composite objects can create and destroy parenthood bonds to attach children.
    // To keep this operation private, Composite has been made friend of Parenthood.
    friend class Composite<ComponentDerived, CompositeDerived, ParenthoodInfo>;


    Parenthood(parent_t& parent, component_t& child)
      : parent_(parent), child_(child)
      , rankOfParent_(child.parents_.size()), rankOfChild_(parent.children_.size())
      , info_()
    {
      // Check preconditions
      ocra_assert(!parent.isAncestorOf(child) && "Parent is already an ancestor of child!");
      ocra_assert(!child.isAncestorOf(parent) && "Parent is already a descendant of child!");
      ocra_assert(&child != &parent && "Cannot attach a node to itself!");

      parent_.children_.push_back(this);
      child_.parents_.push_back(this);

      // Call the callbacks to inform the parent and child about their new bond.
      child_.onAttachedParentI(*this);
      parent_.onAttachedChildI(*this);

      // Check post-conditions.
      ocra_assert(&parent.getChildhood(getRankOfChild()) == &child.getParenthood(getRankOfParent()) &&
        &parent.getChildhood(getRankOfChild()) == this &&
        "The same bond is supposed to be registered in both the parent and the child");
      ocra_assert(parent_.isAncestorOf(child_) && "Parent-child relationship not acknowledged");
      ocra_assert(!child_.isAncestorOf(parent_) && "Reversed parent-child relationship");
    }


    ~Parenthood()
    {
      typename std::vector<parenthood_t*>::iterator itChild = parent_.children_.begin() + rankOfChild_;
      typename std::vector<parenthood_t*>::iterator itParent = child_.parents_.begin() + rankOfParent_;

      // Check invariants.
      ocra_assert(this == *itChild && this == *itParent && "Class invariant broken: the bond is not properly registered in the parent and the child.");
      ocra_assert(parent_.isAncestorOf_impl(child_) && "Class invariant broken");
      // !child_.isAncestorOf(parent_) cannot be tested here since it is a virtual function, so we use a special version.
      ocra_assert(!childIsAncestorOfParent_forDestructor() && "Class invariant broken");

      // Inform child and parents they are no longer bound to each other.
      child_.onDetachedParentI(*this);
      parent_.onDetachedChildI(*this);

      parent_.children_.erase(parent_.children_.begin() + rankOfChild_);
      child_.parents_.erase(child_.parents_.begin() + rankOfParent_);

      // Update rank of all younger brothers of child.
      for(itChild = parent_.children_.begin() + rankOfChild_; itChild != parent_.children_.end(); ++itChild)
      {
        ocra_assert((*itChild)->rankOfChild_ && "rankOfChild_ is not supposed to be decreased when already 0");
        --(*itChild)->rankOfChild_;
      }

      // Update rank of all child's parents younger than parent_.
      for(itParent = child_.parents_.begin() + rankOfParent_; itParent != child_.parents_.end(); ++itParent)
      {
        ocra_assert((*itParent)->rankOfParent_ && "rankOfParent_ is not supposed to be decreased when already 0");
        --(*itParent)->rankOfParent_;
      }
    }

    int childIsAncestorOfParent_forDestructor() // see invariants check in destructor for explanation
    {
      parent_t* child_or_null = dynamic_cast<parent_t*>(&child_);

      if(child_or_null) // we have a composite, just check using the static isAncestorOf_impl!
        return child_or_null->isAncestorOf_impl(parent_);

      return false; // we have a leaf, so of course it's no ancestor!
    }

  public:
    CompositeDerived& getParent() const { return static_cast<CompositeDerived&>(parent_); }
    size_t getRankOfParent() const { return rankOfParent_; }

    ComponentDerived& getChild() const { return static_cast<ComponentDerived&>(child_); }
    size_t getRankOfChild() const { return rankOfChild_; }

    ParenthoodInfo& getInfo() const { return info_; }


    Parenthood* getPreviousParent() const
    {
      ocra_assert(rankOfParent_ < child_.parents_.size() && "rankOfParent_ >= child_->parents_.size() should never happen");
      ocra_assert(*(child_.parents_.begin() + rankOfParent_) == this && "Class invariant broken: parenthood not in the expected place in child's parents");

      if(!rankOfParent_)
        return 0x0;
      return child_.parents_[rankOfParent_ - 1];
    }

    Parenthood* getNextParent() const
    {
      ocra_assert(rankOfParent_ < child_.parents_.size() && "rankOfParent_ >= child_->parents_.size() should never happen");
      ocra_assert(*(child_.parents_.begin() + rankOfParent_) == this && "Class invariant broken: parenthood not in the expected place in child's parents");

      size_t rankOfNextParent = rankOfParent_ + 1;
      if(rankOfNextParent >= child_.parents_.size())
        return 0x0;
      return child_.parents_[rankOfNextParent];
    }

    Parenthood* getPreviousChild() const
    {
      ocra_assert(rankOfChild_ < parent_.children_.size() && "rankOfChild_ >= parent_->children_.size() should never happen");
      ocra_assert(*(parent_.children_.begin() + rankOfChild_) == this && "Class invariant broken: parenthood not in the expected place in parent's children");

      if(!rankOfChild_)
        return 0x0;
      return parent_.children_[rankOfChild_ - 1];
    }

    Parenthood* getNextChild() const
    {
      ocra_assert(rankOfChild_ < parent_.children_.size() && "rankOfChild_ >= parent_->children_.size() should never happen");
      ocra_assert(*(parent_.children_.begin() + rankOfChild_) == this && "Class invariant broken: parenthood not in the expected place in parent's children");

      size_t rankOfNextChild = rankOfChild_ + 1;
      if(rankOfNextChild >= parent_.children_.size())
        return 0x0;
      return parent_.children_[rankOfNextChild];
    }

  public:

    struct parentIs
    {
      bool operator()(const parenthood_t* p) const { ocra_assert(p && "null pointer refused here"); return &p->getParent() == parent_; }
      parentIs(const parent_t* parent): parent_(parent) {}
      const parent_t* parent_;
    };

    struct childIs
    {
      bool operator()(const parenthood_t* p) const { ocra_assert(p && "null pointer refused here"); return &p->getChild() == child_; }
      childIs(const component_t* child): child_(child) {}
      const component_t* child_;
    };

  private:
    // The state of a parenthood is represented by which instances are the child and parent, and by
    // their ranks. The states of the child and parent as well as the additional info are nor part of
    // the parenthood's state and are therefore mutable.
    // Note that the only methods which can change the state of a parenthood are decreaseRankOfChild
    // and decreaseRankOfParent, which are private and only accessible in ocra::detach. All other methods
    // will preserve the state of the class.

    /*mutable*/ parent_t& parent_;
    /*mutable*/ component_t& child_;
    size_t rankOfParent_;
    size_t rankOfChild_;
    mutable ParenthoodInfo info_;

  private: // enforce preconditions
    typedef boost::is_base_of<ComponentDerived, CompositeDerived>
      ComponentDerived_must_be_base_of_CompositeDerived;

    typedef boost::is_convertible<CompositeDerived*, ComponentDerived*>
      CompositeDerived_must_publicly_derive_ComponentDerived;

    typedef boost::has_nothrow_default_constructor<ParenthoodInfo>
      ParenthoodInfo_must_have_default_nothrow_constructor;

    typedef Component<ComponentDerived, CompositeDerived, ParenthoodInfo> component_base_t_;

    typedef boost::is_base_of<component_base_t_, ComponentDerived>
      component_base_t_must_be_base_of_ComponentDerived;

    typedef boost::is_convertible<ComponentDerived*, component_base_t_*>
      ComponentDerived_must_publicly_derive_component_base_t_;

    typedef Composite<ComponentDerived, CompositeDerived, ParenthoodInfo> composite_base_t_;

    typedef boost::is_base_of<composite_base_t_, CompositeDerived>
      composite_base_t_must_be_base_of_CompositeDerived;

    typedef boost::is_convertible<CompositeDerived*, composite_base_t_*>
      CompositeDerived_must_publicly_derive_composite_base_t_;

    BOOST_STATIC_ASSERT( ComponentDerived_must_be_base_of_CompositeDerived          ::value );
    BOOST_STATIC_ASSERT( CompositeDerived_must_publicly_derive_ComponentDerived     ::value );
    //BOOST_STATIC_ASSERT( ParenthoodInfo_must_have_default_nothrow_constructor       ::value );
    BOOST_STATIC_ASSERT( component_base_t_must_be_base_of_ComponentDerived          ::value );
    BOOST_STATIC_ASSERT( ComponentDerived_must_publicly_derive_component_base_t_    ::value );
    BOOST_STATIC_ASSERT( composite_base_t_must_be_base_of_CompositeDerived          ::value );
    BOOST_STATIC_ASSERT( CompositeDerived_must_publicly_derive_composite_base_t_    ::value );
  };


  // ------------------------------------------------------------
  // --- COMPONENT ----------------------------------------------
  // ------------------------------------------------------------


  template<class ComponentDerived, class CompositeDerived, class ParenthoodInfo = NoInfo>
  class Component
  {
  public:
    typedef ComponentDerived                                                    component_t;
    typedef CompositeDerived                                                    parent_t;
    typedef Parenthood<ComponentDerived, CompositeDerived, ParenthoodInfo>      parenthood_t;
    typedef typename std::vector<parenthood_t*>::const_iterator                 const_iterator;
    typedef typename std::vector<parenthood_t*>::iterator                       iterator;

  public:
    size_t getNumParenthoods() const { return parents_.size(); }
    const parenthood_t& getParenthood(size_t i) const { return *parents_[i]; }

    const_iterator parents_begin() const { return parents_.begin(); }
    iterator parents_begin() { return parents_.begin(); }

    const_iterator parents_end() const { return parents_.end(); }
    iterator parents_end() { return parents_.end(); }


    int isDescendantOf(const CompositeDerived& node) const { return isDescendantOf(node, 1); }
    int isDescendantOf(const ComponentDerived& node) const { return node.isAncestorOf(*static_cast<const ComponentDerived*>(this)); }

    bool isChildOf(const CompositeDerived& node)
    {
      for(const_iterator it = parents_begin(); it != parents_end(); ++it)
        if(&(*it)->getParent() == &node)
          return true;
      return false;
    }

    void printTree(std::ostream& os) { printSubTree(0, os); }

    // --- To implement in CompositeDerived and LeafDerived -------
  public:
    /*
    If the object is not a ancestor of node, returns 0. If it is a parent of node, returns 1.
    If it is a grand-parent, returns 2, and so on...
    You must overload this method in the two concrete classes that derive Leaf and Composite (see the
    documentation of the class). Let's call these classes MyLeaf and MyComposite.
    - MyComposite::isAncesterOf must implement the behavior just described. simple way to do it is to forward
    the call to Composite::isAncestorOf_impl, as shown in the example in the class documentation.
    - MyLeaf::isAncesterOf must always return 0.
    \sa class Component.
    */
    virtual int isAncestorOf(const ComponentDerived& node) const = 0;


    virtual void printSubTree(int depth, std::ostream& os) const = 0;


    virtual void printNode(int depth, std::ostream& os) const = 0;

    // --- To overload if derived class (optional) ----------------
  protected:

    virtual void onAttachedParent(const parenthood_t& parent) {}
    virtual void onDetachedParent(const parenthood_t& parent) {}

  protected:

    Component(): componentBeingDestroyed_(false) // this boolean is to avoid CRTP virtual calls in the destructor.
    {}

    ~Component()
    {
      componentBeingDestroyed_ = true; // therefore, no (CRTP) virtual call is possible!
      while(parents_.size())
        parents_.back()->getParent().Composite<ComponentDerived, CompositeDerived, ParenthoodInfo>::remove(*static_cast<ComponentDerived*>(this));
    }

  private:
    int isDescendantOf(const CompositeDerived& node, int level) const
    {
      int result = 0;

      for(size_t i = 0; !result && (i < parents_.size()); ++i)
      {
        const parent_t& parent = parents_[i]->getParent();
        if(&node == &parent)
          return level;

        result = parent.isDescendantOf(node, level + 1);
      }

      return result;
    }

    void onAttachedParentI(const parenthood_t& parent)
    {
      if(!componentBeingDestroyed_) // If entered destructor, do not forward the call to the derived class (already destructed!).
        onAttachedParent(parent);
    }

    void onDetachedParentI(const parenthood_t& parent)
    {
      if(!componentBeingDestroyed_)
        onDetachedParent(parent);
    }

  private:
    std::vector<parenthood_t*> parents_;
    bool componentBeingDestroyed_;

    // http://stackoverflow.com/questions/392120/why-cant-i-declare-a-friend-through-a-typedef
    // friend class parenthood_t; // Rather make the mediator a friend rather than open the internals!
    friend class Parenthood<ComponentDerived, CompositeDerived, ParenthoodInfo>;
  };


  // ------------------------------------------------------------
  // --- COMPOSITE ----------------------------------------------
  // ------------------------------------------------------------


  template<class ComponentDerived, class CompositeDerived, class ParenthoodInfo = NoInfo>
  class Composite
  {
  private:
    typedef Parenthood<ComponentDerived, CompositeDerived, ParenthoodInfo>                          parenthood_t_;
    typedef typename Component<ComponentDerived, CompositeDerived, ParenthoodInfo>::component_t     component_t_;
    typedef typename Component<ComponentDerived, CompositeDerived, ParenthoodInfo>::parent_t        parent_t_;
    typedef typename std::vector<parenthood_t_*>::const_iterator                                    const_iterator_;
    typedef typename std::vector<parenthood_t_*>::iterator                                          iterator_;

  public:
    bool isParentOf(const ComponentDerived& node)
    {
      for(const_iterator_ it = children_begin(); it != children_end(); ++it)
        if(&(*it)->getChild() == &node)
          return true;
      return false;
    }

    size_t getNumChildhoods() const { return children_.size(); }
    const parenthood_t_& getChildhood(size_t i) const { return *children_[i]; }

    const_iterator_ children_begin() const { return children_.begin(); }
    iterator_ children_begin() { return children_.begin(); }

    const_iterator_ children_end() const { return children_.end(); }
    iterator_ children_end() { return children_.end(); }


    virtual CompositeDerived& add(ComponentDerived& child) { attach(child); return *static_cast<CompositeDerived*>(this); }
    virtual CompositeDerived& remove(ComponentDerived& child) { detach(child); return *static_cast<CompositeDerived*>(this); }

  protected:

    virtual void onAttachedChild(const parenthood_t_& child) {}
    virtual void onDetachedChild(const parenthood_t_& child) {}

  protected:
    Composite(): compositeBeingDestroyed_(false) // see Component for an explanation about this bool
    {}

    ~Composite()
    {
      compositeBeingDestroyed_ = true;
      while(children_.size())
        detach(children_.back()->getChild());
    }

  protected:
    void attach(ComponentDerived& child)
    {
      new parenthood_t_(*static_cast<CompositeDerived*>(this), child);
    }

    void detach(ComponentDerived& child)
    {
      typename std::vector<parenthood_t_*>::iterator itParent =
        std::find_if(child.parents_begin(), child.parents_end(), typename parenthood_t_::parentIs(static_cast<CompositeDerived*>(this)));

      if(itParent == child.parents_end())
        throw std::runtime_error("[ocra::Composite::detach]: parent not found in child's parents... Are the nodes really bound together?");

      delete *itParent;
    }

    int isAncestorOf_impl(const ComponentDerived& node) const { return node.isDescendantOf(*static_cast<const CompositeDerived*>(this)); }

    void printTree_impl(int depth, std::ostream& os) const
    {
      static_cast<const CompositeDerived*>(this)->printNode(depth, os);
      for(size_t i = 0; i < children_.size(); ++i)
        static_cast<ComponentDerived*>(&children_[i]->getChild())->printSubTree(depth + 1, os);
    }

  private:
    void onAttachedChildI(const parenthood_t_& child)
    {
      if(!compositeBeingDestroyed_)
        onAttachedChild(child);
    }

    void onDetachedChildI(const parenthood_t_& child)
    {
      if(!compositeBeingDestroyed_)
        onDetachedChild(child);
    }

  private:
    std::vector<parenthood_t_*> children_;
    bool compositeBeingDestroyed_;

    // see line 603 (why-cant-i-declare-a-friend-through-a-typedef)
    friend class Parenthood<ComponentDerived, CompositeDerived, ParenthoodInfo>;
  };


  // ------------------------------------------------------------
  // --- LEAF ---------------------------------------------------
  // ------------------------------------------------------------


  template<class LeafDerived>
  class Leaf
  {
  public:
    typedef LeafDerived leaf_t;

  protected:
    Leaf()
    {
      // enforce preconditions
      typedef Leaf<LeafDerived> leaf_base_t_;

      typedef boost::is_base_of<leaf_base_t_, LeafDerived>
        leaf_base_t_must_be_base_of_LeafDerived;

      typedef boost::is_convertible<LeafDerived*, leaf_base_t_*>
        LeafDerived_must_publicly_derive_leaf_base_t_;

      BOOST_STATIC_ASSERT( leaf_base_t_must_be_base_of_LeafDerived          ::value );
      BOOST_STATIC_ASSERT( LeafDerived_must_publicly_derive_leaf_base_t_    ::value );
    }

    ~Leaf() {}

    void printTree_impl(int depth, std::ostream& os) const
    {
      static_cast<const LeafDerived*>(this)->printNode(depth, os);
    }
  };
}

#endif // _OCRA_COMPOSITE_H_

// cmake:sourcegroup=utils