00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #pragma once
00025 #ifndef __D_STL__
00026 #define __D_STL__
00027
00028 #include <vector>
00029 #include <algorithm>
00030 #include <iostream>
00031 #include <string>
00032
00033 namespace DUtils {
00034
00036 class STL {
00037 public:
00038
00047 template<class T>
00048 static void removeIndices(std::vector<T> &data,
00049 const std::vector<unsigned int> &indices, bool preserve_order = true);
00050
00059 template<class T>
00060 static void removeIndices(std::vector<T> &data,
00061 std::vector<unsigned int> &indices, bool preserve_order = true);
00062
00071 template<class T>
00072 static void removeIndices(std::vector<T> &data,
00073 const std::vector<unsigned char> &status, bool preserve_order = true);
00074
00082 template<class T>
00083 static void print(const std::vector<T> &v, const std::string &name,
00084 std::ostream &f = std::cout);
00085
00093 template< class RandomIt >
00094 inline static void indexSort(RandomIt first, RandomIt last,
00095 std::vector<unsigned int>& sorted_indexes);
00096
00105 template< class RandomIt, class Compare >
00106 static void indexSort(RandomIt first, RandomIt last,
00107 std::vector<unsigned int>& sorted_indexes, Compare fun);
00108
00117 template<class RandomIt>
00118 inline static void arrange(RandomIt first, RandomIt last,
00119 const std::vector<unsigned int> &indices);
00120
00121 public:
00122
00133 template<class T>
00134 static void _removeIndices(std::vector<T> &data,
00135 const std::vector<unsigned int> &indices, bool preserve_order);
00136
00137 protected:
00138
00144 template<class RandomIt, class Compare>
00145 struct index_cmp
00146 {
00147 index_cmp(const RandomIt& _first, const Compare &_fun)
00148 : m_first(_first), m_fun(_fun) {}
00149
00150
00151 bool operator()(const unsigned int a, const unsigned int b) const
00152 {
00153 return m_fun( *(m_first + a), *(m_first + b) );
00154 }
00155
00156 private:
00157 const RandomIt& m_first;
00158 const Compare& m_fun;
00159 };
00160
00161
00162 };
00163
00164
00165
00166 template<class T>
00167 void STL::removeIndices(std::vector<T> &data,
00168 const std::vector<unsigned char> &status, bool preserve_order)
00169 {
00170 assert(data.size() == status.size());
00171
00172 std::vector<unsigned int> indices;
00173 for(unsigned int i = 0; i < status.size(); ++i)
00174 if (status[i] == 0) indices.push_back(i);
00175
00176 STL::_removeIndices(data, indices, preserve_order);
00177 }
00178
00179
00180
00181 template<class T>
00182 void STL::removeIndices(std::vector<T> &data,
00183 const std::vector<unsigned int> &indices, bool preserve_order)
00184 {
00185 if(indices.empty()) return;
00186
00187 std::vector<unsigned int> copied_indices = indices;
00188 STL::removeIndices(data, copied_indices, preserve_order);
00189 }
00190
00191
00192
00193 template<class T>
00194 void STL::removeIndices(std::vector<T> &data,
00195 std::vector<unsigned int> &indices, bool preserve_order)
00196 {
00197 if(indices.empty()) return;
00198
00199
00200 std::sort(indices.begin(), indices.end());
00201
00202
00203 {
00204 int i_idx = (int)indices.size() - 1;
00205 while( indices[i_idx] >= data.size() ) i_idx--;
00206 indices.resize(i_idx+1);
00207 }
00208
00209
00210 {
00211 const std::vector<unsigned int>::iterator last =
00212 std::unique(indices.begin(), indices.end());
00213 indices.erase(last, indices.end());
00214 }
00215
00216 STL::_removeIndices(data, indices, preserve_order);
00217 }
00218
00219
00220
00221 template<class T>
00222 void STL::_removeIndices(std::vector<T> &data,
00223 const std::vector<unsigned int> &indices, bool preserve_order)
00224 {
00225
00226 if(preserve_order)
00227 {
00228
00229 int i_idx = (int)indices.size() - 1;
00230 while(i_idx >= 0)
00231 {
00232 int j_idx = i_idx - 1;
00233 while(j_idx >= 0 && ((int)(indices[i_idx] - indices[j_idx]) == i_idx - j_idx))
00234 {
00235 j_idx--;
00236 }
00237 data.erase(data.begin() + indices[j_idx + 1],
00238 data.begin() + indices[i_idx] + 1);
00239 i_idx = j_idx;
00240 }
00241
00242 }
00243 else
00244 {
00245
00246 int nremoved = 0;
00247
00248 const typename std::vector<T>::iterator first = data.begin();
00249 const typename std::vector<T>::iterator last = data.end()-1;
00250
00251 int i_idx = (int)indices.size() - 1;
00252
00253
00254 while(i_idx >= 0 &&
00255 (indices.size() - i_idx == data.size() - indices[i_idx]))
00256 {
00257 i_idx--;
00258 nremoved++;
00259 }
00260
00261 while(i_idx >= 0)
00262 {
00263 int j_idx = i_idx - 1;
00264 while(j_idx >= 0 && ((int)(indices[i_idx] - indices[j_idx]) == i_idx - j_idx))
00265 {
00266 j_idx--;
00267 }
00268
00269 int nremoving = i_idx - j_idx;
00270
00271 const typename std::vector<T>::iterator cpy_end = last - nremoved + 1;
00272 const typename std::vector<T>::iterator cpy_src = cpy_end -
00273 std::min( nremoving, (int)data.size()-1 - nremoved - (int)indices[i_idx] );
00274 const typename std::vector<T>::iterator trg = first + indices[j_idx + 1];
00275
00276 std::copy( cpy_src, cpy_end, trg );
00277
00278 nremoved += nremoving;
00279 i_idx = j_idx;
00280 }
00281
00282 data.resize(data.size() - nremoved);
00283
00284
00285 #if 0
00286 std::vector<unsigned int>::reverse_iterator rit;
00287 for(rit = indices.rbegin(); rit != indices.rend(); ++rit)
00288 {
00289 if(*rit < data.size())
00290 {
00291 *(first + *rit) = *(last - nremoved);
00292 nremoved++;
00293 }
00294 }
00295 data.resize(data.size() - nremoved);
00296 #endif
00297 }
00298
00299 }
00300
00301
00302
00303 template<class T>
00304 void STL::print(const std::vector<T> &v, const std::string &name,
00305 std::ostream &f)
00306 {
00307 if(!name.empty())
00308 {
00309 f << name << " = ";
00310 }
00311 f << "[ ";
00312
00313 typename std::vector<T>::const_iterator vit;
00314 for(vit = v.begin(); vit != v.end(); ++vit)
00315 {
00316 f << *vit << " ";
00317 }
00318 f << "]";
00319 f << endl;
00320 }
00321
00322
00323
00324 template< class RandomIt >
00325 void STL::indexSort(RandomIt first, RandomIt last,
00326 std::vector<unsigned int>& sorted_indexes)
00327 {
00328 STL::indexSort(first, last, sorted_indexes,
00329 std::less<typename RandomIt::value_type>() );
00330 }
00331
00332
00333
00334 template< class RandomIt, class Compare >
00335 void STL::indexSort(RandomIt first, RandomIt last,
00336 std::vector<unsigned int>& sorted_indexes, Compare fun)
00337 {
00338 if(last == first)
00339 {
00340 sorted_indexes.clear();
00341 return;
00342 }
00343
00344 sorted_indexes.clear();
00345 sorted_indexes.reserve(last - first);
00346
00347 RandomIt it = first;
00348 for(unsigned int i = 0; it != last; ++it, ++i)
00349 sorted_indexes.push_back(i);
00350
00351 std::sort(sorted_indexes.begin(), sorted_indexes.end(),
00352 index_cmp<RandomIt, Compare>(first, fun));
00353 }
00354
00355
00356
00357 template<class RandomIt>
00358 void STL::arrange(RandomIt first, RandomIt last,
00359 const std::vector<unsigned int> &indices)
00360 {
00361 for(size_t i = 0; i < indices.size(); ++i)
00362 {
00363 unsigned int idx = indices[i];
00364 while(idx < i)
00365 {
00366 idx = indices[idx];
00367 }
00368
00369 if(idx > i)
00370 {
00371 iter_swap(first + idx, first + i);
00372 }
00373 }
00374 }
00375
00376
00377
00378 }
00379
00380 #endif
00381