Completed
Push — master ( 960337...9d7981 )
by Doug
06:00
created

VolumePacker::findPossibleOrientations()   C

Complexity

Conditions 7
Paths 3

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 28
Code Lines 14

Code Coverage

Tests 11
CRAP Score 8.4953

Importance

Changes 0
Metric Value
dl 0
loc 28
ccs 11
cts 16
cp 0.6875
rs 6.7272
c 0
b 0
f 0
cc 7
eloc 14
nc 3
nop 5
crap 8.4953
1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
5
 * @author Doug Wright
6
 */
7
namespace DVDoug\BoxPacker;
8
9
use Psr\Log\LoggerAwareInterface;
10
use Psr\Log\LoggerAwareTrait;
11
use Psr\Log\NullLogger;
12
13
/**
14
 * Actual packer
15
 * @author Doug Wright
16
 * @package BoxPacker
17
 */
18
class VolumePacker implements LoggerAwareInterface
19
{
20
    use LoggerAwareTrait;
21
22
    /**
23
     * 3D rotation of items is a WIP and should not be used in production environments
24
     */
25
    const ALWAYS_SHIP_FLAT = true;
26
27
    /**
28
     * Box to pack items into
29
     * @var Box
30
     */
31
    protected $box;
32
33
    /**
34
     * List of items to be packed
35
     * @var ItemList
36
     */
37
    protected $items;
38
39
    /**
40
     * Remaining width of the box to pack items into
41
     * @var int
42
     */
43
    protected $widthLeft;
44
45
    /**
46
     * Remaining length of the box to pack items into
47
     * @var int
48
     */
49
    protected $lengthLeft;
50
51
    /**
52
     * Remaining depth of the box to pack items into
53
     * @var int
54
     */
55
    protected $depthLeft;
56
57
    /**
58
     * Remaining weight capacity of the box
59
     * @var int
60
     */
61
    protected $remainingWeight;
62
63
    /**
64
     * Used width inside box for packing items
65
     * @var int
66
     */
67
    protected $usedWidth = 0;
68
69
    /**
70
     * Used length inside box for packing items
71
     * @var int
72
     */
73
    protected $usedLength = 0;
74
75
    /**
76
     * Used depth inside box for packing items
77
     * @var int
78
     */
79
    protected $usedDepth = 0;
80
81
    /**
82
     * Constructor
83
     */
84 26
    public function __construct(Box $box, ItemList $items)
85
    {
86 26
        $this->logger = new NullLogger();
87
88 26
        $this->box = $box;
89 26
        $this->items = $items;
90
91 26
        $this->depthLeft = $this->box->getInnerDepth();
92 26
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
93 26
        $this->widthLeft = $this->box->getInnerWidth();
94 26
        $this->lengthLeft = $this->box->getInnerLength();
95 26
    }
96
97
    /**
98
     * Pack as many items as possible into specific given box
99
     * @return PackedBox packed box
100
     */
101 26
    public function pack()
102
    {
103 26
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
104
105 26
        $packedItems = new ItemList;
106
107 26
        $layerWidth = $layerLength = $layerDepth = 0;
108
109 26
        $prevItem = null;
110
111 26
        while (!$this->items->isEmpty()) {
112
113 26
            $itemToPack = $this->items->extract();
114
115
            //skip items that are simply too heavy
116 26
            if ($itemToPack->getWeight() > $this->remainingWeight) {
117 4
                continue;
118
            }
119
120 26
            $this->logger->debug(
121 26
                "evaluating item {$itemToPack->getDescription()}",
122
                [
123 26
                    'item' => $itemToPack,
124
                    'space' => [
125 26
                        'widthLeft'   => $this->widthLeft,
126 26
                        'lengthLeft'  => $this->lengthLeft,
127 26
                        'depthLeft'   => $this->depthLeft,
128 26
                        'layerWidth'  => $layerWidth,
129 26
                        'layerLength' => $layerLength,
130
                        'layerDepth'  => $layerDepth
131 26
                    ]
132 26
                ]
133 26
            );
134
135 26
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
136 26
            $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
137
138 26
            if ($orientatedItem) {
139
140 26
                $packedItems->insert($orientatedItem->getItem());
141 26
                $this->remainingWeight -= $itemToPack->getWeight();
142
143 26
                $this->lengthLeft -= $orientatedItem->getLength();
144 26
                $layerLength += $orientatedItem->getLength();
145 26
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);
146
147 26
                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
148
149 26
                $this->usedLength = max($this->usedLength, $layerLength);
150 26
                $this->usedWidth = max($this->usedWidth, $layerWidth);
151
152
                //allow items to be stacked in place within the same footprint up to current layerdepth
153 26
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
154 26
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
155
156 26
                $prevItem = $orientatedItem;
157
158 26
                if (!$nextItem) {
159 23
                    $this->usedDepth += $layerDepth;
160 23
                }
161 26
            } else {
162
163 23
                $prevItem = null;
164
165 23
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
166 22
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
167 22
                    $this->lengthLeft += $layerLength;
168 22
                    $this->widthLeft -= $layerWidth;
169 22
                    $layerWidth = $layerLength = 0;
170 22
                    $this->items->insert($itemToPack);
171 22
                    continue;
172 18
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
173 7
                    $this->logger->debug("doesn't fit on layer even when empty");
174 7
                    continue;
175
                }
176
177 17
                $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $layerWidth ? min(floor(...s->box->getInnerWidth() can also be of type double. However, the property $widthLeft is declared as type integer. Maybe add an additional type check?

Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly.

For example, imagine you have a variable $accountId that can either hold an Id object or false (if there is no account id yet). Your code now assigns that value to the id property of an instance of the Account class. This class holds a proper account, so the id value must no longer be false.

Either this assignment is in error or a type check should be added for that assignment.

class Id
{
    public $id;

    public function __construct($id)
    {
        $this->id = $id;
    }

}

class Account
{
    /** @var  Id $id */
    public $id;
}

$account_id = false;

if (starsAreRight()) {
    $account_id = new Id(42);
}

$account = new Account();
if ($account instanceof Id)
{
    $account->id = $account_id;
}
Loading history...
178 17
                $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
0 ignored issues
show
Documentation Bug introduced by Doug Wright
It seems like $layerLength ? min(floor...->box->getInnerLength() can also be of type double. However, the property $lengthLeft is declared as type integer. Maybe add an additional type check?

Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly.

For example, imagine you have a variable $accountId that can either hold an Id object or false (if there is no account id yet). Your code now assigns that value to the id property of an instance of the Account class. This class holds a proper account, so the id value must no longer be false.

Either this assignment is in error or a type check should be added for that assignment.

class Id
{
    public $id;

    public function __construct($id)
    {
        $this->id = $id;
    }

}

class Account
{
    /** @var  Id $id */
    public $id;
}

$account_id = false;

if (starsAreRight()) {
    $account_id = new Id(42);
}

$account = new Account();
if ($account instanceof Id)
{
    $account->id = $account_id;
}
Loading history...
179 17
                $this->depthLeft -= $layerDepth;
180 17
                $this->usedDepth += $layerDepth;
181
182 17
                $layerWidth = $layerLength = $layerDepth = 0;
183 17
                $this->logger->debug("doesn't fit, so starting next vertical layer");
184 17
                $this->items->insert($itemToPack);
185
            }
186 26
        }
187 26
        $this->logger->debug("done with this box");
188 26
        return new PackedBox(
189 26
            $this->box,
190 26
            $packedItems,
191 26
            $this->widthLeft,
192 26
            $this->lengthLeft,
193 26
            $this->depthLeft,
194 26
            $this->remainingWeight,
195 26
            $this->usedWidth,
196 26
            $this->usedLength,
197 26
            $this->usedDepth);
198
    }
199
200
    /**
201
     * Get the best orientation for an item
202
     * @param Item $item
203
     * @param OrientatedItem|null $prevItem
204
     * @param Item|null $nextItem
205
     * @param int $widthLeft
206
     * @param int $lengthLeft
207
     * @param int $depthLeft
208
     * @return OrientatedItem|false
209
     */
210 26
    protected function findBestOrientation(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) {
211
212 26
        $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
213
214
        // special casing based on next item
215 26
        if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) {
216 6
            $this->logger->debug("not rotating based on next item");
217 6
            return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations()
218
        }
219
220 26
        $orientationFits = [];
221
222
        /** @var OrientatedItem $orientation */
223 26
        foreach ($orientations as $o => $orientation) {
224 26
            $orientationFit = min($widthLeft   - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
225 26
            $orientationFits[$o] = $orientationFit;
226 26
        }
227
228 26
        if (!empty($orientationFits)) {
229 26
            asort($orientationFits);
230 26
            reset($orientationFits);
231 26
            $bestFit = key($orientationFits);
232 26
            $this->logger->debug("Using orientation #{$bestFit}");
233 26
            return $orientations[$bestFit];
234
        } else {
235 25
            return false;
236
        }
237
    }
238
239
    /**
240
     * Find all possible orientations for an item
241
     * @param Item $item
242
     * @param OrientatedItem|null $prevItem
243
     * @param int $widthLeft
244
     * @param int $lengthLeft
245
     * @param int $depthLeft
246
     * @return OrientatedItem[]
247
     */
248 26
    protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
249
250 26
        $orientations = [];
251
252
        //Special case items that are the same as what we just packed - keep orientation
253 26
        if ($prevItem && $prevItem->getItem() == $item) {
254 10
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
255 10
        } else {
256
257
            //simple 2D rotation
258 26
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
259 26
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
260
261
            //add 3D rotation if we're allowed
262 26
            if (self::ALWAYS_SHIP_FLAT === false && !$item->getKeepFlat()) {
263
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
264
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
265
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
266
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
267
            }
268
        }
269
270
        //remove any that simply don't fit
271 26
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
272 26
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
273 26
        });
