graphFace.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//
// $Id: graphFace.h,v 1.14.26.2 2007/06/17 07:02:20 oliver Exp $
//
// Author:
// 
//

#ifndef BALL_STRUCTURE_GRAPHFACE_H
#define BALL_STRUCTURE_GRAPHFACE_H

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

#include <list>
#include <vector>

namespace BALL
{

  template <typename Vertex, typename Edge, typename Face>
  class GraphVertex;

  template <typename Vertex, typename Edge, typename Face>
  class GraphEdge;

  template <typename Vertex, typename Edge, typename Face>
  class GraphFace
  {
    public:

    friend class GraphVertex<Vertex,Edge,Face>;
    friend class GraphEdge<Vertex,Edge,Face>;

    BALL_CREATE(GraphFace)

    

    typedef typename std::list<Vertex*>::iterator VertexIterator;
    typedef typename std::list<Vertex*>::const_iterator ConstVertexIterator;
    typedef typename std::list<Edge*>::iterator EdgeIterator;
    typedef typename std::list<Edge*>::const_iterator ConstEdgeIterator;



    GraphFace();

    GraphFace(const GraphFace<Vertex,Edge,Face>& face, bool deep = false);

    virtual ~GraphFace();



    void set(const GraphFace<Vertex,Edge,Face>& face, bool deep = false);

    GraphFace<Vertex,Edge,Face>& operator =
        (const GraphFace<Vertex,Edge,Face>& face);



    void insert(Vertex* vertex);

    void insert(Edge* edge);

    void remove(Vertex* vertex);

    void remove(Edge* edge);

    Position numberOfVertices() const;

    Position numberOfEdges() const;


    void setIndex(Index index);

    Index getIndex() const;

    bool getEdges(const Vertex* vertex, Edge*& edge1, Edge*& edge2) const;

    bool getEdge
        (const Vertex* vertex1,
         const Vertex* vertex2,
         Edge*& edge) const;

    Edge* getSimilarEdge(const Edge* edge) const;

    bool substitute(const Vertex* old_vertex, Vertex* new_vertex);

    bool substitute(const Edge* old_edge, Edge* new_edge);



    virtual bool operator == (const Face& face) const;

    virtual bool operator != (const Face& face) const;

    virtual bool operator *= (const Face& face) const;

    Vertex* has(Vertex* vertex) const;

    Edge* has(Edge* edge) const;



    VertexIterator beginVertex();
    ConstVertexIterator beginVertex() const;
    VertexIterator endVertex();
    ConstVertexIterator endVertex() const;
    EdgeIterator beginEdge();
    ConstEdgeIterator beginEdge() const;
    EdgeIterator endEdge();
    ConstEdgeIterator endEdge() const;


    protected:

    /*_ @name Attributes
    */

    /*_ The vertices of the GraphFace
    */
    std::list<Vertex*> vertex_;
    /*_ The edges of the GraphFace
    */
    std::list<Edge*> edge_;
    /* The index of the GraphFace
    */
    Index index_;


  };



