/* $Id: trisold.c,v 1.137 2024/04/26 19:12:58 kili Exp $ */
/*
 * Copyright (c) 2016, 2017 Matthias Kilian <kili@outback.escape.de>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <errno.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <sys/resource.h>
#include <sys/wait.h>

#include "canvas.h"
#include "map.h"
#include "moves.h"

static struct mv_cost_info *
next_mvci(struct map *m, struct mv_cost_info *mvci, int dd)
{
	int cpm;
	struct move *mv = mvci->mv;
	struct mv_cost *mvc = MVCI_C(mvci);
	static struct mv_cost_info res;

	cpm = m->cps ? mv_cpm(mv) : 0;

	if (!(mv = adj_mv(m, mv, 1, dd)) || !mv->valid)
		return NULL;

	/* In case we just touched a checkpoint, zero it out in the
	 * search mask of missing checkpoints.
	 */
	if ((res.i = findcost(mv, mvc->mcps & ~cpm)) < 0)
		return NULL;
	res.mv = mv;
	return &res;
}

/* Note: mvcis must point to an array of at least 9 elements */
static size_t
next_nc_mvcs(struct map *m, struct mv_cost_info *mvcip, struct mv_cost_info *mvcis)
{
	int dd;
	size_t mcount;

	for (mcount = 0, dd = 8; dd >= 0; dd--) {
		struct mv_cost_info *nmvcip = next_mvci(m, mvcip, dd);
		if (!nmvcip)
			continue;
		mvcis[mcount++] = *nmvcip;
	}
	return mcount;
}

/* Same comparision as in map.c: cost, y, x, dy, dx (in this order).
 * While sorting by cost would be enough, we want some reproducible
 * order to get the same results for equivalent algorithms.
 */
static int
cmp_mvci_cyxdydx(const void *a, const void *b)
{
	int d;
	const struct mv_cost_info *mvci1 = (const struct mv_cost_info *) a;
	const struct mv_cost_info *mvci2 = (const struct mv_cost_info *) b;

	if ((d = MVCI_C(mvci1)->dist - MVCI_C(mvci2)->dist))
		return d;
	if ((d = mvci1->mv->y - mvci2->mv->y))
		return d;
	if ((d = mvci1->mv->x - mvci2->mv->x))
		return d;
	if ((d = mvci1->mv->dy - mvci2->mv->dy))
		return d;
	return mvci1->mv->dx - mvci2->mv->dx;
}

static int rand_from_n(int n)
{
	return (long) --n * rand() / RAND_MAX;
}

/* Return the number of cheapest mvcis from the possibly larger number
 * (given in mcount) of mvcis. mcount must be > 0.
 */
static
size_t cheap_mvci_count(struct mv_cost_info *mvcis, size_t mcount)
{
	size_t n;

	for (n = 1; n < mcount; n++)
		if (MVCI_C(mvcis + n)->dist != MVCI_C(mvcis + n - 1)->dist)
			break;
	return n;
}

static void
drawroute(struct map *m)
{
	struct canvas *cv;
	struct mv_cost_info *mvcis, mvci;
	size_t mcount;

	if(!(cv = drawmap(m))) {
		fprintf(stderr, "could not create %d/%d canvas",
			m->w, m->h);
		return;
	}

	if (!(mvcis = find_best_start_mvcs(m, &mcount))) {
		fprintf(stderr,
			"%s: could not find best start move costs\n",
			m->fname);
		return;
	}

	/* We want some pseudo-random but reproducible selection of
	 * moves with the same costs.
	 * On systems other than OpenBSD, srand() should be used instead
	 * of srand_deterministic().
	 */
	srand_deterministic(42);

	/* This already contains only the cheapest mvcis, so we can just
	 * use mcount as the upper bound.
	 */
	mvci = mvcis[rand_from_n(mcount)];
	free(mvcis);
	while (1) {
		struct mv_cost_info nmvcis[9];
		struct move *mv = mvci.mv;

		drawmove(cv, mv->x, mv->y, mv->dx, mv->dy);
		if (MVCI_C(&mvci)->dist == 1 || !(mcount = next_nc_mvcs(m, &mvci, nmvcis)))
			break;
		qsort(nmvcis, mcount, sizeof(*nmvcis), cmp_mvci_cyxdydx);
		/* Only consider the cheapest mvcis. */
		mcount = cheap_mvci_count(nmvcis, mcount);
		mvci = nmvcis[rand_from_n(mcount)];
	}
	printcanvas(cv);
	puts("");
	freecanvas(cv);
}

void
dump_startcosts(struct map *m)
{
	struct move *mv;
	struct mv_cost_info *mvcis;
	size_t mcount, h, i;

	if (!(mvcis = find_best_start_mvcs(m, &mcount)))
		return;

	/* Accumulate over all moves with minimal distance from the same
	 * start point.
	 * A more verbose mode (printing start point and next point) may
	 * be re-added later.
	 */
	for (h = i = 0; i < mcount; i++) {
		mv = mvcis[h].mv;
		if (mvcis[i].mv->x == mv->x && mvcis[i].mv->y == mv->y)
			continue;
		printf("%d/%d (%zd):\t%d\n", mv->x, mv->y, i - h,
		       MVCI_C(mvcis + h)->dist);
		h = i;
	}
	mv = mvcis[h].mv;
	printf("%d/%d (%zd):\t%d\n", mv->x, mv->y, i - h,
	       MVCI_C(mvcis + h)->dist);
	free(mvcis);
}

static void
dump_dnfs(struct map *m)
{
	int d, x, y;

	for (y = 0; y < m->h; y++)
		for (x = 0; x < m->w; x++)
			if (d = m->dnfs[y * m->w + x])
				printf("%d/%d:\t%d\n", x, y, d);
}

