#include <map>
#include <vector>
#include <algorithm>
class BinKey;
typedef std::vector<double> Bin;
typedef std::multimap<BinKey,Bin> BinMap;
class BinKey
{
private:
double m_size;
bool m_isFull;
public:
BinKey()
: m_size(0),m_isFull(false){}
BinKey(double val)
: m_size(val),m_isFull(false){}
bool operator<(const BinKey & rhs ) const
{
return this->size() > rhs.size();
}
double size() const { return m_size; }
bool isFull() const { return m_isFull; }
void isFull(bool val) { m_isFull = val; }
};
class BinPacker
{
private:
Bin m_bin;
BinMap m_binMap;
const size_t m_binSize;
public:
BinPacker(const Bin &bin, size_t binSize) : m_bin(bin),m_binSize(binSize)
{
}
~BinPacker(void)
{
}
void eval()
{
std::sort(m_bin.begin(), m_bin.end(),std::greater<double>());
double minVal = m_bin.back();
for(auto vecIter = m_bin.begin(); vecIter != m_bin.end() ; ++vecIter)
{
if(m_binMap.size() == 0)
m_binMap.insert(std::make_pair(BinKey(),Bin()));
bool erase = false;
BinMap::iterator lastIter;
for(auto mapIter = m_binMap.begin(); mapIter != m_binMap.end(); ++mapIter)
{
const double siz = m_binSize - mapIter->first.size();
if(!mapIter->first.isFull() && siz >= *vecIter && *vecIter <= m_binSize)
{
lastIter = mapIter;
erase = true;
break;
}
}
if(erase)
{
BinKey newKey(lastIter->first.size()+*vecIter);
if(m_binSize - newKey.size() < minVal)
newKey.isFull(true);
auto thisIter = m_binMap.insert(std::make_pair(newKey,Bin()));
lastIter->second.push_back(*vecIter);
thisIter->second.swap(lastIter->second);
m_binMap.erase(lastIter);
}
else
{
if(*vecIter <= m_binSize)
{
auto thisIter = m_binMap.insert(std::make_pair(BinKey(*vecIter),Bin()));
thisIter->second.push_back(*vecIter);
}
}
}
}
};