Разрезы прямоугольника на детали без отходов

#include <cstdlib>
#include <cassert>
#include <cstring>
#include <bit>
#include <span>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <thread>
#include <stdexcept>
#include <iomanip>
#include <fstream>
#include <chrono>
#include <sstream>
#include <iostream>
 
#ifdef _MSC_VER
  #pragma warning(disable : 4146 4245 4189 4100)
#endif // _MSC_VER
 
#define noEXTRA_STATS
#define noDUMP_GDS
 
#ifdef EXTRA_STATS
  #define EXTRA_STATS_ONLY(x) x
#else // EXTRA_STATS
  #define EXTRA_STATS_ONLY(x)
#endif // EXTRA_STATS
 
//////////////////////////////////////////////////////////////////////////////////////////
 
using Size = unsigned;
using Area = unsigned;
 
//////////////////////////////////////////////////////////////////////////////////////////
 
template <typename T> std::size_t hash_mix(std::size_t hash, T v)
{
  return std::rotl(hash, 1) ^ std::hash<T>()(v);
}
 
class Rect
{ 
  Size dx_, dy_; 
  Area area_;
 
public:
  Rect() = default;
  Rect(Size dx, Size dy) : dx_(dx), dy_(dy), area_(dx * dy)
    {}    
 
  Size dx() const
    { return dx_; }
 
  Size dy() const
    { return dy_; }
 
  Area area() const
    { return area_; }
 
  bool is_horizontal() const
    { return dx_ > dy_; }
 
  void flip()
    { std::swap(dx_, dy_); }
 
  bool fits(const Rect &limits) const
    { return dx_ <= limits.dx_ && dy_ <= limits.dy_; }
 
  friend Rect horizontal_composition(const Rect &lhs, const Rect &rhs)
    { return { lhs.dx_ + rhs.dx_, std::max(lhs.dy_, rhs.dy_) }; }
 
  friend Rect vertical_composition(const Rect &lhs, const Rect &rhs)
    { return { std::max(lhs.dx_, rhs.dx_), lhs.dy_ + rhs.dy_ }; }
 
  friend Rect horizontal_waste(const Rect &lhs, const Rect &rhs)
  { 
    if (lhs.dy_ < rhs.dy_)
      return { lhs.dx_, rhs.dy_ - lhs.dy_ };
    else
      return { rhs.dx_, lhs.dy_ - rhs.dy_ };
  }
    
  friend Rect vertical_waste(const Rect &lhs, const Rect &rhs)
  {
    if (lhs.dx_ < rhs.dx_)
      return { rhs.dx_ - lhs.dx_, lhs.dy_ };
    else
      return { lhs.dx_ - rhs.dx_, rhs.dy_ };
  }
 
  struct Hash
  {
    std::size_t operator ()(const Rect &r) const
      { return hash_mix(hash_mix(0, r.dx_), r.dy_); }
  };
 
  friend bool operator ==(const Rect &lhs, const Rect &rhs)
    { return lhs.dx_ == rhs.dx_ && lhs.dy_ == rhs.dy_; }
 
  friend std::istream &operator >>(std::istream &strm, Rect &rhs)
  {
    if (!(strm >> rhs.dx_ >> rhs.dy_))
      throw std::invalid_argument("invalid rectangle size");
    return strm;
  }
 
  friend std::ostream &operator <<(std::ostream &strm, const Rect &rhs)
    { return strm << rhs.dx_ << 'x' << rhs.dy_; }
};
 
enum class Composition
{
  ORIGINAL,
  HORIZONTAL,
  VERTICAL
};
 
struct PatternDesc
{
  Area waste = std::numeric_limits<Area>::max();
 
  mutable std::size_t index;
 
#ifdef DUMP_GDS
  unsigned id;
  Composition composition = Composition::ORIGINAL;
  Rect key_a, key_b; // Patterns::const_iterator it_a, it_b;
  mutable bool is_dumped = false;
#endif // DUMP_GDS
};
 
using Patterns = std::unordered_map<Rect, PatternDesc, Rect::Hash>;
using Pattern = Patterns::value_type;
 
#ifdef EXTRA_STATS
 
