and
MakeXS at Sun Oct 24 17:35:34 PDT 2004
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
and
MakeXS at Sun Oct 24 17:35:34 PDT 2004