forked from dvdoug/BoxPacker
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBoxList.php
More file actions
82 lines (71 loc) · 1.83 KB
/
Copy pathBoxList.php
File metadata and controls
82 lines (71 loc) · 1.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
<?php
/**
* Box packing (3D bin packing, knapsack problem).
*
* @author Doug Wright
*/
declare(strict_types=1);
namespace DVDoug\BoxPacker;
use ArrayIterator;
use IteratorAggregate;
use Traversable;
use function usort;
/**
* List of boxes available to put items into, ordered by volume.
*
* @author Doug Wright
*/
class BoxList implements IteratorAggregate
{
/**
* List containing boxes.
*
* @var Box[]
*/
private $list = [];
/**
* Has this list already been sorted?
*
* @var bool
*/
private $isSorted = false;
/**
* @return Traversable
*/
public function getIterator(): Traversable
{
if (!$this->isSorted) {
usort($this->list, [$this, 'compare']);
$this->isSorted = true;
}
return new ArrayIterator($this->list);
}
/**
* @param Box $item
*/
public function insert(Box $item): void
{
$this->list[] = $item;
}
/**
* @param Box $boxA
* @param Box $boxB
*
* @return int
*/
public function compare($boxA, $boxB): int
{
$boxAVolume = $boxA->getInnerWidth() * $boxA->getInnerLength() * $boxA->getInnerDepth();
$boxBVolume = $boxB->getInnerWidth() * $boxB->getInnerLength() * $boxB->getInnerDepth();
$volumeDecider = $boxAVolume <=> $boxBVolume; // try smallest box first
$emptyWeightDecider = $boxB->getEmptyWeight() <=> $boxA->getEmptyWeight(); // with smallest empty weight
if ($volumeDecider !== 0) {
return $volumeDecider;
}
if ($emptyWeightDecider !== 0) {
return $emptyWeightDecider;
}
// maximum weight capacity as fallback decider
return ($boxA->getMaxWeight() - $boxA->getEmptyWeight()) <=> ($boxB->getMaxWeight() - $boxB->getEmptyWeight());
}
}