@jinxonik / UniLecs #220

file_mask.cxx

#include <iostream>
#include <string>
#include <string_view>
#include <vector>
#include <algorithm>

// CLASS DECLARATION ///////////////////////////////////////////////////////////////////////////////

class FileMask
{
  private:
    struct Submask {
      public:
        using StrIt = std::string::const_iterator;
        const std::string_view mask;
        // Store submask string and prefix function values
        Submask(const std::string_view mask, bool calc_pi = true);
        // Find submask in chars [first..last) by KMP search
        auto find(StrIt first, const StrIt last) const;
        // Compare mask char with filename char
        static bool ch_comp(const char mask_ch, const char fn_ch) {
          return mask_ch == fn_ch || mask_ch == '?';
        }
      private:
        std::vector<size_t> _pi;  // prefix function for KMP search
    };
    std::string _mask;               // full mask
    std::vector<Submask> _submasks;  // submasks between '*' chars

  public:
    // Empty constructor
    FileMask() {}
    // Constructor: set mask
    FileMask(const std::string& mask) {
      set_mask(mask);
    }
    // Set new file mask
    void set_mask(const std::string& mask);
    // Check if file name matches file mask
    bool check_match(const std::string& filename) const;
};

// FileMask::Submask METHOD DEFINITIONS ////////////////////////////////////////////////////////////

FileMask::Submask::Submask(const std::string_view mask, bool calc_pi) : mask(mask)
{
  if (!calc_pi) { return; }
  const size_t mask_len = mask.length();
  // Prefix function values calculation. Item [i] will contain the number of matched
  // chars at the start and at the end of mask substring with i+1 chars in length
  _pi.resize(mask_len);
  for (size_t i = 1; i < mask_len; ++i) {  // p[0] = 0
    const char ch = mask[i];
    size_t matches = _pi[i-1];
    while (matches > 0 && !ch_comp(ch, mask[matches])) { matches = _pi[matches-1]; }
    if (ch_comp(ch, mask[matches])) { ++matches; };
    _pi[i] = matches;
  }
}

// Find submask in chars [first..last) by KMP search
auto FileMask::Submask::find(StrIt first, const StrIt last) const
{
  const size_t mask_len = mask.length();
  for (size_t matches = 0; first != last; ++first) {
    const char ch = *first;
    while (matches > 0 && !ch_comp(mask[matches], ch)) { matches = _pi[matches-1]; }
    if (ch_comp(mask[matches], ch)) { ++matches; }
    if (matches == mask_len) { return first - mask_len; }
  }
  return last;
}

// FileMask METHOD DEFINITIONS /////////////////////////////////////////////////////////////////////

// Set new file mask
void FileMask::set_mask(const std::string& mask)
{
  _mask = mask;
  _submasks.clear();
  const auto begin = _mask.begin(), end = _mask.end();
  auto start = begin;
  // Split file mask by submasks divided by asterisk char
  while (true) {
    const auto pos = std::find(start, end, '*');
    // Add submask (including last, even if it's empty)
    _submasks.emplace_back(std::string_view(_mask).substr(start-begin, pos-start), !(_submasks.empty() || pos == end));
    if (pos == end) { break; }
    // Skip asterisks (including repeating)
    start = std::find_if(pos+1, end, [](const char ch) { return ch != '*'; });
  }
}

// Check if file name matches file mask
bool FileMask::check_match(const std::string& filename) const
{
  size_t sm_count = _submasks.size();
  if (sm_count == 0) { return false; }  // file mask is not initialized

  // Search for the first submask
  const auto& sm0_str = _submasks.front().mask;
  const size_t sm0_str_len = sm0_str.length();
  if (filename.length() < sm0_str_len) { return false; }
  if (!std::equal(sm0_str.begin(), sm0_str.end(), filename.begin(), Submask::ch_comp)) { return false; }
  auto pos = filename.begin() + sm0_str_len, fn_end = filename.end();

  if (sm_count > 1) {
    // Search for all other submasks (except the last)
    for (size_t i = 1, lim = sm_count - 1; i < lim; ++i) {
      const auto& sm = _submasks[i];
      pos = sm.find(pos, fn_end);
      if (pos == fn_end) { return false; }
      pos += sm.mask.length();
    }

    // Search for the last submask
    const auto& smL_str = _submasks.back().mask;
    const size_t smL_str_len = smL_str.length(), fn_rest = std::distance(pos, fn_end);
    if (fn_rest < smL_str_len) { return false; }
    return std::equal(smL_str.begin(), smL_str.end(), fn_end - smL_str_len, Submask::ch_comp);
  }

  // If there is only one submask
  return pos == fn_end;
}

// MAIN FUNCTION ///////////////////////////////////////////////////////////////////////////////////

using std::cout;
using std::cin;

int main()
{
  std::string s;
  cout << "Enter mask: ";
  std::getline(cin, s);
  if (s.empty()) {
    cout << "Mask can't be empty!\n";
    return 1;
  }

  FileMask fm(s);
  for (;;) {
    cout << "Enter string (empty to exit): ";
    std::getline(cin, s);
    if (s.empty()) { break; }
    if (fm.check_match(s)) {
      cout << "Yeah it matches! :)\n";
    } else {
      cout << "No, it doesn't match, try again :(\n";
    }
  }

  return 0;
}