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

use function array_merge;
use function count;
use const PHP_INT_MAX;
use SplObjectStorage;
use function usort;

/**
 * Actual packer.
 *
 * @author Doug Wright
 */
class Packer
{
    /**
     * Number of boxes at which balancing weight is deemed not worth it.
     *
     * @var int
     */
    protected $maxBoxesToBalanceWeight = 12;

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

    /**
     * List of box sizes available to pack items into.
     *
     * @var BoxList
     */
    protected $boxes;

    /**
     * Quantities available of each box type.
     *
     * @var SplObjectStorage
     */
    protected $boxesQtyAvailable;

    /**
     * Constructor.
     */
    public function __construct()
    {
        $this->items = new ItemList();
        $this->boxes = new BoxList();
        $this->boxesQtyAvailable = new SplObjectStorage();
    }

    /**
     * Add item to be packed.
     * @param Item $item
     * @param int $qty
     * @return void
     */
    public function addItem(Item $item, $qty = 1)
    {
        for ($i = 0; $i < $qty; ++$i) {
            $this->items->insert($item);
        }
    }

    /**
     * Set a list of items all at once.
     * @param iterable|Item[] $items
     * @return void
     */
    public function setItems($items)
    {
        if ($items instanceof ItemList) {
            $this->items = clone $items;
        } else {
            $this->items = new ItemList();
            foreach ($items as $item) {
                $this->items->insert($item);
            }
        }
    }

    /**
     * Add box size.
     * @param Box $box
     * @return void
     */
    public function addBox(Box $box)
    {
        $this->boxes->insert($box);
        $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
    }

    /**
     * Add a pre-prepared set of boxes all at once.
     * @param BoxList $boxList
     * @return void
     */
    public function setBoxes(BoxList $boxList)
    {
        $this->boxes = $boxList;
        foreach ($this->boxes as $box) {
            $this->setBoxQuantity($box, $box instanceof LimitedSupplyBox ? $box->getQuantityAvailable() : PHP_INT_MAX);
        }
    }

    /**
     * Set the quantity of this box type available.
     * @param Box $box
     * @param int $qty
     * @return void
     */
    public function setBoxQuantity(Box $box, $qty)
    {
        $this->boxesQtyAvailable[$box] = $qty;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
     * @return int
     */
    public function getMaxBoxesToBalanceWeight()
    {
        return $this->maxBoxesToBalanceWeight;
    }

    /**
     * Number of boxes at which balancing weight is deemed not worth the extra computation time.
     * @param int $maxBoxesToBalanceWeight
     * @return void
     */
    public function setMaxBoxesToBalanceWeight($maxBoxesToBalanceWeight)
    {
        $this->maxBoxesToBalanceWeight = $maxBoxesToBalanceWeight;
    }

    /**
     * Pack items into boxes.
     * @return PackedBoxList
     */
    public function pack()
    {
        $this->sanityPrecheck();
        $packedBoxes = $this->doVolumePacking();

        //If we have multiple boxes, try and optimise/even-out weight distribution
        if ($packedBoxes->count() > 1 && $packedBoxes->count() <= $this->maxBoxesToBalanceWeight) {
            $redistributor = new WeightRedistributor($this->boxes, $this->boxesQtyAvailable);
            $packedBoxes = $redistributor->redistributeWeight($packedBoxes);
        }

        return $packedBoxes;
    }

    /**
     * Pack items into boxes using the principle of largest volume item first.
     *
     * @param bool $singlePassMode
     * @param bool $enforceSingleBox
     * @return PackedBoxList
     */
    public function doVolumePacking($singlePassMode = false, $enforceSingleBox = false)
    {
        $packedBoxes = new PackedBoxList();

        //Keep going until everything packed
        while ($this->items->count()) {
            $packedBoxesIteration = [];

            //Loop through boxes starting with smallest, see what happens
            foreach ($this->getBoxList($enforceSingleBox) as $box) {
                $volumePacker = new VolumePacker($box, $this->items);
                $volumePacker->setSinglePassMode($singlePassMode);
                $packedBox = $volumePacker->pack();
                if ($packedBox->getItems()->count()) {
                    $packedBoxesIteration[] = $packedBox;

                    //Have we found a single box that contains everything?
                    if ($packedBox->getItems()->count() === $this->items->count()) {
                        break;
                    }
                }
            }

            try {
                //Find best box of iteration, and remove packed items from unpacked list
                $bestBox = $this->findBestBoxFromIteration($packedBoxesIteration);
            } catch (NoBoxesAvailableException $e) {
                if ($enforceSingleBox) {
                    return new PackedBoxList();
                }
                throw $e;
            }

            $this->items->removePackedItems($bestBox->getItems());

            $packedBoxes->insert($bestBox);
            $this->boxesQtyAvailable[$bestBox->getBox()] = $this->boxesQtyAvailable[$bestBox->getBox()] - 1;
        }

        return $packedBoxes;
    }

    /**
     * Get a "smart" ordering of the boxes to try packing items into. The initial BoxList is already sorted in order
     * so that the smallest boxes are evaluated first, but this means that time is spent on boxes that cannot possibly
     * hold the entire set of items due to volume limitations. These should be evaluated first.
     * @param bool $enforceSingleBox
     * @return iterable
     */
    protected function getBoxList($enforceSingleBox)
    {
        $itemVolume = 0;
        foreach ($this->items as $item) {
            $itemVolume += $item->getWidth() * $item->getLength() * $item->getDepth();
        }

        $preferredBoxes = [];
        $otherBoxes = [];
        foreach ($this->boxes as $box) {
            if ($this->boxesQtyAvailable[$box] > 0) {
                if ($box->getInnerWidth() * $box->getInnerLength() * $box->getInnerDepth() >= $itemVolume) {
                    $preferredBoxes[] = $box;
                } elseif (!$enforceSingleBox) {
                    $otherBoxes[] = $box;
                }
            }
        }

        return array_merge($preferredBoxes, $otherBoxes);
    }

    /**
     * @param PackedBox[] $packedBoxes
     * @return PackedBox
     */
    protected function findBestBoxFromIteration(array $packedBoxes)
    {
        if (count($packedBoxes) === 0) {
            throw new NoBoxesAvailableException("No boxes could be found for item '{$this->items->top()->getDescription()}'", $this->items->top());
        }

        usort($packedBoxes, [$this, 'compare']);

        return $packedBoxes[0];
    }

    /**
     * @return void
     */
    private function sanityPrecheck()
    {
        /** @var Item $item */
        foreach ($this->items as $item) {
            $possibleFits = 0;

            /** @var Box $box */
            foreach ($this->boxes as $box) {
                if ($item->getWeight() <= ($box->getMaxWeight() - $box->getEmptyWeight())) {
                    $possibleFits += count((new OrientatedItemFactory($box))->getPossibleOrientationsInEmptyBox($item));
                }
            }

            if ($possibleFits === 0) {
                throw new ItemTooLargeException("Item '{$item->getDescription()}' is too large to fit into any box", $item);
            }
        }
    }

    /**
     * @param PackedBox $boxA
     * @param PackedBox $boxB
     * @return int
     */
    private static function compare(PackedBox $boxA, PackedBox $boxB)
    {
        $choice = mixCmp($boxB->getItems()->count(), $boxA->getItems()->count());

        if ($choice === 0) {
            $choice = mixCmp($boxB->getVolumeUtilisation(), $boxA->getVolumeUtilisation());
        }
        if ($choice === 0) {
            $choice = mixCmp($boxB->getUsedVolume(), $boxA->getUsedVolume());
        }

        return $choice;
    }
}
