RhodeCode

        visitor.reach(node);

        visitor.process(node);

        visitor.discover(arc);

        visitor.examine(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    ///

    /// The type of the map that indicates which nodes are reached.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %BFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a BFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = BfsVisitor<_Digraph>,

            typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithm.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw()

      {

        return "lemon::BfsVisit::UninitializedParameter";

      }

    };

    ///The traits class.

    typedef _Traits Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef _Visitor Visitor;

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_BASE_EXTENDER_H

#define LEMON_BITS_BASE_EXTENDER_H

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/bits/map_extender.h>

#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup digraphbits

///\file

///\brief Extenders for the digraph types

namespace lemon {

  /// \ingroup digraphbits

  ///

  /// \brief BaseDigraph to BaseGraph extender

  template <typename Base>

  class UndirDigraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef typename Parent::Arc Edge;

    typedef typename Parent::Node Node;

    typedef True UndirectedTag;

    class Arc : public Edge {

      friend class UndirDigraphExtender;

    protected:

      bool forward;

      Arc(const Edge &ue, bool _forward) :

        Edge(ue), forward(_forward) {}

    public:

      Arc() {}

      Arc(Invalid i) : Edge(i), forward(true) {}

      bool operator==(const Arc &that) const {

        return forward==that.forward && Edge(*this)==Edge(that);

      }

      bool operator!=(const Arc &that) const {

        return forward!=that.forward || Edge(*this)!=Edge(that);

      }

      bool operator<(const Arc &that) const {

        return forward<that.forward ||

          (!(that.forward<forward) && Edge(*this)<Edge(that));

      }

    };

    Node source(const Arc &e) const {

      return e.forward ? Parent::source(e) : Parent::target(e);

    }

    Node target(const Arc &e) const {

      return e.forward ? Parent::target(e) : Parent::source(e);

    }

    /// \brief Directed arc from an edge.

    ///

    }

    ///

    /// \todo reference to the corresponding point of the undirected digraph

    /// concept. "What does the direction of an edge mean?"

    using Parent::first;

    using Parent::next;

    void first(Arc &e) const {

      Parent::first(e);

      e.forward=true;

    }

    void next(Arc &e) const {

      if( e.forward ) {

        e.forward = false;

      }

      else {

        Parent::next(e);

        e.forward = true;

      }

    }

    void firstOut(Arc &e, const Node &n) const {

      Parent::firstIn(e,n);

      if( Edge(e) != INVALID ) {

        e.forward = false;

      }

      else {

        Parent::firstOut(e,n);

        e.forward = true;

      }

    }

    void nextOut(Arc &e) const {

      if( ! e.forward ) {

        Node n = Parent::target(e);

        Parent::nextIn(e);

        if( Edge(e) == INVALID ) {

          Parent::firstOut(e, n);

          e.forward = true;

        }

      }

      else {

        Parent::nextOut(e);

      }

    }

    void firstIn(Arc &e, const Node &n) const {

      Parent::firstOut(e,n);

      if( Edge(e) != INVALID ) {

        e.forward = false;

      }

    void nextInc(Edge &e, bool &d) const {

      if (d) {

        Node s = Parent::source(e);

        Parent::nextOut(e);

        if (e != INVALID) return;

        d = false;

        Parent::firstIn(e, s);

      } else {

        Parent::nextIn(e);

      }

    }

    Node nodeFromId(int ix) const {

      return Parent::nodeFromId(ix);

    }

    Arc arcFromId(int ix) const {

      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));

    }

    Edge edgeFromId(int ix) const {

      return Parent::arcFromId(ix);

    }

    int id(const Node &n) const {

      return Parent::id(n);

    }

    int id(const Edge &e) const {

      return Parent::id(e);

    }

    int id(const Arc &e) const {

      return 2 * Parent::id(e) + int(e.forward);

    }

    int maxNodeId() const {

      return Parent::maxNodeId();

    }

    int maxArcId() const {

      return 2 * Parent::maxArcId() + 1;

    }

    int maxEdgeId() const {

      return Parent::maxArcId();

    }

    int arcNum() const {

      return 2 * Parent::arcNum();

    }

    int edgeNum() const {

      return Parent::arcNum();

    }

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

      if (p == INVALID) {

        Edge arc = Parent::findArc(s, t);

        if (arc != INVALID) return direct(arc, true);

        arc = Parent::findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else if (direction(p)) {

        Edge arc = Parent::findArc(s, t, p);

        if (arc != INVALID) return direct(arc, true);

        arc = Parent::findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else {

        Edge arc = Parent::findArc(t, s, p);

        if (arc != INVALID) return direct(arc, false);

      }

      return INVALID;

    }

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

      if (s != t) {

        if (p == INVALID) {

          Edge arc = Parent::findArc(s, t);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;

        } else if (Parent::s(p) == s) {

          Edge arc = Parent::findArc(s, t, p);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;

        } else {

          Edge arc = Parent::findArc(t, s, p);

          if (arc != INVALID) return arc;

        }

      } else {

        return Parent::findArc(s, t, p);

      }

      return INVALID;

    }

  };

        visitor.discover(arc);

        visitor.examine(arc);

        visitor.leave(node);

        visitor.backtrack(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of DfsVisit class.

  ///

  /// Default traits class of DfsVisit class.

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  template<class _Digraph>

  struct DfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    ///

    /// The type of the map that indicates which nodes are reached.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %DFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the %DFS algorithm

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

  /// the member functions of the \c Visitor class on every DFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which

  /// does not observe the DFS events. If you want to observe the DFS

  /// events, you should implement your own visitor class.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a DFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = DfsVisitor<_Digraph>,

            typename _Traits = DfsDefaultTraits<_Digraph> >

#endif

  class DfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithm.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw()

      {

        return "lemon::DfsVisit::UninitializedParameter";

      }

    };

    ///The traits class.

    typedef _Traits Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef _Visitor Visitor;

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,Value> DistMap;

    ///Instantiates a \ref DistMap.

    ///This function instantiates a \ref DistMap.

    ///\param g is the digraph, to which we would like to define

    ///the \ref DistMap

