Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
97.56% covered (success)
97.56%
40 / 41
66.67% covered (warning)
66.67%
2 / 3
 CRAP
0.00% covered (danger)
0.00%
0 / 1
Weighted
97.56% covered (success)
97.56%
40 / 41
66.67% covered (warning)
66.67%
2 / 3
 19
0.00% covered (danger)
0.00%
0 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 sortByEnd
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 7
 binarySearch
91.67% covered (success)
91.67%
11 / 12
0.00% covered (danger)
0.00%
0 / 1
 6.02
 solve
100.00% covered (success)
100.00%
22 / 22
100.00% covered (success)
100.00%
1 / 1
 5
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\JobScheduling
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\JobScheduling;
16
17/**
18 * Job scheduling algorithm with no overlapping jobs
19 *
20 * @package phpOMS\Algorithm\JobScheduling
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class Weighted
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * Sort jobs by end date.
39     *
40     * @param JobInterface $j1 Job 1
41     * @param JobInterface $j2 Job 2
42     *
43     * @return int
44     *
45     * @since 1.0.0
46     */
47    private static function sortByEnd(JobInterface $j1, JobInterface $j2) : int
48    {
49        if ($j1->getEnd() === null && $j2->getEnd() !== null) {
50            return 1;
51        }
52
53        if ($j1->getEnd() === null && $j2->getEnd() === null) {
54            return 0;
55        }
56
57        if ($j1->getEnd() !== null && $j2->getEnd() === null) {
58            return -1;
59        }
60
61        return $j1->getEnd()->getTimestamp() <=> $j2->getEnd()->getTimestamp();
62    }
63
64    /**
65     * Search for a none-conflicting job that comes befor a defined job
66     *
67     * @param JobInterface[] $jobs  List of jobs
68     * @param int            $pivot Job to find the previous job to
69     *
70     * @return int
71     *
72     * @since 1.0.0
73     */
74    private static function binarySearch(array $jobs, int $pivot) : int
75    {
76        $lo = 0;
77        $hi = $pivot - 1;
78
79        while ($lo <= $hi) {
80            $mid = (int) (($lo + $hi) / 2);
81
82            if ($jobs[$mid]->getEnd() !== null
83                && $jobs[$mid]->getEnd()->getTimestamp() <= $jobs[$pivot]->getStart()->getTimestamp()
84            ) {
85                if ($jobs[$mid + 1]->getEnd() !== null
86                    && $jobs[$mid + 1]->getEnd()->getTimestamp() <= $jobs[$pivot]->getStart()->getTimestamp()
87                ) {
88                    $lo = $mid + 1;
89                } else {
90                    return $mid;
91                }
92            } else {
93                $hi = $mid - 1;
94            }
95        }
96
97        return -1;
98    }
99
100    /**
101     * Maximize the value of the job execution without overlapping jobs
102     *
103     * @param JobInterface[] $jobs Jobs to filter
104     *
105     * @return JobInterface[]
106     *
107     * @since 1.0.0
108     */
109    public static function solve(array $jobs) : array
110    {
111        $n = \count($jobs);
112
113        if ($n < 2) {
114            return $jobs;
115        }
116
117        \usort($jobs, function (\phpOMS\Algorithm\JobScheduling\JobInterface $j1, \phpOMS\Algorithm\JobScheduling\JobInterface $j2) : int {
118            return self::sortByEnd($j1, $j2);
119        });
120
121        $valueTable = [$jobs[0]->getValue()];
122
123        $resultTable    = [];
124        $resultTable[0] = [$jobs[0]];
125
126        for ($i = 1; $i < $n; ++$i) {
127            $value = $jobs[$i]->getValue();
128            $jList = [$jobs[$i]];
129            $l     = self::binarySearch($jobs, $i);
130
131            if ($l != -1) {
132                $value += $valueTable[$l];
133                $jList  = \array_merge($resultTable[$l], $jList);
134            }
135
136            if ($value > $valueTable[$i - 1]) {
137                $valueTable[$i]  = $value;
138                $resultTable[$i] = $jList;
139            } else {
140                $valueTable[$i]  = $valueTable[$i - 1];
141                $resultTable[$i] = $resultTable[$i - 1];
142            }
143        }
144
145        return $resultTable[$n - 1];
146    }
147}