  template <typename Vertex, typename Edge, typename Face>
  GraphFace<Vertex,Edge,Face>::GraphFace()
    : vertex_(),
      edge_(),
      index_(-1)
  {
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphFace<Vertex,Edge,Face>::GraphFace
      (const GraphFace<Vertex,Edge,Face>& face, bool deep)
    : vertex_(),
      edge_(),
      index_(face.index_)
  {
    if (deep)
    {
      vertex_ = face.vertex_;
      edge_ = face.edge_;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphFace<Vertex,Edge,Face>::~GraphFace()
  {
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::set
      (const GraphFace<Vertex,Edge,Face>& face, bool deep)
  {
    if (this != &face)
    {
      if (deep)
      {
        vertex_ = face.vertex_;
        edge_ = face.edge_;
      }
      index_ = face.index_;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphFace<Vertex,Edge,Face>& GraphFace<Vertex,Edge,Face>::operator =
      (const GraphFace<Vertex,Edge,Face>& face)
  {
    if (this != &face)
    {
      vertex_ = face.vertex_;
      edge_ = face.edge_;
      index_ = face.index_;
    }
    return *this;
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::insert(Vertex* vertex)
  {
    typename std::list<Vertex*>::iterator v = vertex_.begin();
    bool found = false;
    while ((!found) && (v != vertex_.end()))
    {
      found = (*v == vertex);
      v++;
    }
    if (!found)
    {
      vertex_.push_back(vertex);
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::insert(Edge* edge)
  {
    typename std::list<Edge*>::iterator e = edge_.begin();
    bool found = false;
    while ((!found) && (e != edge_.end()))
    {
      found = (*e == edge);
      e++;
    }
    if (!found)
    {
      edge_.push_back(edge);
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::remove(Vertex* vertex)
  {
    vertex_.remove(vertex);
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::remove(Edge* edge)
  {
    edge_.remove(edge);
  }


  template <typename Vertex, typename Edge, typename Face>
  Position GraphFace<Vertex,Edge,Face>::numberOfVertices() const
  {
    return vertex_.size();
  }


  template <typename Vertex, typename Edge, typename Face>
  Position GraphFace<Vertex,Edge,Face>::numberOfEdges() const
  {
    return edge_.size();
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphFace<Vertex,Edge,Face>::setIndex(Index index)
  {
    index_ = index;
  }


  template <typename Vertex, typename Edge, typename Face>
  Index GraphFace<Vertex,Edge,Face>::getIndex() const
  {
    return index_;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::getEdges
      (const Vertex*  vertex,
       Edge*&         edge1,
       Edge*&         edge2) const
  {
    bool found1 = false;
    bool found2 = false;
    typename std::list<Edge*>::const_iterator e = edge_.begin();
    while ((!found1) && (e != edge_.end()))
    {
      if (((*e)->vertex_[0] == vertex) || ((*e)->vertex_[1] == vertex))
      {
        edge1 = *e;
        found1 = true;
      }
      e++;
    }
    if (found1)
    {
      while ((!found2) && (e != edge_.end()))
      {
        if (((*e)->vertex_[0] == vertex) || ((*e)->vertex_[1] == vertex))
        {
          edge2 = *e;
          found2 = true;
        }
        e++;
      }
    }
    return (found1 && found2);
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::getEdge
      (const Vertex*  vertex1,
       const Vertex*  vertex2,
       Edge*&         edge) const
  {
    typename std::list<Edge*>::const_iterator e = edge_.begin();
    bool found = false;
    while ((!found) && (e != edge_.end()))
    {
      if ((((*e)->vertex_[0] == vertex1) && ((*e)->vertex_[1] == vertex2)) ||
          (((*e)->vertex_[0] == vertex2) && ((*e)->vertex_[1] == vertex1))    )
      {
        edge = *e;
        found = true;
      }
      e++;
    }
    return found;
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphFace<Vertex,Edge,Face>::getSimilarEdge(const Edge* edge) const
  {
    typename std::list<Edge*>::const_iterator e = edge_.begin();
    while (e != edge_.end())
    {
      if (**e *= *edge)
      {
        return *e;
      }
      e++;
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::substitute
      (const Vertex* old_vertex, Vertex* new_vertex)
  {
    typename std::list<Vertex*>::iterator v = vertex_.begin();
    while (v != vertex_.end())
    {
      if (*v == old_vertex)
      {
        *v = new_vertex;
        return true;
      }
      v++;
    }
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::substitute
      (const Edge* old_edge, Edge* new_edge)
  {
    typename std::list<Edge*>::iterator e = edge_.begin();
    while (e != edge_.end())
    {
      if (*e == old_edge)
      {
        *e = new_edge;
        return true;
      }
      e++;
    }
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::operator == (const Face&) const
  {
    return true;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::operator != (const Face&) const
  {
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphFace<Vertex,Edge,Face>::operator *= (const Face&) const
  {
    return true;
  }


  template <typename Vertex, typename Edge, typename Face>
  Vertex* GraphFace<Vertex,Edge,Face>::has(Vertex* vertex) const
  {
    typename std::list<Vertex*>::const_iterator v = vertex_.begin();
    while (v != vertex_.end())
    {
      if (*v == vertex)
      {
        return *v;
      }
      v++;
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphFace<Vertex,Edge,Face>::has(Edge* edge) const
  {
    typename std::list<Edge*>::const_iterator e = edge_.begin();
    while (e != edge_.end())
    {
      if (*e == edge)
      {
        return *e;
      }
      e++;
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::VertexIterator
      GraphFace<Vertex,Edge,Face>::beginVertex()
  {
    return vertex_.begin();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::ConstVertexIterator
      GraphFace<Vertex,Edge,Face>::beginVertex() const
  {
    return vertex_.begin();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::VertexIterator
      GraphFace<Vertex,Edge,Face>::endVertex()
  {
    return vertex_.end();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::ConstVertexIterator
      GraphFace<Vertex,Edge,Face>::endVertex() const
  {
    return vertex_.end();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::EdgeIterator
      GraphFace<Vertex,Edge,Face>::beginEdge()
  {
    return edge_.begin();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::ConstEdgeIterator
      GraphFace<Vertex,Edge,Face>::beginEdge() const
  {
    return edge_.begin();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::EdgeIterator
      GraphFace<Vertex,Edge,Face>::endEdge()
  {
    return edge_.end();
  }


  template <typename Vertex, typename Edge, typename Face>
  typename GraphFace<Vertex,Edge,Face>::ConstEdgeIterator
      GraphFace<Vertex,Edge,Face>::endEdge() const
  {
    return edge_.end();
  }



  template <typename Vertex, typename Edge, typename Face>
  class GraphTriangle
  {
    public:

    friend class GraphVertex<Vertex,Edge,Face>;
    friend class GraphEdge<Vertex,Edge,Face>;


    BALL_CREATE(GraphTriangle)

    
    GraphTriangle();

    GraphTriangle
        (const GraphTriangle<Vertex,Edge,Face>& face, bool deep = false);

    GraphTriangle
        (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
         Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
         Index    index);

    virtual ~GraphTriangle();



    void set(const GraphTriangle<Vertex,Edge,Face>& face, bool deep = false);

    GraphTriangle<Vertex,Edge,Face>& operator =
        (const GraphTriangle<Vertex,Edge,Face>& face);

    void set
        (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
         Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
         Index    index);



    void setVertex(Position i, Vertex* vertex)
      throw(Exception::IndexOverflow);

    Vertex* getVertex(Position i) const
      throw(Exception::IndexOverflow);

    void setEdge(Position i, Edge* edge)
      throw(Exception::IndexOverflow);

    Edge* getEdge(Position i) const
      throw(Exception::IndexOverflow);

    void setIndex(Index index);

    Index getIndex() const;

    bool getEdges(const Vertex* vertex, Edge*& edge1, Edge*& edge2) const;

    bool getEdge
        (const Vertex* vertex1,
         const Vertex* vertex2,
         Edge*& edge) const;

    Index getSimilarEdge(const Edge* edge, Edge*& similar_edge) const;

    Index getRelativeIndex(const Vertex* vertex) const;

    Index getRelativeIndex(const Edge* edge) const;

    Vertex* third(const Vertex* v1, const Vertex* v2) const;

    Edge* third(const Edge* e1, const Edge* e2) const;


    Edge* getOppositeEdge(const Vertex* vertex) const;


    Vertex* getOppositeVertex(const Edge* edge) const;

    bool substitute(const Vertex* old_vertex, Vertex* new_vertex);

    bool substitute(const Edge* old_edge, Edge* new_edge);



    virtual bool operator == (const Face&) const;

    virtual bool operator != (const Face&) const;

    virtual bool operator *= (const Face&) const;

    Vertex* has(Vertex* vertex) const;

    Edge* has(Edge* edge) const;


    protected:

    /*_ The vertices of the GraphTriangle
    */
    Vertex* vertex_[3];
    /*_ The edges of the GraphTriangle
    */
    Edge* edge_[3];
    /* The index of the GraphTriangle
    */
    Index index_;

  };



  template <typename Vertex, typename Edge, typename Face>
  GraphTriangle<Vertex,Edge,Face>::GraphTriangle()
    : index_(-1)
  {
    vertex_[0] = NULL;
    vertex_[1] = NULL;
    vertex_[2] = NULL;
    edge_[0] = NULL;
    edge_[1] = NULL;
    edge_[2] = NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphTriangle<Vertex,Edge,Face>::GraphTriangle
      (const GraphTriangle<Vertex,Edge,Face>& face, bool deep)
    : index_(face.index_)
  {
    if (deep)
    {
      vertex_[0] = face.vertex_[0];
      vertex_[1] = face.vertex_[1];
      vertex_[2] = face.vertex_[2];
      edge_[0] = face.edge_[0];
      edge_[1] = face.edge_[1];
      edge_[2] = face.edge_[2];
    }
    else
    {
      vertex_[0] = NULL;
      vertex_[1] = NULL;
      vertex_[2] = NULL;
      edge_[0] = NULL;
      edge_[1] = NULL;
      edge_[2] = NULL;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphTriangle<Vertex,Edge,Face>::GraphTriangle
      (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
       Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
       Index    index)
    : index_(index)
  {
    vertex_[0] = vertex1;
    vertex_[1] = vertex2;
    vertex_[2] = vertex3;
    edge_[0] = edge1;
    edge_[1] = edge2;
    edge_[2] = edge3;
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphTriangle<Vertex,Edge,Face>::~GraphTriangle()
  {
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphTriangle<Vertex,Edge,Face>::set
      (const GraphTriangle<Vertex,Edge,Face>& face, bool deep)
  {
    if (this != &face)
    {
      if (deep)
      {
        vertex_[0] = face.vertex_[0];
        vertex_[1] = face.vertex_[1];
        vertex_[2] = face.vertex_[2];
        edge_[0] = face.edge_[0];
        edge_[1] = face.edge_[1];
        edge_[2] = face.edge_[2];
      }
      else
      {
        vertex_[0] = NULL;
        vertex_[1] = NULL;
        vertex_[2] = NULL;
        edge_[0] = NULL;
        edge_[1] = NULL;
        edge_[2] = NULL;
      }
      index_ = face.index_;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  GraphTriangle<Vertex,Edge,Face>& GraphTriangle<Vertex,Edge,Face>::operator =
      (const GraphTriangle<Vertex,Edge,Face>& face)
  {
    if (this != &face)
    {
      vertex_[0] = face.vertex_[0];
      vertex_[1] = face.vertex_[1];
      vertex_[2] = face.vertex_[2];
      edge_[0] = face.edge_[0];
      edge_[1] = face.edge_[1];
      edge_[2] = face.edge_[2];
      index_ = face.index_;
    }
    return *this;
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphTriangle<Vertex,Edge,Face>::set
      (Vertex*  vertex1,  Vertex* vertex2, Vertex*  vertex3,
       Edge*    edge1,    Edge*   edge2,   Edge*    edge3,
       Index    index)
  {
    vertex_[0] = vertex1;
    vertex_[1] = vertex2;
    vertex_[2] = vertex3;
    edge_[0] = edge1;
    edge_[1] = edge2;
    edge_[2] = edge3;
    index_ = index;
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphTriangle<Vertex,Edge,Face>::setVertex(Position i, Vertex* vertex)
    throw(Exception::IndexOverflow)
  {
    if (i > 2)
    {
      throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
    }
    else
    {
      vertex_[i] = vertex;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  Vertex* GraphTriangle<Vertex,Edge,Face>::getVertex(Position i) const
    throw(Exception::IndexOverflow)
  {
    if (i > 2)
    {
      throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
    }
    else
    {
      return vertex_[i];
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphTriangle<Vertex,Edge,Face>::setEdge(Position i, Edge* edge)
    throw(Exception::IndexOverflow)
  {
    if (i > 2)
    {
      throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
    }
    else
    {
      edge_[i] = edge;
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphTriangle<Vertex,Edge,Face>::getEdge(Position i) const
    throw(Exception::IndexOverflow)
  {
    if (i > 2)
    {
      throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
    }
    else
    {
      return edge_[i];
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  void GraphTriangle<Vertex,Edge,Face>::setIndex(Index index)
  {
    index_ = index;
  }


  template <typename Vertex, typename Edge, typename Face>
  Index GraphTriangle<Vertex,Edge,Face>::getIndex() const
  {
    return index_;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::getEdges
      (const Vertex*  vertex,
       Edge*&         edge1,
       Edge*&         edge2) const
  {
    Position i = 0;
    bool found1 = false;
    bool found2 = false;
    while ((!found1) && (i < 3))
    {
      if (edge_[i] != NULL)
      {
        if ((edge_[i]->vertex_[0] == vertex) ||
            (edge_[i]->vertex_[1] == vertex)    )
        {
          edge1 = edge_[i];
          found1 = true;
        }
      }
      i++;
    }
    if (found1)
    {
      while ((!found2) && (i < 3))
      {
        if (edge_[i] != NULL)
        {
          if ((edge_[i]->vertex_[0] == vertex) ||
              (edge_[i]->vertex_[1] == vertex)    )
          {
            edge2 = edge_[i];
            found2 = true;
          }
        }
        i++;
      }
    }
    return (found1 && found2);
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::getEdge
      (const Vertex*  vertex1,
       const Vertex*  vertex2,
       Edge*&         edge) const
  {
    Position i = 0;
    bool found = false;
    while ((!found) && (i < 3))
    {
      if (edge_[i] != NULL)
      {
        if (((edge_[i]->vertex_[0] == vertex1) &&
             (edge_[i]->vertex_[1] == vertex2)    ) ||
            ((edge_[i]->vertex_[0] == vertex2) &&
             (edge_[i]->vertex_[1] == vertex1)    )     )
        {
          edge = edge_[i];
          found = true;
        }
      }
      i++;
    }
    return found;
  }


  template <typename Vertex, typename Edge, typename Face>
  Index GraphTriangle<Vertex,Edge,Face>::getSimilarEdge
      (const Edge* edge, Edge*& similar_edge) const
  {
    if (*edge_[0] *= *edge)
    {
      similar_edge = edge_[0];
      return 0;
    }
    if (*edge_[1] *= *edge)
    {
      similar_edge = edge_[1];
      return 1;
    }
    if (*edge_[2] *= *edge)
    {
      similar_edge = edge_[2];
      return 2;
    }
    similar_edge = NULL;
    return -1;
  }


  template <typename Vertex, typename Edge, typename Face>
  Index GraphTriangle<Vertex,Edge,Face>::getRelativeIndex
      (const Vertex* vertex) const
  {
    for (Position i = 0; i < 3; i++)
    {
      if (vertex_[i] == vertex)
      {
        return i;
      }
    }
    return -1;
  }


  template <typename Vertex, typename Edge, typename Face>
  Index GraphTriangle<Vertex,Edge,Face>::getRelativeIndex
      (const Edge* edge) const
  {
    for (Position i = 0; i < 3; i++)
    {
      if (edge_[i] == edge)
      {
        return i;
      }
    }
    return -1;
  }


  template <typename Vertex, typename Edge, typename Face>
  Vertex* GraphTriangle<Vertex,Edge,Face>::third
      (const Vertex* v1, const Vertex* v2) const
  {
    if ((vertex_[0] == v1) || (vertex_[0] == v2))
    {
      if ((vertex_[1] == v1) || (vertex_[1] == v2))
      {
        return vertex_[2];
      }
      else
      {
        return vertex_[1];
      }
    }
    else
    {
      return vertex_[0];
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphTriangle<Vertex,Edge,Face>::third
      (const Edge* e1, const Edge* e2) const
  {
    if ((edge_[0] == e1) || (edge_[0] == e2))
    {
      if ((edge_[1] == e1) || (edge_[1] == e2))
      {
        return edge_[2];
      }
      else
      {
        return edge_[1];
      }
    }
    else
    {
      return edge_[0];
    }
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphTriangle<Vertex,Edge,Face>::getOppositeEdge
      (const Vertex* vertex) const
  {
    for (Position i = 0; i < 3; i++)
    {
      if ((edge_[i]->vertex_[0] != vertex) &&
          (edge_[i]->vertex_[1] != vertex)    )
      {
        return edge_[i];
      }
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  Vertex* GraphTriangle<Vertex,Edge,Face>::getOppositeVertex
      (const Edge* edge) const
  {
    for (Position i = 0; i < 3; i++)
    {
      if ((vertex_[i] != edge->vertex_[0]) &&
          (vertex_[i] != edge->vertex_[1])    )
      {
        return vertex_[i];
      }
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::substitute
      (const Vertex* old_vertex, Vertex* new_vertex)
  {
    for (Position i = 0; i < 3; i++)
    {
      if (vertex_[i] == old_vertex)
      {
        vertex_[i] = new_vertex;
        return true;
      }
    }
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::substitute
      (const Edge* old_edge, Edge* new_edge)
  {
    for (Position i = 0; i < 3; i++)
    {
      if (edge_[i] == old_edge)
      {
        edge_[i] = new_edge;
        return true;
      }
    }
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::operator == (const Face&) const
  {
    return true;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::operator != (const Face&) const
  {
    return false;
  }


  template <typename Vertex, typename Edge, typename Face>
  bool GraphTriangle<Vertex,Edge,Face>::operator *= (const Face&) const
  {
    return true;
  }


  template <typename Vertex, typename Edge, typename Face>
  Vertex* GraphTriangle<Vertex,Edge,Face>::has(Vertex* vertex) const
  {
    if (vertex_[0] == vertex)
    {
      return vertex_[0];
    }
    if (vertex_[1] == vertex)
    {
      return vertex_[1];
    }
    if (vertex_[2] == vertex)
    {
      return vertex_[2];
    }
    return NULL;
  }


  template <typename Vertex, typename Edge, typename Face>
  Edge* GraphTriangle<Vertex,Edge,Face>::has(Edge* edge) const
  {
    if (edge_[0] == edge)
    {
      return edge_[0];
    }
    if (edge_[1] == edge)
    {
      return edge_[1];
    }
    if (edge_[2] == edge)
    {
      return edge_[2];
    }
    return NULL;
  }


} // namespace BALL

#endif // BALL_STRUCTURE_RSFACE_H