/*
 * Utility to convert overlapping Excellon drill hits into drill slots.
 * Copyright © 2018, 2021, 2023 Nick Bowler
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include <locale.h>

#include <getopt.h>
#include <gettext.h>
#include <localcharset.h>
#include <mbswidth.h>

#include <CNearTree.h>
#include <gerbv.h>

#include "options.h"
#include "help.h"
#include "xtra.h"
#include "copysym.h"

#if !ENABLE_NLS
#  undef ENABLE_NLS
#  define ENABLE_NLS 0
#endif

#define _(x) (gettext(x))

static const char *progname = "slotifier";
static unsigned verbose;

static void print_version(void)
{
	const char *copysign = copyright_symbol(locale_charset());

	puts(PACKAGE_STRING);
	printf("Copyright %s 2023 Nick Bowler.\n", copysign);
	puts("License GPLv3+: GNU GPL version 3 or any later version.");
	puts("This is free software: you are free to change and redistribute it.");
	puts("There is NO WARRANTY, to the extent permitted by law.");
}

static void print_usage(FILE *f)
{
	fprintf(f, _("Usage: %s [options] [-o filename] filename\n"), progname);
	if (f != stdout)
		fprintf(f, _("Try %s --help for more information.\n"),
		           progname);
}

static void print_help(const struct option *lopts)
{
	const struct option *opt;

	print_usage(stdout);

	puts(_("This is \"slotifier\": a tool to convert overlapping drill hits in Excellon\n"
	       "drill files to G85 drill slots."));
	putchar('\n');

	puts(_("Options:"));
	for (opt = lopts; opt->val; opt++) {
		struct lopt_help help;

		if (!lopt_get_help(opt, &help))
			continue;

		help_print_option(opt, help.arg, help.desc, 20);
	}
	putchar('\n');

	puts(_("For more information, see the slotifier(1) man page."));
	putchar('\n');

	/*
	 * TRANSLATORS: Please add *another line* indicating where users should
	 * report translation bugs.
	 */
	printf(_("Report bugs to <%s>.\n"), PACKAGE_BUGREPORT);
}

static void init_i18n(void)
{
	setlocale(LC_ALL, "");
	bindtextdomain(PACKAGE, LOCALEDIR);
	textdomain(PACKAGE);
}

static CNearTreeHandle build_search_tree(gerbv_image_t *drill)
{
	CNearTreeHandle t;
	gerbv_net_t *x;

	if (CNearTreeCreate(&t, 2, CNEARTREE_TYPE_DOUBLE|CNEARTREE_NORM_L2))
		return 0;

	/* Build a search tree from all the holes. */
	for (x = drill->netlist; x; x = x->next) {
		double xy[2] = { x->start_x, x->start_y };

		assert(x->aperture >= 0 && x->aperture < APERTURE_MAX);

		/* Skip things that aren't drill hits */
		if (!drill->aperture[x->aperture])
			continue;

		/* Holes are marked as "flashing"; otherwise it's an existing
		 * slot; skip it. */
		if (x->aperture_state != GERBV_APERTURE_STATE_FLASH)
			continue;

		if (CNearTreeInsert(t, xy, x)) {
			CNearTreeFree(&t);
			return 0;
		}
	}

	if (CNearTreeCompleteDelayedInsert(t)) {
		CNearTreeFree(&t);
		return 0;
	}

	return t;
}

static gerbv_aperture_type_t tool_type(gerbv_image_t *drill, int aperture)
{
	gerbv_aperture_t *tool = drill->aperture[abs(aperture)];

	return tool->type;
}

static double tool_radius(gerbv_image_t *drill, int aperture)
{
	gerbv_aperture_t *tool = drill->aperture[abs(aperture)];

	/* Half a mil slop to decisively include points on boundary. */
	return tool->parameter[0] / 2.0 + 0.0005;
}

static int holes_overlap(gerbv_image_t *drill, gerbv_net_t *a, gerbv_net_t *b)
{
	double d = hypot(a->start_x - b->start_x, a->start_y - b->start_y);

	return tool_radius(drill, a->aperture) >= d
	    || tool_radius(drill, b->aperture) >= d;
}

