The Hanoi Tower Sort Algorithm

hanoi.cpp

#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>

typedef std::deque<int> stack;
void move_top1(stack& from, stack& to, stack& spare);

int top(const stack& o)
{
	if (o.empty())
		return INT_MAX;
	else
		return o.front();
}

void dump(const stack& o)
{
	printf("%p:\n", &o);
	for (stack::const_iterator it = o.begin(); it != o.end(); ++it)
		printf("\t%d\n", *it);
}

void move(stack& from, stack& to)
{
	printf("%d: %p -> %p\n", from.front(), &from, &to);
	assert(top(from) < top(to));
	to.push_front(from.front());
	from.pop_front();
}

void move_top(int cut, stack& from, stack& to, stack& spare)
{
	int sz = -1;

	for (stack::iterator it = from.begin(); it != from.end() && *it < cut; ++it)
		sz = *it;
	if (sz == -1)
		return;
	move_top(sz, from, spare, to);
	move_top1(from, to, spare);
	move_top(sz, spare, to, from);
}

void move_top1(stack& from, stack& to, stack& spare)
{
	if (from.empty())
		return;
	if (top(from) < top(to))
		move(from, to);
	else {
		move_top(top(from), to, spare, from);
		move(from, to);
	}
}

void move_all(stack& from, stack& to, stack& spare)
{
	while (!from.empty())
		move_top1(from, to, spare);
	if (!spare.empty())
		move_top(spare.back() + 1, spare, to, from);
}

int main()
{
	const int N = 6;
	int o[N];
	int s[N];

	for (int i = 0; i < N; ++i)
		o[i] = s[i] = i + 1;

	do {
		stack from(s, s + N), to, spare;

		printf("==================================\n");
		move_all(from, to, spare);

		assert(from.empty());
		assert(spare.empty());
		assert(std::equal(o, o + N, to.begin()));

		dump(from);
		dump(to);
		dump(spare);
	} while (std::next_permutation(s, s + N));
}