1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#ifndef FIRSTFIT_HPP
#define FIRSTFIT_HPP
#include "../libnest2d.hpp"
#include "selection_boilerplate.hpp"
namespace libnest2d { namespace selections {
template<class RawShape>
class _FirstFitSelection: public SelectionBoilerplate<RawShape> {
using Base = SelectionBoilerplate<RawShape>;
public:
using typename Base::Item;
using Config = int; //dummy
private:
using Base::packed_bins_;
using typename Base::ItemGroup;
using Container = ItemGroup;//typename std::vector<_Item<RawShape>>;
Container store_;
public:
void configure(const Config& /*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())
{
using Placer = PlacementStrategyLike<TPlacer>;
store_.clear();
store_.reserve(last-first);
packed_bins_.clear();
std::vector<Placer> placers;
placers.reserve(last-first);
std::copy(first, last, std::back_inserter(store_));
auto sortfunc = [](Item& i1, Item& i2) {
return i1.area() > i2.area();
};
std::sort(store_.begin(), store_.end(), sortfunc);
auto total = last-first;
auto makeProgress = [this, &total](Placer& placer, size_t idx) {
packed_bins_[idx] = placer.getItems();
this->progress_(static_cast<unsigned>(--total));
};
auto& cancelled = this->stopcond_;
// Safety test: try to pack each item into an empty bin. If it fails
// then it should be removed from the list
{ auto it = store_.begin();
while (it != store_.end() && !cancelled()) {
Placer p(bin); p.configure(pconfig);
if(!p.pack(*it)) {
it = store_.erase(it);
} else it++;
}
}
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_) )))
makeProgress(placers[j], j);
}
if(!was_packed) {
placers.emplace_back(bin);
placers.back().configure(pconfig);
packed_bins_.emplace_back();
j = placers.size() - 1;
}
}
++it;
}
}
};
}
}
#endif // FIRSTFIT_HPP
|