struct ExtraStats
{
  std::size_t n_compositions; 
 
  std::size_t n_patterns_built; 
  // Passed size and waste limits
 
  std::size_t n_patterns_updated; 
  // Accepted as updates to previously known patterns
 
  ExtraStats &operator +=(const ExtraStats &rhs) noexcept
  {
    n_compositions += rhs.n_compositions;
    n_patterns_built += rhs.n_patterns_built;
    n_patterns_updated += rhs.n_patterns_updated;
    return *this;
  }
};
 
#endif // EXTRA_STATS
 
struct Context
{
  unsigned n_threads = std::thread::hardware_concurrency();
 
  Rect limits;
 
  unsigned allowed_waste_perc = 100;
  Area allowed_waste = std::numeric_limits<Area>::max();
  bool is_absolute_waste = true;
 
  std::vector<Rect> originals;
  Area min_original_area = std::numeric_limits<Area>::max();
 
  EXTRA_STATS_ONLY(ExtraStats extra_stats;)
 
  void postprocess()
  {
    if (allowed_waste_perc == -1)
    { // Absolute value 'allowed_waste' is already set
      assert(is_absolute_waste);
      return;
    }
 
    // Percentage value is set, 'allowed_waste' is not
 
    if (allowed_waste_perc == 0)
    {
      allowed_waste = 0;
      is_absolute_waste = true;
    }
    else if (allowed_waste_perc == 100)
    {
      allowed_waste = std::numeric_limits<Area>::max();
      is_absolute_waste = true;
    }
    else if (is_absolute_waste)
      allowed_waste = limits.area() * allowed_waste_perc / 100;
  }
 
  bool fits_limits(const Rect &box) const
    { return box.fits(limits); }
 
  bool is_allowed_waste(Area waste, const Rect &box) const
  { 
    if (is_absolute_waste)
      return waste <= allowed_waste;
 
    assert(allowed_waste_perc > 0 && allowed_waste_perc < 100);
    return waste <= box.area() * allowed_waste_perc / 100;
  }
 
  bool encloses_original(const Rect &box) const
  {
    Area area = box.area();
    if (area < min_original_area)
      return false;
 
    for (const Rect &original : originals)
    {
      if (original.fits(box))
        return true;
 
      if (area < original.area())
        break;
    }
 
    return false;
  }
 
  Area total_waste(const Pattern &pattern) const
  {
    const Rect &box = pattern.first;
    const PatternDesc &desc = pattern.second;
    assert(box.area() <= limits.area()); 
    return limits.area() - box.area() + desc.waste;
  }
};
 
struct ThreadContext
{
  std::thread thread;
  EXTRA_STATS_ONLY(ExtraStats extra_stats;)
};
 
void combine(const Pattern &a, const Pattern &b, 
             const Patterns &all_patterns, Patterns &new_patterns,
             const Context &context, ThreadContext &thread_context)
{
  const Rect &box_a = a.first, &box_b = b.first;
  const PatternDesc &desc_a = a.second, &desc_b = b.second;
 
  EXTRA_STATS_ONLY(++thread_context.extra_stats.n_compositions);
 
  for (Composition composition : { Composition::HORIZONTAL, Composition::VERTICAL })
  {
    Rect box = composition == Composition::HORIZONTAL ?
      horizontal_composition(box_a, box_b) : vertical_composition(box_a, box_b);
 
    assert(box_a.area() + box_b.area() <= box.area());
 
    if (!context.fits_limits(box))
      continue;
 
    Rect new_waste_box = composition == Composition::HORIZONTAL ?
      horizontal_waste(box_a, box_b) : vertical_waste(box_a, box_b);
 
    Area new_waste = new_waste_box.area();
    assert(box.area() == box_a.area() + box_b.area() + new_waste);
 
    Area waste = new_waste + desc_a.waste + desc_b.waste;
    assert(waste < box.area());
 
    if (new_waste > 0)
    { // Otherwise there's no point in checking against allowable waste since waste 
      // percentage could only decrease
      if (!context.is_allowed_waste(waste, box))
        continue;
 
      if (context.encloses_original(new_waste_box))
        continue;
    }
 
    EXTRA_STATS_ONLY(++thread_context.extra_stats.n_patterns_built);
 
    Patterns::const_iterator it = all_patterns.find(box);
    if (it != all_patterns.end())
    {
      const PatternDesc &desc = it->second;
      if (waste >= desc.waste)
        continue;
    }
 
    // New or better pattern
 
    PatternDesc &new_desc = new_patterns[box];
    if (waste >= new_desc.waste)
      continue;
 
    new_desc.waste = waste;
 
#ifdef DUMP_GDS
    static unsigned i_desc_id;
    new_desc.id = ++i_desc_id; 
    new_desc.composition = composition;
    new_desc.key_a = box_a;
    new_desc.key_b = box_b;
#endif // DUMP_GDS
 
    EXTRA_STATS_ONLY(++thread_context.extra_stats.n_patterns_updated);
  }
}
 
