#include <src/libnest2d/include/libnest2d/selections/firstfit.hpp>

Inheritance diagram for libnest2d::selections::_FirstFitSelection< RawShape >:

Collaboration diagram for libnest2d::selections::_FirstFitSelection< RawShape >:

Public Types
using	Config = int

using	Item = _Item< RawShape >

using	ShapeType = RawShape

using	PackGroup = _PackGroup< RawShape >

Public Member Functions
void	configure (const Config &)

template<class TPlacer , class TIterator , class TBin = typename PlacementStrategyLike<TPlacer>::BinType, class PConfig = typename PlacementStrategyLike<TPlacer>::Config>
void	packItems (TIterator first, TIterator last, TBin &&bin, PConfig &&pconfig=PConfig())

const PackGroup &	getResult () const

int	lastPackedBinId () const

void	progressIndicator (ProgressFunction fn)

void	stopCondition (StopCondition cond)

void	clear ()

Protected Member Functions
template<class Placer , class Container , class Bin , class PCfg >
void	remove_unpackable_items (Container &c, const Bin &bin, const PCfg &pcfg)

Protected Attributes
ProgressFunction	progress_ = [](unsigned){}

StopCondition	stopcond_ = [](){ return false; }

int	last_packed_bin_id_ = -1

Private Types
using	Base = SelectionBoilerplate< RawShape >

using	Container = ItemGroup

using	ItemGroup = _ItemGroup< RawShape >

Private Attributes
Container	store_

PackGroup	packed_bins_

Detailed Description

template<class RawShape>
class libnest2d::selections::_FirstFitSelection< RawShape >

Member Typedef Documentation

◆ Base

template<class RawShape >

using libnest2d::selections::_FirstFitSelection< RawShape >::Base = SelectionBoilerplate<RawShape>

private

◆ Config

template<class RawShape >

using libnest2d::selections::_FirstFitSelection< RawShape >::Config = int

◆ Container

template<class RawShape >

using libnest2d::selections::_FirstFitSelection< RawShape >::Container = ItemGroup

private

◆ Item

template<class RawShape >

using libnest2d::selections::SelectionBoilerplate< RawShape >::Item = _Item<RawShape>

◆ ItemGroup

template<class RawShape >

using libnest2d::selections::SelectionBoilerplate< RawShape >::ItemGroup = _ItemGroup<RawShape>

private

◆ PackGroup

template<class RawShape >

using libnest2d::selections::SelectionBoilerplate< RawShape >::PackGroup = _PackGroup<RawShape>

inherited

◆ ShapeType

template<class RawShape >

using libnest2d::selections::SelectionBoilerplate< RawShape >::ShapeType = RawShape

inherited

Member Function Documentation

◆ clear()

template<class RawShape >

void libnest2d::selections::SelectionBoilerplate< RawShape >::clear ( )

inlineinherited

27{ packed_bins_.clear(); }

libnest2d::selections::SelectionBoilerplate::packed_bins_

PackGroup packed_bins_

Definition selection_boilerplate.hpp:56

References libnest2d::selections::SelectionBoilerplate< RawShape >::packed_bins_.

◆ configure()

template<class RawShape >

void libnest2d::selections::_FirstFitSelection< RawShape >::configure ( const Config & )

inline

24{ }

◆ getResult()

template<class RawShape >

const PackGroup & libnest2d::selections::SelectionBoilerplate< RawShape >::getResult ( ) const

inlineinherited

                                              {
        return packed_bins_;
    }

References libnest2d::selections::SelectionBoilerplate< RawShape >::packed_bins_.

◆ lastPackedBinId()

template<class RawShape >

int libnest2d::selections::SelectionBoilerplate< RawShape >::lastPackedBinId ( ) const

inlineinherited

21{ return last_packed_bin_id_; }

libnest2d::selections::SelectionBoilerplate::last_packed_bin_id_

int last_packed_bin_id_

Definition selection_boilerplate.hpp:59

References libnest2d::selections::SelectionBoilerplate< RawShape >::last_packed_bin_id_.

◆ packItems()

template<class RawShape >

template<class TPlacer , class TIterator , class TBin = typename PlacementStrategyLike<TPlacer>::BinType, class PConfig = typename PlacementStrategyLike<TPlacer>::Config>