static void
test_map(int startcosts, int dumpmoves, int showroute, int showstats,
	 int showdnfs, int nocps, char *fname)
{
	int w = 0, h = 0;
	int dx_max, dy_max;
	long vcount;
	double utm, stm, utm2, stm2;
	struct map_stat st;
	FILE *f;
	struct map *m;
	struct rusage ru0, ru1, ru2;

	if (!(f = fopen(fname, "r"))) {
		perror(fname);
		return;
	}

	if (showstats && getrusage(RUSAGE_SELF, &ru0)) {
		perror(fname);
		fclose(f);
		return;
	}

	m = readmap(f, fname, showstats ? &st : NULL);
	fclose(f);

	if (!m)
		return;

	if (nocps)
		m->cps = 0;

	w = m->w;
	h = m->h;
	if ((vcount = calc_moves(m)) == -1) {
		perror(fname);
		return;
	}

	if (showstats && getrusage(RUSAGE_SELF, &ru1)) {
		perror(fname);
		return;
	}

	if ((startcosts || showroute) && calc_costs(m)) {
		perror(fname);
		return;
	}

	if (showstats && getrusage(RUSAGE_SELF, &ru2)) {
		perror(fname);
		return;
	}

	if (dumpmoves)
		dump_moves(m);

	if (showstats) {
		dx_max = st.dx_max;
		dy_max = st.dy_max;

		utm = ru2.ru_utime.tv_sec - ru0.ru_utime.tv_sec;
		utm += (ru2.ru_utime.tv_usec - ru0.ru_utime.tv_usec) / 1000000.0;
		stm = ru2.ru_stime.tv_sec - ru0.ru_stime.tv_sec;
		stm += (ru2.ru_stime.tv_usec - ru0.ru_stime.tv_usec) / 1000000.0;
		utm2 = ru2.ru_utime.tv_sec - ru1.ru_utime.tv_sec;
		utm2 += (ru2.ru_utime.tv_usec - ru1.ru_utime.tv_usec) / 1000000.0;
		stm2 = ru2.ru_stime.tv_sec - ru1.ru_stime.tv_sec;
		stm2 += (ru2.ru_stime.tv_usec - ru1.ru_stime.tv_usec) / 1000000.0;

		printf("%s: %d x %d, "
		       "d_max: %d x %d, "
		       "v_max: %.2f, "
		       "checkpoints: %03x\n"
		       "first real max: (%d x %d) / (%d x %d), v: %.2f\n"
		       "first valid max: (%d x %d) / (%d x %d), v: %.2f\n"
		       "%lu total, %lu real, %ld valid moves, "
		       "max_mc: %lu (%d x %d)\n"
		       "%lu costs, %lu unresolved start moves\n"
		       "usr: %.2f, sys: %.2f, costs-usr: %.2f, costs-sys %.2f, maxrss: %ld\n",
		       fname, w, h,
		       dx_max, dy_max,
		       sqrt(dx_max * dx_max + dy_max * dy_max),
		       m->cps,
		       st.max1r_x, st.max1r_y, st.max1r_dx, st.max1r_dy, st.max1r_v,
		       st.max1v_x, st.max1v_y, st.max1v_dx, st.max1v_dy, st.max1v_v,
		       st.tcount, st.rcount, vcount,
		       st.max_mc, st.max_mc_x, st.max_mc_y,
		       st.ccount, st.ucount,
		       utm, stm, utm2, stm2, ru2.ru_maxrss);
	}

	if (showdnfs)
		dump_dnfs(m);

	if (startcosts) {
		if (!showstats)
			printf("\n%s: %d x %d\n", fname, w, h);
		dump_startcosts(m);
	}

	if (showroute)
		drawroute(m);

	freemap(m);
}

static void
usage()
{
	fputs("usage: trisold [-cdfnprs] mapfile ...\n", stderr);
	exit(EXIT_FAILURE);
}

int
main(int argc, char *argv[])
{
	extern char *optarg;

	int c_flag, d_flag, f_flag, n_flag, p_flag, r_flag, s_flag, ch;

	c_flag = f_flag = d_flag = n_flag = p_flag = r_flag = s_flag = 0;

	while((ch = getopt(argc, argv, "cdfnprs")) != -1)
		switch (ch) {
		case 'c':
			c_flag = 1;
			break;
		case 'd':
			d_flag = 1;
			break;
		case 'f':
			f_flag = 1;
			break;
		case 'n':
			n_flag = 1;
			break;
		case 'p':
			p_flag = 1;
			break;
		case 'r':
			r_flag = 1;
			break;
		case 's':
			s_flag = 1;
			break;
		default:
			usage();
		}

	argc-= optind;
	argv += optind;

	if (argc == 0)
		usage();

	/* No flag means -r and -s. */
	if (!(c_flag || d_flag || n_flag || r_flag || s_flag))
		r_flag = s_flag = 1;

	/* Forking is pointless if there's only one map to process. */
	if (argc == 1)
		f_flag = 1;

	while (argc--) {
		pid_t pid;
		char *mapname = *argv++;

		if (f_flag || !(pid = fork())) {
			setproctitle("%s", mapname);
			test_map(c_flag, d_flag, r_flag, s_flag,
				 n_flag, p_flag, mapname);
			if (!f_flag)
				exit(0);
		}
		if (f_flag)
			continue;

		if (pid == -1) {
			perror(mapname);
			continue;
		}
		if ((pid = waitpid(pid, NULL, 0)) == -1)
			perror(mapname);
		else if (!pid)
			fprintf(stderr, "%s: child disappeared\n", mapname);
	}

	return 0;
}