mapscplinear.cpp

// Copyright (c) 2024-2026 Stefan Teleman.
//
// Licensed under the MIT License.
// See https://opensource.org/license/mit
// SPDX-License-Identifier: MIT
//

#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <fstream>
#include <limits>
#include <algorithm>
#include <cstring>
#include <cstdint>
#include <cassert>
#include <ctime>
#include <cerrno>
#include <getopt.h>

static bool PS;

static int Timestamp(struct timespec* ts) {
  if (clock_gettime(CLOCK_MONOTONIC, ts) != 0) {
    std::cerr << "clock_gettime(2) failed: " << strerror(errno)
      << std::endl;
    return -1;
  }

  return 0;
}

static void PrintTimediff(const struct timespec* S,
                          const struct timespec* E) {
  struct timespec R;

  if (clock_getres(CLOCK_REALTIME, &R) != 0) {
    std::cerr << "clock_getres(2) failed: " << strerror(errno)
      << std::endl;
    return;
  }

  int64_t Sec = ((int64_t) E->tv_sec - (int64_t) S->tv_sec) * 1000000000;
  int64_t Nns = ((int64_t) E->tv_nsec - (int64_t) S->tv_nsec) / 1000000;

  std::cerr << "Clock Resolution: " << (int64_t) R.tv_sec << '.'
    << std::setfill('0') << std::setw(9) << (int64_t) R.tv_nsec
    << '.' << std::endl;
  std::cerr << "CPU time: " << (int64_t) Sec / 1000000000L << '.'
    << std::setfill('0') << std::setw(12) << (int64_t) Nns
    << " second(s)." << std::endl;
}

struct SCSet {
  uint32_t IX;
  std::set<int32_t>* EL;

  SCSet()
  : IX(static_cast<uint32_t>(~0x0)), EL(new std::set<int32_t>()) { }

  ~SCSet() = default;

  size_t Size() const {
    return EL->size();
  }

  inline bool operator<(const SCSet& R) const {
    return *EL < *(R.EL);
  }

  inline bool operator>(const SCSet& R) const {
    return *EL > *(R.EL);
  }
};

struct SCSetElement {
  uint32_t SetIndex;
  uint32_t SetSize;
  mutable bool Covered;

  SCSetElement() : SetIndex(static_cast<uint32_t>(~0x0)),
  SetSize(static_cast<uint32_t>(~0x0)), Covered(false) { }

  SCSetElement(uint32_t SI, uint32_t SS)
  : SetIndex(SI), SetSize(SS), Covered(false) { }

  void SetCovered(bool V) {
    Covered = V;
  }

  void SetCovered(bool V) const {
    Covered = V;
  }

  inline bool operator<(const SCSetElement& R) const {
    return SetSize > R.SetSize ? true :
           SetSize == R.SetSize ? SetIndex > R.SetIndex : false;
  }

  inline bool operator==(const SCSetElement& R) const {
    return SetIndex == R.SetIndex &&
           SetSize == R.SetSize;
  }

  inline bool operator>(const SCSetElement& R) const {
    return !(*this < R) && !(*this == R);
  }

  void Print() const {
    std::cerr << '[' << SetIndex << ':' << SetSize << ':'
      << std::boolalpha << Covered << ']';
  }
};

class SCSetMatrix {
private:
  std::vector<SCSet> MX;

public:
  SCSetMatrix() = default;

  void ReadFromFile(const std::string& IN) {
    MX.clear();

    std::ifstream IFS(IN);
    if (IFS.good()) {
      std::string Line;
      const char* Sep = ", \t\n";
      char* End;
      uint32_t IX = 0U;

      while (std::getline(IFS, Line)) {
        SCSet MR;

        if (!Line.empty()) {
          if (char* Tok = strtok_r(const_cast<char*>(Line.data()), Sep, &End))
            MR.EL->insert(std::stoi(Tok));
          while (char* Tok = strtok_r(NULL, Sep, &End))
            MR.EL->insert(std::stoi(Tok));

          MR.IX = IX++;
          MX.push_back(MR);
        }
      }
    }
  }

  void SortLowToHigh() {
    auto SCSetSort = [=] (const SCSet& L, const SCSet& R) {
      return L.Size() < R.Size() ? true : L.Size() == R.Size() ? L < R : false;
    };

    std::sort(MX.begin(), MX.end(), SCSetSort);
  }

  void SortHighToLow() {
    auto SCSetSort = [=] (const SCSet& L, const SCSet& R) {
      return L.Size() > R.Size() ? true : L.Size() == R.Size() ? L > R : false;
    };

    std::sort(MX.begin(), MX.end(), SCSetSort);
  }