void libnest2d::selections::_FirstFitSelection< RawShape >::packItems	(	TIterator	first,
		TIterator	last,
		TBin &&	bin,
		PConfig &&	pconfig = `PConfig()`
	)

inline

    {
 
        using Placer = PlacementStrategyLike<TPlacer>;
 
        store_.clear();
        store_.reserve(last-first);
 
        std::vector<Placer> placers;
        placers.reserve(last-first);
        
        std::for_each(first, last, [this](Item& itm) {
            if(itm.isFixed()) {
                if (itm.binId() < 0) itm.binId(0);
                auto binidx = size_t(itm.binId());
                
                while(packed_bins_.size() <= binidx)
                    packed_bins_.emplace_back();
                
                packed_bins_[binidx].emplace_back(itm);
            } else {
                store_.emplace_back(itm);
            }
        });
 
        // If the packed_items array is not empty we have to create as many
        // placers as there are elements in packed bins and preload each item
        // into the appropriate placer
        for(ItemGroup& ig : packed_bins_) {
            placers.emplace_back(bin);
            placers.back().configure(pconfig);
            placers.back().preload(ig);
        }
        
        auto sortfunc = [](Item& i1, Item& i2) {
            int p1 = i1.priority(), p2 = i2.priority();
            return p1 == p2 ? i1.area() > i2.area() : p1 > p2;
        };
 
        std::sort(store_.begin(), store_.end(), sortfunc);
 
        auto total = last-first;
        auto makeProgress = [this, &total](Placer& placer, size_t bin_idx) {
            packed_bins_[bin_idx] = placer.getItems();
            this->last_packed_bin_id_ = int(bin_idx);
            this->progress_(static_cast<unsigned>(--total));
        };
 
        auto& cancelled = this->stopcond_;
        
        this->template remove_unpackable_items<Placer>(store_, bin, pconfig);
 
        auto it = store_.begin();
 
        while(it != store_.end() && !cancelled()) {
            bool was_packed = false;
            size_t j = 0;
            while(!was_packed && !cancelled()) {
                for(; j < placers.size() && !was_packed && !cancelled(); j++) {
                    if((was_packed = placers[j].pack(*it, rem(it, store_) ))) {
                        it->get().binId(int(j));
                        makeProgress(placers[j], j);
                    }
                }
 
                if(!was_packed) {
                    placers.emplace_back(bin);
                    placers.back().configure(pconfig);
                    packed_bins_.emplace_back();
                    j = placers.size() - 1;
                }
            }
            ++it;
        }
    }

References libnest2d::_Item< RawShape >::area(), libnest2d::_Item< RawShape >::isFixed(), libnest2d::selections::SelectionBoilerplate< RawShape >::last_packed_bin_id_, libnest2d::selections::_FirstFitSelection< RawShape >::packed_bins_, libnest2d::_Item< RawShape >::priority(), libnest2d::selections::SelectionBoilerplate< RawShape >::progress_, libnest2d::rem(), libnest2d::selections::SelectionBoilerplate< RawShape >::stopcond_, and libnest2d::selections::_FirstFitSelection< RawShape >::store_.

Here is the call graph for this function:

◆ progressIndicator()

template<class RawShape >

void libnest2d::selections::SelectionBoilerplate< RawShape >::progressIndicator ( ProgressFunction fn )

inlineinherited

23{ progress_ = fn; }

References libnest2d::selections::SelectionBoilerplate< RawShape >::progress_.

◆ remove_unpackable_items()

template<class RawShape >

template<class Placer , class Container , class Bin , class PCfg >

void libnest2d::selections::SelectionBoilerplate< RawShape >::remove_unpackable_items	(	Container &	c,
		const Bin &	bin,
		const PCfg &	pcfg
	)

inlineprotectedinherited

    {
        // Safety test: try to pack each item into an empty bin. If it fails
        // then it should be removed from the list
        auto it = c.begin();
        while (it != c.end() && !stopcond_()) {
 
            // WARNING: The copy of itm needs to be created before Placer.
            // Placer is working with references and its destructor still
            // manipulates the item this is why the order of stack creation
            // matters here.
            const Item& itm = *it;
            Item cpy{itm};
 
            Placer p{bin};
            p.configure(pcfg);
            if (itm.area() <= 0 || !p.pack(cpy)) {
                static_cast<Item&>(*it).binId(BIN_ID_UNSET);
                it = c.erase(it);
            }
            else it++;
        }
    }