Not handling logical beds in arrange()

5 files changed, 122 insertions, 152 deletions

diff --git a/src/libnest2d/include/libnest2d.h b/src/libnest2d/include/libnest2d.h
index f1d2506f4..5f7a29dfb 100644
--- a/src/libnest2d/include/libnest2d.h
+++ b/src/libnest2d/include/libnest2d.h
@@ -59,20 +59,20 @@ extern template PackGroup Nester<BottomLeftPlacer, FirstFitSelection>::execute(
 template<class Placer = NfpPlacer,
          class Selector = FirstFitSelection,
          class Iterator = std::vector<Item>::iterator>
-PackGroup nest(Iterator from, Iterator to,
+void nest(Iterator from, Iterator to,
                const typename Placer::BinType& bin,
                Coord dist = 0,
                const typename Placer::Config& pconf = {},
                const typename Selector::Config& sconf = {})
 {
     Nester<Placer, Selector> nester(bin, dist, pconf, sconf);
-    return nester.execute(from, to);
+    nester.execute(from, to);
 }
 
 template<class Placer = NfpPlacer,
          class Selector = FirstFitSelection,
          class Iterator = std::vector<Item>::iterator>
-PackGroup nest(Iterator from, Iterator to,
+void nest(Iterator from, Iterator to,
                const typename Placer::BinType& bin,
                ProgressFunction prg,
                StopCondition scond = []() { return false; },
@@ -83,7 +83,7 @@ PackGroup nest(Iterator from, Iterator to,
     Nester<Placer, Selector> nester(bin, dist, pconf, sconf);
     if(prg) nester.progressIndicator(prg);
     if(scond) nester.stopCondition(scond);
-    return nester.execute(from, to);
+    nester.execute(from, to);
 }
 
 #ifdef LIBNEST2D_STATIC
@@ -91,14 +91,14 @@ PackGroup nest(Iterator from, Iterator to,
 extern template class Nester<NfpPlacer, FirstFitSelection>;
 extern template class Nester<BottomLeftPlacer, FirstFitSelection>;
 
-extern template PackGroup nest(std::vector<Item>::iterator from, 
+extern template void nest(std::vector<Item>::iterator from, 
                                std::vector<Item>::iterator to,
                                const Box& bin,
                                Coord dist = 0,
                                const NfpPlacer::Config& pconf,
                                const FirstFitSelection::Config& sconf);
 
-extern template PackGroup nest(std::vector<Item>::iterator from, 
+extern template void nest(std::vector<Item>::iterator from, 
                                std::vector<Item>::iterator to,
                                const Box& bin,
                                ProgressFunction prg,
@@ -112,20 +112,19 @@ extern template PackGroup nest(std::vector<Item>::iterator from,
 template<class Placer = NfpPlacer,
          class Selector = FirstFitSelection,
          class Container = std::vector<Item>>
-PackGroup nest(Container&& cont,
+void nest(Container&& cont,
                const typename Placer::BinType& bin,
                Coord dist = 0,
                const typename Placer::Config& pconf = {},
                const typename Selector::Config& sconf = {})
 {
-    return nest<Placer, Selector>(cont.begin(), cont.end(),
-                                  bin, dist, pconf, sconf);
+    nest<Placer, Selector>(cont.begin(), cont.end(), bin, dist, pconf, sconf);
 }
 
 template<class Placer = NfpPlacer,
          class Selector = FirstFitSelection,
          class Container = std::vector<Item>>
-PackGroup nest(Container&& cont,
+void nest(Container&& cont,
                const typename Placer::BinType& bin,
                ProgressFunction prg,
                StopCondition scond = []() { return false; },
@@ -133,8 +132,8 @@ PackGroup nest(Container&& cont,
                const typename Placer::Config& pconf = {},
                const typename Selector::Config& sconf = {})
 {
-    return nest<Placer, Selector>(cont.begin(), cont.end(),
-                                  bin, prg, scond, dist, pconf, sconf);
+    nest<Placer, Selector>(cont.begin(), cont.end(), bin, prg, scond, dist,
+                           pconf, sconf);
 }
 
 }
diff --git a/src/libnest2d/include/libnest2d/libnest2d.hpp b/src/libnest2d/include/libnest2d/libnest2d.hpp
index 99c8c90c1..a83a16ecf 100644
--- a/src/libnest2d/include/libnest2d/libnest2d.hpp
+++ b/src/libnest2d/include/libnest2d/libnest2d.hpp
@@ -12,6 +12,8 @@
 
 namespace libnest2d {
 
+static const constexpr int BIN_ID_UNSET = -1;
+
 /**
  * \brief An item to be placed on a bin.
  *
@@ -34,9 +36,9 @@ class _Item {
     RawShape sh_;
 
     // Transformation data
-    Vertex translation_;
-    Radians rotation_;
-    Coord inflation_;
+    Vertex translation_{0, 0};
+    Radians rotation_{0.0};
+    Coord inflation_{0};
 
     // Info about whether the transformations will have to take place
     // This is needed because if floating point is used, it is hard to say
@@ -66,9 +68,7 @@ class _Item {
         BBCache(): valid(false) {}
     } bb_cache_;
     
-    static const size_t ID_UNSET = size_t(-1);
-    
-    size_t id_{ID_UNSET};
+    int binid_{BIN_ID_UNSET};
     bool fixed_{false};
 
 public:
@@ -149,8 +149,8 @@ public:
     
     inline bool isFixed() const noexcept { return fixed_; }
     inline void markAsFixed(bool fixed = true) { fixed_ = fixed; }
-    inline void id(size_t idx) { id_ = idx; }
-    inline long id() const noexcept { return id_; }
+    inline void binId(int idx) { binid_ = idx; }
+    inline int binId() const noexcept { return binid_; }
 
     /**
      * @brief Convert the polygon to string representation. The format depends
@@ -766,25 +766,6 @@ public:
     void clear() { impl_.clear(); }
 };
 
-using BinIdx = unsigned;
-template<class S, class Key = size_t> using _NestResult =
-    std::vector<
-        std::tuple<Key,          // Identifier of the original shape
-                   TPoint<S>,    // Translation calculated by nesting
-                   Radians,      // Rotation calculated by nesting
-                   BinIdx>       // Logical bin index, first is zero
-        >;
-
-template<class T> struct Indexed {
-    using ShapeType = T;
-    static T& get(T& obj) { return obj; }
-};
-
-template<class K, class S> struct Indexed<std::pair<K, S>> {
-    using ShapeType = S;
-    static S& get(std::pair<K, S>& obj) { return obj.second; }
-};
-
 /**
  * The Arranger is the front-end class for the libnest2d library. It takes the
  * input items and outputs the items with the proper transformations to be
@@ -805,7 +786,6 @@ public:
     using Coord = TCoord<TPoint<typename Item::ShapeType>>;
     using PackGroup = _PackGroup<typename Item::ShapeType>;
     using ResultType = PackGroup;
-    template<class K> using NestResult = _NestResult<ShapeType, K>;
 
 private:
     BinType bin_;
@@ -816,8 +796,13 @@ private:
     using TPItem = remove_cvref_t<Item>;
     using TSItem = remove_cvref_t<SItem>;
 
-    std::vector<TPItem> item_cache_;
     StopCondition stopfn_;
+    
+    template<class It> using TVal = remove_cvref_t<typename It::value_type>;
+    
+    template<class It, class Out>
+    using ConvertibleOnly =
+        enable_if_t< std::is_convertible<TVal<It>, TPItem>::value, void>;
 
 public:
 
@@ -864,12 +849,20 @@ public:
      * The number of groups in the pack group is the number of bins opened by
      * the selection algorithm.
      */
-    template<class It, class Key = size_t>
-    inline const NestResult<Key> execute(It from, It to,
-                                         std::function<Key(It)> keyfn = nullptr)
+    template<class It>
+    inline ConvertibleOnly<It, void> execute(It from, It to)
     {
-        if (!keyfn) keyfn = [to](It it) { return to - it; };
-        return _execute(from, to, keyfn);
+        auto infl = static_cast<Coord>(std::ceil(min_obj_distance_/2.0));
+        if(infl > 0) std::for_each(from, to, [this, infl](Item& item) {
+            item.inflate(infl);
+        });
+        
+        selector_.template packItems<PlacementStrategy>(
+            from, to, bin_, pconfig_);
+        
+        if(min_obj_distance_ > 0) std::for_each(from, to, [infl](Item& item) {
+            item.inflate(-infl);
+        });
     }
 
     /// Set a progress indicator function object for the selector.
@@ -890,74 +883,32 @@ public:
     }
 
 private:
-    
-    template<class It> using TVal = remove_cvref_t<typename It::value_type>;
-    
-    template<class It, class Out>
-    using ConvertibleOnly =
-        enable_if_t< std::is_convertible<TVal<It>, TPItem>::value, void>;
-    
-    template<class It, class Out>
-    using NotConvertibleOnly =
-        enable_if_t< ! std::is_convertible<TVal<It>, TPItem>::value, void>;
-    
+
+      
     // This function will be used only if the iterators are pointing to
     // a type compatible with the libnets2d::_Item template.
     // This way we can use references to input elements as they will
     // have to exist for the lifetime of this call.
-    template<class It, class Key>
-    inline ConvertibleOnly<It, const NestResult<Key>> _execute(
-        It from, It to, std::function<Key(It)> keyfn)
-    {
-        {
-            auto it = from; size_t id = 0;
-            while(it != to) 
-                if (it->id() == Item::ID_UNSET) (it++)->id(id++);
-                else { id = it->id() + 1; ++it; }
-        }
-        
-        NestResult<Key> result(to - from);
-        
-        __execute(from, to, keyfn);
-        
-        BinIdx binidx = 0;
-        for(auto &itmgrp : lastResult()) {
-            for(const Item& itm : itmgrp) 
-                result[itm.id()] =
-                    std::make_tuple(keyfn(from + itm.id()), itm.translation(),
-                                    itm.rotation(), binidx);
-            
-            ++binidx;
-        }
-        
-        return result;
-    }
+//    template<class It, class Key>
+//    inline ConvertibleOnly<It, void> _execute(It from, It to)
+//    {
+//        __execute(from, to);
+//    }
     
-    template<class It, class Key = size_t>
-    inline NotConvertibleOnly<It, const NestResult<Key>> _execute(
-        It from, It to, std::function<Key(It)> keyfn)
-    {
-        item_cache_.reserve(to - from);
-        for(auto it = from; it != to; ++it)
-            item_cache_.emplace_back(Indexed<typename It::value_type>::get(*it));
-
-        return _execute(item_cache_.begin(), item_cache_.end(), keyfn);
-    }
-
-    template<class It> inline void __execute(It from, It to)
-    {
-        auto infl = static_cast<Coord>(std::ceil(min_obj_distance_/2.0));
-        if(infl > 0) std::for_each(from, to, [this](Item& item) {
-            item.inflate(infl);
-        });
+//    template<class It> inline void _execute(It from, It to)
+//    {
+//        auto infl = static_cast<Coord>(std::ceil(min_obj_distance_/2.0));
+//        if(infl > 0) std::for_each(from, to, [this](Item& item) {
+//            item.inflate(infl);
+//        });
 
-        selector_.template packItems<PlacementStrategy>(
-                    from, to, bin_, pconfig_);
+//        selector_.template packItems<PlacementStrategy>(
+//                    from, to, bin_, pconfig_);
         
-        if(min_obj_distance_ > 0) std::for_each(from, to, [](Item& item) {
-            item.inflate(-infl);
-        });
-    }
+//        if(min_obj_distance_ > 0) std::for_each(from, to, [](Item& item) {
+//            item.inflate(-infl);
+//        });
+//    }
 };
 
 }
diff --git a/src/libnest2d/include/libnest2d/selections/djd_heuristic.hpp b/src/libnest2d/include/libnest2d/selections/djd_heuristic.hpp
index 25007e580..f904210aa 100644
--- a/src/libnest2d/include/libnest2d/selections/djd_heuristic.hpp
+++ b/src/libnest2d/include/libnest2d/selections/djd_heuristic.hpp
@@ -711,7 +711,12 @@ public:
             addBin();
             packjob(placers[idx], remaining, idx); idx++;
         }
-
+        
+        int binid = 0;
+        for(auto &bin : packed_bins_) {
+            for(Item& itm : bin) itm.binId(binid);
+            binid++;
+        }
     }
 };
 
diff --git a/src/libnest2d/include/libnest2d/selections/firstfit.hpp b/src/libnest2d/include/libnest2d/selections/firstfit.hpp
index 287204c08..6a3e2e61b 100644
--- a/src/libnest2d/include/libnest2d/selections/firstfit.hpp
+++ b/src/libnest2d/include/libnest2d/selections/firstfit.hpp
@@ -90,8 +90,10 @@ public:
             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[j].pack(*it, rem(it, store_) ))) {
+                        it->get().binId(int(j));
+                        makeProgress(placers[j], j);
+                    }
                 }
 
                 if(!was_packed) {
diff --git a/src/libnest2d/tests/test.cpp b/src/libnest2d/tests/test.cpp
index e5bd87182..6891b16e1 100644
--- a/src/libnest2d/tests/test.cpp
+++ b/src/libnest2d/tests/test.cpp
@@ -372,27 +372,34 @@ TEST(GeometryAlgorithms, ArrangeRectanglesTight)
     
     Nester<BottomLeftPlacer, DJDHeuristic> arrange(bin);
     
-    auto groups = arrange.execute(rects.begin(), rects.end());
-    
-    ASSERT_EQ(groups.size(), 1u);
-    ASSERT_EQ(groups[0].size(), rects.size());
-    
+    arrange.execute(rects.begin(), rects.end());
+
+    auto max_group = std::max_element(rects.begin(), rects.end(),
+                                      [](const Item &i1, const Item &i2) {
+                                          return i1.binId() < i2.binId();
+                                      });
+
+    int groups = max_group == rects.end() ? 0 : max_group->binId() + 1;
+
+    ASSERT_EQ(groups, 1u);
+    ASSERT_TRUE(
+        std::all_of(rects.begin(), rects.end(), [](const Rectangle &itm) {
+            return itm.binId() != BIN_ID_UNSET;
+        }));
+
     // check for no intersections, no containment:
     
-    for(auto result : groups) {
-        bool valid = true;
-        for(Item& r1 : result) {
-            for(Item& r2 : result) {
-                if(&r1 != &r2 ) {
-                    valid = !Item::intersects(r1, r2) || Item::touches(r1, r2);
-                    ASSERT_TRUE(valid);
-                    valid = (valid && !r1.isInside(r2) && !r2.isInside(r1));
-                    ASSERT_TRUE(valid);
-                }
+    bool valid = true;
+    for(Item& r1 : rects) {
+        for(Item& r2 : rects) {
+            if(&r1 != &r2 ) {
+                valid = !Item::intersects(r1, r2) || Item::touches(r1, r2);
+                ASSERT_TRUE(valid);
+                valid = (valid && !r1.isInside(r2) && !r2.isInside(r1));
+                ASSERT_TRUE(valid);
             }
         }
     }
-    
 }
 
 TEST(GeometryAlgorithms, ArrangeRectanglesLoose)
@@ -433,16 +440,25 @@ TEST(GeometryAlgorithms, ArrangeRectanglesLoose)
     
     Nester<BottomLeftPlacer, DJDHeuristic> arrange(bin, min_obj_distance);
     
-    auto groups = arrange.execute(rects.begin(), rects.end());
+    arrange.execute(rects.begin(), rects.end());
+    
+    auto max_group = std::max_element(rects.begin(), rects.end(),
+                                      [](const Item &i1, const Item &i2) {
+                                          return i1.binId() < i2.binId();
+                                      });
     
-    ASSERT_EQ(groups.size(), 1u);
-    ASSERT_EQ(groups[0].size(), rects.size());
+    size_t groups = max_group == rects.end() ? 0 : max_group->binId() + 1;
+    
+    ASSERT_EQ(groups, 1u);
+    ASSERT_TRUE(
+        std::all_of(rects.begin(), rects.end(), [](const Rectangle &itm) {
+            return itm.binId() != BIN_ID_UNSET;
+        }));
     
     // check for no intersections, no containment:
-    auto result = groups[0];
     bool valid = true;
-    for(Item& r1 : result) {
-        for(Item& r2 : result) {
+    for(Item& r1 : rects) {
+        for(Item& r2 : rects) {
             if(&r1 != &r2 ) {
                 valid = !Item::intersects(r1, r2);
                 valid = (valid && !r1.isInside(r2) && !r2.isInside(r1));
@@ -554,27 +570,24 @@ TEST(GeometryAlgorithms, convexHull) {
 
 TEST(GeometryAlgorithms, NestTest) {
     std::vector<Item> input = prusaParts();
+
+    libnest2d::nest(input, Box(250000000, 210000000), [](unsigned cnt) {
+        std::cout << "parts left: " << cnt << std::endl;
+    });
+
+    auto max_binid_it = std::max_element(input.begin(), input.end(),
+                                         [](const Item &i1, const Item &i2) {
+                                             return i1.binId() < i2.binId();
+                                         });
+
+    size_t bins = max_binid_it == input.end() ? 0 : max_binid_it->binId() + 1;
     
-    PackGroup result = libnest2d::nest(input,
-                                       Box(250000000, 210000000),
-                                       [](unsigned cnt) {
-                                           std::cout
-                                               << "parts left: " << cnt
-                                               << std::endl;
-                                       });
-    
-    ASSERT_LE(result.size(), 2);
-    
-    size_t partsum = std::accumulate(result.begin(),
-                                     result.end(),
-                                     size_t(0),
-                                     [](size_t s,
-                                        const decltype(
-                                            result)::value_type &bin) {
-                                         return s += bin.size();
-                                     });
-    
-    ASSERT_EQ(input.size(), partsum);
+    ASSERT_EQ(bins, 2u);
+
+    ASSERT_TRUE(
+        std::all_of(input.begin(), input.end(), [](const Item &itm) {
+            return itm.binId() != BIN_ID_UNSET;
+        }));
 }
 
 namespace {