  void Clear() {
    MX.clear();
  }

  const std::vector<SCSet>& Matrix() const {
    return MX;
  }

  size_t Size() const {
    return MX.size();
  }
};

class SCPLinear {
private:
  struct SCSetComp {
    inline bool operator()(const SCSetElement& L, const SCSetElement& R) const {
      return L.SetSize > R.SetSize ? true :
        L.SetSize == R.SetSize ? L > R : false;
    }
  };

private:
  struct SCSetSizeComp {
    inline bool operator()(size_t L, size_t R) const {
      return L > R;
    }
  };

private:
  std::vector<SCSet> Sets;
  std::vector<const std::set<int32_t>*> UNV;
  std::map<int32_t, std::set<SCSetElement, SCSetComp>> SCSetElementMap;
  std::map<uint32_t, const std::set<int32_t>* const> SCSetIndexMap;
  std::multimap<size_t, const std::set<int32_t>* const, SCSetSizeComp> SCSetSizeMap;
  std::vector<uint32_t> CSetIndexVec;
  std::set<int32_t> UniverseSet;
  uint64_t IT;
  uint32_t MC;

  void PrintSet(const std::set<int32_t>& S) const {
    std::cerr << "{ ";
    if (!S.empty()) {
      std::set<int32_t>::const_iterator I = S.begin();
      std::set<int32_t>::const_iterator E = S.end();

      std::cerr << *I;
      while (++I != E) {
        std::cerr << ", " << *I;
      }
    }

    std::cerr << " }";
  }

public:
  SCPLinear()
  : Sets(), UNV(), SCSetElementMap(), SCSetIndexMap(), SCSetSizeMap(),
  CSetIndexVec(), UniverseSet(), IT(0UL), MC(static_cast<uint32_t>(~0x0)) { }

  uint64_t Iterations() const {
    return IT;
  }

  uint32_t MinCoverage() const {
    return MC == static_cast<uint32_t>(~0x0) ? 0 : MC;
  }

  const std::vector<const std::set<int32_t>*>& Universe() const {
    return UNV;
  }

  void SetUniverse(const std::vector<const std::set<int32_t>*>& UV) {
    UNV = UV;
  }

  void CreateUniverse(const std::vector<SCSet>& M) {
    UNV.clear();

    std::vector<SCSet>::const_iterator I = M.begin();
    std::vector<SCSet>::const_iterator E = M.end();
    std::map<int32_t, std::set<SCSetElement, SCSetComp>>::iterator MI;

    while (I != E) {
      const std::set<int32_t>* const S = (*I).EL;
      UniverseSet.insert((*I).EL->begin(), (*I).EL->end());
      UNV.push_back((*I).EL);
      SCSetSizeMap.insert(std::make_pair((*I).EL->size(), (*I).EL));

      for (std::set<int32_t>::const_iterator SI = S->begin();
           SI != S->end(); ++SI) {
        MI = SCSetElementMap.find(*SI);
        if (MI == SCSetElementMap.end()) {
          SCSetElement SEL((*I).IX, (*I).EL->size());
          std::set<SCSetElement, SCSetComp> SCM;
          SCM.insert(SEL);
          SCSetElementMap.insert(std::make_pair(*SI, SCM));
          SCSetIndexMap.insert(std::make_pair((*I).IX, (*I).EL));
        } else {
          std::set<SCSetElement, SCSetComp>& SCM = (*MI).second;
          SCSetElement SEL((*I).IX, (*I).EL->size());
          SCM.insert(SEL);
          SCSetIndexMap.insert(std::make_pair((*I).IX, (*I).EL));
        }
      }

      ++I;
    }
  }

  void PrintSetUniverse() const {
    if (PS) {
      std::multimap<size_t, const std::set<int32_t>* const,
                    SCSetSizeComp>::const_iterator I = SCSetSizeMap.begin();
      std::multimap<size_t, const std::set<int32_t>* const,
                    SCSetSizeComp>::const_iterator E = SCSetSizeMap.end();
      while (I != E) {
        std::cerr << '[' << (*I).first << "]: ";
        PrintSet(*(*I).second);
        std::cerr << std::endl;
        ++I;
      }
    }
  }

