1b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner//===----------------------------------------------------------------------===// 2b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// 3b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// The LLVM Compiler Infrastructure 4b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// 5b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// This file is dual licensed under the MIT and the University of Illinois Open 6b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// Source Licenses. See LICENSE.TXT for details. 7b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// 8b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner//===----------------------------------------------------------------------===// 9b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 10b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// <algorithm> 11b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 12b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// template<BidirectionalIterator Iter> 13b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// requires ShuffleIterator<Iter> 14b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// && LessThanComparable<Iter::value_type> 15b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// bool 16b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner// next_permutation(Iter first, Iter last); 17b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 18b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner#include <algorithm> 19b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner#include <cassert> 20b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 21b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner#include "test_iterators.h" 22b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 23b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner#include <cstdio> 24b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 25b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turnerint factorial(int x) 26b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner{ 27b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner int r = 1; 28b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner for (; x; --x) 29b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner r *= x; 30b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner return r; 31b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner} 32b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 33b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turnertemplate <class Iter> 34b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turnervoid 35b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turnertest() 36b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner{ 37b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner int ia[] = {1, 2, 3, 4, 5, 6}; 38b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner const int sa = sizeof(ia)/sizeof(ia[0]); 39b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner int prev[sa]; 40b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner for (int e = 0; e <= sa; ++e) 41b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner { 42b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner int count = 0; 43b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner bool x; 44b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner do 45b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner { 46b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner std::copy(ia, ia+e, prev); 47b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner x = std::next_permutation(Iter(ia), Iter(ia+e)); 48b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner if (e > 1) 49b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner { 50b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner if (x) 51b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner assert(std::lexicographical_compare(prev, prev+e, ia, ia+e)); 52b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner else 53b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner assert(std::lexicographical_compare(ia, ia+e, prev, prev+e)); 54b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner } 55b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner ++count; 56b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner } while (x); 57b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner assert(count == factorial(e)); 58b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner } 59b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner} 60b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner 61b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turnerint main() 62b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner{ 63b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner test<bidirectional_iterator<int*> >(); 64b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner test<random_access_iterator<int*> >(); 65b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner test<int*>(); 66b9a36c36f4b257de79bd656aefa7bfde40cedb0fDavid 'Digit' Turner} 67