|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* Box packing (3D bin packing, knapsack problem) |
|
4
|
|
|
* @package BoxPacker |
|
5
|
|
|
* @author Doug Wright |
|
6
|
|
|
*/ |
|
7
|
|
|
declare(strict_types=1); |
|
8
|
|
|
namespace DVDoug\BoxPacker; |
|
9
|
|
|
|
|
10
|
|
|
use ArrayIterator, Countable, IteratorAggregate, Traversable; |
|
11
|
|
|
|
|
12
|
|
|
/** |
|
13
|
|
|
* List of items to be packed, ordered by volume |
|
14
|
|
|
* @author Doug Wright |
|
15
|
|
|
* @package BoxPacker |
|
16
|
|
|
*/ |
|
17
|
|
|
class ItemList implements Countable, IteratorAggregate |
|
18
|
|
|
{ |
|
19
|
|
|
/** |
|
20
|
|
|
* List containing items |
|
21
|
|
|
* @var Item[] |
|
22
|
|
|
*/ |
|
23
|
|
|
private $list = []; |
|
24
|
|
|
|
|
25
|
|
|
/** |
|
26
|
|
|
* Has this list already been sorted? |
|
27
|
|
|
* @var bool |
|
28
|
|
|
*/ |
|
29
|
|
|
private $isSorted = false; |
|
30
|
|
|
|
|
31
|
|
|
/** |
|
32
|
|
|
* @param Item $item |
|
33
|
|
|
*/ |
|
34
|
39 |
|
public function insert(Item $item) |
|
35
|
|
|
{ |
|
36
|
39 |
|
$this->list[] = $item; |
|
37
|
|
|
} |
|
38
|
|
|
|
|
39
|
|
|
/** |
|
40
|
|
|
* @internal |
|
41
|
|
|
* @return Item |
|
42
|
|
|
*/ |
|
43
|
36 |
View Code Duplication |
public function extract(): Item |
|
|
|
|
|
|
44
|
|
|
{ |
|
45
|
36 |
|
if (!$this->isSorted) { |
|
46
|
36 |
|
usort($this->list, [$this, 'compare']); |
|
47
|
36 |
|
$this->isSorted = true; |
|
48
|
|
|
} |
|
49
|
36 |
|
return array_shift($this->list); |
|
50
|
|
|
} |
|
51
|
|
|
|
|
52
|
|
|
/** |
|
53
|
|
|
* @internal |
|
54
|
|
|
* @return Item |
|
55
|
|
|
*/ |
|
56
|
33 |
View Code Duplication |
public function top(): Item |
|
|
|
|
|
|
57
|
|
|
{ |
|
58
|
33 |
|
if (!$this->isSorted) { |
|
59
|
2 |
|
usort($this->list, [$this, 'compare']); |
|
60
|
2 |
|
$this->isSorted = true; |
|
61
|
|
|
} |
|
62
|
33 |
|
$temp = $this->list; |
|
63
|
33 |
|
return reset($temp); |
|
64
|
|
|
} |
|
65
|
|
|
|
|
66
|
|
|
/** |
|
67
|
|
|
* @return Traversable |
|
68
|
|
|
*/ |
|
69
|
27 |
View Code Duplication |
public function getIterator(): Traversable |
|
|
|
|
|
|
70
|
|
|
{ |
|
71
|
27 |
|
if (!$this->isSorted) { |
|
72
|
27 |
|
usort($this->list, [$this, 'compare']); |
|
73
|
27 |
|
$this->isSorted = true; |
|
74
|
|
|
} |
|
75
|
27 |
|
return new ArrayIterator($this->list); |
|
76
|
|
|
} |
|
77
|
|
|
|
|
78
|
|
|
/** |
|
79
|
|
|
* Number of items in list |
|
80
|
|
|
* @return int |
|
81
|
|
|
*/ |
|
82
|
37 |
|
public function count(): int |
|
83
|
|
|
{ |
|
84
|
37 |
|
return count($this->list); |
|
85
|
|
|
} |
|
86
|
|
|
|
|
87
|
|
|
/** |
|
88
|
|
|
* @param Item $itemA |
|
89
|
|
|
* @param Item $itemB |
|
90
|
|
|
* |
|
91
|
|
|
* @return int |
|
92
|
|
|
*/ |
|
93
|
35 |
|
private function compare(Item $itemA, Item $itemB): int |
|
94
|
|
|
{ |
|
95
|
35 |
|
$itemAVolume = $itemA->getWidth() * $itemA->getLength() * $itemA->getDepth(); |
|
96
|
35 |
|
$itemBVolume = $itemB->getWidth() * $itemB->getLength() * $itemB->getDepth(); |
|
97
|
35 |
|
$volumeDecider = $itemBVolume <=> $itemAVolume; |
|
98
|
35 |
|
$weightDecider = $itemB->getWeight() - $itemA->getWeight(); |
|
99
|
35 |
|
if ($volumeDecider !== 0) { |
|
100
|
18 |
|
return $volumeDecider; |
|
101
|
32 |
|
} elseif ($weightDecider !== 0) { |
|
102
|
4 |
|
return $weightDecider; |
|
103
|
|
|
} else { |
|
104
|
28 |
|
return $itemA->getDescription() <=> $itemB->getDescription(); |
|
105
|
|
|
} |
|
106
|
|
|
} |
|
107
|
|
|
|
|
108
|
|
|
} |
|
109
|
|
|
|
dvdoug /
BoxPacker
Loading history...
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.