ukengine/pattern.cpp

   1 // -*- coding:unix; mode:c++; tab-width:4; c-basic-offset:4; indent-tabs-mode:nil -*-
   2 /*------------------------------------------------------------------------------
   3 VnConv: Vietnamese Encoding Converter Library
   4 UniKey Project: http://unikey.sourceforge.net
   5 Copyleft (C) 1998-2002 Pham Kim Long
   6 Contact: longp@cslab.felk.cvut.cz
   7
   8 This program is free software; you can redistribute it and/or
   9 modify it under the terms of the GNU General Public License
  10 as published by the Free Software Foundation; either version 2
  11 of the License, or (at your option) any later version.
  12
  13 This program is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with this program; if not, write to the Free Software
  20 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  21 --------------------------------------------------------------------------------*/
  22
  23 #include "pattern.h"
  24
  25 //////////////////////////////////////////////////
  26 // Pattern matching (based on KPM algorithm)
  27 //////////////////////////////////////////////////
  28
  29 //----------------------------
  30 void PatternState::reset()
  31 {
  32         m_pos = 0;
  33         m_found = 0;
  34 }
  35
  36 //----------------------------
  37 void PatternState::init(char *pattern)
  38 {
  39         m_pos = 0;
  40         m_found = 0;
  41         m_pattern = pattern;
  42
  43         int i=0, j=-1;
  44     m_border[i]=j;
  45     while (m_pattern[i])
  46     {
  47         while (j>=0 && m_pattern[i]!=m_pattern[j]) j=m_border[j];
  48         i++; j++;
  49         m_border[i]=j;
  50     }
  51 }
  52
  53 //-----------------------------------------------------
  54 //get next input char, returns 1 if pattern is found.
  55 //-----------------------------------------------------
  56 int PatternState::foundAtNextChar(char ch)
  57 {
  58         int ret = 0;
  59         //int j = m_pos;
  60         while (m_pos>=0 && ch!=m_pattern[m_pos]) m_pos=m_border[m_pos];
  61         m_pos++;
  62         if (m_pattern[m_pos]==0) {
  63                 m_found++;
  64                 m_pos = m_border[m_pos];
  65                 ret = 1;
  66         }
  67         return ret;
  68 }
  69
  70 //-----------------------------------------------------
  71 void PatternList::init(char **patterns, int count)
  72 {
  73         m_count = count;
  74         delete [] m_patterns;
  75         m_patterns = new PatternState[count];
  76         for (int i=0; i<count; i++)
  77                 m_patterns[i].init(patterns[i]);
  78 }
  79
  80 //-----------------------------------------------------
  81 // return the order number of the pattern that is found.
  82 // If more than 1 pattern is found, returns any pattern
  83 // Returns -1 if no pattern is found
  84 //-----------------------------------------------------
  85 int PatternList::foundAtNextChar(char ch)
  86 {
  87         int patternFound = -1;
  88         for (int i=0; i<m_count; i++) {
  89                 if (m_patterns[i].foundAtNextChar(ch))
  90                         patternFound = i;
  91         }
  92         return patternFound;
  93 }
  94
  95 //-----------------------------------------------------
  96 void PatternList::reset()
  97 {
  98         for (int i=0; i<m_count; i++)
  99                 m_patterns[i].reset();
 100 }