Subversion-Projekte lars-tiefland.ci

Revision

Details | Letzte Änderung | Log anzeigen | RSS feed

Revision Autor Zeilennr. Zeile
875 lars 1 
(function ($) {
2 
	$.vakata = {};
3 
})(jQuery);
4 
(function ($) {
5 
	// from http://kiro.me/projects/fuse.html
6 
	$.vakata.search = function(pattern, txt, options) {
7 
		options = options || {};
8 
		if(options.fuzzy !== false) {
9 
			options.fuzzy = true;
10 
		}
11 
		pattern = options.caseSensitive ? pattern : pattern.toLowerCase();
12 
		var MATCH_LOCATION	= options.location || 0,
13 
			MATCH_DISTANCE	= options.distance || 100,
14 
			MATCH_THRESHOLD	= options.threshold || 0.6,
15 
			patternLen = pattern.length;
16 
		if(patternLen > 32) {
17 
			options.fuzzy = false;
18 
		}
19 
		if(options.fuzzy) {
20 
			var matchmask = 1 << (patternLen - 1);
21 
			var pattern_alphabet = (function () {
22 
				var mask = {},
23 
					i = 0;
24 
				for (i = 0; i < patternLen; i++) {
25 
					mask[pattern.charAt(i)] = 0;
26 
				}
27 
				for (i = 0; i < patternLen; i++) {
28 
					mask[pattern.charAt(i)] |= 1 << (patternLen - i - 1);
29 
				}
30 
				return mask;
31 
			})();
32 
			var match_bitapScore = function (e, x) {
33 
				var accuracy = e / patternLen,
34 
					proximity = Math.abs(MATCH_LOCATION - x);
35 
				if(!MATCH_DISTANCE) {
36 
					return proximity ? 1.0 : accuracy;
37 
				}
38 
				return accuracy + (proximity / MATCH_DISTANCE);
39 
			};
40 
		}
41 
		var search = function (text) {
42 
			text = options.caseSensitive ? text : text.toLowerCase();
43 
			if(pattern === text || text.indexOf(pattern) !== -1) {
44 
				return {
45 
					isMatch: true,
46 
					score: 0
47 
				};
48 
			}
49 
			if(!options.fuzzy) {
50 
				return {
51 
					isMatch: false,
52 
					score: 1
53 
				};
54 
			}
55 
			var i, j,
56 
				textLen = text.length,
57 
				scoreThreshold = MATCH_THRESHOLD,
58 
				bestLoc = text.indexOf(pattern, MATCH_LOCATION),
59 
				binMin, binMid,
60 
				binMax = patternLen + textLen,
61 
				lastRd, start, finish, rd, charMatch,
62 
				score = 1,
63 
				locations = [];
64 
			if (bestLoc != -1) {
65 
				scoreThreshold = Math.min(match_bitapScore(0, bestLoc), scoreThreshold);
66 
				bestLoc = text.lastIndexOf(pattern, MATCH_LOCATION + patternLen);
67 
				if (bestLoc != -1) {
68 
					scoreThreshold = Math.min(match_bitapScore(0, bestLoc), scoreThreshold);
69 
				}
70 
			}
71 
			bestLoc = -1;
72 
			for (i = 0; i < patternLen; i++) {
73 
				binMin = 0;
74 
				binMid = binMax;
75 
				while (binMin < binMid) {
76 
					if (match_bitapScore(i, MATCH_LOCATION + binMid) <= scoreThreshold) {
77 
						binMin = binMid;
78 
					} else {
79 
						binMax = binMid;
80 
					}
81 
					binMid = Math.floor((binMax - binMin) / 2 + binMin);
82 
				}
83 
				binMax = binMid;
84 
				start = Math.max(1, MATCH_LOCATION - binMid + 1);
85 
				finish = Math.min(MATCH_LOCATION + binMid, textLen) + patternLen;
86 
				rd = Array(finish + 2);
87 
				rd[finish + 1] = (1 << i) - 1;
88 
				for (j = finish; j >= start; j--) {
89 
					charMatch = pattern_alphabet[text.charAt(j - 1)];
90 
					if (i === 0) {
91 
						rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;
92 
					} else {
93 
						rd[j] = ((rd[j + 1] << 1) | 1) & charMatch | (((lastRd[j + 1] | lastRd[j]) << 1) | 1) | lastRd[j + 1];
94 
					}
95 
					if (rd[j] & matchmask) {
96 
						score = match_bitapScore(i, j - 1);
97 
						if (score <= scoreThreshold) {
98 
							scoreThreshold = score;
99 
							bestLoc = j - 1;
100 
							locations.push(bestLoc);
101 
							if (bestLoc > MATCH_LOCATION) {
102 
								start = Math.max(1, 2 * MATCH_LOCATION - bestLoc);
103 
							} else {
104 
								break;
105 
							}
106 
						}
107 
					}
108 
				}
109 
				if (match_bitapScore(i + 1, MATCH_LOCATION) > scoreThreshold) {
110 
					break;
111 
				}
112 
				lastRd = rd;
113 
			}
114 
			return {
115 
				isMatch: bestLoc >= 0,
116 
				score: score
117 
			};
118 
		};
119 
		return txt === true ? { 'search' : search } : search(txt);
120 
	};
121 
})(jQuery);