use bufio;
use crandom = crypto::random;
use endian;
use errors;
use fmt::*;
use fmt;
use fs;
use io;
use math::random;
use os;
use strconv;
use strings;
use sort;

use image;

fn read_uint(h: io::handle) uint = {
	let arr = bufio::scantok(h, ' ': u32: u8, '\n': u32: u8) as []u8;
	let string = strings::fromutf8(arr);
	return strconv::stou(string)!;
};

fn read(hn: io::handle, casenr: uint) bool = {
	bufio::scantok(hn, '\n': u32: u8) as []u8; // empty line
	let tc: uint = read_uint(hn);

	w = read_uint(hn);
	h = read_uint(hn);
	b = read_uint(hn);

	if (tc == casenr) {
		a = image::create(w, h, 0);
		assert(len(a) == h);
		assert(len(a[0]) == w);
	};
	for (let i = 0z; i < h; i += 1) {
		for (let j = 0z; j < w; j += 1) {
			if (tc == casenr) {
				a[i][j] = read_uint(hn);
			} else {
				read_uint(hn);
			};
		};
	};
	return tc == casenr;
};

fn distcmp(a: const *void, b: const *void) int = {
	let a = g[*(a: *size)].dist;
	let b = g[*(b: *size)].dist;
	return (a-b): int;
};

fn draw(hn: io::handle, img: image::image) void = {
	let cl: []image::color = [];
	image::pick_colors(&cl, b);
	image::write(hn, cl, img);
	assert(len(cl) == b);
	free(cl);
};

fn drawgraph(hn: io::handle) void = {
	let img = image::create(w, h, 0);
	defer image::finish(img);
	for (let r = 0z; r < h; r += 1) {
		for (let c = 0z; c < w; c += 1) {
			img[r][c] = g[ids[r][c]].col;
		};
	};
	draw(hn, img);
};

fn dbg(v: uint) void=  {
	for (let r = 0z; r < h; r += 1) {
		for (let c = 0z; c < w; c += 1) {
			if (ids[r][c] == v) {
				g[ids[r][c]].col = 0;
			};
		};
	};
};

export fn main() void = {
	let animate = false;
	let casenr = switch (len(os::args)) {
	case 2 =>
		yield strconv::stou(os::args[1]) as uint;
	case 4 =>
		assert(os::args[2] == "draw", "invalid argument");
		animate = true;
		yield strconv::stou(os::args[1]) as uint;
	case => abort("invalid argument");
	};

	// read
	bufio::scantok(os::stdin, '\n': u32: u8) as []u8; // header "Poplavljanje"
	bufio::scantok(os::stdin, '\n': u32: u8) as []u8; // number of tests
	for (!read(os::stdin, casenr)) void;

	// rng init
	let buf: [8]u8 = [0...];
	crandom::buffer(buf);
	rng = random::init(endian::begetu64(buf));

	// dsinit
	ids = image::create(w,h, -1);
	let n = buildgraph();
	bfs();
	for (let i = 0z; i < n; i += 1) {
		append(dists, i);
	};
	sort::sort(dists, size(size), &distcmp);
	assert(len(dists) != 0);

	if (animate) {
		animation(os::args[3]);
		return;
	};

	let opt: size = -1;
	printf("{}\nPoplavljanje\n\n", TOKEN)!;

	let c = copyg(g);
	let distcp: []size = alloc(dists...);
	let fctx = context { sol = [], curr = [], g = g, d = dists };
	for (true) {
		let ctx = ctx_copy(&fctx);
		defer ctx_finish(ctx);

		solve(ctx);

		if (len(ctx.sol) >= opt) continue;
		let img = fs::create(os::cwd, "img.ppm", 0o777, fs::flags::TRUNC, fs::flags::RDWR)!;
		drawgraph(img);
		io::close(img);
		opt = len(ctx.sol);
		assert(len(ctx.sol) != 0);
		fmt::printf("{}\n{}\n", casenr, len(ctx.sol))!;
		for (let i = 0z; i < len(ctx.sol) - 1; i += 1) {
			fmt::printf("{} ", ctx.sol[i])!;
		};
		fmt::printf("{}\n\n", ctx.sol[len(ctx.sol) - 1])!;
	};
};