lib/TinyCon/Trie.cxx

   1 // =========================================================================
   2 // @author Leonardo Florez-Valencia (florez-l@javeriana.edu.co)
   3 // =========================================================================
   4
   5 #include <TinyCon/Trie.h>
   6 #include <sstream>
   7
   8 // -------------------------------------------------------------------------
   9 TinyCon::Trie::
  10 Trie( )
  11   : m_IsWord( false ),
  12     m_Extension( NULL )
  13 {
  14 }
  15
  16 // -------------------------------------------------------------------------
  17 TinyCon::Trie::
  18 ~Trie( )
  19 {
  20   if( this->m_Extension != NULL )
  21     delete this->m_Extension;
  22   for( TChildren::value_type& v: this->m_Next )
  23     if( v.second != NULL ) delete v.second;
  24 }
  25
  26 // -------------------------------------------------------------------------
  27 bool TinyCon::Trie::
  28 IsWord( ) const
  29 {
  30   return( this->m_IsWord );
  31 }
  32
  33 // -------------------------------------------------------------------------
  34 TinyCon::Trie::
  35 Self* TinyCon::Trie::
  36 createExtension( )
  37 {
  38   if( this->m_Extension != NULL )
  39     delete this->m_Extension;
  40   this->m_Extension = new Self( );
  41   return( this->m_Extension );
  42 }
  43
  44 // -------------------------------------------------------------------------
  45 TinyCon::Trie::
  46 Self* TinyCon::Trie::
  47 getExtension( )
  48 {
  49   return( this->m_Extension );
  50 }
  51
  52 // -------------------------------------------------------------------------
  53 const TinyCon::Trie::
  54 Self* TinyCon::Trie::
  55 getExtension( ) const
  56 {
  57   return( this->m_Extension );
  58 }
  59
  60 // -------------------------------------------------------------------------
  61 void TinyCon::Trie::
  62 setExtension( Self* extension )
  63 {
  64   if( this->m_Extension != NULL )
  65     delete this->m_Extension;
  66   this->m_Extension = extension;
  67 }
  68
  69 // -------------------------------------------------------------------------
  70 TinyCon::Trie::
  71 Self* TinyCon::Trie::
  72 insert( const std::string& w )
  73 {
  74   Trie* n = this;
  75   for( const char& c: w )
  76   {
  77     if( n->m_Next.find( c ) == n->m_Next.end( ) )
  78       n->m_Next[ c ] = new Trie( );
  79     n = n->m_Next[ c ];
  80   } // end for
  81   n->m_IsWord = true;
  82   return( n );
  83 }
  84
  85 // -------------------------------------------------------------------------
  86 void TinyCon::Trie::
  87 words( std::vector< std::string >& options ) const
  88 {
  89   TChildren::const_iterator mIt = this->m_Next.begin( );
  90   for( ; mIt != this->m_Next.end( ); ++mIt )
  91   {
  92     std::string prefix;
  93     prefix.push_back( mIt->first );
  94     if( !( mIt->second->m_IsWord ) )
  95     {
  96       std::vector< std::string > opts;
  97       mIt->second->words( opts );
  98       for( std::string& o: opts )
  99         options.push_back( prefix + o );
 100     }
 101     else
 102       options.push_back( prefix );
 103   } // end for
 104 }
 105
 106 // -------------------------------------------------------------------------
 107 std::pair< TinyCon::Trie::Self*, std::string >
 108 TinyCon::Trie::
 109 find( const std::string& line, const std::size_t& p )
 110 {
 111   typedef std::pair< TinyCon::Trie::Self*, std::string > _TP;
 112
 113   if( p < line.size( ) )
 114   {
 115     TChildren::iterator mIt = this->m_Next.find( line[ p ] );
 116     if( mIt != this->m_Next.end( ) )
 117     {
 118       _TP r = mIt->second->find( line, p + 1 );
 119       std::stringstream s;
 120       s << mIt->first << r.second;
 121       return( _TP( r.first, s.str( ) ) );
 122     }
 123     else
 124       return( _TP( NULL, "" ) );
 125   }
 126   else
 127     return( _TP( this, "" ) );
 128 }
 129
 130 // -------------------------------------------------------------------------
 131 std::pair< const TinyCon::Trie::Self*, std::string >
 132 TinyCon::Trie::
 133 find( const std::string& line, const std::size_t& p ) const
 134 {
 135   typedef std::pair< const TinyCon::Trie::Self*, std::string > _TP;
 136
 137   if( p < line.size( ) )
 138   {
 139     TChildren::const_iterator mIt = this->m_Next.find( line[ p ] );
 140     if( mIt != this->m_Next.end( ) )
 141     {
 142       _TP r = mIt->second->find( line, p + 1 );
 143       std::stringstream s;
 144       s << mIt->first << r.second;
 145       return( _TP( r.first, s.str( ) ) );
 146     }
 147     else
 148       return( _TP( NULL, "" ) );
 149   }
 150   else
 151     return( _TP( this, "" ) );
 152 }
 153
 154 // eof - $RCSfile$