Completed
Push — master ( 155d90...ef0051 )
by Doug
01:49
created

VolumePacker::findBestOrientation()   B

Complexity

Conditions 6
Paths 5

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 28
Code Lines 17

Code Coverage

Tests 17
CRAP Score 6

Importance

Changes 0
Metric Value
dl 0
loc 28
ccs 17
cts 17
cp 1
rs 8.439
c 0
b 0
f 0
cc 6
eloc 17
nc 5
nop 6
crap 6
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
        // special casing based on next item
164 26
        if (isset($orientations[0]) && $nextItem == $item && $lengthLeft >= 2 * $item->getLength()) {
165 5
            $this->logger->debug("not rotating based on next item");
166 5
            return $orientations[0]; // XXX this is tied to the ordering from ->findPossibleOrientations()
167
        }
168
169 26
        $orientationFits = [];
170
171
        /** @var OrientatedItem $orientation */
172 26
        foreach ($orientations as $o => $orientation) {
173 26
            $orientationFit = min($widthLeft   - $orientation->getWidth(), $lengthLeft  - $orientation->getLength());
174 26
            $orientationFits[$o] = $orientationFit;
175 26
        }
176
177 26
        if (!empty($orientationFits)) {
178 26
            asort($orientationFits);
179 26
            reset($orientationFits);
180 26
            $bestFit = key($orientationFits);
181 26
            $this->logger->debug("Using orientation #{$bestFit}");
182 26
            return $orientations[$bestFit];
183
        } else {
184 24
            return false;
185
        }
186
    }
187
188
    /**
189
     * Find all possible orientations for an item
190
     * @param Item $item
191
     * @param OrientatedItem|null $prevItem
192
     * @param int $widthLeft
193
     * @param int $lengthLeft
194
     * @param int $depthLeft
195
     * @return OrientatedItem[]
196
     */
197 26
    protected function findPossibleOrientations(Item $item, OrientatedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
198
199 26
        $orientations = [];
200
201
        //Special case items that are the same as what we just packed - keep orientation
202 26
        if ($prevItem && $prevItem->getItem() == $item) {
203 9
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
204 9
        } else {
205
206
            //simple 2D rotation
207 26
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
208 26
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
209
210
            //add 3D rotation if we're allowed
211 26
            if (!$item->getKeepFlat()) {
212 10
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
213 10
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
214 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
215 10
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
216 10
            }
217
        }
218
219
        //remove any that simply don't fit
220 26
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
221 26
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
222 26
        });
223
224
    }
225
226
    /**
227
     * Figure out if we can stack the next item vertically on top of this rather than side by side
228
     * Used when we've packed a tall item, and have just put a shorter one next to it
229
     * @param ItemList $packedItems
230
     * @param int $maxWidth
231
     * @param int $maxLength
232
     * @param int $maxDepth
233
     */
234 26
    protected function tryAndStackItemsIntoSpace(ItemList $packedItems, $maxWidth, $maxLength, $maxDepth)
235
    {
236 26
        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
237 24
            $stackedItem = $this->findBestOrientation($this->items->top(), null, null, $maxWidth, $maxLength, $maxDepth);
238 24
            if ($stackedItem) {
239 1
                $this->remainingWeight -= $this->items->top()->getWeight();
240 1
                $maxDepth -= $stackedItem->getDepth();
241 1
                $packedItems->insert($this->items->extract());
242 1
            } else {
243 24
                break;
244
            }
245 1
        }
246 26
    }
247
248
    /**
249
     * @param int $layerWidth
250
     * @param int $layerLength
251
     * @param int $layerDepth
252
     * @return bool
253
     */
254 23
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) {
255 23
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
256
    }
257
}
258