[gi-docgen: 1/10] feat: add fzy.js
- From: Emmanuele Bassi <ebassi src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gi-docgen: 1/10] feat: add fzy.js
- Date: Fri, 9 Apr 2021 18:19:37 +0000 (UTC)
commit e93b512ec887281271224f82df8c8577f0d60afd
Author: Rom Grk <romgrk cc gmail com>
Date: Thu Apr 1 00:07:24 2021 -0400
feat: add fzy.js
gidocgen/templates/basic/base.html | 1 +
gidocgen/templates/basic/basic.toml | 1 +
gidocgen/templates/basic/fzy.js | 241 ++++++++++++++++++++++++++++++++++++
3 files changed, 243 insertions(+)
---
diff --git a/gidocgen/templates/basic/base.html b/gidocgen/templates/basic/base.html
index 4861059..ca3d3cb 100644
--- a/gidocgen/templates/basic/base.html
+++ b/gidocgen/templates/basic/base.html
@@ -83,6 +83,7 @@ SPDX-License-Identifier: Apache-2.0 OR GPL-3.0-or-later
<section id="search" class="content hidden"></section>
{% if CONFIG.search_index %}
+ <script src="fzy.js"></script>
<script src="search.js"></script>
{% endif %}
diff --git a/gidocgen/templates/basic/basic.toml b/gidocgen/templates/basic/basic.toml
index 0937194..35bf168 100644
--- a/gidocgen/templates/basic/basic.toml
+++ b/gidocgen/templates/basic/basic.toml
@@ -36,6 +36,7 @@ style = "style.css"
[extra_files]
files = [
"main.js",
+ "fzy.js",
"search.js",
"stemmer.js",
"pygment.css",
diff --git a/gidocgen/templates/basic/fzy.js b/gidocgen/templates/basic/fzy.js
new file mode 100644
index 0000000..c7dd78f
--- /dev/null
+++ b/gidocgen/templates/basic/fzy.js
@@ -0,0 +1,241 @@
+/* The MIT License (MIT)
+ *
+ * Copyright (c) 2014 John Hawthorn
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+window.fzy = (function() {
+ var SCORE_MIN = -Infinity;
+ var SCORE_MAX = Infinity;
+
+ var SCORE_GAP_LEADING = -0.005
+ var SCORE_GAP_TRAILING = -0.005
+ var SCORE_GAP_INNER = -0.01
+ var SCORE_MATCH_CONSECUTIVE = 1.0
+ var SCORE_MATCH_SLASH = 0.9
+ var SCORE_MATCH_WORD = 0.8
+ var SCORE_MATCH_CAPITAL = 0.7
+ var SCORE_MATCH_DOT = 0.6
+
+ function islower(s) {
+ return s.toLowerCase() === s;
+ }
+
+ function isupper(s) {
+ return s.toUpperCase() === s;
+ }
+
+ function precompute_bonus(haystack) {
+ /* Which positions are beginning of words */
+ var m = haystack.length;
+ var match_bonus = new Array(m);
+
+ var last_ch = '/';
+ for (var i = 0; i < m; i++) {
+ var ch = haystack[i];
+
+ if (last_ch === '/') {
+ match_bonus[i] = SCORE_MATCH_SLASH;
+ } else if (last_ch === '-' || last_ch === '_' || last_ch === ' ') {
+ match_bonus[i] = SCORE_MATCH_WORD;
+ } else if (last_ch === '.') {
+ match_bonus[i] = SCORE_MATCH_DOT;
+ } else if (islower(last_ch) && isupper(ch)) {
+ match_bonus[i] = SCORE_MATCH_CAPITAL;
+ } else {
+ match_bonus[i] = 0;
+ }
+
+ last_ch = ch;
+ }
+
+ return match_bonus;
+ }
+
+ function compute(needle, haystack, D, M) {
+ var n = needle.length;
+ var m = haystack.length;
+
+ var match_bonus = precompute_bonus(haystack, match_bonus);
+
+ /*
+ * D[][] Stores the best score for this position ending with a match.
+ * M[][] Stores the best possible score at this position.
+ */
+
+ for (var i = 0; i < n; i++) {
+ D[i] = new Array(m);
+ M[i] = new Array(m);
+
+ var prev_score = SCORE_MIN;
+ var gap_score = i === n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;
+
+ for (var j = 0; j < m; j++) {
+ if (needle[i] === haystack[j]) {
+ var score = SCORE_MIN;
+ if (!i) {
+ score = (j * SCORE_GAP_LEADING) + match_bonus[j];
+ } else if (j) { /* i > 0 && j > 0*/
+ score = Math.max(
+ M[i - 1][j - 1] + match_bonus[j],
+
+ /* consecutive match, doesn't stack with match_bonus */
+ D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE);
+ }
+ D[i][j] = score;
+ M[i][j] = prev_score = Math.max(score, prev_score + gap_score);
+ } else {
+ D[i][j] = SCORE_MIN;
+ M[i][j] = prev_score = prev_score + gap_score;
+ }
+ }
+ }
+ }
+
+ function score(needle, haystack) {
+ var n = needle.length;
+ var m = haystack.length;
+
+ if (!n || !m)
+ return SCORE_MIN;
+
+ if (n === m) {
+ /* Since this method can only be called with a haystack which
+ * matches needle. If the lengths of the strings are equal the
+ * strings themselves must also be equal (ignoring case).
+ */
+ return SCORE_MAX;
+ }
+
+ if (m > 1024) {
+ /*
+ * Unreasonably large candidate: return no score
+ * If it is a valid match it will still be returned, it will
+ * just be ranked below any reasonably sized candidates
+ */
+ return SCORE_MIN;
+ }
+
+ var D = new Array(n);
+ var M = new Array(n);
+
+ compute(needle, haystack, D, M)
+
+ return M[n - 1][m - 1];
+ }
+
+ function positions(needle, haystack) {
+ var n = needle.length;
+ var m = haystack.length;
+
+ var positions = new Array(n);
+
+ if (!n || !m)
+ return positions;
+
+ if (n === m) {
+ for (var i = 0; i < n; i++)
+ positions[i] = i;
+ return positions;
+ }
+
+ if (m > 1024) {
+ return positions;
+ }
+
+ var D = new Array(n);
+ var M = new Array(n);
+
+ compute(needle, haystack, D, M)
+
+ /* backtrack to find the positions of optimal matching */
+ var match_required = false;
+
+ for (var i = n - 1, j = m - 1; i >= 0; i--) {
+ for (; j >= 0; j--) {
+ /*
+ * There may be multiple paths which result in
+ * the optimal weight.
+ *
+ * For simplicity, we will pick the first one
+ * we encounter, the latest in the candidate
+ * string.
+ */
+ if (D[i][j] !== SCORE_MIN &&
+ (match_required || D[i][j] === M[i][j])) {
+ /* If this score was determined using
+ * SCORE_MATCH_CONSECUTIVE, the
+ * previous character MUST be a match
+ */
+ match_required =
+ i && j &&
+ M[i][j] === D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE;
+ positions[i] = j--;
+ break;
+ }
+ }
+ }
+
+ return positions;
+ }
+
+ function hasMatch(needle, haystack) {
+ var l = needle.length
+ for (var i = 0, j = 0; i < l; i += 1) {
+ j = haystack.indexOf(needle[i], j) + 1
+ if (j === 0) return false
+ }
+ return true
+ }
+
+ function filter(needle, items, selector) {
+ const isCaseSensitive = needle.toLowerCase() !== needle;
+ const actualNeedle = isCaseSensitive ? needle : needle.toLowerCase();
+ const filteredItems = items.reduce((results, item) => {
+ const haystack = isCaseSensitive ? selector(item) : selector(item).toLowerCase();
+ if (hasMatch(actualNeedle, haystack))
+ results.push({ item, score: score(needle, haystack) })
+ return results;
+ }, [])
+ filteredItems.sort((a, b) => b.score - a.score)
+ return filteredItems;
+ }
+
+ return {
+ /* constants */
+ SCORE_MIN,
+ SCORE_MAX,
+
+ SCORE_GAP_LEADING,
+ SCORE_GAP_TRAILING,
+ SCORE_GAP_INNER,
+ SCORE_MATCH_CONSECUTIVE,
+ SCORE_MATCH_SLASH,
+ SCORE_MATCH_WORD,
+ SCORE_MATCH_CAPITAL,
+ SCORE_MATCH_DOT,
+
+ /* functions */
+ score,
+ positions,
+ hasMatch,
+ filter,
+ }
+})();
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]