using ItsUpdated = std::vector<Patterns::const_iterator>;
using ItsUpdatedSpan = std::span<Patterns::const_iterator>;
 
void generate_new_patterns(ItsUpdatedSpan its_updated, const Patterns &all_patterns, 
                           Patterns &new_patterns, 
                           const Context &context, ThreadContext &thread_context)
{
  // Patterns from 'its_updated' have 'PatternDesc::index' values assigned to them. All 
  // other patterns have zero in that field 
 
  for (Patterns::const_iterator it_a : its_updated)
  {
    const Pattern &a = *it_a;
    assert(a.second.index > 0);
 
    for (const Pattern &b : all_patterns)
      if (a.second.index >= b.second.index)
        // The comparison ensures that we combine updated-to-old unconditionally, and 
        // updated-to-updated only one way
        combine(a, b, all_patterns, new_patterns, context, thread_context);
  }
}
 
void merge_new_patterns(Patterns &dst_patterns, Patterns &src_patterns, 
                        ItsUpdated *its_updated = nullptr)
{
  while (!src_patterns.empty())
  {
    Patterns::iterator it_src = src_patterns.begin();
    const Rect &src_box = it_src->first;
    const PatternDesc &src_desc = it_src->second;
    // These should remain valid during extraction-insertion of the node
 
    Patterns::node_type node = src_patterns.extract(it_src);
    auto ir = dst_patterns.insert(std::move(node));
 
    assert(ir.position->first == src_box);
    PatternDesc &dst_desc = ir.position->second;
 
    if (!ir.inserted)
    {
      if (src_desc.waste >= dst_desc.waste)
        continue;
 
      dst_desc.waste = src_desc.waste;
    }
 
    assert(dst_desc.waste == src_desc.waste);
 
    if (its_updated != nullptr)
    {
      assert(dst_desc.index == 0);
      its_updated->push_back(ir.position);
      dst_desc.index = its_updated->size();
    }
  }
}
 
//////////////////////////////////////////////////////////////////////////////////////////
 
#ifdef DUMP_GDS
 
void dump_gds_sname(std::ofstream &f, Patterns::const_iterator it_cell)
{
  const Rect &box = it_cell->first;
  const PatternDesc &desc = it_cell->second;
  f << (desc.composition == Composition::ORIGINAL ? "Box_" : "Pattern_") << 
    desc.id << "_" << box;
}
 
void dump_gds_rect(std::ofstream &f, unsigned layer, const Rect &r)
{
  f << "BOUNDARY" << std::endl;
  f << "LAYER " << layer << std::endl;
  f << "DATATYPE 0" << std::endl;
  f << "XY 0:0" << std::endl;
  f << r.dx() << ":0" << std::endl;
  f << r.dx() << ":" << r.dy() << std::endl;
  f << "0:" << r.dy() << std::endl;
  f << "0:0" << std::endl;
  f << "ENDEL" << std::endl;
}
 
