Issues in VolumePacker.php - All Issues - Inspection of "PackedBox->getUsedDepth() could incorrectly return..." - dvdoug/BoxPacker - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — 2.x-dev ( c9b8f5...bdb7c7 )

by Doug

created 2017-04-15 17:39 UTC

VolumePacker.php (4 issues)

Labels

Severity

Upgrade to new PHP Analysis Engine

These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more

<?php
/**
 * Box packing (3D bin packing, knapsack problem)
 * @package BoxPacker
 * @author Doug Wright
 */
namespace DVDoug\BoxPacker;

use Psr\Log\LoggerAwareInterface;
use Psr\Log\LoggerAwareTrait;
use Psr\Log\NullLogger;

/**
 * Actual packer
 * @author Doug Wright
 * @package BoxPacker
 */
class VolumePacker implements LoggerAwareInterface
{
    use LoggerAwareTrait;

    /**
     * Box to pack items into
     * @var Box
     */
    protected $box;

    /**
     * List of items to be packed
     * @var ItemList
     */
    protected $items;

    /**
     * Remaining width of the box to pack items into
     * @var int
     */
    protected $widthLeft;

    /**
     * Remaining length of the box to pack items into
     * @var int
     */
    protected $lengthLeft;

    /**
     * Remaining depth of the box to pack items into
     * @var int
     */
    protected $depthLeft;

    /**
     * Remaining weight capacity of the box
     * @var int
     */
    protected $remainingWeight;

    /**
     * Used width inside box for packing items
     * @var int
     */
    protected $usedWidth = 0;

    /**
     * Used length inside box for packing items
     * @var int
     */
    protected $usedLength = 0;

    /**
     * Used depth inside box for packing items
     * @var int
     */
    protected $usedDepth = 0;

    /**
     * Constructor
     *
     * @param Box      $box
     * @param ItemList $items
     */
    public function __construct(Box $box, ItemList $items)
    {
        $this->logger = new NullLogger();

        $this->box = $box;
        $this->items = $items;

        $this->depthLeft = $this->box->getInnerDepth();
        $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
        $this->widthLeft = $this->box->getInnerWidth();
        $this->lengthLeft = $this->box->getInnerLength();
    }

