もしかして機能はじめました

LL魂のイベントで、Rubyにもしかして機能が追加された、というジョークを聞いて以来、そのうち実装してみたいなーと考えていました。

array.langwerth　と length と書くつもりが手が滑ってlangwerthと書いてしまった場合、次のように表示されるようになりました。

lib::builtin::Array::langwerth は定義されていません。'length'と間違えている可能性があります。

あるクラスのメンバが無いとき、存在するメンバ名のedit distance*1が一番近いものを求めて表示します。
edit distanceは次のようにして求めています。

void edit_distance_helper(const void* data1, unsigned int size1, const void* data2, unsigned int size2, int* buf, unsigned int k, int offset){
	unsigned int x = std::max(buf[k-1+offset]+1, buf[k+1+offset]);
	unsigned int y = x-k;
	while(x<size1 && y<size2 && ((unsigned char*)data1)[x-1]==((unsigned char*)data2)[y-1]){
		++x;
		++y;
	}
	buf[k+offset] = x;
}

unsigned int edit_distance(const void* data1, unsigned int data_size1, const void* data2, unsigned int data_size2){
	unsigned int size1 = data_size1 + 1;
	unsigned int size2 = data_size2 + 1;

	int buf_size = size1+size2+6;
	int* buf = (int*)malloc(sizeof(int)*buf_size);
	
	for(int i=0; i<buf_size; ++i){
		buf[i] = 0;
	}

	if(size1<size2){
		std::swap(data1, data2);
		std::swap(size1, size2);
	}

	int offset = size2+1, delta = size1-size2;
	for(int p=0;;++p){
		for(int k=-p; k<delta; ++k){
			edit_distance_helper(data1, size1, data2, size2, buf, k, offset);
		}

		for(int k=delta+p; k>delta; --k){
			edit_distance_helper(data1, size1, data2, size2, buf, k, offset);
		}

		edit_distance_helper(data1, size1, data2, size2, buf, delta, offset);

		if(buf[delta+offset]==size1){
			free(buf);
			return p+delta;
		}
	}
	return 0;
}

これは2002年頃のCマガジンでこのedit distanceの紹介がされていて、その当時にその説明を読みながら実装したもの、だと記憶してます。過去プログラムの残骸から発掘してこのたび移植しました。

*1:編集距離　二つの文字列の一方を何回編集したらもう一方の文字列となるかを示す