Code: Select all
// Our dedicated sort in range [firstMove, lastMove), first splits
// positive scores from ramining then order seaprately the two sets.
template<typename T>
inline void sort_moves(T* firstMove, T* lastMove, T** lastPositive)
{
T tmp;
T *p, *d;
d = lastMove;
p = firstMove - 1;
d->score = -1; // right guard
// Split positives vs non-positives
do {
while ((++p)->score > 0) {}
if (p != d)
{
while (--d != p && d->score <= 0) {}
tmp = *p;
*p = *d;
*d = tmp;
}
} while (p != d);
// Sort just positive scored moves, remaining only when we get there
insertion_sort<T, T*>(firstMove, p);
*lastPositive = p;
}
// in movepick.cpp (lines 146-149)
case PH_NONCAPTURES:
lastMove = generate<MV_NON_CAPTURE>(pos, moves);
score_noncaptures();
sort_moves(moves, lastMove, &lastGoodNonCapture);
return;
Code: Select all
#include <algorithm>
#include <functional>
// function object to test move scores (can be inlined when passed to algorithms)
template<typename T>
struct HasPositiveScore: public std::unary_function<T, bool>
{
bool operator()(T* move) const
{
return move->score > 0;
}
}
// Our dedicated sort in range [firstMove, lastMove), first splits
// positive scores from ramining then order seaprately the two sets.
template<typename T>
inline T partition_and_sort_positive_moves(T* firstMove, T* lastMove)
{
// Split positives vs non-positives
firstNonPositive = std::partition(firstMove, lastMove, HasPositiveScore);
// Sort just positive scored moves, remaining only when we get there
if (firstMove != firstNonPositive)
std::sort(firstMove, firstNonPositive);
return firstNonPositive;
}
// in movepick.cpp (lines 146-149)
case PH_NONCAPTURES:
lastMove = generate<MV_NON_CAPTURE>(pos, moves);
score_noncaptures();
lastGoodNonCapture = partition_and_sort_positive_moves(moves, lastMove);
return;
Finally, if one insists on stability for equal scored moves, std::stable_partition and std::stable_sort can take care of that (but they are more expensive). Of course, for debugging drop-in replacements for algorithms, stable functions are essential because you can test functional equivalence.
Rein
P.S. It literally took me 5 minutes to write this code after seeing the comments specifying the functional behavior. I have made no attempt to properly check the current implementation of sort_moves and insertion_sort. I bet it took a lot longer to make sure those functions were 100% correct.
aka put your personal judgment always before any written how-to rule.