|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* Box packing (3D bin packing, knapsack problem) |
|
4
|
|
|
* @package BoxPacker |
|
5
|
|
|
* @author Doug Wright |
|
6
|
|
|
*/ |
|
7
|
|
|
|
|
8
|
|
|
namespace DVDoug\BoxPacker; |
|
9
|
|
|
|
|
10
|
|
|
use DVDoug\BoxPacker\Test\TestBox; |
|
11
|
|
|
use DVDoug\BoxPacker\Test\TestConstrainedTestItem; |
|
12
|
|
|
use DVDoug\BoxPacker\Test\TestItem; |
|
13
|
|
|
use PHPUnit\Framework\TestCase; |
|
14
|
|
|
|
|
15
|
|
|
class VolumePackerTest extends TestCase |
|
16
|
|
|
{ |
|
17
|
|
View Code Duplication |
public function testPackBoxThreeItemsFitEasily() |
|
|
|
|
|
|
18
|
|
|
{ |
|
19
|
|
|
|
|
20
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
21
|
|
|
|
|
22
|
|
|
$items = new ItemList; |
|
23
|
|
|
$items->insert(new TestItem('Item 1', 250, 250, 2, 200)); |
|
24
|
|
|
$items->insert(new TestItem('Item 2', 250, 250, 2, 200)); |
|
25
|
|
|
$items->insert(new TestItem('Item 3', 250, 250, 2, 200)); |
|
26
|
|
|
|
|
27
|
|
|
$packer = new VolumePacker($box, $items); |
|
28
|
|
|
$packedBox = $packer->pack(); |
|
29
|
|
|
|
|
30
|
|
|
self::assertEquals(3, $packedBox->getItems()->count()); |
|
31
|
|
|
} |
|
32
|
|
|
|
|
33
|
|
View Code Duplication |
public function testPackBoxThreeItemsFitExactly() |
|
|
|
|
|
|
34
|
|
|
{ |
|
35
|
|
|
|
|
36
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
37
|
|
|
|
|
38
|
|
|
$items = new ItemList; |
|
39
|
|
|
$items->insert(new TestItem('Item 1', 296, 296, 2, 200)); |
|
40
|
|
|
$items->insert(new TestItem('Item 2', 296, 296, 2, 500)); |
|
41
|
|
|
$items->insert(new TestItem('Item 3', 296, 296, 4, 290)); |
|
42
|
|
|
|
|
43
|
|
|
$packer = new VolumePacker($box, $items); |
|
44
|
|
|
$packedBox = $packer->pack(); |
|
45
|
|
|
|
|
46
|
|
|
self::assertEquals(3, $packedBox->getItems()->count()); |
|
47
|
|
|
} |
|
48
|
|
|
|
|
49
|
|
View Code Duplication |
public function testPackBoxThreeItemsFitExactlyNoRotation() |
|
|
|
|
|
|
50
|
|
|
{ |
|
51
|
|
|
|
|
52
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
53
|
|
|
|
|
54
|
|
|
$items = new ItemList; |
|
55
|
|
|
$items->insert(new TestItem('Item 1', 296, 148, 2, 200)); |
|
56
|
|
|
$items->insert(new TestItem('Item 2', 296, 148, 2, 500)); |
|
57
|
|
|
|
|
58
|
|
|
$packer = new VolumePacker($box, $items); |
|
59
|
|
|
$packedBox = $packer->pack(); |
|
60
|
|
|
|
|
61
|
|
|
self::assertEquals(2, $packedBox->getItems()->count()); |
|
62
|
|
|
} |
|
63
|
|
|
|
|
64
|
|
View Code Duplication |
public function testPackBoxThreeItemsFitSizeButOverweight() |
|
|
|
|
|
|
65
|
|
|
{ |
|
66
|
|
|
|
|
67
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
68
|
|
|
|
|
69
|
|
|
$items = new ItemList; |
|
70
|
|
|
$items->insert(new TestItem('Item 1', 250, 250, 2, 400)); |
|
71
|
|
|
$items->insert(new TestItem('Item 2', 250, 250, 2, 500)); |
|
72
|
|
|
$items->insert(new TestItem('Item 3', 250, 250, 2, 200)); |
|
73
|
|
|
|
|
74
|
|
|
$packer = new VolumePacker($box, $items); |
|
75
|
|
|
$packedBox = $packer->pack(); |
|
76
|
|
|
|
|
77
|
|
|
self::assertEquals(2, $packedBox->getItems()->count()); |
|
78
|
|
|
} |
|
79
|
|
|
|
|
80
|
|
View Code Duplication |
public function testPackBoxThreeItemsFitWeightBut2Oversize() |
|
|
|
|
|
|
81
|
|
|
{ |
|
82
|
|
|
|
|
83
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
84
|
|
|
|
|
85
|
|
|
$items = new ItemList; |
|
86
|
|
|
$items->insert(new TestItem('Item 1', 297, 296, 2, 200)); |
|
87
|
|
|
$items->insert(new TestItem('Item 2', 297, 296, 2, 500)); |
|
88
|
|
|
$items->insert(new TestItem('Item 3', 296, 296, 4, 290)); |
|
89
|
|
|
|
|
90
|
|
|
$packer = new VolumePacker($box, $items); |
|
91
|
|
|
$packedBox = $packer->pack(); |
|
92
|
|
|
|
|
93
|
|
|
self::assertEquals(1, $packedBox->getItems()->count()); |
|
94
|
|
|
} |
|
95
|
|
|
|
|
96
|
|
View Code Duplication |
public function testPackTwoItemsFitExactlySideBySide() |
|
|
|
|
|
|
97
|
|
|
{ |
|
98
|
|
|
|
|
99
|
|
|
$box = new TestBox('Le box', 300, 400, 10, 10, 296, 496, 8, 1000); |
|
100
|
|
|
|
|
101
|
|
|
$items = new ItemList; |
|
102
|
|
|
$items->insert(new TestItem('Item 1', 296, 248, 8, 200)); |
|
103
|
|
|
$items->insert(new TestItem('Item 2', 248, 296, 8, 200)); |
|
104
|
|
|
|
|
105
|
|
|
$packer = new VolumePacker($box, $items); |
|
106
|
|
|
$packedBox = $packer->pack(); |
|
107
|
|
|
|
|
108
|
|
|
self::assertEquals(2, $packedBox->getItems()->count()); |
|
109
|
|
|
} |
|
110
|
|
|
|
|
111
|
|
View Code Duplication |
public function testPackThreeItemsBottom2FitSideBySideOneExactlyOnTop() |
|
|
|
|
|
|
112
|
|
|
{ |
|
113
|
|
|
|
|
114
|
|
|
$box = new TestBox('Le box', 300, 300, 10, 10, 296, 296, 8, 1000); |
|
115
|
|
|
|
|
116
|
|
|
$items = new ItemList; |
|
117
|
|
|
$items->insert(new TestItem('Item 1', 248, 148, 4, 200)); |
|
118
|
|
|
$items->insert(new TestItem('Item 2', 148, 248, 4, 200)); |
|
119
|
|
|
$items->insert(new TestItem('Item 3', 296, 296, 4, 200)); |
|
120
|
|
|
|
|
121
|
|
|
$packer = new VolumePacker($box, $items); |
|
122
|
|
|
$packedBox = $packer->pack(); |
|
123
|
|
|
|
|
124
|
|
|
self::assertEquals(3, $packedBox->getItems()->count()); |
|
125
|
|
|
} |
|
126
|
|
|
|
|
127
|
|
View Code Duplication |
public function testPackThreeItemsBottom2FitSideBySideWithSpareSpaceOneOverhangSlightlyOnTop() |
|
|
|
|
|
|
128
|
|
|
{ |
|
129
|
|
|
|
|
130
|
|
|
$box = new TestBox('Le box', 250, 250, 10, 10, 248, 248, 8, 1000); |
|
131
|
|
|
|
|
132
|
|
|
$items = new ItemList; |
|
133
|
|
|
$items->insert(new TestItem('Item 1', 200, 200, 4, 200)); |
|
134
|
|
|
$items->insert(new TestItem('Item 2', 110, 110, 4, 200)); |
|
135
|
|
|
$items->insert(new TestItem('Item 3', 110, 110, 4, 200)); |
|
136
|
|
|
|
|
137
|
|
|
$packer = new VolumePacker($box, $items); |
|
138
|
|
|
$packedBox = $packer->pack(); |
|
139
|
|
|
|
|
140
|
|
|
self::assertEquals(3, $packedBox->getItems()->count()); |
|
141
|
|
|
} |
|
142
|
|
|
|
|
143
|
|
|
public function testPackSingleItemFitsBetterRotated() |
|
144
|
|
|
{ |
|
145
|
|
|
|
|
146
|
|
|
$box = new TestBox('Le box', 400, 300, 10, 10, 396, 296, 8, 1000); |
|
147
|
|
|
|
|
148
|
|
|
$items = new ItemList; |
|
149
|
|
|
$items->insert(new TestItem('Item 1', 250, 290, 2, 200)); |
|
150
|
|
|
|
|
151
|
|
|
$packer = new VolumePacker($box, $items); |
|
152
|
|
|
$packedBox = $packer->pack(); |
|
153
|
|
|
|
|
154
|
|
|
self::assertEquals(1, $packedBox->getItems()->count()); |
|
155
|
|
|
} |
|
156
|
|
|
|
|
157
|
|
View Code Duplication |
public function testIssue53() |
|
|
|
|
|
|
158
|
|
|
{ |
|
159
|
|
|
$packer = new Packer(); |
|
160
|
|
|
$packer->addBox(new TestBox('Box', 500, 1000, 500, 0, 500, 1000, 500, 0)); |
|
161
|
|
|
$packer->addItem(new TestItem('Item 1', 500, 500, 500, 0)); |
|
162
|
|
|
$packer->addItem(new TestItem('Item 2', 500, 500, 250, 0), 2); |
|
163
|
|
|
$packedBoxes = $packer->pack(); |
|
164
|
|
|
|
|
165
|
|
|
self::assertEquals(1, $packedBoxes->count()); |
|
166
|
|
|
} |
|
167
|
|
|
|
|
168
|
|
View Code Duplication |
public function testIssue75() |
|
|
|
|
|
|
169
|
|
|
{ |
|
170
|
|
|
$packer = new Packer(); |
|
171
|
|
|
$packer->addBox(new TestBox('CONTAINER (20 x 12 x 10)', 20, 12, 10, 0, 20, 12, 10, 2500)); |
|
172
|
|
|
$packer->addItem(new TestItem('B (12 x 12 x 5)', 12, 12, 5, 8),2); |
|
173
|
|
|
$packer->addItem(new TestItem('C (8 x 12 x 5)', 8, 12, 5, 8),2); |
|
174
|
|
|
$packedBoxes = $packer->pack(); |
|
175
|
|
|
|
|
176
|
|
|
self::assertEquals(1, $packedBoxes->count()); |
|
177
|
|
|
} |
|
178
|
|
|
|
|
179
|
|
|
|
|
180
|
|
|
public function testIssue86() |
|
181
|
|
|
{ |
|
182
|
|
|
$packer = new Packer(); |
|
183
|
|
|
$packer->addBox(new TestBox('Box', 22.5, 27, 13.5, 0.2, 22.5, 27, 13.5, 30)); |
|
184
|
|
|
$packer->addItem(new TestItem('Item 1', 11.2, 22.2, 2.2, 0.075),3); |
|
185
|
|
|
$packer->addItem(new TestItem('Item 2', 10.8, 21.5, 2, 0.102),4); |
|
186
|
|
|
$packer->addItem(new TestItem('Item 3', 6.2, 17, 1.8, 0.03),3); |
|
187
|
|
|
$packedBoxes = $packer->pack(); |
|
188
|
|
|
|
|
189
|
|
|
self::assertEquals(1, $packedBoxes->count()); |
|
190
|
|
|
|
|
191
|
|
|
/** @var PackedBox $packedBox */ |
|
192
|
|
|
$packedBox = $packedBoxes->top(); |
|
193
|
|
|
self::assertEquals(22.2, $packedBox->getUsedWidth()); //23.2 |
|
194
|
|
|
self::assertEquals(23.2, $packedBox->getUsedLength()); //22.2 |
|
195
|
|
|
self::assertEquals(10.2, $packedBox->getUsedDepth()); |
|
196
|
|
|
self::assertEquals(0.3, $packedBox->getRemainingWidth()); |
|
197
|
|
|
self::assertEquals(3.8, $packedBox->getRemainingLength()); |
|
198
|
|
|
self::assertEquals(3.3, $packedBox->getRemainingDepth()); |
|
199
|
|
|
} |
|
200
|
|
|
|
|
201
|
|
View Code Duplication |
public function testConstraints() |
|
|
|
|
|
|
202
|
|
|
{ |
|
203
|
|
|
TestConstrainedTestItem::$limit = 2; |
|
204
|
|
|
|
|
205
|
|
|
$packer = new Packer(); |
|
206
|
|
|
$packer->addBox(new TestBox('Box', 10, 10, 10, 0, 10, 10, 10, 0)); |
|
207
|
|
|
$packer->addItem(new TestConstrainedTestItem('Item', 1, 1, 1, 0), 8); |
|
208
|
|
|
$packedBoxes = $packer->pack(); |
|
209
|
|
|
|
|
210
|
|
|
self::assertEquals(4, $packedBoxes->count()); |
|
211
|
|
|
} |
|
212
|
|
|
} |
|
213
|
|
|
|
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.