void dump_gds_cell(std::ofstream &f, Patterns::const_iterator it_cell, 
                   const Patterns &all_patterns)
{
  const Rect &box = it_cell->first;
  const PatternDesc &desc = it_cell->second;
 
  if (desc.is_dumped)
    return;
 
  desc.is_dumped = true;
 
  f << "BGNSTR 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "STRNAME "; dump_gds_sname(f, it_cell); f << std::endl;
 
  Patterns::const_iterator it_sub_cell_a, it_sub_cell_b;
 
  if (desc.composition == Composition::ORIGINAL)
    dump_gds_rect(f, desc.id, box);
  else
  {
    it_sub_cell_a = all_patterns.find(desc.key_a);
    it_sub_cell_b = all_patterns.find(desc.key_b);
    assert(it_sub_cell_a != all_patterns.end() && it_sub_cell_b != all_patterns.end());
 
    f << "SREF" << std::endl;
    f << "SNAME "; dump_gds_sname(f, it_sub_cell_a); f << std::endl;
    f << "XY 0:0" << std::endl;
    f << "ENDEL" << std::endl;
 
    f << "SREF" << std::endl;
    f << "SNAME "; dump_gds_sname(f, it_sub_cell_b); f << std::endl;
 
    if (desc.composition == Composition::HORIZONTAL)
      f << "XY " << it_sub_cell_a->first.dx() << ":0" << std::endl;
    else
      f << "XY 0:" << it_sub_cell_a->first.dy() << std::endl;
 
    f << "ENDEL" << std::endl;
  }
 
  f << "ENDSTR" << std::endl << std::endl;
 
  if (desc.composition != Composition::ORIGINAL)
  {
    dump_gds_cell(f, it_sub_cell_a, all_patterns);
    dump_gds_cell(f, it_sub_cell_b, all_patterns);
  }
}
 
void dump_gds(const char *file, Patterns::const_iterator it_root, 
              const Patterns &all_patterns, const Context &context)
{
  std::ofstream f(file);
  if (!f)
    return;
 
  f << "HEADER 600" << std::endl;
  f << "BGNLIB 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "LIBNAME " << context.limits << std::endl;
  f << "UNITS 0.001 1e-09" << std::endl << std::endl;
 
  f << "BGNSTR 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "STRNAME Result_" << context.limits << std::endl;
  dump_gds_rect(f, 0, context.limits);
  f << "SREF" << std::endl;
  f << "SNAME "; dump_gds_sname(f, it_root); f << std::endl;
  f << "XY 0:0" << std::endl;
  f << "ENDEL" << std::endl;
  f << "ENDSTR" << std::endl << std::endl;
 
  dump_gds_cell(f, it_root, all_patterns);
 
  f << "ENDLIB" << std::endl;
}
 
#endif // DUMP_GDS
 
//////////////////////////////////////////////////////////////////////////////////////////
 