    /**
     * Pack as many items as possible into specific given box
     * @return PackedBox packed box
     */
    public function pack()
    {
        $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");

        $packedItems = new ItemList;

        $layerWidth = $layerLength = $layerDepth = 0;

        $prevItem = null;

        while (!$this->items->isEmpty()) {

            $itemToPack = $this->items->extract();

            //skip items that are simply too heavy
            if (!$this->checkNonDimensionalConstraints($itemToPack, $packedItems)) {
                continue;
            }

            $this->logger->debug(
                "evaluating item {$itemToPack->getDescription()} for fit",
                [
                    'item' => $itemToPack,
                    'space' => [
                        'widthLeft'   => $this->widthLeft,
                        'lengthLeft'  => $this->lengthLeft,
                        'depthLeft'   => $this->depthLeft,
                        'layerWidth'  => $layerWidth,
                        'layerLength' => $layerLength,
                        'layerDepth'  => $layerDepth
                    ]
                ]
            );

            $nextItem = !$this->items->isEmpty() ? $this->items->top() : null;

            $orientatedItemFactory = new OrientatedItemFactory();
            $orientatedItemFactory->setLogger($this->logger);
            $orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);

            if ($orientatedItem) {

                $packedItems->insert($orientatedItem->getItem());
                $this->remainingWeight -= $itemToPack->getWeight();

                $this->lengthLeft -= $orientatedItem->getLength();
                $layerLength += $orientatedItem->getLength();
                $layerWidth = max($orientatedItem->getWidth(), $layerWidth);

                $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep

                $this->usedLength = max($this->usedLength, $layerLength);
                $this->usedWidth = max($this->usedWidth, $layerWidth);

                //allow items to be stacked in place within the same footprint up to current layerdepth
                $stackableDepth = $layerDepth - $orientatedItem->getDepth();
                $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);

                $prevItem = $orientatedItem;

                if ($this->items->isEmpty()) {
                    $this->usedDepth += $layerDepth;
                }
            } else {

                $prevItem = null;

                if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
                    $this->logger->debug("No more fit in lengthwise, resetting for new row");
                    $this->lengthLeft += $layerLength;
                    $this->widthLeft -= $layerWidth;
                    $layerWidth = $layerLength = 0;
                    $this->items->insert($itemToPack);
                    continue;
                } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) {
                    $this->logger->debug("doesn't fit on layer even when empty");
                    $this->usedDepth += $layerDepth;
                    continue;
                }

                $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
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;
}
                $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
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;
}
                $this->depthLeft -= $layerDepth;
                $this->usedDepth += $layerDepth;

                $layerWidth = $layerLength = $layerDepth = 0;
                $this->logger->debug("doesn't fit, so starting next vertical layer");
                $this->items->insert($itemToPack);
            }
        }
        $this->logger->debug("done with this box");
        return new PackedBox(
            $this->box,
            $packedItems,
            $this->widthLeft,
            $this->lengthLeft,
            $this->depthLeft,
            $this->remainingWeight,
            $this->usedWidth,
            $this->usedLength,
            $this->usedDepth);
    }

    /**
     * Figure out if we can stack the next item vertically on top of this rather than side by side
     * Used when we've packed a tall item, and have just put a shorter one next to it
     *
     * @param ItemList       $packedItems
     * @param OrientatedItem $prevItem

     * @param Item           $nextItem

     * @param int            $maxWidth
     * @param int            $maxLength
     * @param int            $maxDepth
     */
    protected function tryAndStackItemsIntoSpace(
        ItemList $packedItems,
        OrientatedItem $prevItem = null,
        Item $nextItem = null,
        $maxWidth,
        $maxLength,
        $maxDepth
    ) {
        $orientatedItemFactory = new OrientatedItemFactory();
        $orientatedItemFactory->setLogger($this->logger);

        while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
            $stackedItem = $orientatedItemFactory->getBestOrientation(
                $this->box,
                $this->items->top(),
                $prevItem,
                $nextItem,
                $maxWidth,
                $maxLength,
                $maxDepth
            );
            if ($stackedItem) {
                $this->remainingWeight -= $this->items->top()->getWeight();
                $maxDepth -= $stackedItem->getDepth();
                $packedItems->insert($this->items->extract());
            } else {
                break;
            }
        }
    }

    /**
     * @param int $layerWidth
     * @param int $layerLength
     * @param int $layerDepth
     * @return bool
     */
    protected function isLayerStarted($layerWidth, $layerLength, $layerDepth)
    {
        return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
    }

    /**
     * As well as purely dimensional constraints, there are other constraints that need to be met
     * e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box)
     *
     * @param Item     $itemToPack
     * @param ItemList $packedItems
     *
     * @return bool
     */
    protected function checkNonDimensionalConstraints(Item $itemToPack, ItemList $packedItems)
    {
        $weightOK = $itemToPack->getWeight() <= $this->remainingWeight;

        if ($itemToPack instanceof ConstrainedItem) {
            return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box);
        }

        return $weightOK;
    }
}


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		* Used width inside box for packing items
60		* @var int
61		*/
62		protected $usedWidth = 0;
63
64		/**
65		* Used length inside box for packing items
66		* @var int
67		*/
68		protected $usedLength = 0;
69
70		/**
71		* Used depth inside box for packing items
72		* @var int
73		*/
74		protected $usedDepth = 0;
75
76		/**
77		* Constructor
78		*
79		* @param Box $box
80		* @param ItemList $items
81		*/
82	33	public function __construct(Box $box, ItemList $items)
83		{
84	33	$this->logger = new NullLogger();
85
86	33	$this->box = $box;
87	33	$this->items = $items;
88
89	33	$this->depthLeft = $this->box->getInnerDepth();
90	33	$this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight();
91	33	$this->widthLeft = $this->box->getInnerWidth();
92	33	$this->lengthLeft = $this->box->getInnerLength();
93		}
94
95		/**
96		* Pack as many items as possible into specific given box
97		* @return PackedBox packed box
98		*/
99	33	public function pack()
100		{
101	33	$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}");
102
103	33	$packedItems = new ItemList;
104
105	33	$layerWidth = $layerLength = $layerDepth = 0;
106
107	33	$prevItem = null;
108
109	33	while (!$this->items->isEmpty()) {
110
111	33	$itemToPack = $this->items->extract();
112
113		//skip items that are simply too heavy
114	33	if (!$this->checkNonDimensionalConstraints($itemToPack, $packedItems)) {
115	5	continue;
116		}
117
118	33	$this->logger->debug(
119	33	"evaluating item {$itemToPack->getDescription()} for fit",
120		[
121	33	'item' => $itemToPack,
122		'space' => [
123	33	'widthLeft' => $this->widthLeft,
124	33	'lengthLeft' => $this->lengthLeft,
125	33	'depthLeft' => $this->depthLeft,
126	33	'layerWidth' => $layerWidth,
127	33	'layerLength' => $layerLength,
128	33	'layerDepth' => $layerDepth
129		]
130		]
131		);
132
133	33	$nextItem = !$this->items->isEmpty() ? $this->items->top() : null;
134
135	33	$orientatedItemFactory = new OrientatedItemFactory();
136	33	$orientatedItemFactory->setLogger($this->logger);
137	33	$orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft);
138
139	33	if ($orientatedItem) {
140
141	33	$packedItems->insert($orientatedItem->getItem());
142	33	$this->remainingWeight -= $itemToPack->getWeight();
143
144	33	$this->lengthLeft -= $orientatedItem->getLength();
145	33	$layerLength += $orientatedItem->getLength();
146	33	$layerWidth = max($orientatedItem->getWidth(), $layerWidth);
147
148	33	$layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep
149
150	33	$this->usedLength = max($this->usedLength, $layerLength);
151	33	$this->usedWidth = max($this->usedWidth, $layerWidth);
152
153		//allow items to be stacked in place within the same footprint up to current layerdepth
154	33	$stackableDepth = $layerDepth - $orientatedItem->getDepth();
155	33	$this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth);
156
157	33	$prevItem = $orientatedItem;
158
159	33	if ($this->items->isEmpty()) {
160	33	$this->usedDepth += $layerDepth;
161		}
162		} else {
163
164	25	$prevItem = null;
165
166	25	if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) {
167	24	$this->logger->debug("No more fit in lengthwise, resetting for new row");
168	24	$this->lengthLeft += $layerLength;
169	24	$this->widthLeft -= $layerWidth;
170	24	$layerWidth = $layerLength = 0;
171	24	$this->items->insert($itemToPack);
172	24	continue;
173	19	} elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) \|\| $layerDepth == 0) {
174	8	$this->logger->debug("doesn't fit on layer even when empty");
175	8	$this->usedDepth += $layerDepth;
176	8	continue;
177		}
178
179	17	$this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth();
		0 ignored issues – show Documentation Bug introduced 2016-09-25 18:15 UTC by Report Bug Copy Issue Report Show Similar Issues like this 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...
