JavaScriptでインクリメンタルサーチ雛形

インクリメンタルサーチ (書くまま検索) ってどうやったら出来るかなーと考えていた。

自分が考えていたのは、元から配列を用意しておいて、入力欄にタイプするごとに配列を走査する物で、なんとか汎用的に書けないかなーと思っていた。配列の要素数は、まあ1万ぐらいまでが目安。

でもたぶん最近は Google Suggest みたいに毎回リクエストするのが主流で、インクリメンタルサーチの為に1万ものデータをいちいち落とすサービスなんて無いだろうってことで、誰の得にもならなさそうだけど、ここに書いて埋葬しておく。

ちなみに以下に書く方法は gemのドキュメントをブラウザで一括検索できるようにするソフトウェア、croc の検索を高速化するのにめでたく利用することが出来た。その話は別の機会に書くと思う。(こういうローカルに配列データがある場合だけ有効な方法かなと思う)

使い方としては、プロトタイプだけ定義しておいて、実際には

var incs = new IncSearch(document.getElementById('searchbox'));
incs.data = myData;

とするだけで使えるようになっている。もし雛形の中で、一つだけ処理を置き換えたい場合は

incs.display = function(query,ary){ /* ほにゃらら */ };

みたいにする。そういった場合でも、メインの IncSearch.prototype.startSearch や IncSearch.prototype.search は置き換えないでも使えるはず。

というわけで埋葬物。JSDeferred 依存なので、 とかで最初に定義しておく必要がある。(このぐらいだったらJSDeferred 使わなくてもよかったかも)

// まず IncSearch クラスを定義。searchbox があれば監視を開始。
function IncSearch(arg){
	this.init();
	if (arg) this.watch(arg);
};
// 定数を定義。
IncSearch.DISPLAY_NUM = 10;  // 検索結果を表示する件数
IncSearch.BATCH_SEARCH_TIME = 20;  // 一度に検索する時間
// プロトタイプ定義。上書き可能。
IncSearch.prototype = {
	init : function() {
		this.data = [];
		this.cache = {};
		this.query = '';
		this.DISPLAY_NUM = IncSearch.DISPLAY_NUM;
		this.BATCH_SEARCH_TIME = IncSearch.BATCH_SEARCH_TIME;
	},
	// 検索欄にイベントリスナーを定義。
	watch : function(input) {
		if (/^input$/i.test(input.tagName)){
			var self = this;
			var handler = function(){ self.startSearch(input.value) };
			if (input.addEventListener) {
				input.addEventListener('input',handler,false);
			} else if (input.attachEvent) {
				input.attachEvent('oninput',handler);
			} else {
				input.oninput = handler;
			}
			this.input = input;
		}
	},
	// 検索を始める前に query によって効率の良い方法を探る。
	startSearch : function(query){
		if (query == this.query) return;	 // もし一つ前の query と同じなら辞める
		this.query = query;
		this.clear();  // 検索結果表示をクリア
		if (this.disableSearch(query)) return;  // query の種類によっては検索しない。
		if (this.cache[query]) {  // キャッシュがあればそれを使う。
			this.display(query, this.cache[query].slice(0,this.DISPLAY_NUM));
		} else {
			var prev = this.refineSearchFrom(query);  // 前の結果から絞り込める場合など。
			if (prev != null) {
				this.search(query, prev);
			} else {
				this.search(query, this.data);  // 普通にデータ配列から検索。
			}
		}
	},
	// もし今の検索 query の最後の文字を除いた query がキャッシュにあったらそこから絞り込む。
	refineSearchFrom : function(query){
		var cached = this.cache[query.slice(0,-1)];
		if (cached !== undefined) {
			return cached;
		} else {
			return null;
		}
	},
	// もし query が空または空白文字だけならそもそも検索しない。
	disableSearch : function(query){
		return !query.match(/[^\s]/);
	},
	// 本検索 JSDeferred 依存。
	search : function(query,ary) {
		var n = 0;
		var len = ary.length;
		var results = [];
		var self = this;
		// 配列の各要素につき、matchFunc が true になるものを収集。
		// もし query により matchFunc を書き換えたい場合は、matchFuncGenerator を定義しておく。
		var func = (this.matchFuncGenerator) ? this.matchFuncGenerator(query) : this.matchFunc;
		// 表示するものだけ一気に収集。
		Deferred.next(function() {
			var temp = [];
			while (n < len) {
				if( func(query, ary[n]) ) temp.push(ary[n]);
				n++;
				if(temp.length >= self.DISPLAY_NUM) break;
			}
			// もし検索している間に次の query を既にタイプしてなければ、結果を表示。
			if (query == self.query) self.display(query, temp);
			results = results.concat(temp);
		})
		.wait(0)
		.next(function(){
			if(n>=len) return;
			var temp = [];
			var start = new Date;
			while(new Date - start < self.BATCH_SEARCH_TIME){  // 非同期で何回かに分けて、とりあえず配列の最後まで検索。
				if(func(query, ary[n])) temp.push(ary[n]);
				if(++n >= len) break;
			}
			results = results.concat(temp);
			return Deferred.next(arguments.callee);
		}).next(function(){
			self.cache[query] = results;  // 検索結果をキャッシュ
		});
	},
	// とりあえず matchFunc はシンプルに。たぶん自分で置き換えが必要。
	matchFunc : function(query,obj){
		return obj.indexOf(query) >= 0;
	},
	// あるいは matchFunc を定義する必要があると思う。
	matchFuncGenerator : null,
	// 表示のための関数も自分で定義したほうがいいかも。とりあえず使える状態。
	display : function(query,ary) {
		if (!this._box) {
			this._box = document.createElement('pre');
			this._box.setAttribute('style','position:absolute;border:black solid 1px;width:200px;');
			this.input.parentNode.insertBefore(this._box, this.input.nextSibling);
		}
		var html = '';
		for(var i=0,len=ary.length;i<len;i++){
			html += ary[i]+'\n';
		}
		this._box.innerHTML = html;
	},
	// 表示をクリア。
	clear : function() {
		if (this._box) {
			this._box.innerHTML = '';
		}
	}
};

キャッシュやら現在の query やらを覚えさせておく必要があるので、インクリメンタルサーチはクラスベースで作るのが良い気がした。

あんまり試してないけど一応クロスブラウザになってるような気がする。

コメントで指摘いただいた部分を修正。