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