---

dsBoyer.h

Go to the documentation of this file.

/* 
 * $Id: dsBoyer.h,v 1.8 2004/06/10 10:58:17 dsamersoff Exp $
 */

#ifndef dsBoyer_h
#define dsBoyer_h

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include <dsutil.h>

#ifdef MAXCHAR
# define BOYER_MAXCHAR MAXCHAR
# else
# define BOYER_MAXCHAR 256
#endif

class boyer_base
{

protected:
  int _skip[BOYER_MAXCHAR];
  int _len;
  char* _pat;

  boyer_base(const char *pat)
  {
    int k;

    _len = strlen(pat);

    for( k=0; k < BOYER_MAXCHAR; k++ ) _skip[k] = _len;

    for( k=0; k < _len-1;  k++ ) _skip[ (int) (pat[k] & 0xFF) ] = _len - k -1;
  }

public:
  template <class T>
  T* find(T* text, int n ) const
  {
    int i, j, k;

    for( k = _len-1; k < n; k += _skip[text[k] & (BOYER_MAXCHAR-1)] )
    {
      for( j=_len-1, i = k; j >= 0 && text[i] == _pat[j]; j-- ) i--;

      if( j == -1 ) return text+i+1;

    }

    return 0;
  }
  
  template <class T>
  T* ucfind(T* text, int n ) const
  {
    int i, j, k;

    for( k = _len-1; k < n;
         k += _skip[tolower(((unsigned char *)text)[k])] )
    {
      for( j=_len-1, i = k;
           j >= 0 && tolower(((unsigned char *)text)[i]) == _pat[j];
           j-- ) i--;

      if( j == -1 ) return text+i+1;

    }

    return 0;
  }

  int len(){ return _len; }

operator const char* () const { return _pat;}
  
operator int () const { return _len;}

};

/* 
 * The same as class boyer below, but search pattern not copyed. 
 * It's faster, but caller is responsible to keep pointer 
 * to pattern. 
 * 
 */

class cboyer : public boyer_base
{

public:
cboyer(const char* pat) : boyer_base(pat)
  {
    _pat = (char *) pat;
  }
};


class boyer : public boyer_base
{

public:
  
  boyer(const char* pattern) : 
           boyer_base(pattern)
  {
    _pat = ds_strdup(pattern);
  }
 
~boyer()
 { if (_pat)
      delete[] _pat;
 }
};

#endif

---