...

[cpPlugins.git] / lib / cpExtensions / DataStructures / Graph.hxx

diff --git a/lib/cpExtensions/DataStructures/Graph.hxx b/lib/cpExtensions/DataStructures/Graph.hxx
index 7ca6d88f55fc9b2dd60710871a776cb430a9b7cb..62c6b75c60012c7f9584e470f300451f01880822 100644 (file)
--- a/lib/cpExtensions/DataStructures/Graph.hxx
+++ b/lib/cpExtensions/DataStructures/Graph.hxx
@@ -1,81 +1,9 @@
-#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
-#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
+#ifndef __cpExtensions__DataStructures__Graph__hxx__
+#define __cpExtensions__DataStructures__Graph__hxx__
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
-BeginVertices( )
-{
-  return( this->m_Vertices.begin( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
-EndVertices( )
-{
-  return( this->m_Vertices.end( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
-BeginVertices( ) const
-{
-  return( this->m_Vertices.begin( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
-EndVertices( ) const
-{
-  return( this->m_Vertices.end( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
-BeginEdgesRows( )
-{
-  return( this->m_Matrix.begin( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
-EndEdgetsRows( )
-{
-  return( this->m_Matrix.end( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
-BeginEdgesRows( ) const
-{
-  return( this->m_Matrix.begin( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
-EndEdgesRows( ) const
-{
-  return( this->m_Matrix.end( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 Clear( )
 {
   this->m_Vertices.clear( );
@@ -83,33 +11,9 @@ Clear( )
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-ClearEdges( )
-{
-  this->m_Matrix.clear( );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-bool cpExtensions::DataStructures::Graph< V, C, I >::
-HasVertexIndex( const I& index ) const
-{
-  return( this->m_Vertices.find( index ) != this->m_Vertices.end( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-SetVertex( const I& index, V& vertex )
-{
-  this->m_Vertices[ index ] = vertex;
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-bool cpExtensions::DataStructures::Graph< V, C, I >::
-RenameVertex( const I& old_index, const I& new_index )
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RenameVertex( const TIndex& old_index, const TIndex& new_index )
 {
   auto old_v = this->m_Vertices.find( old_index );
   auto new_v = this->m_Vertices.find( new_index );
@@ -167,9 +71,9 @@ RenameVertex( const I& old_index, const I& new_index )
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-RemoveVertex( const I& index )
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveVertex( const TIndex& index )
 {
   auto i = this->m_Vertices.find( index );
   if( i != this->m_Vertices.end( ) )
@@ -200,32 +104,65 @@ RemoveVertex( const I& index )
       } // elihw
 
     } // rof
-    return( true );
-  }
-  else
-    return( false );
+
+  } // fi
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-V& cpExtensions::DataStructures::Graph< V, C, I >::
-GetVertex( const I& index )
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+typename
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+TEdges&
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+GetEdges( const TIndex& orig, const TIndex& dest )
 {
-  return( this->m_Vertices[ index ] );
+  static TEdges null_edges;
+  auto o = this->m_Matrix.find( orig );
+  if( o != this->m_Matrix.find( orig ) )
+  {
+    auto d = o->second.find( dest );
+    if( d == o->second.end( ) )
+    {
+      null_edges.clear( );
+      return( null_edges );
+    }
+    else
+      return( d->second );
+  }
+  else
+  {
+    null_edges.clear( );
+    return( null_edges );
+
+  } // fi
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-const V& cpExtensions::DataStructures::Graph< V, C, I >::
-GetVertex( const I& index ) const
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+const typename 
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+TEdges&
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+GetEdges( const TIndex& orig, const TIndex& dest ) const
 {
-  return( this->m_Vertices[ index ] );
+  static const TEdges null_edges;
+  auto o = this->m_Matrix.find( orig );
+  if( o != this->m_Matrix.find( orig ) )
+  {
+    auto d = o->second.find( dest );
+    if( d == o->second.end( ) )
+      return( null_edges );
+    else
+      return( d->second );
+  }
+  else
+    return( null_edges );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-bool cpExtensions::DataStructures::Graph< V, C, I >::
-HasEdge( const I& orig, const I& dest ) const
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+HasEdge( const TIndex& orig, const TIndex& dest ) const
 {
   auto mIt = this->m_Matrix.find( orig );
   if( mIt != this->m_Matrix.end( ) )
@@ -235,17 +172,9 @@ HasEdge( const I& orig, const I& dest ) const
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-AddEdge( const I& orig, const I& dest, const C& cost )
-{
-  this->m_Matrix[ orig ][ dest ].push_back( cost );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-RemoveEdge( const I& orig, const I& dest, const C& cost )
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
 {
   auto m = this->m_Matrix.find( orig );
   if( m != this->m_Matrix.end( ) )
@@ -253,7 +182,14 @@ RemoveEdge( const I& orig, const I& dest, const C& cost )
     auto r = m->second.find( dest );
     if( r != m->second.end( ) )
     {
-      auto e = std::find( r->second.begin( ), r->second.end( ), cost );
+      auto e = r->second.end( );
+      for(
+        auto i = r->second.begin( );
+        i != r->second.end( ) && e == r->second.end( );
+        ++i
+        )
+        if( *i == cost )
+          e = i;
       if( e != r->second.end( ) )
       {
         r->second.erase( e );
@@ -273,9 +209,9 @@ RemoveEdge( const I& orig, const I& dest, const C& cost )
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-void cpExtensions::DataStructures::Graph< V, C, I >::
-RemoveEdges( const I& orig, const I& dest )
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
+RemoveEdges( const TIndex& orig, const TIndex& dest )
 {
   auto m = this->m_Matrix.find( orig );
   if( m != this->m_Matrix.end( ) )
@@ -294,29 +230,12 @@ RemoveEdges( const I& orig, const I& dest )
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-typename cpExtensions::DataStructures::Graph< V, C, I >::
-TEdges& cpExtensions::DataStructures::Graph< V, C, I >::
-GetEdges( const I& orig, const I& dest )
-{
-  return( this->m_Matrix[ orig ][ dest ] );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-const typename cpExtensions::DataStructures::Graph< V, C, I >::
-TEdges& cpExtensions::DataStructures::Graph< V, C, I >::
-GetEdges( const I& orig, const I& dest ) const
-{
-  return( this->m_Matrix[ orig ][ dest ] );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class I >
-std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+std::set< _TIndex, _TIndexCompare >
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 GetSinks( ) const
 {
-  std::set< I > sinks;
+  std::set< _TIndex, _TIndexCompare > sinks;
 
   auto vIt = this->m_Vertices.begin( );
   for( ; vIt != this->m_Vertices.end( ); ++vIt )
@@ -329,20 +248,20 @@ GetSinks( ) const
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-cpExtensions::DataStructures::Graph< V, C, I >::
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 Graph( )
   : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class I >
-cpExtensions::DataStructures::Graph< V, C, I >::
+template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
+cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 ~Graph( )
 {
 }
 
-#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
+#endif // __cpExtensions__DataStructures__Graph__hxx__
 
 // eof - $RCSfile$