I cleaned up the code a bit.
#include <algorithm> // for std::swap
#include <vector> // for size_t
template<typename IntType>
class LeoNum
{
public:
LeoNum(): cur(1), prev(1) { }
LeoNum(IntType c, IntType p) : cur(c), prev(p) { }
void go_up() { *this = LeoNum<IntType>(cur+prev+1, cur); }
void go_down() { *this = LeoNum<IntType>(prev, cur-prev-1); }
IntType value() const { return cur; }
IntType prevvalue() const { return prev; }
IntType get_gap() const { return value() - prevvalue(); }
private:
IntType cur, prev;
};
namespace
{
template<typename PtrT, typename IntType>
void sift(PtrT array, IntType root, LeoNum<IntType> b)
{
// Sifts up the root of the stretch in question.
IntType root2;
while(b.value() >= 3)
{
if(array[root - b.get_gap()] >= array[root - 1])
root2 = root - b.get_gap();
else
{ root2 = root-1; b.go_down(); }
if(array[root] >= array[root2]) break;
std::swap(array[root], array[root2]);
root=root2;
b.go_down();
}
}
template<typename PtrT, typename IntType, typename Ptype>
void trinkle_if_adjacent_stretches_are_trusty(PtrT array, IntType root, Ptype p, LeoNum<IntType> b)
{
if(array[root - b.prevvalue()] >= array[root])
{
std::swap(array[root], array[root - b.prevvalue()]);
trinkle(array, root - b.prevvalue(), p, b);
}
}
template<typename PtrT, typename IntType, typename Ptype>
void trinkle(PtrT array, IntType root, Ptype p, LeoNum<IntType> b)
{
// Trinkles the roots of the stretches of a given array and root.
// p describes a "standard concatenation's codification
while(p != 0)
{
while(p % 2 == 0) { p >>= 1; b.go_up(); } // p bitmask is xxxxx0
--p;
if(!p || array[root] >= array[root - b.value()]) break;
if(b.value() == 1)
{ std::swap(array[root], array[root - b.value()]); root -= b.value(); }
else if(b.value() >= 3)
{
IntType root2 = root - b.get_gap(), root3 = root - b.value();
if(array[root-1] >= array[root2])
{ root2 = root-1; p <<= 1; b.go_down(); }
if(array[root3] >= array[root2])
{ std::swap(array[root], array[root3]); root = root3; }
else
{ std::swap(array[root], array[root2]); root = root2; b.go_down(); break; }
}
}
sift(array, root, b);
}
}
template<typename PtrT, typename IntType, typename Ptype>
void smoothsort(PtrT array, IntType count)
{
if(!array || !count) return;
Ptype p = 1;
LeoNum<IntType> b(1,1);
// p describes a "standard concatenation's codification
for(IntType q=0; ++q < count; ++p)
if(p % 8 == 3) // p bitmask is xxxx011
{
sift(array, q-1, b);
b.go_up();
b.go_up();
p >>= 2;
}
else if(p % 4 == 1) // p bitmask is xxxxx01
{
if(q + b.prevvalue() < count)
sift(array, q-1, b);
else
trinkle(array, q-1, p, b);
for(;;)
{
p <<= 1;
b.go_down();
if(b.value() <= 1) break;
}
}
trinkle(array, count-1, p, b);
while(count > 1)
{
--p; --count;
if(b.value() == 1)
while(p % 2 == 0) { p >>= 1; b.go_up(); } // p bitmask is xxxxx0
else if(b.value() >= 3)
{
if(p != 0)
trinkle_if_adjacent_stretches_are_trusty(array, count - b.get_gap(), p, b);
b.go_down(); p <<= 1; ++p;
trinkle_if_adjacent_stretches_are_trusty(array, count-1, p, b);
b.go_down(); p <<= 1; ++p;
}
}
}
template<typename RandomIterator>
void smoothsort(RandomIterator begin, RandomIterator end)
{
typedef size_t ptrdiff_t ;
smoothsort<RandomIterator, ptrdiff_t, unsigned long long>
(begin, ptrdiff_t(end-begin));
}
Still compiles and works, has less obnoxious operator overloads and less _ characters.
And is shorter and therefore less demanding on human memory, and thus easier to understand.
Though its working still defies me.
I can't even find the word "trinkle" in a dictionary.