274
275
    }
276
277
    /**
278
     * Figure out if we can stack the next item vertically on top of this rather than side by side
279
     * Used when we've packed a tall item, and have just put a shorter one next to it
280
     *
281
     * @param ItemList       $packedItems
282
     * @param OrientatedItem $prevItem
0 ignored issues
show
Documentation introduced by Doug Wright
Should the type for parameter $prevItem not be null|OrientatedItem?

This check looks for @param annotations where the type inferred by our type inference engine differs from the declared type.

It makes a suggestion as to what type it considers more descriptive.

Most often this is a case of a parameter that can be null in addition to its declared types.

Loading history...
283
     * @param Item           $nextItem
0 ignored issues
show
Documentation introduced by Doug Wright
Should the type for parameter $nextItem not be null|Item?

This check looks for @param annotations where the type inferred by our type inference engine differs from the declared type.

It makes a suggestion as to what type it considers more descriptive.

Most often this is a case of a parameter that can be null in addition to its declared types.

Loading history...
284
     * @param int            $maxWidth
285
     * @param int            $maxLength
286
     * @param int            $maxDepth
287
     */
288 26
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, OrientatedItem $prevItem = null, Item $nextItem = null, $maxWidth, $maxLength, $maxDepth)
289
    {
290 26
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
291 25
            $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $maxWidth, $maxLength, $maxDepth);
292 25
            if ($stackedItem) {
293 1
                $this->remainingWeight -= $this->items->top()->getWeight();
294 1
                $maxDepth -= $stackedItem->getDepth();
295 1
                $packedItems->insert($this->items->extract());
296 1
            } else {
297 25
                break;
298
            }
299 1
        }
300 26
    }
301
302
    /**
303
     * @param int $layerWidth
304
     * @param int $layerLength
305
     * @param int $layerDepth
306
     * @return bool
307
     */
308 23
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
309 23
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
310
    }
311
}
312