/* -*- C++ -*-
 * Copyright ©2005 Hugo Mills <hugo@carfax.org.uk>
 *
 * This software is distributed under the terms of the GNU GPL v3
 * For more information on the GPL, see the file COPYING or 
 * visit http://www.gnu.org/
 *
 * This software is distributed without warranty
 */

#include "datablock.h"
#include "crossing.h"

#include <cstdlib>
#include <list>

// Sequence to search relative to a corner
const int search_corner_length = 16;
const Diff search_corner[] = {
	Diff(-1, -1), Diff(-1, -1, 1), Diff(-1, 0), Diff(-1, 0, 1),
	Diff(-1, 1), Diff(-1, 1, 2), Diff(0, 1), Diff(0, 1, 2),
	Diff(1, 1), Diff(1, 1, 3), Diff(1, 0), Diff(1, 0, 3),
	Diff(1, -1), Diff(1, -1, 0), Diff(1, 0), Diff(1, 0, 0)
};

// Sequence to search relative to an edge
const int search_edge_length = 7;
const Diff search_edge[][search_edge_length] = {
	{
		Diff(-1, 0),
		Diff(-1, 0, 1), Diff(-1, -1),
		Diff(-1, -1, 2), Diff(0, -1),
		Diff(0, -1, 3), Diff(0, 0)
	},
	{
		Diff(0, -1),
		Diff(0, -1, 2), Diff(1, -1),
		Diff(1, -1, 3), Diff(1, 0),
		Diff(1, 0, 0), Diff(0, 0)
	},
	{
		Diff(1, 0),
		Diff(1, 0, 3), Diff(1, 1),
		Diff(1, 1, 0), Diff(0, 1),
		Diff(0, 1, 1), Diff(0, 0)
	},
	{
		Diff(0, 1),
		Diff(0, 1, 0), Diff(-1, 1),
		Diff(-1, 1, 1), Diff(-1, 0),
		Diff(-1, 0, 2), Diff(0, 0)
	}
};

int main(int argc, char* argv[])
{
	DataBlock test("W100N40");
	Trace trace;
	int height = 20;
	std::list<Crossing> last;
	last.push_back(Crossing(-1, -1));
	last.push_back(Crossing(-1, -1));

	// Now go looking in nearby cells for the edges. The algorithm is
	// to start with a grid square and entrance side. Search
	// anti-clockwise round the square for a crossing point which
	// hasn't been used already, and move to that square, updating the
	// entrance side of the square to suit.
	while(true)
	{
		Crossing pos = test.next(height);
		if(pos == Crossing())
			break;
		// At this point, pos is the edge of a square that is
		// crossed by the contour
		
		// Start a new contour
		trace.push_back(Contour());
		Contour& contour = trace.back();
		contour.push_back(test.intercept(pos, height));
		
		// Follow this contour until we hit an edge or we come round
		// again
		while(true)
		{
			int offset;
			int seqlen;
			const Diff* seq;

			if(pos._isc)
			{
				seqlen = search_corner_length;
				seq = search_corner;

				for(offset = 0; offset < seqlen; offset++)
				{
					Crossing tmp = pos + seq[offset];
					if(tmp == last.front())
						break;
				}
				offset = (offset+1)%seqlen;
			}
			else
			{
				seqlen = search_edge_length;
				seq = search_edge[pos._d];
				offset = 0;
			}

			int i;
			for(i=0; i<seqlen; i++)
			{
				int j = (i + offset) % seqlen;
				Crossing seek = pos + seq[j];
				if(!test.valid(seek) || test.visited(seek)) continue;
				// Visit
				test.visit(seek);
				// Check
				if(test.crossed(seek, height))
				{
					contour.push_back(test.intercept(seek, height));
					last.push_back(seek);
					last.pop_front();
					std::cout << contour.back() << std::endl;
					pos = seek.opp();
					break;
				}
			}
			if(i == seqlen)	break;
		}
	}

	return EXIT_SUCCESS;
}