dcdd144598 2011-02-23        kinaba: #ifndef AFX_NSEARCH_H__8336E133_90C5_4059_8605_6066BD37D042__INCLUDED_
dcdd144598 2011-02-23        kinaba: #define AFX_NSEARCH_H__8336E133_90C5_4059_8605_6066BD37D042__INCLUDED_
dcdd144598 2011-02-23        kinaba: #include "Search.h"
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{ @pkg Gp.Search //@}
dcdd144598 2011-02-23        kinaba: // BM法検索用ポリシーs
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //@{ 大文字小文字を区別するポリシー //@}
dcdd144598 2011-02-23        kinaba: struct CaseSensitive
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	static unicode map( unicode c )
dcdd144598 2011-02-23        kinaba: 		{ return c; }
dcdd144598 2011-02-23        kinaba: 	static bool not_equal( unicode c1, unicode c2 )
dcdd144598 2011-02-23        kinaba: 		{ return c1!=c2; }
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //@{ 大文字小文字を区別しないポリシー //@}
dcdd144598 2011-02-23        kinaba: struct IgnoreCase
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	static unicode map( unicode c )
dcdd144598 2011-02-23        kinaba: 		{ return (L'a'<=c && c<=L'z' ? c-L'a'+L'A' : c); }
dcdd144598 2011-02-23        kinaba: 	static bool not_equal( unicode c1, unicode c2 )
dcdd144598 2011-02-23        kinaba: 		{ return map(c1)!=map(c2); }
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	BM法による普通の正方向検索
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: template<class ComparisonPolicy> class BMSearch
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	BMSearch( const unicode* key )
dcdd144598 2011-02-23        kinaba: 		: keylen_( my_lstrlenW(key) )
dcdd144598 2011-02-23        kinaba: 		, key_( my_lstrcpyW( new unicode[keylen_+1], key ) )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		memFF( lastAppearance_, sizeof(lastAppearance_) );
dcdd144598 2011-02-23        kinaba: 		for( int i=0, e=keylen_; i<e; ++i )
dcdd144598 2011-02-23        kinaba: 			lastAppearance_[ ComparisonPolicy::map(key[i]) ] = i;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	~BMSearch()
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		delete [] key_;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int Search( const unicode* str, int strlen )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		for( int i=0, e=strlen-keylen_, j, t; i<=e; i+=(j>t?j-t:1) )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			for( j=keylen_-1; j>=0; --j )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				if( ComparisonPolicy::not_equal( key_[j], str[i+j] ) )
dcdd144598 2011-02-23        kinaba: 					break;
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 			if( j < 0 )
dcdd144598 2011-02-23        kinaba: 				return i;
dcdd144598 2011-02-23        kinaba: 			t = lastAppearance_[ ComparisonPolicy::map(str[i+j]) ];
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 		return -1;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int keylen() const { return keylen_; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	int      keylen_;
dcdd144598 2011-02-23        kinaba: 	unicode* key_;
dcdd144598 2011-02-23        kinaba: 	int      lastAppearance_[65536];
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	BM法による逆方向検索
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: template<class ComparisonPolicy> class BMSearchRev
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	BMSearchRev( const unicode* key )
dcdd144598 2011-02-23        kinaba: 		: keylen_( my_lstrlenW(key) )
dcdd144598 2011-02-23        kinaba: 		, key_( my_lstrcpyW( new unicode[keylen_+1], key ) )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		memFF( firstAppearance_, sizeof(firstAppearance_) );
dcdd144598 2011-02-23        kinaba: 		for( int i=keylen_-1; i>=0; --i )
dcdd144598 2011-02-23        kinaba: 			firstAppearance_[ ComparisonPolicy::map(key[i]) ] = i;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	~BMSearchRev()
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		delete [] key_;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int Search( const unicode* str, int strlen )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		for( int i=strlen-keylen_-1, j, e, t; i>=0; i-=(t>j?t-j:1) )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			for( j=0, e=keylen_; j<e; ++j )
dcdd144598 2011-02-23        kinaba: 				if( ComparisonPolicy::not_equal( key_[j], str[i+j] ) )
dcdd144598 2011-02-23        kinaba: 					break;
dcdd144598 2011-02-23        kinaba: 			if( j >= e )
dcdd144598 2011-02-23        kinaba: 				return i;
dcdd144598 2011-02-23        kinaba: 			t = firstAppearance_[ ComparisonPolicy::map(str[i+j]) ];
dcdd144598 2011-02-23        kinaba: 			if( t == -1 ) t = keylen_;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 		return -1;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int keylen() const { return keylen_; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	int      keylen_;
dcdd144598 2011-02-23        kinaba: 	unicode* key_;
dcdd144598 2011-02-23        kinaba: 	int      firstAppearance_[65536];
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: // Searhcableとしての実装（正方向検索）
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: template<class CompalisonPolicy>
dcdd144598 2011-02-23        kinaba: class NSearch : public Searchable
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	NSearch( const unicode* key ) : s_(key) {}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	bool Search(
dcdd144598 2011-02-23        kinaba: 		const unicode* str, ulong len, ulong stt, ulong* mbg, ulong* med )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		int n = s_.Search( str+stt, len-stt );
dcdd144598 2011-02-23        kinaba: 		if( n < 0 )
dcdd144598 2011-02-23        kinaba: 			return false;
dcdd144598 2011-02-23        kinaba: 		*mbg = stt + n;
dcdd144598 2011-02-23        kinaba: 		*med = stt + n + s_.keylen();
dcdd144598 2011-02-23        kinaba: 		return true;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	BMSearch<CompalisonPolicy> s_;
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: // Searhcableとしての実装（逆方向検索）
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: template<class CompalisonPolicy>
dcdd144598 2011-02-23        kinaba: class NSearchRev : public Searchable
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	NSearchRev( const unicode* key ) : s_(key) {}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	bool Search(
dcdd144598 2011-02-23        kinaba: 		const unicode* str, ulong len, ulong stt, ulong* mbg, ulong* med )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		int n = s_.Search( str, stt+s_.keylen() );
dcdd144598 2011-02-23        kinaba: 		if( n < 0 )
dcdd144598 2011-02-23        kinaba: 			return false;
dcdd144598 2011-02-23        kinaba: 		*mbg = n;
dcdd144598 2011-02-23        kinaba: 		*med = n + s_.keylen();
dcdd144598 2011-02-23        kinaba: 		return true;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	BMSearchRev<CompalisonPolicy> s_;
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: #endif