Moved to version 1.0

[cpPlugins.git] / lib / TinyCon / Trie.cxx

diff --git a/lib/TinyCon/Trie.cxx b/lib/TinyCon/Trie.cxx
new file mode 100644 (file)
index 0000000..a8446cc
--- /dev/null
+++ b/lib/TinyCon/Trie.cxx
@@ -0,0 +1,154 @@
+// =========================================================================
+// @author Leonardo Florez-Valencia (florez-l@javeriana.edu.co)
+// =========================================================================
+
+#include <TinyCon/Trie.h>
+#include <sstream>
+
+// -------------------------------------------------------------------------
+TinyCon::Trie::
+Trie( )
+  : m_IsWord( false ),
+    m_Extension( NULL )
+{
+}
+
+// -------------------------------------------------------------------------
+TinyCon::Trie::
+~Trie( )
+{
+  if( this->m_Extension != NULL )
+    delete this->m_Extension;
+  for( TChildren::value_type& v: this->m_Next )
+    if( v.second != NULL ) delete v.second;
+}
+
+// -------------------------------------------------------------------------
+bool TinyCon::Trie::
+IsWord( ) const
+{
+  return( this->m_IsWord );
+}
+
+// -------------------------------------------------------------------------
+TinyCon::Trie::
+Self* TinyCon::Trie::
+createExtension( )
+{
+  if( this->m_Extension != NULL )
+    delete this->m_Extension;
+  this->m_Extension = new Self( );
+  return( this->m_Extension );
+}
+
+// -------------------------------------------------------------------------
+TinyCon::Trie::
+Self* TinyCon::Trie::
+getExtension( )
+{
+  return( this->m_Extension );
+}
+
+// -------------------------------------------------------------------------
+const TinyCon::Trie::
+Self* TinyCon::Trie::
+getExtension( ) const
+{
+  return( this->m_Extension );
+}
+
+// -------------------------------------------------------------------------
+void TinyCon::Trie::
+setExtension( Self* extension )
+{
+  if( this->m_Extension != NULL )
+    delete this->m_Extension;
+  this->m_Extension = extension;
+}
+
+// -------------------------------------------------------------------------
+TinyCon::Trie::
+Self* TinyCon::Trie::
+insert( const std::string& w )
+{
+  Trie* n = this;
+  for( const char& c: w )
+  {
+    if( n->m_Next.find( c ) == n->m_Next.end( ) )
+      n->m_Next[ c ] = new Trie( );
+    n = n->m_Next[ c ];
+  } // end for
+  n->m_IsWord = true;
+  return( n );
+}
+
+// -------------------------------------------------------------------------
+void TinyCon::Trie::
+words( std::vector< std::string >& options ) const
+{
+  TChildren::const_iterator mIt = this->m_Next.begin( );
+  for( ; mIt != this->m_Next.end( ); ++mIt )
+  {
+    std::string prefix;
+    prefix.push_back( mIt->first );
+    if( !( mIt->second->m_IsWord ) )
+    {
+      std::vector< std::string > opts;
+      mIt->second->words( opts );
+      for( std::string& o: opts )
+        options.push_back( prefix + o );
+    }
+    else
+      options.push_back( prefix );
+  } // end for
+}
+
+// -------------------------------------------------------------------------
+std::pair< TinyCon::Trie::Self*, std::string >
+TinyCon::Trie::
+find( const std::string& line, const std::size_t& p )
+{
+  typedef std::pair< TinyCon::Trie::Self*, std::string > _TP;
+
+  if( p < line.size( ) )
+  {
+    TChildren::iterator mIt = this->m_Next.find( line[ p ] );
+    if( mIt != this->m_Next.end( ) )
+    {
+      _TP r = mIt->second->find( line, p + 1 );
+      std::stringstream s;
+      s << mIt->first << r.second;
+      return( _TP( r.first, s.str( ) ) );
+    }
+    else
+      return( _TP( NULL, "" ) );
+  }
+  else
+    return( _TP( this, "" ) );
+}
+
+// -------------------------------------------------------------------------
+std::pair< const TinyCon::Trie::Self*, std::string >
+TinyCon::Trie::
+find( const std::string& line, const std::size_t& p ) const
+{
+  typedef std::pair< const TinyCon::Trie::Self*, std::string > _TP;
+
+  if( p < line.size( ) )
+  {
+    TChildren::const_iterator mIt = this->m_Next.find( line[ p ] );
+    if( mIt != this->m_Next.end( ) )
+    {
+      _TP r = mIt->second->find( line, p + 1 );
+      std::stringstream s;
+      s << mIt->first << r.second;
+      return( _TP( r.first, s.str( ) ) );
+    }
+    else
+      return( _TP( NULL, "" ) );
+  }
+  else
+    return( _TP( this, "" ) );
+}
+
+// eof - $RCSfile$