Combination.hpp

   1 /* COMBINATION_HPP_ */
   2 //  (C) Copyright Ben Bear, Herve Bronnimann 2007.
   3 //  Use, modification and distribution are subject to the
   4 //  Boost Software License, Version 1.0. (See accompanying file
   5 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 /*
   8  Revision history:
   9 Nov 13, 2007:  Incorporation of boost-devel comments (Jens Seidel, Ben Bear and myself)
  10 Nov 11, 2007:  Rewrite of Ben Bear's Gacap
  11 */
  12
  13 #ifndef BOOST_ALGORITHM_COMBINATION_HPP
  14 #define BOOST_ALGORITHM_COMBINATION_HPP
  15
  16 #include <algorithm>
  17
  18 namespace boost {
  19
  20 namespace detail {
  21
  22 template<class BidirectionalIterator>
  23   bool next_combination(BidirectionalIterator first1,
  24                         BidirectionalIterator last1,
  25                         BidirectionalIterator first2,
  26                         BidirectionalIterator last2)
  27   {
  28       if ((first1 == last1) || (first2 == last2)) {
  29           return false;
  30       }
  31
  32       BidirectionalIterator m1 = last1;
  33       BidirectionalIterator m2 = last2; --m2;
  34
  35       // Find first m1 not less than *m2 (i.e., lower_bound(first1, last1, *m2)).
  36       // Actually, this loop stops at one position before that, except perhaps
  37       // if m1 == first1 (in which case one must compare *first1 with *m2).
  38       while (--m1 != first1 && !(*m1 < *m2)) {
  39       }
  40
  41       // Test if all elements in [first1, last1) not less than *m2.
  42       bool result = (m1 == first1) && !(*first1 < *m2);
  43
  44       if (!result) {
  45
  46           // Find first first2 greater than *m1 (since *m1 < *m2, we know it
  47           // can't pass m2 and there's no need to test m2).
  48           while (first2 != m2 && !(*m1 < *first2)) {
  49               ++first2;
  50           }
  51
  52           first1 = m1;
  53           std::iter_swap (first1, first2);
  54           ++first1;
  55           ++first2;
  56       }
  57
  58       // Merge [first1, last1) with [first2, last2), given that the rest of the
  59       // original ranges are sorted and compare appropriately.
  60       if ((first1 != last1) && (first2 != last2)) {
  61           for (m1 = last1, m2 = first2;  (m1 != first1) && (m2 != last2); ++m2) {
  62               // changed decrement at m1 to postfix - rieger, fhi, jan 2010
  63                   std::iter_swap (--m1, m2);
  64           }
  65
  66           std::reverse (first1, m1);
  67           std::reverse (first1, last1);
  68
  69           std::reverse (m2, last2);
  70           std::reverse (first2, last2);
  71       }
  72
  73       return !result;
  74   }
  75
  76 template<class BidirectionalIterator, class Compare>
  77   bool next_combination(BidirectionalIterator first1,
  78                         BidirectionalIterator last1,
  79                         BidirectionalIterator first2,
  80                         BidirectionalIterator last2, Compare comp)
  81   {
  82       if ((first1 == last1) || (first2 == last2)) {
  83           return false;
  84       }
  85
  86       BidirectionalIterator m1 = last1;
  87       BidirectionalIterator m2 = last2; --m2;
  88
  89       while (--m1 != first1 && !comp(*m1, *m2)) {
  90       }
  91
  92       bool result = (m1 == first1) && !comp(*first1, *m2);
  93
  94       if (!result) {
  95
  96           while (first2 != m2 && !comp(*m1, *first2)) {
  97               ++first2;
  98           }
  99
 100           first1 = m1;
 101           std::iter_swap (first1, first2);
 102           ++first1;
 103           ++first2;
 104       }
 105
 106       if ((first1 != last1) && (first2 != last2)) {
 107           for (m1 = last1, m2 = first2;  (m1 != first1) && (m2 != last2); ++m2) {
 108               std::iter_swap (--m1, m2);
 109           }
 110
 111           std::reverse (first1, m1);
 112           std::reverse (first1, last1);
 113
 114           std::reverse (m2, last2);
 115           std::reverse (first2, last2);
 116       }
 117
 118       return !result;
 119   }
 120
 121 }  // namespace detail
 122
 123 /* PROPOSED STANDARD EXTENSIONS:
 124  *
 125  * template<class BidirectionalIterator>
 126  *   bool next_partial_permutation(BidirectionalIterator first,
 127  *                                 BidirectionalIterator middle,
 128  *                                 BidirectionalIterator last);
 129  *
 130  * template<class BidirectionalIterator, class Compare>
 131  *   bool next_partial_permutation(BidirectionalIterator first,
 132  *                                 BidirectionalIterator middle,
 133  *                                 BidirectionalIterator last, Compare comp);
 134  */
 135
 136 template <class BidirectionalIterator>
 137   bool next_partial_permutation(BidirectionalIterator first,
 138                                 BidirectionalIterator middle,
 139                                 BidirectionalIterator last)
 140 {
 141   reverse (middle, last);
 142   return next_permutation(first, last);
 143 }
 144
 145 template<class BidirectionalIterator, class Compare>
 146   bool next_partial_permutation(BidirectionalIterator first,
 147                                 BidirectionalIterator middle,
 148                                 BidirectionalIterator last, Compare comp)
 149 {
 150   reverse (middle, last);
 151   return next_permutation(first, last, comp);
 152 }
 153
 154 /* PROPOSED STANDARD EXTENSIONS:
 155  *
 156  * template<class BidirectionalIterator>
 157  *   bool prev_partial_permutation(BidirectionalIterator first,
 158  *                                 BidirectionalIterator middle,
 159  *                                 BidirectionalIterator last);
 160  *
 161  * template<class BidirectionalIterator, class Compare>
 162  *   bool prev_partial_permutation(BidirectionalIterator first,
 163  *                                 BidirectionalIterator middle,
 164  *                                 BidirectionalIterator last, Compare comp);
 165  */
 166
 167 template<class BidirectionalIterator>
 168   bool prev_partial_permutation(BidirectionalIterator first,
 169                                 BidirectionalIterator middle,
 170                                 BidirectionalIterator last)
 171 {
 172   bool result = prev_permutation(first, last);
 173   reverse (middle, last);
 174   return result;
 175 }
 176
 177
 178 template<class BidirectionalIterator, class Compare>
 179   bool prev_partial_permutation(BidirectionalIterator first,
 180                                 BidirectionalIterator middle,
 181                                 BidirectionalIterator last, Compare comp)
 182 {
 183   bool result = prev_permutation(first, last);
 184   reverse (middle, last);
 185   return result;
 186 }
 187
 188 /* PROPOSED STANDARD EXTENSIONS:
 189  *
 190  * template<class BidirectionalIterator>
 191  *   bool next_combination(BidirectionalIterator first,
 192  *                         BidirectionalIterator middle,
 193  *                         BidirectionalIterator last);
 194  *
 195  * template<class BidirectionalIterator, class Compare>
 196  *   bool next_combination(BidirectionalIterator first,
 197  *                         BidirectionalIterator middle,
 198  *                         BidirectionalIterator last, Compare comp);
 199  */
 200
 201 template<class BidirectionalIterator>
 202   bool next_combination(BidirectionalIterator first,
 203                         BidirectionalIterator middle,
 204                         BidirectionalIterator last)
 205   {
 206     return detail::next_combination(first, middle, middle, last);
 207   }
 208
 209 template<class BidirectionalIterator, class Compare>
 210   bool next_combination(BidirectionalIterator first,
 211                         BidirectionalIterator middle,
 212                         BidirectionalIterator last, Compare comp)
 213   {
 214       return detail::next_combination(first, middle, middle, last, comp);
 215   }
 216
 217 /* PROPOSED STANDARD EXTENSIONS:
 218  *
 219  * template<class BidirectionalIterator>
 220  *   bool prev_combination(BidirectionalIterator first,
 221  *                         BidirectionalIterator middle,
 222  *                         BidirectionalIterator last);
 223  *
 224  * template<class BidirectionalIterator, class Compare>
 225  *   bool prev_combination(BidirectionalIterator first,
 226  *                         BidirectionalIterator middle,
 227  *                         BidirectionalIterator last, Compare comp);
 228  */
 229
 230 template<class BidirectionalIterator>
 231   inline
 232   bool prev_combination(BidirectionalIterator first,
 233                         BidirectionalIterator middle,
 234                         BidirectionalIterator last)
 235   {
 236     return detail::next_combination(middle, last, first, middle);
 237   }
 238
 239 template<class BidirectionalIterator, class Compare>
 240   inline
 241   bool prev_combination(BidirectionalIterator first,
 242                         BidirectionalIterator middle,
 243                         BidirectionalIterator last, Compare comp)
 244   {
 245     return detail::next_combination(middle, last, first, middle, comp);
 246   }
 247
 248 /* PROPOSED STANDARD EXTENSION:
 249  *
 250  * template<class BidirectionalIterator, class T>
 251  *   bool next_mapping(BidirectionalIterator first,
 252  *                     BidirectionalIterator last,
 253  *                     T first_value, T last_value);
 254  *
 255  * template<class BidirectionalIterator, class T, class Incrementor>
 256  *   bool next_mapping(BidirectionalIterator first,
 257  *                     BidirectionalIterator last,
 258  *                     T first_value, T last_value, Incrementor increment);
 259 */
 260
 261 template <class BidirectionalIterator, class T>
 262   bool
 263   next_mapping(BidirectionalIterator first,
 264                BidirectionalIterator last,
 265                T first_value, T last_value)
 266 {
 267     if (last == first ) {
 268         return false;
 269     }
 270     do {
 271         if (++(*(--last)) != last_value) {
 272             return true;
 273         }
 274         *last = first_value;
 275     } while (last != first);
 276     return false;
 277 }
 278
 279 template <class BidirectionalIterator, class T, class Incrementer>
 280   bool
 281   next_mapping(BidirectionalIterator first,
 282                BidirectionalIterator last,
 283                T first_value, T last_value, Incrementer increment)
 284 {
 285     if (last == first ) {
 286         return false;
 287     }
 288     do {
 289         if (incrementer(*(--last)) != last_value) {
 290             return true;
 291         }
 292         *last = first_value;
 293     } while (last != first);
 294     return false;
 295 }
 296
 297 /* PROPOSED STANDARD EXTENSION:
 298  *
 299  * template<class BidirectionalIterator, class T>
 300  *   bool prev_mapping(BidirectionalIterator first,
 301  *                     BidirectionalIterator last,
 302  *                     T first_value, T last_value);
 303  *
 304  * template<class BidirectionalIterator, class T, class Decrementor>
 305  *   bool prev_mapping(BidirectionalIterator first,
 306  *                     BidirectionalIterator last,
 307  *                     T first_value, T last_value, Decrementor decrement);
 308  */
 309
 310 template <class BidirectionalIterator, class T>
 311   bool
 312   prev_mapping(BidirectionalIterator first,
 313                BidirectionalIterator last,
 314                T first_value, T last_value)
 315 {
 316     if (last == first) {
 317         return false;
 318     }
 319     --last_value;
 320     do {
 321         if (*(--last) != first_value) {
 322             --(*last);
 323             return true;
 324         }
 325         *last = last_value;
 326     } while (last != first);
 327     return true;
 328 }
 329
 330 template <class BidirectionalIterator, class T, class Decrementer>
 331   bool
 332   prev_mapping(BidirectionalIterator first,
 333                BidirectionalIterator last,
 334                T first_value, T last_value, Decrementer decrement)
 335 {
 336     if (last == first) {
 337         return false;
 338     }
 339     decrement(last_value);
 340     do {
 341         if (*(--last) != first_value) {
 342             decrement(*last);
 343             return true;
 344         }
 345         *last = last_value;
 346     } while (last != first);
 347     return true;
 348 }
 349
 350 /* PROPOSED STANDARD EXTENSION:
 351  *
 352  * template<class BidirectionalIterator, class T>
 353  *   bool next_combination_counts(BidirectionalIterator first,
 354  *                                BidirectionalIterator last);
 355  */
 356
 357 template <class BidirectionalIterator>
 358   bool
 359   next_combination_counts(BidirectionalIterator first,
 360                          BidirectionalIterator last)
 361 {
 362     BidirectionalIterator current = last;
 363     while (current != first && *(--current) == 0) {
 364     }
 365     if (current == first) {
 366         if (first != last && *first != 0)
 367             std::iter_swap(--last, first);
 368         return false;
 369     }
 370     --(*current);
 371     std::iter_swap(--last, current);
 372     ++(*(--current));
 373     return true;
 374 }
 375
 376 /* PROPOSED STANDARD EXTENSION:
 377  *
 378  * template<class BidirectionalIterator>
 379  *   bool prev_combination_counts(BidirectionalIterator first,
 380  *                                BidirectionalIterator last);
 381  */
 382
 383 template <class BidirectionalIterator>
 384 bool
 385 prev_combination_counts(BidirectionalIterator first,
 386                         BidirectionalIterator last)
 387 {
 388     if (first == last)
 389         return false;
 390     BidirectionalIterator current = --last;
 391     while (current != first && *(--current) == 0) {
 392     }
 393     if (current == last || current == first && *current == 0) {
 394         if (first != last)
 395             std::iter_swap(first, last);
 396         return false;
 397     }
 398     --(*current);
 399     ++current;
 400     if (0 != *last) {
 401         std::iter_swap(current, last);
 402     }
 403     ++(*current);
 404     return true;
 405 }
 406
 407 } // namespace boost
 408
 409 #endif // BOOST_ALGORITHM_COMBINATION_HPP