patience sort

Implementation of patience sorting algorithm.

/**

* Patience sort algorithm as per Aldous and Diaconis,

* using binary search to select the leftmost heap for a new card.

* Compares cards using operator<

*

* TableType requirements

* -# whatever lower_bound needs

* -# begin(), end(): ForwardIterator of piles

*

* PileType requirements

* -# default constructible

* -# constructible from a single card const reference

* typedef typename PileType::value_type card_type;

* -# push_back(const card_type&)

* -# assignable, lightweight on a singleton pile

* -# whatever lower_bound needs

* -# back() implemented or an

appropriate pile_less specialization

*/

template <>

void patience_sort

(TableType& table, InputIterator first,

InputIterator last)

{

typedef PileType pile_type;

typedef typename PileType::value_type card_type;

typedef TableType table_type;

typedef typename table_type::iterator iterator;

while (first != last) {

pile_type new_pile(*first); // read *first only once! (input iterator)

// find the leftmost heap with the top card greater

// than *first , to push *first on it

iterator pile_p = std::lower_bound(

table.begin(), table.end(), new_pile,

pile_less() );

if (pile_p != table.end()) {

pile_p->push_back(new_pile.back());

}

// ...or allocate a new heap on the

right with *first

else {

table.push_back(new_pile);

}

first++;

}

}