void read_input(const char *const args[], Patterns &initial_patterns, Context &context)
{ // Relies on the standard convention: `args[]` is terminated by a null pointer 
  std::stringstream params;
 
  {
    struct Arg
    {
      const char *arg;
      unsigned i_arg;
    };
 
    auto pre_arg = [=](Arg &arg) -> bool
    {
      if (arg.arg == nullptr)
        return false;
 
      if (*arg.arg != '\0')
        return true;
 
      arg.arg = args[++arg.i_arg];
      return arg.arg != nullptr;
    };
 
    auto consume = [&](Arg &arg, const char *str) -> bool
    {
      if (!pre_arg(arg))
        return false;
 
      std::size_t n = std::strlen(str);
      return std::strncmp(arg.arg, str, n) == 0 ? arg.arg += n, true : false;
    };
 
    auto consume_uint = [&](Arg &arg) -> unsigned
    {
      consume(arg, "=");
 
      if (!pre_arg(arg))
        throw std::invalid_argument("missing argument");
 
      std::size_t n;
      unsigned long v = std::stoul(arg.arg, &n);
      arg.arg += n;
 
      if (v > std::numeric_limits<unsigned>::max())
        throw std::out_of_range("argument out of range");
 
      return v;
    };
 
    Arg arg = { args[0] };
    while (pre_arg(arg))
    {
      if (consume(arg, "-"))
      {
        consume(arg, "-");
        if (consume(arg, "waste_abs"))
        { // Percentage of the full area
          context.allowed_waste_perc = consume_uint(arg);
          if (context.allowed_waste_perc > 100)
            throw std::out_of_range("argument out of range");
 
          context.is_absolute_waste = true;
        } 
        else if (consume(arg, "waste_rel"))
        { // Percentage of the partial solution area
          context.allowed_waste_perc = consume_uint(arg);
          if (context.allowed_waste_perc > 100)
            throw std::out_of_range("argument out of range");
 
          context.is_absolute_waste = false;
        } 
        else if (consume(arg, "waste"))
        { // Exact area
          context.allowed_waste_perc = -1;
          context.allowed_waste = consume_uint(arg);
          context.is_absolute_waste = true;
        }
        else if (consume(arg, "threads"))
          context.n_threads = consume_uint(arg);
      }
      else
      {
        params << ' ' << arg.arg;
        arg.arg += std::strlen(arg.arg);
      }
    }
  }
 
  {
    std::istream &in = params.tellp() == 0 ? std::cin : params;
 
    in >> context.limits;
 
    unsigned n_blocks = 0;
    if (!(in >> n_blocks))
      throw std::invalid_argument("invalid number of blocks");
 
    for (unsigned i = 0; i < n_blocks; ++i)
    {
      Rect box;
      in >> box;
 
      {
        PatternDesc &desc = initial_patterns[box];
        if (desc.waste != 0)
        { // New entry
          desc = { 0 };
  #ifdef DUMP_GDS
          desc.id = i + 1;
          desc.composition = Composition::ORIGINAL;
  #endif // DUMP_GDS
 
          context.originals.push_back(box);
        }
      }
      
      box.flip();
 
      {
        PatternDesc &desc = initial_patterns[box];
        if (desc.waste != 0)
        { // New entry
          desc = { 0 };
  #ifdef DUMP_GDS
          desc.id = i + 1;
          desc.composition = Composition::ORIGINAL;
  #endif // DUMP_GDS
 
          context.originals.push_back(box);
        }
      }
    }
  }
}
 
void display_input(const Context &context)
{
  std::cout << "Limits: " << context.limits << std::endl;
 
  std::cout << "Blocks:";
 
  unsigned n_blocks = 0;
  for (const Rect &box : context.originals)
    if (!box.is_horizontal())
    {
      std::cout << ' ' << box;
      ++n_blocks;
    }
 
  std::cout << " (" << n_blocks << ")" << std::endl;
 
  std::cout << "Allowable intermediate waste: ";
  if (context.allowed_waste_perc != -1)
  {
    assert(context.allowed_waste_perc <= 100);
    std::cout << context.allowed_waste_perc << "% " <<
      (context.allowed_waste_perc == 100 ? "(unlimited)" :
       context.allowed_waste_perc == 0 ? "(perfect)" :
       context.is_absolute_waste ? "(absolute)" : "(relative)");
  }
  else
    std::cout << context.allowed_waste << " sq units " <<
      (context.allowed_waste >= context.limits.area() ? "(unlimited)" :
       context.allowed_waste == 0 ? "(perfect)" : "");
 
  std::cout << std::endl;
 
  std::cout << "Threads: " << context.n_threads << std::endl;
}
 
//////////////////////////////////////////////////////////////////////////////////////////
 
