gmt-makemap/modules/gmt/cmpstr.c++

#include <iostream>
#include <set>
#include <string>
#include <vector>

bool CmpStrEx(const std::string& expr, const std::string& str)
{
 if(expr.empty() || str.empty()) return false;

 struct State
 {
  struct Block
  {
   const size_t b,len;
   const bool optional;
   Block(const size_t bb,const size_t ee,const bool o):b(bb),len(ee-bb),optional(o) {}
  };

  struct Cursor
  {
   size_t block,offset;
   bool operator <(const struct Cursor& c) const
   {
    if(block<c.block) return true;
    if(block>c.block) return false;
    if(offset<c.offset) return true;
    return false;
   }
  };

  typedef std::set<struct Cursor> Cursors;
  typedef std::set<struct Cursor>::iterator pCursor;

  std::vector<struct Block> blockchain;
  Cursors cursors;
  const std::string& s;

  Cursors InitCursors(size_t block) const
  {
   Cursors cs;
   for(size_t i=block; i<blockchain.size(); ++i)
   {
    cs.insert({i,0});
    if(!blockchain[i].optional) break;
   }
   return cs;
  }

  State(const std::string& str):s(str)
  {
   size_t cur=0;
   size_t bpos=0;

   // Parse blocks
   while(cur<s.length())
   {
    if('['==s[cur] || ']'==s[cur])
    {
     // Add current block to blockchain
     if(cur>bpos) blockchain.push_back(Block(bpos,cur,(']'==s[cur])));
     cur++;
     bpos=cur;
     continue;
    }
    cur++;
   }
   // Add last block
   if(bpos<s.length()) blockchain.push_back(Block(bpos,s.length(),false));

   // Creating cursors for the first symbol
   cursors=InitCursors(0);
  }

  bool CmpSmb(const char c)
  {
   pCursor p=cursors.begin();
   bool res=false;

   // Compare symbol with all cursors
   while(p!=cursors.end())
   {
    const Block& bl=blockchain[p->block];
    if(c==s[bl.b+p->offset]) {res=true; ++p;}
    else p=cursors.erase(p);
   }

   // Increment cursors
   Cursors upd;  // New cursors
   p=cursors.begin();
   while(p!=cursors.end())
   {
    // Increment cursor on one position
    if(p->offset+1>=blockchain[p->block].len) // Go to next block
    {
     Cursors cs=InitCursors(p->block+1); // Get cursors for next block
     p=cursors.erase(p); // Erase current cursor
     for(const auto& cur: cs) upd.insert(cur); // Copy cursors to new set
     continue;
    }
    else upd.insert({p->block,p->offset+1});
    if(blockchain[p->block].optional) // If current block is optional next symbol may be from next block
    {
     Cursors cs=InitCursors(p->block+1); // Get cursors for next blockchain
     for(const auto& cur: cs) upd.insert(cur); // Copy cursors to new set
    }
    ++p;
   }

   cursors=upd;
   return res;
  }

 };

 struct State st(expr);
 for(size_t pos=0; pos<str.length(); ++pos)
 {
  if(!st.CmpSmb(str[pos])) return false;
 }

 return true;
}


int main(int argc, char** argv)
{
 if(argc!=3) return 1;
 std::cout<<"Compare "<<argv[1]<<" with template "<<argv[2]<<": "<<(CmpStrEx(argv[2],argv[1])?"match":"not match")<<std::endl;
 return 0;
}