BALL: graphFace.h Source File

00001 // -*- Mode: C++; tab-width: 2; -*-
00002 // vi: set ts=2:
00003 //
00004 
00005 #ifndef BALL_STRUCTURE_GRAPHFACE_H
00006 #define BALL_STRUCTURE_GRAPHFACE_H
00007 
00008 #ifndef BALL_COMMON_H
00009 # include <BALL/common.h>
00010 #endif
00011 
00012 #include <list>
00013 #include <vector>
00014 
00015 namespace BALL
00016 {
00017 
00018   template <typename Vertex, typename Edge, typename Face>
00019   class GraphVertex;
00020 
00021   template <typename Vertex, typename Edge, typename Face>
00022   class GraphEdge;
00023 
00027   template <typename Vertex, typename Edge, typename Face>
00028   class GraphFace
00029   {
00030     public:
00031 
00038     friend class GraphVertex<Vertex,Edge,Face>;
00039     friend class GraphEdge<Vertex,Edge,Face>;
00040 
00041     BALL_CREATE(GraphFace)
00042 
00043     
00046 
00047     typedef typename std::list<Vertex*>::iterator VertexIterator;
00048     typedef typename std::list<Vertex*>::const_iterator ConstVertexIterator;
00049     typedef typename std::list<Edge*>::iterator EdgeIterator;
00050     typedef typename std::list<Edge*>::const_iterator ConstEdgeIterator;
00051 
00053 
00056 
00060     GraphFace();
00061 
00069     GraphFace(const GraphFace<Vertex,Edge,Face>& face, bool deep = false);
00070 
00074     virtual ~GraphFace();
00075 
00077 
00080 
00087     void set(const GraphFace<Vertex,Edge,Face>& face, bool deep = false);
00088 
00094     GraphFace<Vertex,Edge,Face>& operator =
00095         (const GraphFace<Vertex,Edge,Face>& face);
00096 
00098 
00101 
00105     void insert(Vertex* vertex);
00106 
00110     void insert(Edge* edge);
00111 
00115     void remove(Vertex* vertex);
00116 
00120     void remove(Edge* edge);
00121 
00125     Position numberOfVertices() const;
00126 
00130     Position numberOfEdges() const;
00131 
00132 
00136     void setIndex(Index index);
00137 
00141     Index getIndex() const;
00142 
00150     bool getEdges(const Vertex* vertex, Edge*& edge1, Edge*& edge2) const;
00151 
00159     bool getEdge
00160         (const Vertex* vertex1,
00161          const Vertex* vertex2,
00162          Edge*& edge) const;
00163 
00169     Edge* getSimilarEdge(const Edge* edge) const;
00170 
00177     bool substitute(const Vertex* old_vertex, Vertex* new_vertex);
00178 
00185     bool substitute(const Edge* old_edge, Edge* new_edge);
00186 
00188 
00191 
00195     virtual bool operator == (const Face& face) const;
00196 
00200     virtual bool operator != (const Face& face) const;
00201 
00205     virtual bool operator *= (const Face& face) const;
00206 
00212     Vertex* has(Vertex* vertex) const;
00213 
00218     Edge* has(Edge* edge) const;
00219 
00221 
00224 
00225     VertexIterator beginVertex();
00226     ConstVertexIterator beginVertex() const;
00227     VertexIterator endVertex();
00228     ConstVertexIterator endVertex() const;
00229     EdgeIterator beginEdge();
00230     ConstEdgeIterator beginEdge() const;
00231     EdgeIterator endEdge();
00232     ConstEdgeIterator endEdge() const;
00233 
00235 
00236     protected:
00237 
00238     /*_ @name Attributes
00239     */
00241 
00242     /*_ The vertices of the GraphFace
00243     */
00244     std::list<Vertex*> vertex_;
00245     /*_ The edges of the GraphFace
00246     */
00247     std::list<Edge*> edge_;
00248     /* The index of the GraphFace
00249     */
00250     Index index_;
00251 
00253 
00254   };
00255 
00256 
00257 
00258   template <typename Vertex, typename Edge, typename Face>
00259   GraphFace<Vertex,Edge,Face>::GraphFace()
00260     : vertex_(),
00261       edge_(),
00262       index_(-1)
00263   {
00264   }
00265 
00266 
00267   template <typename Vertex, typename Edge, typename Face>
00268   GraphFace<Vertex,Edge,Face>::GraphFace
00269       (const GraphFace<Vertex,Edge,Face>& face, bool deep)
00270     : vertex_(),
00271       edge_(),
00272       index_(face.index_)
00273   {
00274     if (deep)
00275     {
00276       vertex_ = face.vertex_;
00277       edge_ = face.edge_;
00278     }
00279   }
00280 
00281 
00282   template <typename Vertex, typename Edge, typename Face>
00283   GraphFace<Vertex,Edge,Face>::~GraphFace()
00284   {
00285   }
00286 
00287 
00288   template <typename Vertex, typename Edge, typename Face>
00289   void GraphFace<Vertex,Edge,Face>::set
00290       (const GraphFace<Vertex,Edge,Face>& face, bool deep)
00291   {
00292     if (this != &face)
00293     {
00294       if (deep)
00295       {
00296         vertex_ = face.vertex_;
00297         edge_ = face.edge_;
00298       }
00299       index_ = face.index_;
00300     }
00301   }
00302 
00303 
00304   template <typename Vertex, typename Edge, typename Face>
00305   GraphFace<Vertex,Edge,Face>& GraphFace<Vertex,Edge,Face>::operator =
00306       (const GraphFace<Vertex,Edge,Face>& face)
00307   {
00308     if (this != &face)
00309     {
00310       vertex_ = face.vertex_;
00311       edge_ = face.edge_;
00312       index_ = face.index_;
00313     }
00314     return *this;
00315   }
00316 
00317 
00318   template <typename Vertex, typename Edge, typename Face>
00319   void GraphFace<Vertex,Edge,Face>::insert(Vertex* vertex)
00320   {
00321     typename std::list<Vertex*>::iterator v = vertex_.begin();
00322     bool found = false;
00323     while ((!found) && (v != vertex_.end()))
00324     {
00325       found = (*v == vertex);
00326       v++;
00327     }
00328     if (!found)
00329     {
00330       vertex_.push_back(vertex);
00331     }
00332   }
00333 
00334 
00335   template <typename Vertex, typename Edge, typename Face>
00336   void GraphFace<Vertex,Edge,Face>::insert(Edge* edge)
00337   {
00338     typename std::list<Edge*>::iterator e = edge_.begin();
00339     bool found = false;
00340     while ((!found) && (e != edge_.end()))
00341     {
00342       found = (*e == edge);
00343       e++;
00344     }
00345     if (!found)
00346     {
00347       edge_.push_back(edge);
00348     }
00349   }
00350 
00351 
00352   template <typename Vertex, typename Edge, typename Face>
00353   void GraphFace<Vertex,Edge,Face>::remove(Vertex* vertex)
00354   {
00355     vertex_.remove(vertex);
00356   }
00357 
00358 
00359   template <typename Vertex, typename Edge, typename Face>
00360   void GraphFace<Vertex,Edge,Face>::remove(Edge* edge)
00361   {
00362     edge_.remove(edge);
00363   }
00364 
00365 
00366   template <typename Vertex, typename Edge, typename Face>
00367   Position GraphFace<Vertex,Edge,Face>::numberOfVertices() const
00368   {
00369     return vertex_.size();
00370   }
00371 
00372 
00373   template <typename Vertex, typename Edge, typename Face>
00374   Position GraphFace<Vertex,Edge,Face>::numberOfEdges() const
00375   {
00376     return edge_.size();
00377   }
00378 
00379 
00380   template <typename Vertex, typename Edge, typename Face>
00381   void GraphFace<Vertex,Edge,Face>::setIndex(Index index)
00382   {
00383     index_ = index;
00384   }
00385 
00386 
00387   template <typename Vertex, typename Edge, typename Face>
00388   Index GraphFace<Vertex,Edge,Face>::getIndex() const
00389   {
00390     return index_;
00391   }
00392 
00393 
00394   template <typename Vertex, typename Edge, typename Face>
00395   bool GraphFace<Vertex,Edge,Face>::getEdges
00396       (const Vertex*  vertex,
00397        Edge*&         edge1,
00398        Edge*&         edge2) const
00399   {
00400     bool found1 = false;
00401     bool found2 = false;
00402     typename std::list<Edge*>::const_iterator e = edge_.begin();
00403     while ((!found1) && (e != edge_.end()))
00404     {
00405       if (((*e)->vertex_[0] == vertex) || ((*e)->vertex_[1] == vertex))
00406       {
00407         edge1 = *e;
00408         found1 = true;
00409       }
00410       e++;
00411     }
00412     if (found1)
00413     {
00414       while ((!found2) && (e != edge_.end()))
00415       {
00416         if (((*e)->vertex_[0] == vertex) || ((*e)->vertex_[1] == vertex))
00417         {
00418           edge2 = *e;
00419           found2 = true;
00420         }
00421         e++;
00422       }
00423     }
00424     return (found1 && found2);
00425   }
00426 
00427 
00428   template <typename Vertex, typename Edge, typename Face>
00429   bool GraphFace<Vertex,Edge,Face>::getEdge
00430       (const Vertex*  vertex1,
00431        const Vertex*  vertex2,
00432        Edge*&         edge) const
00433   {
00434     typename std::list<Edge*>::const_iterator e = edge_.begin();
00435     bool found = false;
00436     while ((!found) && (e != edge_.end()))
00437     {
00438       if ((((*e)->vertex_[0] == vertex1) && ((*e)->vertex_[1] == vertex2)) ||
00439           (((*e)->vertex_[0] == vertex2) && ((*e)->vertex_[1] == vertex1))    )
00440       {
00441         edge = *e;
00442         found = true;
00443       }
00444       e++;
00445     }
00446     return found;
00447   }
00448 
00449 
00450   template <typename Vertex, typename Edge, typename Face>
00451   Edge* GraphFace<Vertex,Edge,Face>::getSimilarEdge(const Edge* edge) const
00452   {
00453     typename std::list<Edge*>::const_iterator e = edge_.begin();
00454     while (e != edge_.end())
00455     {
00456       if (**e *= *edge)
00457       {
00458         return *e;
00459       }
00460       e++;
00461     }
00462     return NULL;
00463   }
00464 
00465 
00466   template <typename Vertex, typename Edge, typename Face>
00467   bool GraphFace<Vertex,Edge,Face>::substitute
00468       (const Vertex* old_vertex, Vertex* new_vertex)
00469   {
00470     typename std::list<Vertex*>::iterator v = vertex_.begin();
00471     while (v != vertex_.end())
00472     {
00473       if (*v == old_vertex)
00474       {
00475         *v = new_vertex;
00476         return true;
00477       }
00478       v++;
00479     }
00480     return false;
00481   }
00482 
00483 
00484   template <typename Vertex, typename Edge, typename Face>
00485   bool GraphFace<Vertex,Edge,Face>::substitute
00486       (const Edge* old_edge, Edge* new_edge)
00487   {
00488     typename std::list<Edge*>::iterator e = edge_.begin();
00489     while (e != edge_.end())
00490     {
00491       if (*e == old_edge)
00492       {
00493         *e = new_edge;
00494         return true;
00495       }
00496       e++;
00497     }
00498     return false;
00499   }
00500 
00501 
00502   template <typename Vertex, typename Edge, typename Face>
00503   bool GraphFace<Vertex,Edge,Face>::operator == (const Face&) const
00504   {
00505     return true;
00506   }
00507 
00508 
00509   template <typename Vertex, typename Edge, typename Face>
00510   bool GraphFace<Vertex,Edge,Face>::operator != (const Face&) const
00511   {
00512     return false;
00513   }
00514 
00515 
00516   template <typename Vertex, typename Edge, typename Face>
00517   bool GraphFace<Vertex,Edge,Face>::operator *= (const Face&) const
00518   {
00519     return true;
00520   }
00521 
00522 
00523   template <typename Vertex, typename Edge, typename Face>
00524   Vertex* GraphFace<Vertex,Edge,Face>::has(Vertex* vertex) const
00525   {
00526     typename std::list<Vertex*>::const_iterator v = vertex_.begin();
00527     while (v != vertex_.end())
00528     {
00529       if (*v == vertex)
00530       {
00531         return *v;
00532       }
00533       v++;
00534     }
00535     return NULL;
00536   }
00537 
00538 
00539   template <typename Vertex, typename Edge, typename Face>
00540   Edge* GraphFace<Vertex,Edge,Face>::has(Edge* edge) const
00541   {
00542     typename std::list<Edge*>::const_iterator e = edge_.begin();
00543     while (e != edge_.end())
00544     {
00545       if (*e == edge)
00546       {
00547         return *e;
00548       }
00549       e++;
00550     }
00551     return NULL;
00552   }
00553 
00554 
00555   template <typename Vertex, typename Edge, typename Face>
00556   typename GraphFace<Vertex,Edge,Face>::VertexIterator
00557       GraphFace<Vertex,Edge,Face>::beginVertex()
00558   {
00559     return vertex_.begin();
00560   }
00561 
00562 
00563   template <typename Vertex, typename Edge, typename Face>
00564   typename GraphFace<Vertex,Edge,Face>::ConstVertexIterator
00565       GraphFace<Vertex,Edge,Face>::beginVertex() const
00566   {
00567     return vertex_.begin();
00568   }
00569 
00570 
00571   template <typename Vertex, typename Edge, typename Face>
00572   typename GraphFace<Vertex,Edge,Face>::VertexIterator
00573       GraphFace<Vertex,Edge,Face>::endVertex()
00574   {
00575     return vertex_.end();
00576   }
00577 
00578 
00579   template <typename Vertex, typename Edge, typename Face>
00580   typename GraphFace<Vertex,Edge,Face>::ConstVertexIterator
00581       GraphFace<Vertex,Edge,Face>::endVertex() const
00582   {
00583     return vertex_.end();
00584   }
00585 
00586 
00587   template <typename Vertex, typename Edge, typename Face>
00588   typename GraphFace<Vertex,Edge,Face>::EdgeIterator
00589       GraphFace<Vertex,Edge,Face>::beginEdge()
00590   {
00591     return edge_.begin();
00592   }
00593 
00594 
00595   template <typename Vertex, typename Edge, typename Face>
00596   typename GraphFace<Vertex,Edge,Face>::ConstEdgeIterator
00597       GraphFace<Vertex,Edge,Face>::beginEdge() const
00598   {
00599     return edge_.begin();
00600   }
00601 
00602 
00603   template <typename Vertex, typename Edge, typename Face>
00604   typename GraphFace<Vertex,Edge,Face>::EdgeIterator
00605       GraphFace<Vertex,Edge,Face>::endEdge()
00606   {
00607     return edge_.end();
00608   }
00609 
00610 
00611   template <typename Vertex, typename Edge, typename Face>
00612   typename GraphFace<Vertex,Edge,Face>::ConstEdgeIterator
00613       GraphFace<Vertex,Edge,Face>::endEdge() const
00614   {
00615     return edge_.end();
00616   }
00617 
00618 
00619 
00623   template <typename Vertex, typename Edge, typename Face>
00624   class GraphTriangle
00625   {
00626     public:
00627 
00634     friend class GraphVertex<Vertex,Edge,Face>;
00635     friend class GraphEdge<Vertex,Edge,Face>;
00636 
00640 
00641     BALL_CREATE(GraphTriangle)
00642 
00643     
00646     GraphTriangle();
00647 
00655     GraphTriangle
00656         (const GraphTriangle<Vertex,Edge,Face>& face, bool deep = false);
00657 
00668     GraphTriangle
00669         (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
00670          Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
00671          Index    index);
00672 
00676     virtual ~GraphTriangle();
00677 
00679 
00682 
00690     void set(const GraphTriangle<Vertex,Edge,Face>& face, bool deep = false);
00691 
00697     GraphTriangle<Vertex,Edge,Face>& operator =
00698         (const GraphTriangle<Vertex,Edge,Face>& face);
00699 
00709     void set
00710         (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
00711          Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
00712          Index    index);
00713 
00715 
00718 
00724     void setVertex(Position i, Vertex* vertex)
00725       throw(Exception::IndexOverflow);
00726 
00733     Vertex* getVertex(Position i) const
00734       throw(Exception::IndexOverflow);
00735 
00741     void setEdge(Position i, Edge* edge)
00742       throw(Exception::IndexOverflow);
00743 
00749     Edge* getEdge(Position i) const
00750       throw(Exception::IndexOverflow);
00751 
00755     void setIndex(Index index);
00756 
00760     Index getIndex() const;
00761 
00769     bool getEdges(const Vertex* vertex, Edge*& edge1, Edge*& edge2) const;
00770 
00779     bool getEdge
00780         (const Vertex* vertex1,
00781          const Vertex* vertex2,
00782          Edge*& edge) const;
00783 
00791     Index getSimilarEdge(const Edge* edge, Edge*& similar_edge) const;
00792 
00796     Index getRelativeIndex(const Vertex* vertex) const;
00797 
00801     Index getRelativeIndex(const Edge* edge) const;
00802 
00808     Vertex* third(const Vertex* v1, const Vertex* v2) const;
00809 
00815     Edge* third(const Edge* e1, const Edge* e2) const;
00816 
00817 
00823     Edge* getOppositeEdge(const Vertex* vertex) const;
00824 
00825 
00831     Vertex* getOppositeVertex(const Edge* edge) const;
00832 
00839     bool substitute(const Vertex* old_vertex, Vertex* new_vertex);
00840 
00847     bool substitute(const Edge* old_edge, Edge* new_edge);
00848 
00850 
00853 
00857     virtual bool operator == (const Face&) const;
00858 
00862     virtual bool operator != (const Face&) const;
00863 
00867     virtual bool operator *= (const Face&) const;
00868 
00874     Vertex* has(Vertex* vertex) const;
00875 
00880     Edge* has(Edge* edge) const;
00881 
00883 
00884     protected:
00885 
00886     /*_ The vertices of the GraphTriangle
00887     */
00888     Vertex* vertex_[3];
00889     /*_ The edges of the GraphTriangle
00890     */
00891     Edge* edge_[3];
00892     /* The index of the GraphTriangle
00893     */
00894     Index index_;
00895 
00896   };
00897 
00898 
00899 
00900   template <typename Vertex, typename Edge, typename Face>
00901   GraphTriangle<Vertex,Edge,Face>::GraphTriangle()
00902     : index_(-1)
00903   {
00904     vertex_[0] = NULL;
00905     vertex_[1] = NULL;
00906     vertex_[2] = NULL;
00907     edge_[0] = NULL;
00908     edge_[1] = NULL;
00909     edge_[2] = NULL;
00910   }
00911 
00912 
00913   template <typename Vertex, typename Edge, typename Face>
00914   GraphTriangle<Vertex,Edge,Face>::GraphTriangle
00915       (const GraphTriangle<Vertex,Edge,Face>& face, bool deep)
00916     : index_(face.index_)
00917   {
00918     if (deep)
00919     {
00920       vertex_[0] = face.vertex_[0];
00921       vertex_[1] = face.vertex_[1];
00922       vertex_[2] = face.vertex_[2];
00923       edge_[0] = face.edge_[0];
00924       edge_[1] = face.edge_[1];
00925       edge_[2] = face.edge_[2];
00926     }
00927     else
00928     {
00929       vertex_[0] = NULL;
00930       vertex_[1] = NULL;
00931       vertex_[2] = NULL;
00932       edge_[0] = NULL;
00933       edge_[1] = NULL;
00934       edge_[2] = NULL;
00935     }
00936   }
00937 
00938 
00939   template <typename Vertex, typename Edge, typename Face>
00940   GraphTriangle<Vertex,Edge,Face>::GraphTriangle
00941       (Vertex*  vertex1,  Vertex* vertex2,  Vertex* vertex3,
00942        Edge*    edge1,    Edge*   edge2,    Edge*   edge3,
00943        Index    index)
00944     : index_(index)
00945   {
00946     vertex_[0] = vertex1;
00947     vertex_[1] = vertex2;
00948     vertex_[2] = vertex3;
00949     edge_[0] = edge1;
00950     edge_[1] = edge2;
00951     edge_[2] = edge3;
00952   }
00953 
00954 
00955   template <typename Vertex, typename Edge, typename Face>
00956   GraphTriangle<Vertex,Edge,Face>::~GraphTriangle()
00957   {
00958   }
00959 
00960 
00961   template <typename Vertex, typename Edge, typename Face>
00962   void GraphTriangle<Vertex,Edge,Face>::set
00963       (const GraphTriangle<Vertex,Edge,Face>& face, bool deep)
00964   {
00965     if (this != &face)
00966     {
00967       if (deep)
00968       {
00969         vertex_[0] = face.vertex_[0];
00970         vertex_[1] = face.vertex_[1];
00971         vertex_[2] = face.vertex_[2];
00972         edge_[0] = face.edge_[0];
00973         edge_[1] = face.edge_[1];
00974         edge_[2] = face.edge_[2];
00975       }
00976       else
00977       {
00978         vertex_[0] = NULL;
00979         vertex_[1] = NULL;
00980         vertex_[2] = NULL;
00981         edge_[0] = NULL;
00982         edge_[1] = NULL;
00983         edge_[2] = NULL;
00984       }
00985       index_ = face.index_;
00986     }
00987   }
00988 
00989 
00990   template <typename Vertex, typename Edge, typename Face>
00991   GraphTriangle<Vertex,Edge,Face>& GraphTriangle<Vertex,Edge,Face>::operator =
00992       (const GraphTriangle<Vertex,Edge,Face>& face)
00993   {
00994     if (this != &face)
00995     {
00996       vertex_[0] = face.vertex_[0];
00997       vertex_[1] = face.vertex_[1];
00998       vertex_[2] = face.vertex_[2];
00999       edge_[0] = face.edge_[0];
01000       edge_[1] = face.edge_[1];
01001       edge_[2] = face.edge_[2];
01002       index_ = face.index_;
01003     }
01004     return *this;
01005   }
01006 
01007 
01008   template <typename Vertex, typename Edge, typename Face>
01009   void GraphTriangle<Vertex,Edge,Face>::set
01010       (Vertex*  vertex1,  Vertex* vertex2, Vertex*  vertex3,
01011        Edge*    edge1,    Edge*   edge2,   Edge*    edge3,
01012        Index    index)
01013   {
01014     vertex_[0] = vertex1;
01015     vertex_[1] = vertex2;
01016     vertex_[2] = vertex3;
01017     edge_[0] = edge1;
01018     edge_[1] = edge2;
01019     edge_[2] = edge3;
01020     index_ = index;
01021   }
01022 
01023 
01024   template <typename Vertex, typename Edge, typename Face>
01025   void GraphTriangle<Vertex,Edge,Face>::setVertex(Position i, Vertex* vertex)
01026     throw(Exception::IndexOverflow)
01027   {
01028     if (i > 2)
01029     {
01030       throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
01031     }
01032     else
01033     {
01034       vertex_[i] = vertex;
01035     }
01036   }
01037 
01038 
01039   template <typename Vertex, typename Edge, typename Face>
01040   Vertex* GraphTriangle<Vertex,Edge,Face>::getVertex(Position i) const
01041     throw(Exception::IndexOverflow)
01042   {
01043     if (i > 2)
01044     {
01045       throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
01046     }
01047     else
01048     {
01049       return vertex_[i];
01050     }
01051   }
01052 
01053 
01054   template <typename Vertex, typename Edge, typename Face>
01055   void GraphTriangle<Vertex,Edge,Face>::setEdge(Position i, Edge* edge)
01056     throw(Exception::IndexOverflow)
01057   {
01058     if (i > 2)
01059     {
01060       throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
01061     }
01062     else
01063     {
01064       edge_[i] = edge;
01065     }
01066   }
01067 
01068 
01069   template <typename Vertex, typename Edge, typename Face>
01070   Edge* GraphTriangle<Vertex,Edge,Face>::getEdge(Position i) const
01071     throw(Exception::IndexOverflow)
01072   {
01073     if (i > 2)
01074     {
01075       throw Exception::IndexOverflow(__FILE__,__LINE__,i,2);
01076     }
01077     else
01078     {
01079       return edge_[i];
01080     }
01081   }
01082 
01083 
01084   template <typename Vertex, typename Edge, typename Face>
01085   void GraphTriangle<Vertex,Edge,Face>::setIndex(Index index)
01086   {
01087     index_ = index;
01088   }
01089 
01090 
01091   template <typename Vertex, typename Edge, typename Face>
01092   Index GraphTriangle<Vertex,Edge,Face>::getIndex() const
01093   {
01094     return index_;
01095   }
01096 
01097 
01098   template <typename Vertex, typename Edge, typename Face>
01099   bool GraphTriangle<Vertex,Edge,Face>::getEdges
01100       (const Vertex*  vertex,
01101        Edge*&         edge1,
01102        Edge*&         edge2) const
01103   {
01104     Position i = 0;
01105     bool found1 = false;
01106     bool found2 = false;
01107     while ((!found1) && (i < 3))
01108     {
01109       if (edge_[i] != NULL)
01110       {
01111         if ((edge_[i]->vertex_[0] == vertex) ||
01112             (edge_[i]->vertex_[1] == vertex)    )
01113         {
01114           edge1 = edge_[i];
01115           found1 = true;
01116         }
01117       }
01118       i++;
01119     }
01120     if (found1)
01121     {
01122       while ((!found2) && (i < 3))
01123       {
01124         if (edge_[i] != NULL)
01125         {
01126           if ((edge_[i]->vertex_[0] == vertex) ||
01127               (edge_[i]->vertex_[1] == vertex)    )
01128           {
01129             edge2 = edge_[i];
01130             found2 = true;
01131           }
01132         }
01133         i++;
01134       }
01135     }
01136     return (found1 && found2);
01137   }
01138 
01139 
01140   template <typename Vertex, typename Edge, typename Face>
01141   bool GraphTriangle<Vertex,Edge,Face>::getEdge
01142       (const Vertex*  vertex1,
01143        const Vertex*  vertex2,
01144        Edge*&         edge) const
01145   {
01146     Position i = 0;
01147     bool found = false;
01148     while ((!found) && (i < 3))
01149     {
01150       if (edge_[i] != NULL)
01151       {
01152         if (((edge_[i]->vertex_[0] == vertex1) &&
01153              (edge_[i]->vertex_[1] == vertex2)    ) ||
01154             ((edge_[i]->vertex_[0] == vertex2) &&
01155              (edge_[i]->vertex_[1] == vertex1)    )     )
01156         {
01157           edge = edge_[i];
01158           found = true;
01159         }
01160       }
01161       i++;
01162     }
01163     return found;
01164   }
01165 
01166 
01167   template <typename Vertex, typename Edge, typename Face>
01168   Index GraphTriangle<Vertex,Edge,Face>::getSimilarEdge
01169       (const Edge* edge, Edge*& similar_edge) const
01170   {
01171     if (*edge_[0] *= *edge)
01172     {
01173       similar_edge = edge_[0];
01174       return 0;
01175     }
01176     if (*edge_[1] *= *edge)
01177     {
01178       similar_edge = edge_[1];
01179       return 1;
01180     }
01181     if (*edge_[2] *= *edge)
01182     {
01183       similar_edge = edge_[2];
01184       return 2;
01185     }
01186     similar_edge = NULL;
01187     return -1;
01188   }
01189 
01190 
01191   template <typename Vertex, typename Edge, typename Face>
01192   Index GraphTriangle<Vertex,Edge,Face>::getRelativeIndex
01193       (const Vertex* vertex) const
01194   {
01195     for (Position i = 0; i < 3; i++)
01196     {
01197       if (vertex_[i] == vertex)
01198       {
01199         return i;
01200       }
01201     }
01202     return -1;
01203   }
01204 
01205 
01206   template <typename Vertex, typename Edge, typename Face>
01207   Index GraphTriangle<Vertex,Edge,Face>::getRelativeIndex
01208       (const Edge* edge) const
01209   {
01210     for (Position i = 0; i < 3; i++)
01211     {
01212       if (edge_[i] == edge)
01213       {
01214         return i;
01215       }
01216     }
01217     return -1;
01218   }
01219 
01220 
01221   template <typename Vertex, typename Edge, typename Face>
01222   Vertex* GraphTriangle<Vertex,Edge,Face>::third
01223       (const Vertex* v1, const Vertex* v2) const
01224   {
01225     if ((vertex_[0] == v1) || (vertex_[0] == v2))
01226     {
01227       if ((vertex_[1] == v1) || (vertex_[1] == v2))
01228       {
01229         return vertex_[2];
01230       }
01231       else
01232       {
01233         return vertex_[1];
01234       }
01235     }
01236     else
01237     {
01238       return vertex_[0];
01239     }
01240   }
01241 
01242 
01243   template <typename Vertex, typename Edge, typename Face>
01244   Edge* GraphTriangle<Vertex,Edge,Face>::third
01245       (const Edge* e1, const Edge* e2) const
01246   {
01247     if ((edge_[0] == e1) || (edge_[0] == e2))
01248     {
01249       if ((edge_[1] == e1) || (edge_[1] == e2))
01250       {
01251         return edge_[2];
01252       }
01253       else
01254       {
01255         return edge_[1];
01256       }
01257     }
01258     else
01259     {
01260       return edge_[0];
01261     }
01262   }
01263 
01264 
01265   template <typename Vertex, typename Edge, typename Face>
01266   Edge* GraphTriangle<Vertex,Edge,Face>::getOppositeEdge
01267       (const Vertex* vertex) const
01268   {
01269     for (Position i = 0; i < 3; i++)
01270     {
01271       if ((edge_[i]->vertex_[0] != vertex) &&
01272           (edge_[i]->vertex_[1] != vertex)    )
01273       {
01274         return edge_[i];
01275       }
01276     }
01277     return NULL;
01278   }
01279 
01280 
01281   template <typename Vertex, typename Edge, typename Face>
01282   Vertex* GraphTriangle<Vertex,Edge,Face>::getOppositeVertex
01283       (const Edge* edge) const
01284   {
01285     for (Position i = 0; i < 3; i++)
01286     {
01287       if ((vertex_[i] != edge->vertex_[0]) &&
01288           (vertex_[i] != edge->vertex_[1])    )
01289       {
01290         return vertex_[i];
01291       }
01292     }
01293     return NULL;
01294   }
01295 
01296 
01297   template <typename Vertex, typename Edge, typename Face>
01298   bool GraphTriangle<Vertex,Edge,Face>::substitute
01299       (const Vertex* old_vertex, Vertex* new_vertex)
01300   {
01301     for (Position i = 0; i < 3; i++)
01302     {
01303       if (vertex_[i] == old_vertex)
01304       {
01305         vertex_[i] = new_vertex;
01306         return true;
01307       }
01308     }
01309     return false;
01310   }
01311 
01312 
01313   template <typename Vertex, typename Edge, typename Face>
01314   bool GraphTriangle<Vertex,Edge,Face>::substitute
01315       (const Edge* old_edge, Edge* new_edge)
01316   {
01317     for (Position i = 0; i < 3; i++)
01318     {
01319       if (edge_[i] == old_edge)
01320       {
01321         edge_[i] = new_edge;
01322         return true;
01323       }
01324     }
01325     return false;
01326   }
01327 
01328 
01329   template <typename Vertex, typename Edge, typename Face>
01330   bool GraphTriangle<Vertex,Edge,Face>::operator == (const Face&) const
01331   {
01332     return true;
01333   }
01334 
01335 
01336   template <typename Vertex, typename Edge, typename Face>
01337   bool GraphTriangle<Vertex,Edge,Face>::operator != (const Face&) const
01338   {
01339     return false;
01340   }
01341 
01342 
01343   template <typename Vertex, typename Edge, typename Face>
01344   bool GraphTriangle<Vertex,Edge,Face>::operator *= (const Face&) const
01345   {
01346     return true;
01347   }
01348 
01349 
01350   template <typename Vertex, typename Edge, typename Face>
01351   Vertex* GraphTriangle<Vertex,Edge,Face>::has(Vertex* vertex) const
01352   {
01353     if (vertex_[0] == vertex)
01354     {
01355       return vertex_[0];
01356     }
01357     if (vertex_[1] == vertex)
01358     {
01359       return vertex_[1];
01360     }
01361     if (vertex_[2] == vertex)
01362     {
01363       return vertex_[2];
01364     }
01365     return NULL;
01366   }
01367 
01368 
01369   template <typename Vertex, typename Edge, typename Face>
01370   Edge* GraphTriangle<Vertex,Edge,Face>::has(Edge* edge) const
01371   {
01372     if (edge_[0] == edge)
01373     {
01374       return edge_[0];
01375     }
01376     if (edge_[1] == edge)
01377     {
01378       return edge_[1];
01379     }
01380     if (edge_[2] == edge)
01381     {
01382       return edge_[2];
01383     }
01384     return NULL;
01385   }
01386 
01387 
01388 } // namespace BALL
01389 
01390 #endif // BALL_STRUCTURE_RSFACE_H