Completed
Push — master ( b375e4...08d157 )
by Doug
05:56
created

VolumePacker::tryAndStackItemsIntoSpace()   A

Complexity

Conditions 4
Paths 3

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 13
Code Lines 9

Code Coverage

Tests 11
CRAP Score 4

Importance

Changes 0
Metric Value
dl 0
loc 13
ccs 11
cts 11
cp 1
rs 9.2
c 0
b 0
f 0
cc 4
eloc 9
nc 3
nop 4
crap 4
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
     * Box to pack items into
24
     * @var Box
25
     */
26
    protected $box;
27
28
    /**
29
     * List of items to be packed
30
     * @var ItemList
31
     */
32
    protected $items;
33
34
    /**
35
     * Remaining width of the box to pack items into
36
     * @var int
37
     */
38
    protected $widthLeft;
39
40
    /**
41
     * Remaining length of the box to pack items into
42
     * @var int
43
     */
44
    protected $lengthLeft;
45
46
    /**
47
     * Remaining depth of the box to pack items into
48
     * @var int
49
     */
50
    protected $depthLeft;
51
52
    /**
53
     * Remaining weight capacity of the box
54
     * @var int
55
     */
56
    protected $remainingWeight;
57
58
    /**
59
     * Constructor
60
     */
61 26
    public function __construct(Box $box, ItemList $items)
62
    {
63 26
        $this->logger = new NullLogger();
64
65 26
        $this->box = $box;
66 26
        $this->items = $items;
67
68 26
        $this->depthLeft = $this->box->getInnerDepth();
69 26
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
70 26
        $this->widthLeft = $this->box->getInnerWidth();
71 26
        $this->lengthLeft = $this->box->getInnerLength();
72 26
    }
73
74
    /**
75
     * Pack as many items as possible into specific given box
76
     * @return PackedBox packed box
77
     */
78 26
    public function pack()
79
    {
80 26
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
81
82 26
        $packedItems = new ItemList;
83
84 26
        $layerWidth = $layerLength = $layerDepth = 0;
85
86 26
        $prevItem = null;
87
88 26
        while (!$this->items->isEmpty()) {
89
90 26
            $itemToPack = $this->items->extract();
91
92
            //skip items that are simply too heavy
93 26
            if ($itemToPack->getWeight() > $this->remainingWeight) {
94 4
                continue;
95
            }
96
97 26
            $this->logger->debug("evaluating item {$itemToPack->getDescription()}");
98 26
            $this->logger->debug("remaining width: {$this->widthLeft}, length: {$this->lengthLeft}, depth: {$this->depthLeft}");
99 26
            $this->logger->debug("layerWidth: {$layerWidth}, layerLength: {$layerLength}, layerDepth: {$layerDepth}");
100
101 26
            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
102 26
            $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
103
104 26
            if ($orientatedItem) {
105
106 26
                $packedItems->insert($orientatedItem->getItem());
107 26
                $this->remainingWeight -= $itemToPack->getWeight();
108
109 26
                $this->lengthLeft -= $orientatedItem->getLength();
110 26
                $layerLength += $orientatedItem->getLength();
111 26
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);
112
113 26
                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
114
115
                //allow items to be stacked in place within the same footprint up to current layerdepth
116 26
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
117 26
                $this->tryAndStackItemsIntoSpace($packedItems, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
118
119 26
                $prevItem = $orientatedItem;
120 26
            } else {
121
122 23
                $prevItem = null;
123
124 23
                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
125 22
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
126 22
                    $this->lengthLeft += $layerLength;
127 22
                    $this->widthLeft -= $layerWidth;
128 22
                    $layerWidth = $layerLength = 0;
129 22
                    $this->items->insert($itemToPack);
130 22
                    continue;
131 18
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
132 7
                    $this->logger->debug("doesn't fit on layer even when empty");
133 7
                    continue;
134
                }
135
136 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...
137 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...
138 17
                $this->depthLeft -= $layerDepth;
139
140 17
                $layerWidth = $layerLength = $layerDepth = 0;
141 17
                $this->logger->debug("doesn't fit, so starting next vertical layer");
142 17
                $this->items->insert($itemToPack);
143
            }
144 26
        }
