Completed
Push — master ( 18eaf3...294029 )
by Doug
28:49 queued 27:07
created

Packer::setMaxBoxesToBalanceWeight()   A

Complexity

Conditions 1
Paths 1

Duplication

Lines 0
Ratio 0 %

Size

Total Lines 4
Code Lines 2

Code Coverage

Tests 2
CRAP Score 1

Importance

Changes 0
Metric Value
dl 0
loc 4
ccs 2
cts 2
cp 1
rs 10
c 0
b 0
f 0
cc 1
eloc 2
nc 1
nop 1
crap 1
1
<?php
2
/**
3
 * Box packing (3D bin packing, knapsack problem)
4
 * @package BoxPacker
5
 * @author Doug Wright
6
 */
7
declare(strict_types=1);
8
namespace DVDoug\BoxPacker;
9
10
use Psr\Log\LoggerAwareInterface;
11
use Psr\Log\LoggerAwareTrait;
12
use Psr\Log\LogLevel;
13
use Psr\Log\NullLogger;
14
15
/**
16
 * Actual packer
17
 * @author Doug Wright
18
 * @package BoxPacker
19
 */
20
class Packer implements LoggerAwareInterface
21
{
22
    use LoggerAwareTrait;
23
24
    /**
25
     * Number of boxes at which balancing weight is deemed not worth it
26
     * @var int
27
     */
28
    protected $maxBoxesToBalanceWeight = 12;
29
30
    /**
31
     * List of items to be packed
32
     * @var ItemList
33
     */
34
    protected $items;
35
36
    /**
37
     * List of box sizes available to pack items into
38
     * @var BoxList
39
     */
40
    protected $boxes;
41
42
    /**
43
     * Constructor
44
     */
45 27
    public function __construct()
46
    {
47 27
        $this->items = new ItemList();
48 27
        $this->boxes = new BoxList();
49
50 27
        $this->logger = new NullLogger();
51
    }
52
53
    /**
54
     * Add item to be packed
55
     * @param Item $item
56
     * @param int  $qty
57
     */
58 26
    public function addItem(Item $item, int $qty = 1): void
59
    {
60 26
        for ($i = 0; $i < $qty; $i++) {
61 26
            $this->items->insert($item);
62
        }
63 26
        $this->logger->log(LogLevel::INFO, "added {$qty} x {$item->getDescription()}");
64
    }
65
66
    /**
67
     * Set a list of items all at once
68
     * @param \Traversable|array $items
69
     */
70 2
    public function setItems($items): void
71
    {
72 2
        if ($items instanceof ItemList) {
73
            $this->items = clone $items;
74
        } else {
75 2
            $this->items = new ItemList();
76 2
            foreach ($items as $item) {
77 2
                $this->items->insert($item);
78
            }
79
        }
80 2
    }
81
82
    /**
83
     * Add box size
84
     * @param Box $box
85
     */
86 25
    public function addBox(Box $box): void
87
    {
88 25
        $this->boxes->insert($box);
89 25
        $this->logger->log(LogLevel::INFO, "added box {$box->getReference()}");
90
    }
91
92
    /**
93
     * Add a pre-prepared set of boxes all at once
94
     * @param BoxList $boxList
95
     */
96 2
    public function setBoxes(BoxList $boxList): void
97
    {
98 2
        $this->boxes = clone $boxList;
99
    }
100
101
    /**
102
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
103
     * @return int
104
     */
105 1
    public function getMaxBoxesToBalanceWeight(): int
106
    {
107 1
        return $this->maxBoxesToBalanceWeight;
108
    }
109
110
    /**
111
     * Number of boxes at which balancing weight is deemed not worth the extra computation time
112
     * @param int $maxBoxesToBalanceWeight
113
     */
114 2
    public function setMaxBoxesToBalanceWeight(int $maxBoxesToBalanceWeight)
115
    {
116 2
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
117
    }
118
119
    /**
120
     * Pack items into boxes
121
     *
122
     * @return PackedBoxList
123
     */
124 26
    public function pack(): PackedBoxList
125
    {
126 26
        $packedBoxes = $this->doVolumePacking();
127
128
        //If we have multiple boxes, try and optimise/even-out weight distribution
129 24
        if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
130 6
            $redistributor = new WeightRedistributor($this->boxes);
131 6
            $redistributor->setLogger($this->logger);
132 6
            $packedBoxes = $redistributor->redistributeWeight($packedBoxes);
133
        }
134
135 24
        $this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
136 24
        return $packedBoxes;
137
    }
138
139
    /**
140
     * Pack items into boxes using the principle of largest volume item first
141
     *
142
     * @throws ItemTooLargeException
143
     * @return PackedBoxList
144
     */
145 26
    public function doVolumePacking(): PackedBoxList
146
    {
147
148 26
        $packedBoxes = new PackedBoxList;
149
150
        //Keep going until everything packed
151 26
        while ($this->items->count()) {
152 26
            $boxesToEvaluate = clone $this->boxes;
153 26
            $packedBoxesIteration = new PackedBoxList;
154
155
            //Loop through boxes starting with smallest, see what happens
156 26
            while (!$boxesToEvaluate->isEmpty()) {
157 25
                $box = $boxesToEvaluate->extract();
158
159 25
                $volumePacker = new VolumePacker($box, clone $this->items);
160 25
                $volumePacker->setLogger($this->logger);
161 25
                $packedBox = $volumePacker->pack();
162 25
                if ($packedBox->getItems()->count()) {
163 25
                    $packedBoxesIteration->insert($packedBox);
164
165
                    //Have we found a single box that contains everything?
166 25
                    if ($packedBox->getItems()->count() === $this->items->count()) {
167
                        break;
168
                    }
169
                }
170
            }
171
172
            //Check iteration was productive
173 26
            if ($packedBoxesIteration->isEmpty()) {
174 2
                throw new ItemTooLargeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box', $this->items->top());
175
            }
176
177
            //Find best box of iteration, and remove packed items from unpacked list
178
            /** @var PackedBox $bestBox */
179 25
            $bestBox = $packedBoxesIteration->top();
180 25
            $unPackedItems = $this->items->asArray();
181 25
            foreach (clone $bestBox->getItems() as $packedItem) {
182 25
                foreach ($unPackedItems as $unpackedKey => $unpackedItem) {
183 25
                    if ($packedItem->getItem() === $unpackedItem) {
184 25
                        unset($unPackedItems[$unpackedKey]);
185 25
                        break;
186
                    }
187
                }
188
            }
189 25
            $unpackedItemList = new ItemList();
190 25
            foreach ($unPackedItems as $unpackedItem) {
191 8
                $unpackedItemList->insert($unpackedItem);
192
            }
193 25
            $this->items = $unpackedItemList;
194 25
            $packedBoxes->insert($bestBox);
195
196
        }
197
198 24
        return $packedBoxes;
199
    }
200
}
201