#include <cstdlib>
#include <bitset>
#include <string>
#include <algorithm>
#include <ctime>
#include <iostream>
using namespace std;
typedef unsigned int DEFTYPE; // Default data type (should be integral types)
size_t constexpr DEFBEADS = 256U; // Default no. of beads (per row)
template<typename Type=DEFTYPE, size_t Beads=DEFBEADS>
class BeadSort
{
public:
enum class Order : unsigned int { ascending, descending };
private:
Order order;
bitset<Beads>* beads;
typedef typename bitset<Beads>::reference bead;
auto beadsort (size_t const, Type const) -> void;
auto freefall (bead, bead) -> bead const;
public:
explicit BeadSort (void);
auto sort (Type [], size_t const, Order const = Order::ascending) -> void;
~BeadSort (void);
// Make objects of this class non-copyable
BeadSort (BeadSort const&) = delete;
BeadSort& operator = (BeadSort const&) = delete;
};
// Disallow floating-point data types by partial template specialization
template<size_t Beads> class BeadSort<float, Beads> { };
template<size_t Beads> class BeadSort<double, Beads> { };
template<size_t Beads> class BeadSort<long double, Beads> { };
// Class default constructor
template<typename Type, size_t Beads>
BeadSort<Type, Beads>::BeadSort (void) : order(Order::ascending), beads(nullptr) { return; }
// Sort array 'arr' of size 'size' in type 'Type' into 'order' order
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::sort (Type arr[], size_t const size, Order const order) -> void
{
Type const minnum = *min_element(arr, arr + size);
this->order = order;
this->beads = new(nothrow) bitset<Beads>[size];
if (beads)
{ // Optimize, also ensure all nos. are non -ve
transform(arr, arr + size, arr,
[minnum](Type const n) -> Type const { return n - minnum; });
// Turn nos. into beads
transform(arr, arr + size, beads,
[](Type const n) -> bitset<Beads> { return bitset<Beads>(string((size_t)n, '1')); });
// Sort array by bead sort
beadsort(size, *max_element(arr, arr + size));
// Turn beads into nos.
transform(beads, beads + size, arr,
[](bitset<Beads> const& n) -> Type const { return (Type)n.count(); });
// Restore the nos. to original
transform(arr, arr + size, arr,
[minnum](Type const n) -> Type const { return n + minnum; });
delete [] beads;
}
else // Abort on fatal error
cerr << "Memory allocation failure." << endl, exit(EXIT_FAILURE);
return;
}
// Implement the beadsort algorithm
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::beadsort (size_t const size, Type const maxnum) -> void
{
size_t const totalrows = size - 1;
size_t const totalcols = (size_t)maxnum;
bool const ascending = order == Order::ascending; // Sort in ascending order?
size_t nextrow[totalcols]; // Point to next row where to start looking for a bead
fill(nextrow, nextrow + totalcols, (size_t)1); // Start looking in 2nd row of each column
for (size_t thisrow = 0, thatrow = 0; thisrow < totalrows; ++thisrow)
for (size_t curcol = 0; curcol < totalcols; ++curcol)
if (!beads[thisrow][curcol] ^ ascending) // Is this a blank?
for (thatrow = nextrow[curcol]; thatrow <= totalrows; ++thatrow)
if (beads[thatrow][curcol] ^ ascending) // Is that a bead?
{ // Found a bead in that row, so let it fall freely to this row
freefall(beads[thatrow][curcol], beads[thisrow][curcol]);
nextrow[curcol] = thatrow + 1;
break; // Next column
}
else
++nextrow[curcol];
else
++nextrow[curcol];
return;
}
// Imitate the free fall of a bead
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::freefall (bead from, bead to) -> bead const
{
return to = ~from.flip();
}
// Class destructor
template<typename Type, size_t Beads>
BeadSort<Type, Beads>::~BeadSort (void) { return; }
// Generate a random no. in the range [0, Beads)
template<typename Type, size_t Beads>
auto random (void) -> Type const
{
return (Type)((size_t)rand() % Beads);
}
// Conduct a test case
template<typename Type=DEFTYPE, size_t Beads=DEFBEADS>
auto testcase (size_t const size, typename BeadSort<Type, Beads>::Order order,
Type const offset) -> void
{
char const static* const orders[] = {"ascending", "descending"};
Type arr[size];
BeadSort<Type, Beads> beadsort;
// Generate test case at random
generate(arr, arr + size, random<Type, Beads>);
// Apply optional offset to nos.
transform(arr, arr + size, arr, [offset](Type const n) { return n + offset; });
// Show unsorted list
for_each(arr, arr + size, [](Type const n) { cout << ' ' << n; }), cout << endl;
// Sort the list
beadsort.sort(arr, size, order);
cout << "sorted in " << orders[(size_t)order] << " order:" << endl;
// Show sorted list
for_each(arr, arr + size, [](Type const n) { cout << ' ' << n; }), cout << endl << endl;
return;
}
auto main (int const argc, char const* const* const argv) -> int
{
srand((unsigned int)time(nullptr));
// Case 1: sort 10 unsigned integers in descending order
testcase<>(10, BeadSort<>::Order::descending, 0U);
// Case 2: sort 12 signed integers in ascending order
testcase<int>(12, BeadSort<int>::Order::ascending, -random<int, 100>());
// Case 3: sort 15 uppercase letters in ascending order
testcase<char, 26>(15, BeadSort<char, 26>::Order::ascending, 'A');
return EXIT_SUCCESS;
}
/********* Sample output **********\
208 248 136 106 0 188 129 250 37 13
sorted in descending order:
250 248 208 188 136 129 106 37 13 0
8 -22 0 -6 13 -64 20 64 -12 31 -9 -46
sorted in ascending order:
-64 -46 -22 -12 -9 -6 0 8 13 20 31 64
W H N X R A H Z P U O P B M P
sorted in ascending order:
A B H H M N O P P P R U W X Z
\**********************************/