static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
                         CNearTreeHandle t)
{
	CVectorHandle group, tmp;
	int biggest_tool, ret = -1;
	double biggest_r;
	size_t i, j;

	/*
	 * Since we consider holes in order of decreasing size, the initial hole
	 * considered is by definition the biggest one we will find in a group.
	 */
	biggest_r = tool_radius(drill, (biggest_tool = hole->aperture));

	if (CVectorCreate(&group, sizeof (gerbv_net_t *), 10)) {
		fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
		return -1;
	}

	if (CVectorCreate(&tmp, sizeof (void *), 10)) {
		fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
		CVectorFree(&group);
		return -1;
	}

	/*
	 * Breadth-first nearest neighbour search of holes.  We negate the
	 * aperture to indicate which holes have been previously visited.
	 */
	CVectorAddElement(group, &hole);
	hole->aperture = -hole->aperture;

	for (i = 0; i < CVectorSize(group); i++) {
		double xy[2];

		CVectorGetElement(group, &hole, i);

		assert(tool_type(drill, hole->aperture) == GERBV_APTYPE_CIRCLE);
		assert(tool_radius(drill, hole->aperture) <= biggest_r);

		xy[0] = hole->start_x; xy[1] = hole->start_y;
		if (CNearTreeFindInSphere(t, biggest_r, 0, tmp, xy, 1) != 0) {
			/* We should always should find at least one hole! */
			fprintf(stderr, _("%s: fatal error searching holes\n"),
			                progname);
			goto err;
		}

		for (j = 0; j < CVectorSize(tmp); j++) {
			/* I don't know why, but CNearTree returns a list
			 * of pointers to its internal copies of pointers
			 * to the objects in the tree.  So we need this
			 * double indirection to get the actual hole. */
			gerbv_net_t *newhole;
			void *p;

			CVectorGetElement(tmp, &p, j);
			newhole = *(void **)p;

			if (newhole->aperture < 0)
				continue; /* already visited */

			if (holes_overlap(drill, hole, newhole)) {
				CVectorAddElement(group, &newhole);
				newhole->aperture = -newhole->aperture;
			}
		}
	}

	/* Compare each pair of matched points to find the longest slot. */
	if (CVectorSize(group) > 1) {
		int biggest_slot = 0;
		double bestlen = 0;

		for (i = 0; i < CVectorSize(group) - 1; i++) {
			CVectorGetElement(group, &hole, i);
			for (j = i+1; j < CVectorSize(group); j++) {
				gerbv_net_t *h2;
				double newlen;

				CVectorGetElement(group, &h2, j);
				newlen = hypot(hole->start_x - h2->start_x,
				               hole->start_y - h2->start_y);

				if (newlen > bestlen) {
					hole->stop_x = h2->start_x;
					hole->stop_y = h2->stop_y;
					bestlen = newlen;
					biggest_slot = i;
				}
			}
		}

		CVectorGetElement(group, &hole, biggest_slot);
		hole->aperture = biggest_tool;
		hole->aperture_state = GERBV_APERTURE_STATE_ON;

		if (verbose) {
			const char *fmt = ngettext(
				"%s: merged %zu hole into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
				"%s: merged %zu holes into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
				CVectorSize(group));

			fprintf(stderr, fmt, progname, CVectorSize(group),
					     hole->start_x, hole->start_y,
					     hole->stop_x, hole->stop_y);
		}
	} else {
		/* The only hole we found was our original one, restore
		 * initial state. */
		CVectorGetElement(group, &hole, 0);

		assert(hole->aperture < 0);
		hole->aperture = -hole->aperture;

		if (verbose > 1) {
			fprintf(stderr, _("%s: hole at (%.4f,%.4f) not merged\n"),
			                progname, hole->start_x, hole->start_y);
		}
	}

	ret = 0;
err:
	CVectorFree(&tmp);
	CVectorFree(&group);
	return ret;
}

/*
 * Order two holes by hole diameter.
 */
static gerbv_image_t *hsc_drill_data;
static int hole_size_cmp(const void *a_, const void *b_)
{
	gerbv_net_t * const *a = a_, * const *b = b_;
	gerbv_aperture_t *ta, *tb;

	ta = hsc_drill_data->aperture[abs(a[0]->aperture)];
	assert(ta->type == GERBV_APTYPE_CIRCLE);

	tb = hsc_drill_data->aperture[abs(b[0]->aperture)];
	assert(tb->type == GERBV_APTYPE_CIRCLE);

	if (ta->parameter[0] > tb->parameter[0])
		return -1;
	if (ta->parameter[0] < tb->parameter[0])
		return 1;
	return 0;
}