145 26
        $this->logger->debug("done with this box");
146 26
        return new PackedBox($this->box, $packedItems, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->remainingWeight);
147
    }
148
149
    /**
150
     * Get the best orientation for an item
151
     * @param Item $item
152
     * @param OrientatedItem|null $prevItem
153
     * @param Item|null $nextItem
154
     * @param int $widthLeft
155
     * @param int $lengthLeft
156
     * @param int $depthLeft
157
     * @return OrientatedItem|false
158
     */
159 26
    protected function findBestOrientation(Item $item, OrientatedItem $prevItem = null, Item $nextItem = null, $widthLeft, $lengthLeft, $depthLeft) {
160
161 26
        $orientations = $this->findPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
162
163 26
        if (empty($orientations)) {
164 24
            return false;
165
        }
166
167
        // special casing based on next item
168 26
        if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) {
169 5
            $this->logger->debug("not rotating based on next item");
170 5
            return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations()
171
        }
172
173 26
        $orientationFits = [];
174
175
        /** @var OrientatedItem $orientation */
176 26
        foreach ($orientations as $o => $orientation) {
177 26
            $orientationFit = min($widthLeft   - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
178 26
            $orientationFits[$o] = $orientationFit;
179 26
        }
180
181 26
        if (!empty($orientationFits)) {
182 26
            asort($orientationFits);
183 26
            reset($orientationFits);
184 26
            $bestFit = key($orientationFits);
185 26
            $this->logger->debug("Using orientation #{$bestFit}");
186 26
            return $orientations[$bestFit];
187
        } else {
188
            return false;
189
        }
190
    }
191
192
    /**
193
     * Find all possible orientations for an item
194
     * @param Item $item
195
     * @param OrientatedItem|null $prevItem
196
     * @param int $widthLeft
197
     * @param int $lengthLeft
198
     * @param int $depthLeft
199
     * @return OrientatedItem[]
200
     */
201 26
    protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
202
203 26
        $orientations = [];
204
205
        //Special case items that are the same as what we just packed - keep orientation
206 26
        if ($prevItem && $prevItem->getItem() == $item) {
207 9
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
208 9
        } else {
209
210
            //simple 2D rotation
211 26
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
212 26
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
213
214
            //add 3D rotation if we're allowed
215 26
            if (!$item->getKeepFlat()) {
216 10
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
217 10
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
218 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
219 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
220 10
            }
221
        }
222
223
        //remove any that simply don't fit
224 26
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
225 26
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
226 26
        });
227
228
    }
229
230
    /**
231
     * Figure out if we can stack the next item vertically on top of this rather than side by side
232
     * Used when we've packed a tall item, and have just put a shorter one next to it
233
     * @param ItemList $packedItems
234
     * @param int $maxWidth
235
     * @param int $maxLength
236
     * @param int $maxDepth
237
     * @return bool
0 ignored issues
show
Documentation introduced by Doug Wright
Should the return type not be boolean|null?

This check compares the return type specified in the @return annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch.

Loading history...
238
     */
239 26
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, $maxWidth, $maxLength, $maxDepth)
240
    {
241 26
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
242 24
            $stackedItem = $this->findBestOrientation($this->items->top(), null, null, $maxWidth, $maxLength, $maxDepth);
243 24
            if ($stackedItem) {
244 1
                $this->remainingWeight -= $this->items->top()->getWeight();
245 1
                $maxDepth -= $stackedItem->getDepth();
246 1
                $packedItems->insert($this->items->extract());
247 1
            } else {
248 24
                break;
249
            }
250 1
        }
251 26
    }
252
253
    /**
254
     * @param int $layerWidth
255
     * @param int $layerLength
256
     * @param int $layerDepth
257
     * @return bool
258
     */
259 23
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
260 23
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
261
    }
262
}
263