00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00047 #ifndef STLSOFT_INCL_STLSOFT_ALGORITHMS_HPP_UNORDERED
00048 #define STLSOFT_INCL_STLSOFT_ALGORITHMS_HPP_UNORDERED
00049
00050 #ifndef STLSOFT_DOCUMENTATION_SKIP_SECTION
00051 # define STLSOFT_VER_STLSOFT_ALGORITHMS_HPP_UNORDERED_MAJOR 3
00052 # define STLSOFT_VER_STLSOFT_ALGORITHMS_HPP_UNORDERED_MINOR 3
00053 # define STLSOFT_VER_STLSOFT_ALGORITHMS_HPP_UNORDERED_REVISION 2
00054 # define STLSOFT_VER_STLSOFT_ALGORITHMS_HPP_UNORDERED_EDIT 71
00055 #endif
00056
00057
00058
00059
00060
00061 #ifndef STLSOFT_INCL_STLSOFT_H_STLSOFT
00062 # include <stlsoft/stlsoft.h>
00063 #endif
00064 #ifndef STLSOFT_INCL_STLSOFT_ALGORITHMS_STD_HPP_ALT
00065 # include <stlsoft/algorithms/std/alt.hpp>
00066 #endif
00067 #ifdef STLSOFT_CF_std_NAMESPACE
00068 # include <functional>
00069 #endif
00070
00071
00072
00073
00074
00075 #ifndef _STLSOFT_NO_NAMESPACE
00076 namespace stlsoft
00077 {
00078 #endif
00079
00080
00081
00082
00083
00084 #ifdef STLSOFT_CF_std_NAMESPACE
00085
00101 template<ss_typename_param_k I>
00102
00103 #if defined(STLSOFT_COMPILER_IS_DMC) && \
00104 !defined(STLSOFT_DOCUMENTATION_SKIP_SECTION)
00105 inline stlsoft_ns_qual_std_(pair)<I, I> find_first_duplicate(I first, I last)
00106 #else
00107 inline stlsoft_ns_qual_std(pair)<I, I> find_first_duplicate(I first, I last)
00108 #endif
00109 {
00110 for(; first != last; ++first)
00111 {
00112 I next = first;
00113
00114 for(++next; next != last; ++next)
00115 {
00116 if(*next == *first)
00117 {
00118 return stlsoft_ns_qual_std(make_pair)(first, next);
00119 }
00120 }
00121 }
00122
00123 return stlsoft_ns_qual_std(make_pair)(last, last);
00124 }
00125
00131 template< ss_typename_param_k I
00132 , ss_typename_param_k BP
00133 >
00134
00135 #if defined(STLSOFT_COMPILER_IS_DMC) && \
00136 !defined(STLSOFT_DOCUMENTATION_SKIP_SECTION)
00137 inline stlsoft_ns_qual_std_(pair)<I, I> find_first_duplicate(I first, I last, BP pred)
00138 #else
00139 inline stlsoft_ns_qual_std(pair)<I, I> find_first_duplicate(I first, I last, BP pred)
00140 #endif
00141 {
00142 for(; first != last; ++first)
00143 {
00144 I next = first;
00145
00146 for(++next; next != last; ++next)
00147 {
00148 if(pred(*next, *first))
00149 {
00150 return stlsoft_ns_qual_std(make_pair)(first, next);
00151 }
00152 }
00153 }
00154
00155 return stlsoft_ns_qual_std(make_pair)(last, last);
00156 }
00157
00158 #endif
00159
00160
00166 template <ss_typename_param_k FI>
00167
00168 inline FI unordered_unique(FI first, FI last)
00169 {
00170 if(first != last)
00171 {
00172
00173
00174 const FI start = first;
00175 FI dest = ++first;
00176
00177 for(; first != last; ++first)
00178 {
00179
00180
00181 if(dest == std_find(start, dest, *first))
00182 {
00183
00184
00185
00186
00187
00188
00189 if(dest != first)
00190 {
00191 *dest = *first;
00192 }
00193 ++dest;
00194 }
00195 }
00196
00197 first = dest;
00198 }
00199
00200 return first;
00201 }
00202
00208 template< ss_typename_param_k FI
00209 , ss_typename_param_k BP
00210 >
00211
00212 inline FI unordered_unique(FI first, FI last, BP pred)
00213 {
00214 if(first != last)
00215 {
00216
00217
00218 const FI start = first;
00219 FI dest = ++first;
00220
00221 for(; first != last; ++first)
00222 {
00223
00224
00225 if(dest == std_find_if(start, dest, std::bind2nd(pred, *first)))
00226 {
00227
00228
00229
00230
00231
00232
00233 if(dest != first)
00234 {
00235 *dest = *first;
00236 }
00237 ++dest;
00238 }
00239 }
00240
00241 first = dest;
00242 }
00243
00244 return first;
00245 }
00246
00252 template< ss_typename_param_k FI
00253 , ss_typename_param_k BP
00254 >
00255
00256 inline FI unordered_unique_if(FI first, FI last, BP pred)
00257 {
00258 return unordered_unique(first, last, pred);
00259 }
00260
00266 template< ss_typename_param_k FI
00267 , ss_typename_param_k OI
00268 >
00269
00270 inline OI unordered_unique_copy(FI first, FI last, OI dest)
00271 {
00272 if(first != last)
00273 {
00274
00275
00276 const OI start = dest;
00277 FI curr = first;
00278
00279 *dest++ = *first++;
00280 for(; first != last; ++first)
00281 {
00282
00283
00284 if(dest == std_find(start, dest, *first))
00285 {
00286
00287
00288 *dest = *first;
00289 ++dest;
00290 }
00291 }
00292 }
00293
00294 return dest;
00295 }
00296
00297
00308
00309 template< ss_typename_param_k C
00310 , ss_typename_param_k BP
00311 >
00312 inline void remove_duplicates_from_unordered_sequence(C &container, BP pred)
00313 {
00314 typedef ss_typename_type_k C::iterator iterator_t;
00315
00316 ss_size_t index;
00317 iterator_t begin;
00318
00319 for(index = 0, begin = container.begin(); begin != container.end(); )
00320 {
00321 iterator_t it = begin;
00322 iterator_t end = container.end();
00323
00324 if(++it == end)
00325 {
00326 ++begin;
00327 }
00328 else
00329 {
00330 for(;;)
00331 {
00332 if(pred(*begin, *it))
00333 {
00334 ss_size_t last;
00335
00336
00337
00338 container.erase(it);
00339
00340 last = index;
00341
00342 begin = container.begin();
00343
00344 std_advance(begin, static_cast<ss_ptrdiff_t>(last));
00345 break;
00346 }
00347 else
00348 {
00349 if(++it == end)
00350 {
00351 ++begin;
00352 ++index;
00353 break;
00354 }
00355 }
00356 }
00357 }
00358 }
00359 }
00360
00361
00362 #ifdef STLSOFT_CF_std_NAMESPACE
00363
00372
00373 template<ss_typename_param_k C>
00374 inline void remove_duplicates_from_unordered_sequence(C &container)
00375 {
00376 typedef ss_typename_type_k C::value_type value_t;
00377
00378 remove_duplicates_from_unordered_sequence(container, stlsoft_ns_qual_std(equal_to)<value_t>());
00379 }
00380
00381 #endif
00382
00383
00394 template<ss_typename_param_k I>
00395
00396 inline I skip_equal(I first, I last)
00397 {
00398 if(first == last)
00399 {
00400 return last;
00401 }
00402 else
00403 {
00404 for(I next = first; next != last; ++next)
00405 {
00406 if(*next != *first)
00407 {
00408 return next;
00409 }
00410 }
00411
00412 return last;
00413 }
00414 }
00415
00416
00426 template< ss_typename_param_k I1
00427 , ss_typename_param_k I2
00428 >
00429 inline ss_bool_t unordered_includes(I1 first1, I1 last1, I2 first2, I2 last2)
00430 {
00431 for(; first2 != last2; ++first2)
00432 {
00433 ss_bool_t bFound = false;
00434
00435 for(I1 i1 = first1; i1 != last1; ++i1)
00436 {
00437 if(*first2 == *i1)
00438 {
00439 bFound = true;
00440 break;
00441 }
00442 }
00443
00444 if(!bFound)
00445 {
00446 return false;
00447 }
00448 }
00449
00450 return true;
00451 }
00452
00454
00455
00456 #ifdef STLSOFT_UNITTEST
00457 # include "./unittest/unordered_unittest_.h"
00458 #endif
00459
00460
00461
00462 #ifndef _STLSOFT_NO_NAMESPACE
00463 }
00464 #endif
00465
00466
00467
00468 #endif
00469
00470