  void LinearSetCoverage() {
    std::set<int32_t> CoveredSet;
    std::map<const std::set<int32_t>* const, uint32_t> SCSetMapIX;
    uint32_t IX = 0U;

    CSetIndexVec.clear();
    MC = 0U;

    for (std::vector<const std::set<int32_t>*>::iterator UI = UNV.begin();
         UI != UNV.end(); ++UI) {
      SCSetMapIX.insert(std::make_pair((*UI), IX++));
    }

    std::multimap<size_t, const std::set<int32_t>* const,
                  SCSetSizeComp>::const_iterator MBI = SCSetSizeMap.begin();
    std::multimap<size_t, const std::set<int32_t>* const,
                  SCSetSizeComp>::const_iterator MEI = SCSetSizeMap.end();
    std::multimap<size_t, const std::set<int32_t>* const,
                  SCSetSizeComp>::const_iterator NEI = MBI;
    std::map<const std::set<int32_t>* const, uint32_t>::const_iterator IXMI;

    while (CoveredSet.size() < UniverseSet.size()) {
      if (MBI == MEI)
        break;

      const std::set<int32_t>* MSet = (*MBI).second;
      ++NEI;

      if (!std::includes(CoveredSet.begin(), CoveredSet.end(),
                         MSet->begin(), MSet->end())) {
        CoveredSet.insert(MSet->begin(), MSet->end());
        IXMI = SCSetMapIX.find(MSet);
        assert(IXMI != SCSetMapIX.end() && "Set not found in the SetIndexMap!");

        CSetIndexVec.push_back((*IXMI).second);
        ++IT;
        ++MC;
      }

      if (NEI != MEI) {
        const std::set<int32_t>* NSet = (*NEI).second;
        MBI = NEI;

        if (!std::includes(CoveredSet.begin(), CoveredSet.end(),
                           NSet->begin(), NSet->end())) {
          CoveredSet.insert(NSet->begin(), NSet->end());
          IXMI = SCSetMapIX.find(NSet);
          assert(IXMI != SCSetMapIX.end() && "Set not found in the SetIndexMap!");

          CSetIndexVec.push_back((*IXMI).second);
          ++IT;
          ++MC;
        }
      }

      ++MBI;
    }
  }

  void PrintCoverageSets() const {
    for (std::vector<uint32_t>::const_iterator I = CSetIndexVec.begin();
         I != CSetIndexVec.end(); ++I) {
      std::map<uint32_t, const std::set<int32_t>* const>::const_iterator MI =
        SCSetIndexMap.find(*I);
      if (MI != SCSetIndexMap.end()) {
        std::cerr << '[' << *I << "]: ";
        PrintSet(*((*MI).second));
        std::cerr << std::endl;
      }
    }
  }
};

static bool ValidateArguments(const std::string& In) {
  return !In.empty();
}

static void PrintHelp() {
  std::cerr << "Usage: mapscplinear [-h | --help]" << std::endl;
  std::cerr << "                    [ -i <input-file> | --input <input-file>]"
    << std::endl;
}

static struct option long_options[] = {
  { "help",   no_argument,        0,  'h' },
  { "input",  required_argument,  0,  'i' },
  { "print",  required_argument,  0,  'p' },
  { 0,        0,                  0,   0  }
};

int main(int argc, char* const argv[])
{
  int C;
  int OIx = 0;
  std::string InFile;

  while (1) {
    C = getopt_long(argc, argv, "hpi:", long_options, &OIx);
    if (C == -1)
      break;

    switch (C) {
    case 'i':
      InFile = optarg;
      break;
    case 'p':
      PS = true;
      break;
    case 'h':
      PrintHelp();
      return 0;
      break;
    default:
      PrintHelp();
      return 1;
      break;
    }
  }

  if (!ValidateArguments(InFile)) {
    PrintHelp();
    return 1;
  }

  SCSetMatrix SCSM;
  SCSM.ReadFromFile(InFile);

  SCPLinear SCPL;
  SCPL.CreateUniverse(SCSM.Matrix());
  SCPL.LinearSetCoverage();

  struct timespec TSStart;
  struct timespec TSEnd;

  Timestamp(&TSStart);
  uint32_t MC = SCPL.MinCoverage();
  Timestamp(&TSEnd);

  if (MC > 0) {
    SCPL.PrintCoverageSets();
    std::cout << "MinCover: " << SCPL.MinCoverage() << " Iterations: "
      << SCPL.Iterations() << std::endl;
    PrintTimediff(&TSStart, &TSEnd);
  } else {
    std::cerr << "No covering possible. Iterations: "
      << SCPL.Iterations() << '.' << std::endl;
    PrintTimediff(&TSStart, &TSEnd);
  }

  SCPL.PrintSetUniverse();

  return 0;
}