#!/usr/bin/env perl

# xd3archival.pl - find smallest xdelta3 permutation
# ed <irc.rizon.net>, MIT-licensed, 2019-02-18, v0.2
# https://ocv.me/dev/

use strict;
use warnings FATAL => 'all';

use Storable qw(dclone);

my %isotab;
my %efftab;

sub lv1 {
	my $spent0 = $_[0];
	my %have0 = %{$_[1]};
	my %maptab0 = %{$_[2]};
	my $depth = $_[3];

	if ($depth == 5) {
		print %maptab0."\n";
	}
	
	die "2deep4me" unless $depth < 100;
	
	my @best;
	foreach my $f1 (keys %have0) {
		foreach my $f2 (keys %isotab) {
			if (exists $have0{$f2}) {
				next;
			}

			my %have = %{dclone(\%have0)};
			my %maptab = %{dclone(\%maptab0)};

			my $spent = $spent0 + $efftab{$f1}{$f2};
			$have{$f2} = 1;
			push @{$maptab{$f1}}, $f2;

			my $complete = 1;
			foreach my $fn (keys %isotab) {
				if (!exists $have{$fn}) {
					$complete = 0;
					last;
				}
			}

			if ($complete == 0) {
				my @rv = lv1(
					$spent, \%have, \%maptab, $depth+1);

				$spent = $rv[0];
				%have = %{$rv[1]};
				%maptab = %{$rv[2]};
			}
			
			if (@best == 0 || $best[0] > $spent) {
				@best = ($spent, \%have, \%maptab);
			}

			last;  # hack
		}
	}
	return @best;
}

my $fn_eff = "xd3archival.efficiency";
my $fn_iso = "xd3archival.isolist";
my $fh;

open($fh, '<:encoding(UTF-8)', $fn_eff)
	or die("could not open ".$fn_eff);

while (my $ln = <$fh>) {
	chomp $ln;
	my @la = split(/ /, $ln);
	$efftab{$la[1]}{$la[2]} = int($la[0]);
	$efftab{$la[2]}{$la[1]} = int($la[0]);
}
close($fh);

open($fh, '<:encoding(UTF-8)', $fn_iso)
	or die("could not open ".$fn_iso);

while (my $ln = <$fh>) {
	chomp $ln;
	my @aln = split(/ /, $ln);
	$isotab{$aln[1]} = int($aln[0]);
}
close($fh);

my @best;
foreach my $fn (keys %isotab) {
	print "trying with base iso ".$fn."\n";
	my $spent = $isotab{$fn};
	my %have;
	my %maptab;
	$have{$fn} = 1;
	my @rv = lv1(
		$spent, \%have, \%maptab, 0);
	
	$spent = $rv[0];
	%have = %{$rv[1]};
	%maptab = %{$rv[2]};
	
	print "-- ".$spent."\n";
	if (@best == 0 || $best[0] > $spent) {
		@best = ($spent, $fn, \%maptab);
	}
	
	last;  # hack
}

print "\nbest = ".$best[0]." bytes; ".$best[1]."\n";

my @seen = ($best[1]);
my %left = %{$best[2]};
while (%left != 0) {
	my $found = 1;
	foreach my $k (@seen) {
		if (grep{$k eq $_}(keys %left)) {  # orz
			$found = 0;
			foreach my $v (@{$left{$k}}) {
				push @seen, $v;
				print $efftab{$k}{$v}." spent;  ".$k."  >>  ".$v."\n";
			}
			delete $left{$k};
			last;
		}
	}
	if ($found == 1) {
		last;
	}
}

foreach my $k (keys %left) {
	foreach my $v (@{$left{$k}}) {
		print "UNLINKED:  ".$efftab{$k}{$v}." spent;  ".$k."  >>  ".$v."\n";
	}
}

