1 #ifndef FIRSTFIT_HPP 2 #define FIRSTFIT_HPP 3 4 #include "selection_boilerplate.hpp" 5 6 namespace libnest2d { namespace selections { 7 8 template<class RawShape> 9 class _FirstFitSelection: public SelectionBoilerplate<RawShape> { 10 using Base = SelectionBoilerplate<RawShape>; 11 public: 12 using typename Base::Item; 13 using Config = int; //dummy 14 15 private: 16 using Base::packed_bins_; 17 using typename Base::ItemGroup; 18 using Container = ItemGroup;//typename std::vector<_Item<RawShape>>; 19 20 Container store_; 21 22 public: 23 configure(const Config &)24 void configure(const Config& /*config*/) { } 25 26 template<class TPlacer, class TIterator, 27 class TBin = typename PlacementStrategyLike<TPlacer>::BinType, 28 class PConfig = typename PlacementStrategyLike<TPlacer>::Config> packItems(TIterator first,TIterator last,TBin && bin,PConfig && pconfig=PConfig ())29 void packItems(TIterator first, 30 TIterator last, 31 TBin&& bin, 32 PConfig&& pconfig = PConfig()) 33 { 34 35 using Placer = PlacementStrategyLike<TPlacer>; 36 37 store_.clear(); 38 store_.reserve(last-first); 39 40 std::vector<Placer> placers; 41 placers.reserve(last-first); 42 43 std::for_each(first, last, [this](Item& itm) { 44 if(itm.isFixed()) { 45 if (itm.binId() < 0) itm.binId(0); 46 auto binidx = size_t(itm.binId()); 47 48 while(packed_bins_.size() <= binidx) 49 packed_bins_.emplace_back(); 50 51 packed_bins_[binidx].emplace_back(itm); 52 } else { 53 store_.emplace_back(itm); 54 } 55 }); 56 57 // If the packed_items array is not empty we have to create as many 58 // placers as there are elements in packed bins and preload each item 59 // into the appropriate placer 60 for(ItemGroup& ig : packed_bins_) { 61 placers.emplace_back(bin); 62 placers.back().configure(pconfig); 63 placers.back().preload(ig); 64 } 65 66 auto sortfunc = [](Item& i1, Item& i2) { 67 int p1 = i1.priority(), p2 = i2.priority(); 68 return p1 == p2 ? i1.area() > i2.area() : p1 > p2; 69 }; 70 71 std::sort(store_.begin(), store_.end(), sortfunc); 72 73 auto total = last-first; 74 auto makeProgress = [this, &total](Placer& placer, size_t idx) { 75 packed_bins_[idx] = placer.getItems(); 76 this->progress_(static_cast<unsigned>(--total)); 77 }; 78 79 auto& cancelled = this->stopcond_; 80 81 this->template remove_unpackable_items<Placer>(store_, bin, pconfig); 82 83 auto it = store_.begin(); 84 85 while(it != store_.end() && !cancelled()) { 86 bool was_packed = false; 87 size_t j = 0; 88 while(!was_packed && !cancelled()) { 89 for(; j < placers.size() && !was_packed && !cancelled(); j++) { 90 if((was_packed = placers[j].pack(*it, rem(it, store_) ))) { 91 it->get().binId(int(j)); 92 makeProgress(placers[j], j); 93 } 94 } 95 96 if(!was_packed) { 97 placers.emplace_back(bin); 98 placers.back().configure(pconfig); 99 packed_bins_.emplace_back(); 100 j = placers.size() - 1; 101 } 102 } 103 ++it; 104 } 105 } 106 107 }; 108 109 } 110 } 111 112 #endif // FIRSTFIT_HPP 113