int main(int argc, char *argv[])
{
  try
  {
    Context context = {};
 
    Patterns all_patterns;
    std::vector<Patterns> new_patterns(context.n_threads);
 
    read_input(argv + 1, new_patterns[0], context);
    display_input(context);
 
    context.postprocess();
 
    std::cout << "Working..." << std::endl;
 
    auto timing_start = std::chrono::high_resolution_clock::now();
 
    std::sort(context.originals.begin(), context.originals.end(), 
      [](const Rect &lhs, const Rect &rhs) { return lhs.area() < rhs.area(); });
    context.min_original_area = context.originals.front().area();
    assert(context.min_original_area > 0);
 
    // Start processing
 
    std::vector<ThreadContext> threads(context.n_threads);
 
    ItsUpdated its_updated;
    // Declared outside the cycle to maintain capacity
 
    do
    {
      assert(its_updated.empty());
 
      // All patterns in all 'new_patterns[]' are either completely new or better than 
      // matching existing patterns in 'all_patterns'. However, it is possible that multiple 
      // threads, working independently, generated same-sized patterns or improved on same 
      // pattern in 'all_patterns'. We have to keep only the best one. To make sure we don't 
      // include improvements for the same pattern into 'its_updated' multiple times, let's 
      // first merge all 'new_patterns[]' to 'new_patterns[0]' and only then transfer the 
      // results to 'all_patterns'
 
      // Merge new patterns and improvements to 'new_patterns[0]'
 
      for (unsigned n_merge_step = 1; n_merge_step < context.n_threads; n_merge_step *= 2)
      {
        unsigned n_threads = 0;
 
        for (unsigned i_patterns = 0; i_patterns + n_merge_step < context.n_threads;
               i_patterns += n_merge_step * 2)
        {
          ThreadContext &thread = threads[n_threads++];
          thread.thread = std::thread(merge_new_patterns, 
            std::ref(new_patterns[i_patterns]), 
            std::ref(new_patterns[i_patterns + n_merge_step]), nullptr);
        }
 
        for (ThreadContext &thread : std::span<ThreadContext>(threads.begin(), n_threads))
          thread.thread.join();
      }
 
      // Transfer new patterns and improvements to 'all_patterns'
 
      its_updated.reserve(new_patterns[0].size());
      merge_new_patterns(all_patterns, new_patterns[0], &its_updated);
 
#ifndef NDEBUG
      for (const Patterns& patterns : new_patterns)
        assert(patterns.empty());
#endif // NDEBUG
 
      if (its_updated.empty())
        break;
 
      // Generate new patterns
 
      std::size_t i_begin = 0, i_end;
      for (unsigned i_thread = 0; i_thread < context.n_threads; ++i_thread, i_begin = i_end)
      {
        i_end = its_updated.size() * (i_thread + 1) / context.n_threads;
        ThreadContext &thread = threads[i_thread];
        EXTRA_STATS_ONLY(thread.extra_stats = {});
        thread.thread = std::thread(generate_new_patterns, 
          ItsUpdatedSpan(its_updated.begin() + i_begin, its_updated.begin() + i_end),
          std::cref(all_patterns), std::ref(new_patterns[i_thread]), 
          std::cref(context), std::ref(thread));
      }
 
      for (ThreadContext &thread : threads)
      {
        thread.thread.join();
        EXTRA_STATS_ONLY(context.extra_stats += thread.extra_stats);
      }
 
      // Release the update list
 
      for (Patterns::const_iterator it : its_updated)
      {
        assert(it->second.index > 0);
        it->second.index = 0;
      }
 
      its_updated.clear();
 
    } while (true);
 
    // Find the best pattern
 
    Patterns::const_iterator it_min = all_patterns.begin();
    Area min_total_waste = context.total_waste(*it_min);
 
    for (Patterns::const_iterator it = all_patterns.begin(); it != all_patterns.end(); ++it)
    {
      Area total_waste = context.total_waste(*it);
      if (total_waste < min_total_waste)
      {
        min_total_waste = total_waste;
        it_min = it;
      }
    }
 
    // Done
 
    auto timing_end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> timing = timing_end - timing_start;
 
#ifdef EXTRA_STATS
    std::cout << "Compositions: " << context.extra_stats.n_compositions << std::endl;
    std::cout << "Patterns built: " << context.extra_stats.n_patterns_built << std::endl;
    std::cout << "Pattern updates: " << context.extra_stats.n_patterns_updated << std::endl;
#endif // EXTRA_STATS
 
    std::cout << "Patterns: " << all_patterns.size() << std::endl;
    std::cout << "Min waste: " << min_total_waste << std::endl;
    std::cout << "Duration: " << std::fixed << std::setprecision(2) << timing.count() << "s" << std::endl;
 
#ifdef DUMP_GDS
    std::cout << "Saving GDS file..." << std::endl;
    dump_gds("result.gds", it_min, all_patterns, context);
    std::cout << "Done." << std::endl;
#endif // DUMP_GDS
  }
  catch (const std::exception &e)
  {
    std::cerr << "Error: " << e.what() << std::endl;
    return EXIT_FAILURE;
  }
  catch (...)
  {
    return EXIT_FAILURE;
  }
}