index.js

const naive_search_index = [];

for (let folder of folders) {
    naive_search_index.push({
        name: folder.title.toLowerCase(),
        id: string_id_to_number(folder.id)
    });
}

function search_naive(query, index) {
    const query_lowercase = query.toLowerCase();
    const result = [];

    for (let folder of index) {
        if (folder.name.indexOf(query_lowercase) !== -1) {
            result.push(folder);
        }
    }

    return result;
}

const search_index = {};
const search_index_size = {};

for (let folder of naive_search_index) {
    const name = folder.name.toLowerCase();
    const unique_characters = String.prototype.concat(...new Set(name));

    for (let character of unique_characters) {
        search_index[character] = search_index[character] || [];

        search_index[character].push(folder);
    }
}

for (let character of Object.keys(search_index)) {
    const folder_set = search_index[character];

    folder_set.sort((a, b) => a.id - b.id);

    search_index_size[character] = folder_set.length;
}

function search_sophisticated(query) {
    const query_lowercase = query.toLowerCase();
    const unique_characters = String.prototype.concat(...new Set(query_lowercase)).split("");

    unique_characters.sort((a, b) => (search_index_size[a] || 1) - (search_index_size[b] || 1));

    let current_set = null;
    // let i = 0;
    // let s = 0;

    for (let character of unique_characters) {
        const folder_set = search_index[character];

        if (!current_set) {
            current_set = folder_set;
            s = current_set.length;

            // if (true) {
            //    return search_naive(query_lowercase, current_set);
            // }
        } else {
            if (current_set.length <= 2000) {
                break;
            }

            const intersection = [];

            for (let index_a = 0, index_b = 0; index_a < current_set.length && index_b < folder_set.length;) {
                const id_a = current_set[index_a].id;
                const id_b = folder_set[index_b].id;

                if (id_a > id_b) {
                    index_b++;
                } else if (id_a < id_b) {
                    index_a++;
                } else {
                    intersection.push(current_set[index_a]);

                    index_a++;
                    index_b++;
                }
            }

            // console.log(character, "[" + folder_set.length + "]", "set delta", s - intersection.length);
            s = intersection.length;

            current_set = intersection;
        }

        i++;
    }

    // console.log("Intersected", i, "out of", unique_characters.length, "sets");

    return search_naive(query_lowercase, current_set);
}