#ifdef DOXYGEN

    static DistMap *createDistMap(const Digraph &g)

#else

    static DistMap *createDistMap(const Digraph &)

#endif

    {

      return new DistMap();

    }

  };

  /// Default traits class used by \ref DijkstraWizard

  /// To make it easier to use Dijkstra algorithm

  /// we have created a wizard class.

  /// This \ref DijkstraWizard class needs default traits,

  /// as well as the \ref Dijkstra class.

  /// The \ref DijkstraWizardBase is a class to be the default traits of the

  /// \ref DijkstraWizard class.

  /// \todo More named parameters are required...

  template<class GR,class LM>

  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>

  {

    typedef DijkstraWizardDefaultTraits<GR,LM> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the length map

    void *_length;

    //Pointer to the map of predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the source node.

    Node _source;

  public:

    /// Constructor.

    /// This constructor does not require parameters, therefore it initiates

    /// all of the attributes to default values (0, INVALID).

                           _dist(0), _source(INVALID) {}

    /// Constructor.

    /// This constructor requires some parameters,

    /// listed in the parameters list.

    /// Others are initiated to 0.

    /// \param g The digraph the algorithm runs on.

    /// \param l The length map.

    /// \param s The source node.

    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :

      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),

      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),

  };

  /// Auxiliary class for the function type interface of Dijkstra algorithm.

  /// This auxiliary class is created to implement the function type

  /// interface of \ref Dijkstra algorithm. It uses the functions and features

  /// of the plain \ref Dijkstra, but it is much simpler to use it.

  /// It should only be used through the \ref dijkstra() function, which makes

  /// it easier to use the algorithm.

  ///

  /// Simplicity means that the way to change the types defined

  /// in the traits class is based on functions that returns the new class

  /// and not on templatable built-in classes.

  /// When using the plain \ref Dijkstra

  /// the new class with the modified type comes from

  /// the original class by using the ::

  /// operator. In the case of \ref DijkstraWizard only

  /// a function have to be called, and it will

  /// return the needed class.

  ///

  /// It does not have own \ref run() method. When its \ref run() method

  /// is called, it initiates a plain \ref Dijkstra object, and calls the

  /// \ref Dijkstra::run() method of it.

  template<class TR>

  class DijkstraWizard : public TR

  {

    typedef TR Base;

    ///The type of the digraph the algorithm runs on.

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    ///The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    ///The type of the length of the arcs.

    typedef typename LengthMap::Value Value;

    ///\brief The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    ///The type of the map that indicates which nodes are processed.

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The heap type used by the dijkstra algorithm.

    typedef typename TR::Heap Heap;

  public:

    /// Constructor.

    DijkstraWizard() : TR() {}

    /// Constructor that requires parameters.

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :

      TR(g,l,s) {}

    ///Copy constructor

    DijkstraWizard(const TR &b) : TR(b) {}

    ~DijkstraWizard() {}

    ///Runs Dijkstra algorithm from a source node.

    ///Runs Dijkstra algorithm from a source node.

    ///The node can be given with the \ref source() function.

    void run()

    {

      if(Base::_source==INVALID) throw UninitializedParameter();

      Dijkstra<Digraph,LengthMap,TR>

        dij(*reinterpret_cast<const Digraph*>(Base::_g),

            *reinterpret_cast<const LengthMap*>(Base::_length));

      dij.run(Base::_source);

    }

    ///Runs Dijkstra algorithm from the given node.

    ///Runs Dijkstra algorithm from the given node.

    ///\param s is the given source.

    void run(Node s)

    {

      Base::_source=s;

      run();

    }

    /// Sets the source node, from which the Dijkstra algorithm runs.

    /// Sets the source node, from which the Dijkstra algorithm runs.

    /// \param s is the source node.

    DijkstraWizard<TR> &source(Node s)

    {

      Base::_source=s;

      return *this;

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &) { return 0; };

      SetPredMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref PredMap object.

    ///

    ///\ref named-templ-param "Named parameter"

    ///for setting \ref PredMap object.

    template<class T>

    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)

    {

      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));

      return DijkstraWizard<SetPredMapBase<T> >(*this);

    }

    template<class T>

    struct SetProcessedMapBase : public Base {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };

      SetProcessedMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_DIM2_H

