//This was copied from VC++ STL library and
//extraneous code removed.
namespace nextpermutation
{
template<class _BidIt> inline
void reverse(_BidIt _First, _BidIt _Last)
{ // reverse elements in [_First, _Last)
for (; _First != _Last && _First != --_Last; ++_First)
swap(*_First, *_Last);
}
// TEMPLATE FUNCTION next_permutation
template<class _BidIt> inline
bool next_permutation(_BidIt _First, _BidIt _Last)
{ // permute and test for pure ascending, using operator<
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
return (false);
for (; ; )
{
// find rightmost element smaller than successor
_BidIt _Next1 = _Next;
// swap with rightmost element that's smaller, flip suffix
if (*--_Next < *_Next1)
{
_BidIt _Mid = _Last;
for (; !(*_Next < *--_Mid); )
;
swap(*_Next, *_Mid);
nextpermutation::reverse(_Next1, _Last);
return (true);
}
if (_Next == _First)
{ // pure descending, flip all
nextpermutation::reverse(_First, _Last);
return (false);
}
}
}
}
#include <list>
#include <iostream>
#include <ostream>
#include <strstream>
using namespace std;
typedef list<int> IntList;
#include "utx.h"
void print(ostream& os, IntList& list)
{
for(IntList::iterator it = list.begin(); it != list.end(); ++it)
{
os << (*it) << " ";
}
os << endl;
}
TEST(nextperm_1)
{
IntList list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
strstream s;
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(!nextpermutation::next_permutation(list.begin(), list.end()));
s << ends;
utxassert(s.str(),
"1 2 3 \n"
"1 3 2 \n"
"2 1 3 \n"
"2 3 1 \n"
"3 1 2 \n"
"3 2 1 \n");
}
TEST(nextperm_2)
{
IntList list;
list.push_back(1);
list.push_back(3);
list.push_back(2);
strstream s;
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
//note: this is the way the original STL code works.
//not sure if it is a bug or working as designed.
utxBoolAssert(!nextpermutation::next_permutation(list.begin(), list.end()));
print(s, list);
utxBoolAssert(nextpermutation::next_permutation(list.begin(), list.end()));
s << ends;
utxassert(s.str(),
"1 3 2 \n"
"2 1 3 \n"
"2 3 1 \n"
"3 1 2 \n"
"3 2 1 \n"
"1 2 3 \n"
);
}
|