<?
/* Copyright (c) Rik Snel 2011, license GNU AGPLv3 */

/* Koppeling met momsched, de C-solver (met nauty) die bepaalt of een
 * (gedeeltelijk) rooster nog af te maken is, en in welke momenten een
 * toets geplaatst mag worden.
 *
 * Het pad naar de binary staat in $momsched_bin (config.php), standaard
 * /usr/local/bin/momsched.
 *
 * Invoer van de solver: de toetsen zoals get_toetsen_from_db ze maakt
 * (dus al zonder buiten beschouwing gelaten toetsen en met samengevoegde
 * toetsen onder hun groepsnaam), de momenten van get_moments (met de
 * conflictlijst die daar met 20% tijdverlenging en 5 minuten wisseltijd
 * wordt berekend) en het rooster van get_rooster. Een toets past alleen in
 * een moment met precies dezelfde duur (zoals in get_bad_colors2).
 *
 * De solver kent toetsen en momenten alleen als getallen: toets i (vanaf 1)
 * is de i-de toets in $toetsen, momenten gaan als moment_id. */

// maak invoer voor momsched; $index[naam] = nummer van de toets
// de plaatsing van toets $zonder (naam) uit het rooster wordt genegeerd
function momsched_input($toetsen, $moments, $rooster, &$index, $zonder = NULL) {
	$index = array();
	$in = 'M '.count($moments)."\n";
	$over = array();
	foreach ($moments as $moment_id => $info) {
		$in .= "$moment_id {$info['duur']}\n";
		foreach (explode(',', $info['conflict']) as $conflict) {
			if ($conflict > $moment_id) $over[] = "$moment_id $conflict";
		}
	}
	$in .= 'O '.count($over)."\n".implode("\n", $over)."\n";

	// toetsen zonder inschrijvingen (die alleen nog in het rooster
	// staan) doen niet mee
	$tests = '';
	foreach ($toetsen as $naam => $info) {
		if (!isset($info['duur'])) continue;
		$index[$naam] = count($index) + 1;
		$tests .= "{$index[$naam]} {$info['duur']}\n";
	}
	$in .= 'T '.count($index)."\n".$tests;

	// elke buren-relatie wordt een 'leerling' met twee toetsen
	$enroll = array();
	foreach ($index as $naam => $nr) {
		foreach ($toetsen[$naam]['neighbors'] as $buur => $aantal) {
			if (!isset($index[$buur]) || $index[$buur] < $nr) continue;
			$leerling = count($enroll)/2 + 1;
			$enroll[] = "$leerling $nr";
			$enroll[] = "$leerling {$index[$buur]}";
		}
	}
	$in .= 'E '.count($enroll)."\n".implode("\n", $enroll)."\n";

	$placed = array();
	foreach ($index as $naam => $nr) {
		if ($naam === $zonder || !isset($rooster[$naam])) continue;
		// een moment dat niet meer bestaat, telt niet als plaatsing
		if (!isset($moments[$rooster[$naam]])) continue;
		$placed[] = "$nr {$rooster[$naam]}";
	}
	$in .= 'A '.count($placed)."\n".implode("\n", $placed)."\n";

	return $in;
}

// draai momsched, geeft array(exitcode, regels uitvoer)
function momsched_run($in, $args) {
	global $momsched_bin;
	$bin = isset($momsched_bin)?$momsched_bin:'/usr/local/bin/momsched';

	$proc = proc_open(array_merge(array($bin), $args), array(
		0 => array('pipe', 'r'),
		1 => array('pipe', 'w'),
		2 => array('pipe', 'w')), $pipes);
	if (!is_resource($proc)) error_system("kan $bin niet starten");
	fwrite($pipes[0], $in);
	fclose($pipes[0]);
	$out = stream_get_contents($pipes[1]);
	$err = stream_get_contents($pipes[2]);
	fclose($pipes[1]);
	fclose($pipes[2]);
	$ret = proc_close($proc);
	if ($ret == 2 || $ret > 3) error_system("momsched faalt ($ret): $err");

	$lines = array();
	foreach (explode("\n", trim($out)) as $line) {
		if ($line === '') continue;
		$lines[] = explode(' ', $line);
	}
	return array($ret, $lines);
}

// vertaal regels van de solver terug naar toetsnamen
function momsched_namen($fields, $index) {
	$namen = array_flip($index);
	$ret = array();
	foreach ($fields as $nr) $ret[] = $namen[$nr];
	return $ret;
}