#define LEMON_DIM2_H

#include <iostream>

///\ingroup misc

///\file

///\brief A simple two dimensional vector and a bounding box implementation

///

/// The class \ref lemon::dim2::Point "dim2::Point" implements

/// a two dimensional vector with the usual operations.

///

/// the rectangular bounding box of a set of

/// \ref lemon::dim2::Point "dim2::Point"'s.

namespace lemon {

  ///Tools for handling two dimensional coordinates

  ///This namespace is a storage of several

  ///tools for handling two dimensional coordinates

  namespace dim2 {

  /// \addtogroup misc

  /// @{

  /// A simple two dimensional vector (plain vector) implementation

  /// with the usual vector operations.

  template<typename T>

    class Point {

    public:

      typedef T Value;

      ///First coordinate

      T x;

      ///Second coordinate

      T y;

      ///Default constructor

      Point() {}

      ///Construct an instance from coordinates

      Point(T a, T b) : x(a), y(b) { }

      ///Returns the dimension of the vector (i.e. returns 2).

      ///The dimension of the vector.

      ///This function always returns 2.

      int size() const { return 2; }

      ///Subscripting operator

      ///\c p[0] is \c p.x and \c p[1] is \c p.y

      ///

      T& operator[](int idx) { return idx == 0 ? x : y; }

      ///Const subscripting operator

      ///\c p[0] is \c p.x and \c p[1] is \c p.y

      ///

      const T& operator[](int idx) const { return idx == 0 ? x : y; }

      ///Conversion constructor

      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}

      ///Give back the square of the norm of the vector

      T normSquare() const {

        return x*x+y*y;

      }

      ///Increment the left hand side by \c u

  inline Point<T> makePoint(const T& x, const T& y) {

    return Point<T>(x, y);

  }

  ///Return a vector multiplied by a scalar

  ///Return a vector multiplied by a scalar.

  ///\relates Point

  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {

    return x*u;

  }

  ///Read a plain vector from a stream

  ///Read a plain vector from a stream.

  ///\relates Point

  ///

  template<typename T>

  inline std::istream& operator>>(std::istream &is, Point<T> &z) {

    char c;

    if (is >> c) {

      if (c != '(') is.putback(c);

    } else {

      is.clear();

    }

    if (!(is >> z.x)) return is;

    if (is >> c) {

      if (c != ',') is.putback(c);

    } else {

      is.clear();

    }

    if (!(is >> z.y)) return is;

    if (is >> c) {

      if (c != ')') is.putback(c);

    } else {

      is.clear();

    }

    return is;

  }

  ///Write a plain vector to a stream

  ///Write a plain vector to a stream.

  ///\relates Point

  ///

  template<typename T>

  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)

  {

    return os;

  }

  ///Rotate by 90 degrees

