Main Page   Modules   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members   File Members  

at_bw_transform.h

Go to the documentation of this file.
00001 //
00002 // The Austria library is copyright (c) Gianni Mariani 2004.
00003 // 
00004 // Grant Of License.  Grants to LICENSEE the non-exclusive right to use the Austria
00005 // library subject to the terms of the LGPL.
00006 // 
00007 // A copy of the license is available in this directory or one may be found at this URL:
00008 //      http://www.gnu.org/copyleft/lesser.txt
00009 // 
00024 #ifndef x_at_bw_transform_h_x
00025 #define x_at_bw_transform_h_x
00026 
00027 #include <vector>
00028 #include <algorithm>
00029 
00030 // Austria namespace
00031 namespace at
00032 {
00033 
00039 template <
00040         typename        w_str_iterator
00041 >
00042 class BWComparator
00043 {
00044         w_str_iterator                            m_str_begin;
00045         w_str_iterator                            m_str_end;
00046                 
00047         public:
00048         BWComparator( 
00049                 w_str_iterator                  & i_str_begin,  
00050                 w_str_iterator                  & i_str_end
00051         )
00052           : m_str_begin( i_str_begin ),
00053                 m_str_end( i_str_end )
00054         {
00055         }
00056 
00057         inline bool operator()(
00058                 w_str_iterator                    i_lhs,        
00059                 w_str_iterator                    i_rhs
00060         ) {
00061 
00062                 w_str_iterator                    l_ilhs = i_lhs;
00063                 w_str_iterator                    l_irhs = i_rhs;
00064 
00065                 w_str_iterator                    l_slhs = m_str_end;
00066                 w_str_iterator                    l_srhs = m_str_end;
00067 
00068                 while ( 1 )
00069                 {
00070 
00071                         if ( * l_ilhs < * l_irhs )
00072                         {
00073                                 return true;
00074                         }
00075                         
00076                         if ( * l_irhs < * l_ilhs )
00077                         {
00078                                 return false;
00079                         }
00080 
00081                         ++ l_ilhs;
00082 
00083                         if ( l_ilhs == l_slhs )
00084                         {
00085                                 if ( l_slhs == m_str_end )
00086                                 {
00087                                         l_slhs = i_lhs;
00088                                         l_ilhs = m_str_begin;
00089                                 }
00090                                 else
00091                                 {
00092                                         return false;
00093                                 }
00094                         }
00095                         
00096                         ++ l_irhs;
00097 
00098                         if ( l_irhs == l_srhs )
00099                         {
00100                                 if ( l_srhs == m_str_end )
00101                                 {
00102                                         l_srhs = i_rhs;
00103                                         l_irhs = m_str_begin;
00104                                 }
00105                                 else
00106                                 {
00107                                         return false;
00108                                 }
00109                         }
00110                         
00111                 }
00112         }
00113 };
00114 
00127 template <
00128         typename        w_str_iterator,
00129         typename        w_out_iterator,
00130         typename        w_ptr_diff_type
00131 >
00132 unsigned BWTEncode(
00133         w_str_iterator                    i_str_begin,  
00134         w_str_iterator                    i_str_end,
00135         w_out_iterator                    i_out_begin,
00136         w_ptr_diff_type                   i_count
00137 )
00138 {
00139 
00140         // create a vector to store for all the iterators to all the elements.
00141         // except for the last one which we will treat in a special way.
00142 
00143         std::vector<w_str_iterator>             l_strs( i_count );
00144 
00145         w_str_iterator  l_str_iter = i_str_begin;
00146         typename std::vector<w_str_iterator>::iterator p_strs = l_strs.begin();
00147         
00148         for ( w_ptr_diff_type l_counter = i_count; l_counter; -- l_counter ) {
00149                 * ( p_strs ++ ) = l_str_iter ++;
00150         }
00151 
00152         BWComparator< w_str_iterator >  l_comparator( i_str_begin, i_str_end );
00153 
00154         std::sort( l_strs.begin(), l_strs.end(), l_comparator );
00155 
00156         w_out_iterator                    l_out = i_out_begin;
00157         
00158         l_str_iter = i_str_begin;
00159         p_strs = l_strs.begin();
00160 
00161         unsigned row_sel = ~0;
00162         
00163         for ( w_ptr_diff_type l_counter = i_count; l_counter; -- l_counter ) {
00164                 w_str_iterator          l_iter = * ( p_strs ++ );
00165                 
00166                 if ( l_iter != i_str_begin )
00167                 {
00168                         -- l_iter;
00169                 }
00170                 else
00171                 {
00172                         row_sel = l_counter - 1;
00173                         l_iter = i_str_end;
00174                         -- l_iter;
00175                 }
00176                 
00177                 * ( l_out ++ ) = * l_iter;
00178         }
00179 
00180         return row_sel;
00181 }
00182 
00183 
00196 template <
00197         typename        w_str_iterator,
00198         typename        w_out_iterator
00199 >       
00200 unsigned BWTEncode(
00201         w_str_iterator                    i_str_begin,  
00202         w_str_iterator                    i_str_end,
00203         w_out_iterator                    i_out_begin
00204 )
00205 {
00206         return BWTEncode( i_str_begin, i_str_end, i_out_begin, i_str_end - i_str_begin );
00207 }
00208 
00209 
00215 template <
00216         typename        w_str_iterator
00217 >
00218 class BWDecComparator
00219 {
00220         w_str_iterator                            m_str_begin;
00221         w_str_iterator                            m_str_end;
00222 
00223         public:
00224         BWDecComparator( 
00225                 w_str_iterator                  & i_str_begin,  
00226                 w_str_iterator                  & i_str_end
00227         )
00228           : m_str_begin( i_str_begin ),
00229                 m_str_end( i_str_end )
00230         {
00231         }
00232 
00233         inline bool operator()(
00234                 w_str_iterator                    i_lhs,        
00235                 w_str_iterator                    i_rhs
00236         ) {
00237 
00238                 w_str_iterator                    l_ilhs = i_lhs;
00239                 w_str_iterator                    l_irhs = i_rhs;
00240 
00241                 w_str_iterator                    l_slhs = m_str_end;
00242                 w_str_iterator                    l_srhs = m_str_end;
00243 
00244                 if ( * l_ilhs < * l_irhs )
00245                 {
00246                         return true;
00247                 }
00248                 
00249                 if ( * l_irhs < * l_ilhs )
00250                 {
00251                         return false;
00252                 }
00253 
00254                 return ( l_ilhs <  l_irhs );
00255 
00256         }
00257 };
00258 
00259 
00274 template <
00275         typename        w_str_iterator,
00276         typename        w_out_iterator,
00277         typename        w_ptr_diff_type
00278 >       
00279 void BWTDecode(
00280         unsigned                                  i_I,
00281         w_str_iterator                    i_str_begin,  
00282         w_str_iterator                    i_str_end,
00283         w_out_iterator                    i_out_begin,
00284         w_ptr_diff_type                   i_count
00285 )
00286 {
00287 
00288         // create a vector to store for all the iterators to all the elements.
00289         // except for the last one which we will treat in a special way.
00290 
00291         std::vector<w_str_iterator>             l_strs( i_count );
00292 
00293         w_str_iterator  l_str_iter = i_str_begin;
00294         typename std::vector<w_str_iterator>::iterator p_strs = l_strs.begin();
00295         
00296         for ( w_ptr_diff_type l_counter = i_count; l_counter; -- l_counter ) {
00297                 * ( p_strs ++ ) = l_str_iter ++;
00298         }
00299 
00300         BWDecComparator< w_str_iterator >       l_comparator( i_str_begin, i_str_end );
00301 
00302         std::sort( l_strs.begin(), l_strs.end(), l_comparator );
00303 
00304         unsigned index = i_I;
00305 
00306         for ( w_ptr_diff_type i = i_count; i; -- i )
00307         {
00308                 l_str_iter = l_strs[ index ];
00309 
00310                 * ( i_out_begin ++ ) = * l_str_iter;
00311                 
00312                 index = l_str_iter - i_str_begin;
00313 
00314         }
00315         
00316 }
00317 
00318 
00319 
00331 template <
00332         typename        w_str_iterator,
00333         typename        w_out_iterator
00334 >       
00335 void BWTDecode(
00336         unsigned                                  i_I,
00337         w_str_iterator                    i_str_begin,  
00338         w_str_iterator                    i_str_end,
00339         w_out_iterator                    i_out_begin
00340 )
00341 {
00342         BWTDecode( i_I, i_str_begin, i_str_end, i_out_begin, ( i_str_end - i_str_begin ) );
00343 }
00344 
00345 }; // namespace
00346 
00347 #endif // x_at_bw_transform_h_x
00348 

Generated for Austria by doxygen and MakeXS at Sun Oct 24 17:35:34 PDT 2004