// in welke momenten mag toets $naam, gegeven de rest van het rooster?
// geeft array('consistent' => true/false, 'ok' => array(0, moment_ids),
// 'nak' => array(moment_ids)), 0 is het vlak 'te roosteren'
function momsched_allowed($toetsen, $moments, $rooster, $naam) {
	$in = momsched_input($toetsen, $moments, $rooster, $index, $naam);
	list($ret, $lines) = momsched_run($in, array('-q', '-t', $index[$naam]));

	$consistent = true;
	$allowed = array();
	foreach ($lines as $f) {
		if ($f[0] == 'inconsistent') $consistent = false;
		else if ($f[0] == 'allowed') $allowed = array_flip(array_slice($f, 2));
	}
	// ret == 3: zoekgrens bereikt, alleen bewezen momenten zijn ok

	$result = array('ok' => array(0), 'nak' => array());
	if (!$consistent) $result = array('consistent' => 'false') + $result;
	foreach ($moments as $moment_id => $info) {
		if ($consistent && isset($allowed[$moment_id])) $result['ok'][] = $moment_id;
		else $result['nak'][] = $moment_id;
	}
	return $result;
}

// is het rooster consistent en af te maken?
// geeft array('status' => 'ok'|'INCONSISTENT'|'CONSISTENT BUT NOT SOLVABLE'
// |'ONBESLIST', 'toetsen' => array(namen van betrokken toetsen))
// bij 'ok' staat in 'oplossing' een complete roostering (naam => moment_id)
function momsched_status($toetsen, $moments, $rooster) {
	$in = momsched_input($toetsen, $moments, $rooster, $index);
	list($ret, $lines) = momsched_run($in, array());

	$res = array('status' => 'ok', 'toetsen' => array(), 'oplossing' => array());
	$namen = array_flip($index);
	foreach ($lines as $f) {
		switch ($f[0]) {
		case 'inconsistent':
			$res['status'] = 'INCONSISTENT';
			$res['toetsen'][] = $namen[$f[1]];
			break;
		case 'infeasible':
		case 'unknown':
			if ($res['status'] == 'ok') $res['status'] =
				($f[0] == 'infeasible')?'CONSISTENT BUT NOT SOLVABLE':'ONBESLIST';
			$res['toetsen'] = array_merge($res['toetsen'],
				momsched_namen(array_slice($f, 1), $index));
			break;
		default:
			$res['oplossing'][$namen[$f[0]]] = $f[1];
		}
	}
	if ($res['status'] != 'ok') $res['oplossing'] = array();
	return $res;
}

// minimaal aantal kleuren per collectie, als elke toets in elk moment past
// en momenten niet overlappen (de roostergraaf): k = 1, 2, ... identieke
// momenten tot elke collectie oplosbaar is; collecties die al opgelost
// zijn, gaan niet opnieuw naar de solver
// $kleur[naam] = kleur van de toets in een oplossing (0, 1, ...)
// $nodig[naam] = benodigd aantal kleuren van de collectie van de toets,
// of -k als de zoekgrens bereikt werd bij k kleuren (onbeslist)
function momsched_kleuren($toetsen, &$kleur, &$nodig, $zoekgrens = 50000000) {
	$kleur = array();
	$nodig = array();
	$open = array();
	foreach ($toetsen as $naam => $info) {
		if (!isset($info['neighbors'])) continue;
		$open[$naam] = $info;
		$open[$naam]['duur'] = 1;
	}
	for ($k = 1; count($open); $k++) {
		$moments = array();
		for ($i = 1; $i <= $k; $i++)
			$moments[$i] = array('duur' => 1, 'conflict' => "$i");
		$in = momsched_input($open, $moments, array(), $index);
		list($ret, $lines) = momsched_run($in, array('-p', '-n', $zoekgrens));
		$namen = array_flip($index);
		$nog = array();
		foreach ($lines as $f) {
			if ($f[0] == 'infeasible') {
				foreach (array_slice($f, 1) as $nr) $nog[$namen[$nr]] = 1;
			} else if ($f[0] == 'unknown') {
				foreach (array_slice($f, 1) as $nr) $nodig[$namen[$nr]] = -$k;
			} else {
				$kleur[$namen[$f[0]]] = $f[1] - 1;
				$nodig[$namen[$f[0]]] = $k;
			}
		}
		$open = array_intersect_key($open, $nog);
	}
}
?>