  ///Returns the parameter rotated by 90 degrees in positive direction.

  ///\relates Point

  ///

  template<typename T>

  inline Point<T> rot90(const Point<T> &z)

  {

    return Point<T>(-z.y,z.x);

  }

  ///Rotate by 180 degrees

  ///Returns the parameter rotated by 180 degrees.

  ///\relates Point

  ///

  template<typename T>

  inline Point<T> rot180(const Point<T> &z)

  {

    return Point<T>(-z.x,-z.y);

  }

  ///Rotate by 270 degrees

  ///Returns the parameter rotated by 90 degrees in negative direction.

  ///\relates Point

  ///

  template<typename T>

  inline Point<T> rot270(const Point<T> &z)

  {

    return Point<T>(z.y,-z.x);

  }

      Point<T> _bottom_left, _top_right;

      bool _empty;

    public:

        _bottom_left = _top_right = a;

        _empty = false;

      }

      ///\param a The bottom left corner.

      ///\param b The top right corner.

      ///\warning The coordinates of the bottom left corner must be no more

      ///than those of the top right one.

      {

        _bottom_left = a;

        _top_right = b;

        _empty = false;

      }

      ///\param l The left side of the box.

      ///\param b The bottom of the box.

      ///\param r The right side of the box.

      ///\param t The top of the box.

      ///\warning The left side must be no more than the right side and

      ///bottom must be no more than the top.

      {

        _bottom_left=Point<T>(l,b);

        _top_right=Point<T>(r,t);

        _empty = false;

      }

      ///if at least one point was added to the box or the coordinates of

      ///the box were set).

      ///

      bool empty() const {

        return _empty;

      }

      void clear() {

        _empty = true;

      }

      ///Give back the bottom left corner of the box

      ///Give back the bottom left corner of the box.

      Point<T> bottomLeft() const {

        return _bottom_left;

      }

      ///Set the bottom left corner of the box

      ///Set the bottom left corner of the box.

      ///\pre The box must not be empty.

      void bottomLeft(Point<T> p) {

        _bottom_left = p;

      }

      ///Give back the top right corner of the box

      ///Give back the top right corner of the box.

      Point<T> topRight() const {

        return _top_right;

      }

      ///Set the top right corner of the box

      ///Set the top right corner of the box.

      ///\pre The box must not be empty.

      void topRight(Point<T> p) {

        _top_right = p;

      }

      ///Give back the bottom right corner of the box

      ///Give back the bottom right corner of the box.

      Point<T> bottomRight() const {

        return Point<T>(_top_right.x,_bottom_left.y);

      }

      ///Set the bottom right corner of the box

      ///Set the bottom right corner of the box.

      ///\pre The box must not be empty.

      void bottomRight(Point<T> p) {

        _top_right.x = p.x;

        _bottom_left.y = p.y;

      }

      ///Give back the top left corner of the box

      ///Give back the top left corner of the box.

      Point<T> topLeft() const {

        return Point<T>(_bottom_left.x,_top_right.y);

      }

      ///Set the top left corner of the box

      ///Set the top left corner of the box.

      ///\pre The box must not be empty.

      void topLeft(Point<T> p) {

        _top_right.y = p.y;

        _bottom_left.x = p.x;

      }

      ///Give back the bottom of the box

      ///Give back the bottom of the box.

      T bottom() const {

        return _bottom_left.y;

      }

      ///Set the bottom of the box

      ///Set the bottom of the box.

      ///\pre The box must not be empty.

      void bottom(T t) {

        _bottom_left.y = t;

      }

      ///Give back the top of the box

      ///Give back the top of the box.

      T top() const {

        return _top_right.y;

      }

      ///Set the top of the box

      ///Set the top of the box.

      ///\pre The box must not be empty.

      void top(T t) {

        _top_right.y = t;

      }

      ///Give back the left side of the box

      ///Give back the left side of the box.

      T left() const {

        return _bottom_left.x;

      }

      ///Set the left side of the box

      ///Set the left side of the box.

      ///\pre The box must not be empty.

      void left(T t) {

        _bottom_left.x = t;

      }

      /// Give back the right side of the box

      /// Give back the right side of the box.

      T right() const {

        return _top_right.x;

      }

      ///Set the right side of the box

      ///Set the right side of the box.

      ///\pre The box must not be empty.

      void right(T t) {

        _top_right.x = t;

      }

      ///Give back the height of the box