180	17	$this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength();
		0 ignored issues – show Documentation Bug introduced 2016-09-25 18:15 UTC by Report Bug Copy Issue Report Show Similar Issues like this 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...
181	17	$this->depthLeft -= $layerDepth;
182	17	$this->usedDepth += $layerDepth;
183
184	17	$layerWidth = $layerLength = $layerDepth = 0;
185	17	$this->logger->debug("doesn't fit, so starting next vertical layer");
186	17	$this->items->insert($itemToPack);
187		}
188		}
189	33	$this->logger->debug("done with this box");
190	33	return new PackedBox(
191	33	$this->box,
192		$packedItems,
193	33	$this->widthLeft,
194	33	$this->lengthLeft,
195	33	$this->depthLeft,
196	33	$this->remainingWeight,
197	33	$this->usedWidth,
198	33	$this->usedLength,
199	33	$this->usedDepth);
200		}
201
202		/**
203		* Figure out if we can stack the next item vertically on top of this rather than side by side
204		* Used when we've packed a tall item, and have just put a shorter one next to it
205		*
206		* @param ItemList $packedItems
207		* @param OrientatedItem $prevItem
		0 ignored issues – show Documentation introduced 2017-01-07 19:45 UTC by Report Bug Copy Issue Report Show Similar Issues like this 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...
208		* @param Item $nextItem
		0 ignored issues – show Documentation introduced 2017-01-07 19:45 UTC by Report Bug Copy Issue Report Show Similar Issues like this 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...
209		* @param int $maxWidth
210		* @param int $maxLength
211		* @param int $maxDepth
212		*/
213	33	protected function tryAndStackItemsIntoSpace(
214		ItemList $packedItems,
215		OrientatedItem $prevItem = null,
216		Item $nextItem = null,
217		$maxWidth,
218		$maxLength,
219		$maxDepth
220		) {
221	33	$orientatedItemFactory = new OrientatedItemFactory();
222	33	$orientatedItemFactory->setLogger($this->logger);
223
224	33	while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) {
225	31	$stackedItem = $orientatedItemFactory->getBestOrientation(
226	31	$this->box,
227	31	$this->items->top(),
228		$prevItem,
229		$nextItem,
230		$maxWidth,
231		$maxLength,
232		$maxDepth
233		);
234	31	if ($stackedItem) {
235	3	$this->remainingWeight -= $this->items->top()->getWeight();
236	3	$maxDepth -= $stackedItem->getDepth();
237	3	$packedItems->insert($this->items->extract());
238		} else {
239	31	break;
240		}
241		}
242		}
243
244		/**
245		* @param int $layerWidth
246		* @param int $layerLength
247		* @param int $layerDepth
248		* @return bool
249		*/
250	25	protected function isLayerStarted($layerWidth, $layerLength, $layerDepth)
251		{
252	25	return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0;
253		}
254
255		/**
256		* As well as purely dimensional constraints, there are other constraints that need to be met
257		* e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box)
258		*
259		* @param Item $itemToPack
260		* @param ItemList $packedItems
261		*
262		* @return bool
263		*/
264	33	protected function checkNonDimensionalConstraints(Item $itemToPack, ItemList $packedItems)
265		{
266	33	$weightOK = $itemToPack->getWeight() <= $this->remainingWeight;
267
268	33	if ($itemToPack instanceof ConstrainedItem) {
269	1	return $weightOK && $itemToPack->canBePackedInBox(clone $packedItems, $this->box);
270		}
271
272	32	return $weightOK;
273		}
274		}
275

dvdoug / BoxPacker

Push — 2.x-dev ( c9b8f5...bdb7c7 )

VolumePacker.php (4 issues)

Labels

Severity

Introduced By

Upgrade to new PHP Analysis Engine

Duplication Side-by-Side

Filter issues like