---

G:/NewGrep/pattern.hpp

Go to the documentation of this file.

static char version[] = "$Header: /TDS Product Cycle/0 Development/Software/MiscTools/NewGrep/pattern.hpp 3     00-11-03 10:19 Vwagner $";

/*
Copyright © 2000 Teton Data Systems

Description:

 */

//! Needed because VS and VC++ (6) don't do namespaces well
typedef std::vector<unsigned short> usv;

//!Holds a set of states for the pattern match algorithm
class StateSet: public  usv
  {
  private:
  public:

    //!Put a state into the set if it isn't already there
    //!\return true if new_state is 0
    bool Put(unsigned short new_state)          //!<new state to put in set
      {
        //! we only put in 'non-zero' states
        if (new_state)
          {
            //! if find doesn't, it returns end()
            if (usv::end() == std::find(usv::begin(), usv::end(), new_state))
              usv::push_back(new_state);
          }

        //! let caller know if we tried to put a 'zero' in
        return !new_state;
      }

    //!override the standard one because it gives back the current vector
    void clear()
      {
        erase(begin(), end());
      }
  };

//!case_independent "pattern match".
/*!
    In usage, two calls are made:
    The first is to the constructor to 'set' the pattern
    Then (possibly) multiple calls to operator () to check strings against the pattern.
    For example:
    \code
    Pattern magic("#?test#?");                  // look for "test" anywhere in the string
    if (magic("this is a test"))                // this would test true
      cout << "Yes, a match.\n";
    if (magic("a rather contrived example"))    // this would test false
      cout << "This is never gonna print\n";
    else cout << "No copy of \"test\" in that string\n.";
    \endcode

    Of course, both calls may be collapsed into a \b single "call" as follows:
    \code
    if (Pattern("#?test#?")("This is a test, isn't it?"))
      cout << "Yes, and successful at that!\n";
    \endcode
    \note this is not particularly efficient as the Pattern will be destructed at the end of the statment, but for a "quick and dirty" it's probably OK

    \b Pattern is designed to work with the \b STL algorithms as a functor.  For example,
    assume a std::vector of string already filled which we wish to test against a pattern.
    The following would be one method:
    \code
    #include <vector>
    #include <algorithm>
    ...
    std::vector<string> text_stuff;
    ...                               // code to fill text_stuff
    ...
    // get an iterator which "points" to the first(1st) string in the vector
    std::vector<string>::const_iterator iter(text_stuff.begin());
    // output all strings which contain the pattern "this matches"
    while (text_stuff.end() != (iter = find(iter, text_stuff.end(), Pattern("#?this'smatches#?"))))
      {
        cout << *iter;      // output string which 'matches'
        ++iter;             // so we start search after this string
      }
    \endcode
    \note we bounded our pattern with #? so that the match could occur anywhere in the target string
    \note we also used 's (whitespace) so that we will match either a space (' ') or tab ('\t') between the two words.
*/
class Pattern
  {
  private:
    std::string the_Pattern;          //!<the actual pattern we're searching for
    unsigned short patp;              //!<working pointer for the match function
    char ch;                          //!<current character from the_Pattern
    usv Compiled_Pattern;             //!<holds 'next state' info
    enum {endstreamch = 0x0d};

    //!get the next character (or 'endstreamch') from the pattern
    //!\return the next character (put it in ch also)
    inline char rch()
      {
        if (patp>=the_Pattern.size())       // if we're past the end
          return ch=endstreamch;            //   return a marker
        return ch=the_Pattern[patp++];      // otherwise return the character AND bump the pointer
      }

    //! get the next 'item' (remove squoted characters)
    //!\return then next character after skipping a squoted one if neccessary
    inline char nextitem()
      {
        if (ch=='\'')         // if the last thing was a 'squote'
          rch();              //   throw away what was squoted
        return rch();         // get the next thing
      }

    //! replace each element of a list starting at 'list' with val
    void setexits(unsigned short list       //!< the start of the list to replace
                 ,unsigned short val)       //!< the value to put in the list
      {
        while (list != 0)
          {
            unsigned short next(Compiled_Pattern[list]);
            Compiled_Pattern[list] = val;
            list = next;
          }
      }

    //! append a value (or list) to a list
    //!\return either val (if the list is empty) or list (if it's not)
    unsigned short join(unsigned short list   //!< start of list
                       ,unsigned short val)   //!< value to append (note this COULD be the start of a new list)
      {
        if (list == 0) return(val);
        unsigned short save_head(list);

        //! follow the list to the end
        while (Compiled_Pattern[list] != 0) list = Compiled_Pattern[list];

        //! add new element to the end
        Compiled_Pattern[list] = val;
        return(save_head);
      }

    //!collect stuff until we get an endstreamch or an unmatched )
    unsigned short expand (unsigned short altp)
      {
        unsigned short exits = 0;
        unsigned short a;

        for (;;)
          {
            a = primative();
              if ((ch == '`') || (ch == '|') || (ch == ')') || (ch == endstreamch))
              {
                exits = join(exits, a);

                  if ( ( ch != '`' ) && ( ch != '|' ) )
                  {
                    return(exits);
                  }

                Compiled_Pattern[altp] = patp;
                altp = patp;
                nextitem();
              }
            else                      // must be just an 'item'
              {
                setexits(a, patp);    // 
              }
          }
      }

    //!get a primative from the pattern
    /*!
    \return pointer (well, patp) of the 1st char of the primative

    a primative is:
    \li an item
    \li a '(' followed by a primative followed by a ')'
    \li a '#' followed by a primative
    */
    unsigned short primative(void)
      {
      unsigned short a;
      char op;

        a = patp;                 // save where we're starting
        op = ch;                  // save current ch for later switching
        nextitem();               // get the next item (we're gonna consume this one)
        switch (op)
          {
          case '(':
            a = expand(a);
            if (ch != ')')
              throw std::runtime_error("bad pattern: expected )");
            nextitem();           // ch == ')' or we would have thrown
            return(a);

          case endstreamch:
          case ')':
          case '`':
          case '|':
            throw std::runtime_error("bad pattern: unexpected ), `, |, or endstreamch");

          case '#':                   // 0 or more of
            setexits(primative(), a); // loop back to try it again
          default:
            return(a);
          }
      }

  protected:
  public:

    //!construct a Pattern object to search (case-independently)
    /*!\verbatim
    The following metacharacters are used in the pattern string
        ? = matches any single character except newline                   
        # = zero or more occurrances of following item               
        % = Matches the null string                   
       () = enclose multiple items to be considered a single item
       'a = any alphabetic character                                      
       'd = any digit                                                     
       'n = any alphanumeric                                              
       's = any white space character                                     
        ' = escape (match following metacharacter literally, '$ = $)     
        | = or (a|b) = a or b   
        ` = or (a`b) = a or b (added to allow easier input from MS command lines)  

      all other characters must be matched exactly
     \endverbatim
     \note The pattern much match the \b entire string presented to \b operator()()
     \note If you mean to look in only \b part of the string, enclose your pattern thusly:
     \note \b #?<your_pattern>#?

    */
    explicit Pattern(std::string pat)           //!<the pattern we'll be attempting to match
      : the_Pattern(pat), patp(0), Compiled_Pattern(pat.size()+1)
      {
        rch();                          //! prime the pump
        setexits(expand(0), 0);         //! generate Compiled_Pattern
      }

    bool operator() (const std::string& String_to_Test)
      {
        StateSet a_states, b_states;
        unsigned short Position_to_Test(0);
        bool success(false);                      //!<working variable that hold's success
        a_states.reserve(the_Pattern.size());
        b_states.reserve(the_Pattern.size());
        a_states.Put(1);
        a_states.Put(Compiled_Pattern[0]);
        for(;;)
          {
            //!for_all a_states .....
            for (StateSet::iterator i = a_states.begin(); i != a_states.end(); ++i)
              {
                unsigned short p = *i;
                unsigned short q = Compiled_Pattern[p];
                switch (the_Pattern[p-1])
                  {
                  case '#':
                    a_states.Put(p+1);
                  case '%':
                    success |= a_states.Put(q);
                    break;
                  case '(':
                  case '`':
                  case '|':
                    a_states.Put(p+1);
                    a_states.Put(q);
                    break;
                  default:
                    break;
                  } // end switch (the_Pattern[p-1])
              } // end for (StateSet::iterator i = a_states.begin(); i != a_states.end(); ++i)

            //! are we done?  test for ONLY two (2) ways out of here
            if (Position_to_Test >= String_to_Test.size()) return success;
            if (!a_states.size()) return false;

            //!Check the next character in the "input" string
            success = false;
            b_states.clear();
            a_states.swap(b_states);
            ch = tolower(String_to_Test[Position_to_Test++]);     //! to make everything 'case independent'

            //!for_all b_states .....
            for (i = b_states.begin(); i != b_states.end(); ++i)
              {
                unsigned short p = *i;
                switch (char k = tolower(the_Pattern[p-1]))       //! to make everything 'case independent'
                  {
                  case '#':
                  case '`':
                  case '|':
                  case '%':
                  case '(':
                    continue;                   // nothing to check here
                  case '\'':                    // AHA!! one of our 'special' characters
                    switch (k = tolower(the_Pattern[p]))          //! to make everything 'case independent'
                      {
                      case 'a':
                        if (isalpha(ch))
                          k = ch;               // so they match later
                        break;
                      case 'd':
                        if (isdigit(ch))
                          k = ch;               // so they match later
                        else
                          k = '0';              // so they canNOT match
                        break;
                      case 'n':
                        if (isalnum(ch))
                          k = ch;               // so they match later
                        break;
                      case 's':
                        if (isspace(ch))
                          k = ch;               // so they match later
                        else
                          k = ' ';              // so they canNOT match
                      default:;     //! nothing to do for 'non-special' characters
                      } // end switch (k = tolower(the_Pattern[p]))

                  //!This is the important part... does the 'pattern' match the 'input string'
                  default:
                    if (ch == k)
                  case '?':     //! remember "?" matches anything
                      success |= a_states.Put(Compiled_Pattern[p]);
                    continue;
                  } // end switch (char k = tolower(the_Pattern[p-1]))
              } // end for (i = b_states.begin(); i != b_states.end(); ++i)
          } // end for (;;) ...... no way out here
      }
  };

---