/*
	$Date: 1997/07/14 13:54:57 $
	$Revision: 1.2 $

	DFA方式が何かと遅いのでシフタ方式を試みる

	Pilot上の曖昧検索

	makepat("[ま][すず][い]")

	または

	makepat("\x82\xdc\x82[\xb7\xb8]\x82\xa2");

	TODO:
		不要なものの除去
		bcmp()導入

*/
#define		STRICT
#include	<windows.h>
#include	"search.h"

#define MAXMISMATCH	3
#define MAXCHARS	256
#define INITPAT		0x4000

unsigned long	statemask = 0 ;
unsigned long	acceptpat = 0 ;
unsigned long	epsilon = 0 ;
unsigned long	shiftpat[ MAXCHARS ] ;
int				mismatch = 0 ;

void
makepat( unsigned char *s, int m )
{
	int				i ;
	unsigned long	mask = INITPAT ;

	if ( !s ) {
		return ;
	}
	mismatch = m ;
	statemask = INITPAT ; // 不要なのか?
	epsilon = 0 ;
	for ( i = 0 ; i < MAXCHARS ; i ++ ) {
		shiftpat[i] = 0 ;
	}
	for ( ; *s ; s ++ ) {
		if ( *s == ' ' ) {		 /* wildcard */
			epsilon |= mask ;
		} else if ( *s == '\x01' ) {
			for ( s ++ ; *s != '\x02' ; s ++ ) {
				shiftpat[(int)(*s)] |= mask ;
			}
			mask >>= 1 ;
			statemask |= mask ;
		} else {
			shiftpat[(int)(*s)] |= mask ;
			mask >>= 1 ;
			statemask |= mask ;
		}
	}
	acceptpat = mask ;
}

int
match( unsigned char *s )
{
	int				i, j ;
	long			n, c, c1, n1 ;
	unsigned long	*curpat,*newpat ;
	unsigned long	p[32][MAXMISMATCH] ;

	curpat = p[0] ;
	newpat = p[1] ;
	curpat[0] = INITPAT ;
	for ( i = 1 ; i <= mismatch ; i ++ ) {
		curpat[i] = 0 ;
	}
	for ( j = 1 ; *s && *s != '/' && j < 32-2 ; s ++ , j ++ ) {
		c = curpat[0] ;
		newpat[0] = n1 = (c & epsilon) | ((c & shiftpat[(int)(*s)]) >> 1) ;
		for ( i = 1 ; i <= mismatch ; i ++ ) {
			c1 = c ;
			c = curpat[i] ;
			n = (c & epsilon) | ((c & shiftpat[(int)(*s)]) >> 1)
			  | c1
			  | (c1 >> 1)
			  | (n1 >> 1) ; /* ε遷移 */
			newpat[i] = n1 = n ;
		}
		curpat = p[j] ;
		newpat = p[j+1] ;
	}
	for ( i = 0 ; i <= mismatch ; i ++ ) {
		if ( curpat[i] & acceptpat ) {
			return 1 ;
		}
	}
	return 0 ;
}

#ifdef TESTONUNIX
main(int argc, char **argv)
{
	int matched;
	unsigned char *s;
	unsigned char *pat = " ab[cd]e ";

//	initsearch();

	pat = " \x82\xdc\x82\x01\xb7\xb8\x02\x82\xa2 "; /* ま[すず]い */

	makepat(pat,0);

	for(s=pat;*s;s++) printf("<%02x> ",*s);

	printf("\n");
	check("\x82\xdc\x82\xb7\x82\xa2");
	check("\x82\xdc\x82\xba\x82\xa2");
	check("\x82\xdc\x82\xb8\x82\xa2xxx");
	check("\x82\xdc");
	check("\x82\xdc\x72\xb8\x82\xa2xxx");
#ifdef XXXX

	check("abce ");
	check("abcef");
	check("abdek");
	check("abcdf");
	check("abckf");
	check("aabcdef");
	check("aabcef");
#endif

	endsearch();
}

check(unsigned char *s)
{
	int matched;
	matched = match(s);
	printf("%d %s\n",matched,s);
}

#endif
