vor langer zeit haben wir eine anwendung zur zeiterfassung geschrieben. ein teilproblem war die berechnung von zuschlägen auf grundlage eines umfangreichen tarifpapiers. die zuschläge für wochenendarbeit, nachtarbeit, etc. sollten sich möglichst konfigurieren lassen. beispielsweise in der form startstunde-endstunde priorität beschreibung
0-4 6 nachts
5-10 4 früh
22-24 6 nachts
12-23 9 sonntag
die priorität ist wichtig, weil sich die zeitintervalle überschneiden können. in diesem fall wird der höherwertige aufschlag berechnet, also wer sonntags 22-23 uhr arbeitet bekommt sonntagszuschlag und nicht nachtzuschlag.
ich finde dieses problem recht interessant. es hatte mir damals einiges kopfzerbrechen bereitet. mit den neuen sprachfeatures von php 5.3, den anonymen funktionen und closures, wollte ich mir das problem nochmal neu anschauen und testen inwieweit sich der code damit straffen läßt.
beginnen wir mit den eingabedaten:
$zeiten_def=<<<EDEF
3-8
9-23
EDEF;
$tarif_def=<<<EDEF
0-4 6 nachts
5-10 4 früh
12-13 3 mittags
6-7 8 blubb
14-15 8 blibb
18-22 4 spät
22-24 6 nachts
12-23 9 sonntag
EDEF;
function parse_input($in, $extended=false){
return array_map(function($line) use($extended){
$l = preg_split("/[-\s]+/", trim($line), 4);
$zeiten = array('start'=>$l[0], 'end'=>$l[1]);
if($extended){
$zeiten['prio']=$l[2];
$zeiten['descr']=$l[3];
}
return $zeiten;
}, explode("\n", $in));
}
function p_ival($i){
$p = ($i['prio']) ?
" kategorie {$i['prio']} ({$i['descr']})" : '' ;
return sprintf("%02d - %02d%s",
$i['start'], $i['end'], $p);
}
$tarife=parse_input($tarif_def, true);
$zeiten=parse_input($zeiten_def);
usort($tarife, function($a, $b){
if($a['prio'] > $b['prio']) return -1;
if($a['prio'] < $b['prio']) return 1;
return 0;
});
aus den eingabedaten werden listen mit intervallen erzeugt. ein intervall ist ein hash mit den schlüsseln start, end und optional prio und descr. beim einlesen kommt schon ein closure zum einsatz: die array_map funktion nutzt eine anonyme funktion, die zugriff auf den übergeordneten funktionsparameter erhält (use $extended). davon abhängig erzeugt sie die optionalen intervallschlüssel. das ist nice. früher hätte man z.b. einen ähnlichen effekt mit einer globalen variable erzielen können (häßlich).
$tarife wir anschliessend nach priorität sortiert. für den lösungsweg gilt: wer zuerst kommt, malt zuerst. daher diese vorsortierung.
die funktion p_ival() ist eine hilfsfunktion, mit der wir einen intervall anzeigen können.
mit einer generischen lösung wird die arbeitszeit mit den tarifintervallen verglichen. eine vergleichsfunktion gibt die treffer und die nichttreffenden teile zurück. die funktion match_interval() erledigt diese arbeit. sie ist etwas länglich geraten, muss sie doch alle möglichkeiten einzeln testen und die ergebnismengen zusammenstellen. vllt. hat jmd ne idee, wie das kürzer zu machen ist.
function match_interval($needle, $haystack){
print "TEST ".p_ival($needle)." VS ".p_ival($haystack)."\n";
$matched=array(); $unmatched=array();
// kein match.
// ende der nadel vor beginn des heu bzw.
// anfang der nadel hinterm heu
if(($needle['end'] <= $haystack['start']) ||
($needle['start'] >= $haystack['end'])){
$unmatched[]=$needle;
// nadel direkt im heu
}elseif(($needle['start']>=$haystack['start']) &&
($needle['end'] <= $haystack['end'])){
$matched[]=$needle;
// nadel ist größer als das heu
}elseif(($haystack['start']>$needle['start']) &&
($haystack['end'] < $needle['end'])){
$matched[]=$haystack;
$unmatched[]=array("start"=>$needle['start'],
"end"=>$haystack['start']);
$unmatched[]=array("start"=>$haystack['end'],
"end"=>$needle['end']);
// teil der nadel is im heu!
// ist es der hintere?
}elseif($needle['end']<=$haystack['end']){
$matched[]=array("start"=>$haystack['start'],
"end"=>$needle['end']);
$unmatched[]=array("start"=>$needle['start'],
"end"=>$haystack['start']);
// oder der vordere?
}else{
$matched[]=array("start"=>$needle['start'],
"end"=>$haystack['end']);
$unmatched[]=array("start"=>$haystack['end'],
"end"=>$needle['end']);
}
// jetzt noch unsere informationen an die
// fundstelle hängen
$matched = array_map(function($f) use($haystack){
$f['prio']=$haystack['prio'];
$f['descr']=$haystack['descr'];
return $f;
}, $matched);
return array($matched, $unmatched);
}
beim vergleich der intervalle sind also 4 fälle denkbar:
- der intervall passt nicht. er wird vollständig als rest zurückgegeben
- der intervall passt vollständig in den (gleich großen oder größeren). es wird kein rest zurückgegeben
- der intervall passt teilweise (vorne oder hinten). es wird genau ein restintervall zurückgegeben.
- der intervall ist größer als der „heu“ intervall. er wird durch das heu gesplittet. es werden 2 reste zurückgegeben.
so, jetzt kommen wir an die stelle, wo der spaß richtig losgeht. wir starten (im einfachsten fall) mit einem intervall (der arbeitszeit) und prüfen es gegen die tarifzeiten. bei jeder prüfung erhalten wir eine neue liste von intervallen, die nicht passen. diese intervalle müssen mit dem rest der liste verglichen werden, während die treffer lediglich gesammelt werden. hier meine erste version:
function match_all_intervals($n, $hay){
$h = array_shift($hay);
if(!$h) return array(array(), $n);
$matched=array();
$un=array();
foreach($n as $test){
list($m, $u) = match_interval($test, $h);
$matched = array_merge($matched, $m);
list($m2, $un2)=match_all_intervals($u, $hay);
$matched=array_merge($matched, $m2);
$un=array_merge($un, $un2);
}
return array($matched, $un);
}
function p_result($r){
print "\n\nERGEBNIS zuschlagspflichtige Zeiten:\n";
print join("\n", array_map("p_ival", $r[0]));
print "\n normale zeiten:\n";
print join("\n", array_map("p_ival", $r[1]));
print "\n";
}
$r = match_all_intervals_r($zeiten, $tarife);
p_result($r);
diese funktion enthält eine rekursion: list($m2, $un2)=match_all_intervals($u, $hay); der neue rest wird gegen den rest des heuhaufens $hay getestet. die ergebnisse kann man sich mit der p_result() funktion ausgeben lassen.
die foreach schleife kann man auch noch durch eine rekursion ersetzen. das wäre version nummer 2:
function match_all_intervals_r($ns, $hay){
$mat=array();
$umat=array();
$h = array_shift($hay);
if(!$h) return array(array(), $ns);
$n = array_shift($ns);
if(!$n) return array(array(), array());
list($m, $u) = match_interval($n, $h);
$mat = array_merge($mat, $m);
list($m, $u)=match_all_intervals_r($u, $hay);
$mat=array_merge($mat, $m);
$umat=$u;
// hier gehen wir mit den nachbarintervallen ($ns)
// original $hay auf den weiter voran
array_unshift($hay, $h);
list($m, $u) = match_all_intervals_r($ns, $hay);
$mat=array_merge($mat, $m);
$umat = array_merge($umat, $u);
return array($mat, $umat);
}
$r = match_all_intervals_r($zeiten, $tarife);
p_result($r);
irgendwie ist die funktion garnicht kürzer geworden. ich habe noch etwas mit array_reduce() herumgespielt und bin noch auf diese variante gekommen.
$r = array_reduce($tarife, function($acc, $z){
$m = $acc['m'];
$u = array();
array_map(function($i) use($z, &$m, &$u){
list($m2, $u2) = match_interval($i, $z);
$m=array_merge($m, $m2);
$u=array_merge($u, $u2);
},
$acc['u']);
return array('m'=>$m, 'u'=>$u);
}, array("m"=>array(), 'u'=>$zeiten));
p_result(array($r2['m'], $r2['u']));
hmm. 10 zeilen. das ist dann die kürzeste variante. hier kommt eine etwas modfizierte datenstruktur zum einsatz. statt eines arrays [0=>liste_der_treffer, 1=>liste_der_reste] heisst es hier ['m'=>liste_der_treffer, 'u'=>liste_der_reste]
tja. das wars dann schon. evtl. lässt sich das problem noch knackiger lösen. ich bin mir sogar sicher, dass das geht. der geneigte leser möge vorschläge bringen :)
Kommentare