static void sort_holes_by_size(gerbv_image_t *drill, CVectorHandle work)
{
	hsc_drill_data = drill;
	qsort(work->array, work->size, work->elementsize, hole_size_cmp);
}

static int slotify(gerbv_image_t *drill)
{
	CVectorHandle holes, work;
	CNearTreeHandle t;
	int ret = 0;
	size_t i;

	t = build_search_tree(drill);
	if (!t) {
		fprintf(stderr, _("%s: failed to build search tree\n"),
		                progname);
		return -1;
	}

	CNearTreeObjects(t, &holes);
	if (!holes)
		goto err_free_tree;

	if (CVectorCreate(&work, sizeof (gerbv_net_t *), CVectorSize(holes))) {
		fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
		goto err_free_tree;
	}

	memcpy(work->array, holes->array, holes->size * holes->elementsize);
	work->size = holes->size;
	sort_holes_by_size(drill, work);

	for (i = 0; i < CVectorSize(work); i++) {
		gerbv_net_t *hole;

		CVectorGetElement(work, &hole, i);
		/* Skip holes we've already looked at */
		if (hole->aperture < 0)
			continue;
		if (hole->aperture_state == GERBV_APERTURE_STATE_ON)
			continue;

		if (verbose > 1) {
			fprintf(stderr, _("%s: checking hole at (%.4f,%.4f) for overlaps\n"),
			                progname, hole->start_x, hole->start_y);
		}

		if (combine_holes(drill, hole, t) < 0) {
			ret = -1;
			break;
		}
	}

	/* Clean out any holes we don't need anymore */
	for (i = 0; i < CVectorSize(holes); i++) {
		gerbv_net_t *hole;

		CVectorGetElement(holes, &hole, i);
		if (hole->aperture < 0)
			gerbv_image_delete_net(hole);
	}

	CVectorFree(&work);
err_free_tree:
	CNearTreeFree(&t);
	return ret;
}

static int do_cmdline(int argc, char **argv, const char **outfile)
{
	const char *sopts = SOPT_STRING;
	int opt;

	XTRA_PACKED_LOPTS(lopts);

	if (argc > 0)
		progname = argv[0];

	while ((opt = getopt_long(argc, argv, sopts, lopts, NULL)) != -1) {
		switch (opt) {
		case 'o':
			*outfile = optarg;
			break;
		case 'v':
			verbose++;
			break;
		case 'V':
			print_version();
			return 1;
		case 'H':
			print_help(lopts);
			return 1;
		default:
			print_usage(stderr);
			return -1;
		}
	}

	if (!argv[optind]) {
		fprintf(stderr, _("%s: error: must specify a filename\n"),
		                progname);
		print_usage(stderr);
		return -1;
	}

	if (optind + 1 < argc) {
		fprintf(stderr, _("%s: error: excess command-line arguments\n"),
		                progname);
		print_usage(stderr);
		return -1;
	}

	return 0;
}

int main(int argc, char **argv)
{
	const char *outfile = "/dev/stdout";
	gerbv_project_t *gp;
	gerbv_image_t *drill;
	int ret = 0;

	init_i18n();
	switch (do_cmdline(argc, argv, &outfile)) {
	case -1: return EXIT_FAILURE;
	case 1: return EXIT_SUCCESS;
	}

	gp = gerbv_create_project();
	if (!gp)
		return EXIT_FAILURE;

	gerbv_open_layer_from_filename(gp, argv[optind]);
	if (!gp->file[0]) {
		ret = EXIT_FAILURE;
		goto out;
	}

	drill = gp->file[0]->image;
	if (drill->layertype != GERBV_LAYERTYPE_DRILL) {
		fprintf(stderr, _("%s: %s: error: not a drill file\n"),
		                progname, argv[optind]);
		ret = EXIT_FAILURE;
		goto out;
	}

	if (slotify(drill) != 0) {
		ret = EXIT_FAILURE;
		goto out;
	}

	if (!gerbv_export_drill_file_from_image(outfile, drill, NULL))
		ret = EXIT_FAILURE;
out:
	gerbv_destroy_project(gp);
	return ret;
}