Created
September 3, 2015 20:39
-
-
Save dcabanaw/f7df7d36f9cfa5763a4f to your computer and use it in GitHub Desktop.
Simple bin packing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class Bin | |
{ | |
private $capacity; | |
private $content; | |
/** | |
* @param integer $capacity | |
* @param array $content | |
*/ | |
public function __construct($capacity, array $content = []) | |
{ | |
$this->capacity = $capacity; | |
$this->content = $content; | |
} | |
/** | |
* @param integer $item | |
* | |
* @return bool | |
*/ | |
public function add($item) | |
{ | |
if($this->addable($item)) | |
{ | |
array_push($this->content, $item); | |
return true; | |
} | |
return false; | |
} | |
/** | |
* @param integer $item | |
* | |
* @return bool | |
*/ | |
public function addable($item) | |
{ | |
return array_sum($this->content) + $item <= $this->capacity && $item > 0; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* Class BinPool | |
* simple implementation of bin packing | |
* | |
* Given a pool of item sizes/weights, a bin capacity and a quantity of bins, can the pool be fully allocated | |
* to the bins and have room to add another item | |
*/ | |
class BinPool | |
{ | |
/** | |
* @var integer | |
*/ | |
private $bin_capacity; | |
/** | |
* @var integer | |
*/ | |
private $bin_quantity; | |
/** | |
* @var array | |
*/ | |
private $pool; | |
/** | |
* @var Bin[] | |
*/ | |
private $bins = []; | |
/** | |
* @param integer $bin_capacity the capacity of each bin | |
* @param integer $bin_quantity how many bins | |
* @param array $pool an array of numeric sizes/weights | |
*/ | |
public function __construct($bin_capacity, $bin_quantity, array $pool = []) | |
{ | |
$this->bin_capacity = $bin_capacity; | |
$this->bin_quantity = $bin_quantity; | |
$this->pool = $pool; | |
$this->bins = array_map(function() use ($bin_capacity, $bin_quantity) { | |
return new Bin($bin_capacity);}, array_pad([], $bin_quantity, null)); | |
} | |
/** | |
* @param $item | |
* | |
* @return bool | |
*/ | |
public function addable($item) | |
{ | |
$this->validatePool(); | |
$this->buildBins(); | |
foreach($this->bins as $bin) | |
{ | |
if($bin->addable($item)) | |
{ | |
return true; | |
} | |
} | |
return false; | |
} | |
private function validatePool() | |
{ | |
if (!empty($this->pool)) | |
{ | |
if (max($this->pool) > $this->bin_capacity) | |
{ | |
throw new RuntimeException("An item in the pool exceeds the max size of {$this->bin_capacity}"); | |
} | |
} | |
} | |
private function buildBins() | |
{ | |
while(!empty($this->pool)) | |
{ | |
$item = array_pop($this->pool); | |
foreach($this->bins as $bin) | |
{ | |
if($bin->add($item)) | |
{ | |
break; | |
} | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
// autolader, incudes, etc... | |
$pool = [1,1,1,2,2]; | |
$bp = new BinPool(4, 2, $pool); | |
$bp->isAddable(1); //true | |
$pool = [1,1,2,2,2]; | |
$bp = new BinPool(4, 2, $pool); | |
$bp->isAddable(1); //false |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment