4
\$\begingroup\$

Background

I am since a long time ago developing a JavaFX application for creating and analysing 'Mech loadouts for Mechwarrior Online.

I previously had a very crude search function based on a FilteredList and a big and complicated predicate. This proved to have many drawbacks, prefix hits were a pain to do and this made searching hard as you had to correctly spell long strings which weren't always obvious.

I have replaced the above implementation with an actual search index based on the Inverted Index approach.

As this is production code that depends on the core data structures of my application, I cannot give an easily runnable example. But if you want, you can fetch the source tree from github and run the tests with ./gradlew test and if you want, you can run the application with ./gradlew run, if you're using Windows cmd.exe, then change ./gradlew to gradlew.bat.

One comment on update(): I made a decision to simply rebuild the index if any of the documents got updated, I found it to be very hard to find which entries in the index matched to to the updated document as the old terms were not available any more to compare to (pointed to document had changed).

I store the full keyword (phrase?) because in the future I intend to support "match all words in this order in one attribute" syntax.

Source

Here is the implementation (github):

/*
 * @formatter:off
 * Li Song Mechlab - A 'mech building tool for PGI's MechWarrior: Online.
 * Copyright (C) 2013  Emily Björk
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
//@formatter:on
package org.lisoft.lsml.model.search;

import java.util.*;

import org.lisoft.lsml.model.chassi.Chassis;
import org.lisoft.lsml.model.item.Faction;
import org.lisoft.lsml.model.loadout.Loadout;
import org.lisoft.lsml.model.modifiers.Modifier;

/**
 * A search index that can be used for finding loadouts based on keywords
 *
 * @author Emily Björk
 */
public class SearchIndex {
    private final static String ALL_DOCUMENTS = "";
    private boolean dirty = false;
    private final Map<String, Set<Loadout>> invertedIndex = new HashMap<>();

    private void addPrefixes(Loadout aLoadout, String aKeyword) {
        if (null == aKeyword) {
            // These keywords will never be null in production but makes
            // setting up tests much easier.
            return;
        }
        if (aKeyword.contains(" ")) {
            for (final String part : aKeyword.split(" ")) {
                addPrefixes(aLoadout, part);
            }
        }
        String prefix = aKeyword.toLowerCase();
        while (!prefix.isEmpty()) {
            final Set<Loadout> documents = documentsByKey(prefix);
            documents.add(aLoadout);
            prefix = prefix.substring(0, prefix.length() - 1);
        }
    }

    private Set<Loadout> documentsByKey(String aKeyword) {
        return invertedIndex.computeIfAbsent(aKeyword, k -> new HashSet<>());
    }

    /**
     * Merges the given loadout into the search index.
     *
     * @param aLoadout
     *            A loadout to merge
     */
    public void merge(Loadout aLoadout) {
        documentsByKey(ALL_DOCUMENTS).add(aLoadout);

        addPrefixes(aLoadout, aLoadout.getName());

        final Chassis chassis = aLoadout.getChassis();
        addPrefixes(aLoadout, chassis.getSeriesName());
        addPrefixes(aLoadout, chassis.getShortName());
        addPrefixes(aLoadout, chassis.getName());
        addPrefixes(aLoadout, Integer.toString(chassis.getMassMax()) + "ton");
        addPrefixes(aLoadout, Integer.toString(chassis.getMassMax()) + " ton");

        final Faction faction = chassis.getFaction();
        addPrefixes(aLoadout, faction.getUiName());
        addPrefixes(aLoadout, faction.getUiShortName());

        for (final Modifier modifier : aLoadout.getAllModifiers()) {
            addPrefixes(aLoadout, modifier.getDescription().getUiName());
        }
    }

    /**
     * Queries the index for a search string. It will match substrings of the indexed document and it will be case
     * insensitive.
     *
     * @param aSearchString
     * @return A {@link Collection} of {@link Loadout}s.
     */
    public Collection<Loadout> query(String aSearchString) {
        if (dirty) {
            rebuild();
        }

        final List<Set<Loadout>> hits = new ArrayList<>();
        for (final String part : aSearchString.toLowerCase().split(" ")) {
            hits.add(invertedIndex.getOrDefault(part, Collections.EMPTY_SET));
        }
        hits.sort((l, r) -> l.size() - r.size());

        final Iterator<Set<Loadout>> it = hits.iterator();
        final Set<Loadout> ans = new HashSet<>(it.next());
        while (it.hasNext()) {
            ans.retainAll(it.next());
        }

        return ans;
    }

    /**
     * Rebuilds the search index to take updated documents changes into the index.
     */
    public void rebuild() {
        final Set<Loadout> documents = documentsByKey(ALL_DOCUMENTS);
        invertedIndex.clear();
        for (final Loadout document : documents) {
            merge(document);
        }
        dirty = false;
    }

    /**
     * Removes the given loadout from the search index.
     *
     * An index rebuild is automatically performed on the next query if it has not been forced before the query.
     *
     * @param aLoadout
     *            The {@link Loadout} to remove from the index.
     */
    public void unmerge(Loadout aLoadout) {
        documentsByKey(ALL_DOCUMENTS).remove(aLoadout);
        dirty = true;
    }

    /**
     * Call when a document has been changed. Will cause a reindexing of all documents on the next query.
     */
    public void update() {
        dirty = true;
    }
}

Here are the unit tests (github):

/*
 * @formatter:off
 * Li Song Mechlab - A 'mech building tool for PGI's MechWarrior: Online.
 * Copyright (C) 2013  Emily Björk
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
//@formatter:on
package org.lisoft.lsml.model.search;

import static org.junit.Assert.*;
import static org.mockito.Mockito.*;

import java.util.*;

import org.junit.Test;
import org.lisoft.lsml.model.chassi.Chassis;
import org.lisoft.lsml.model.item.Faction;
import org.lisoft.lsml.model.loadout.Loadout;
import org.lisoft.lsml.model.modifiers.*;

/**
 * Unit tests for {@link SearchIndex}.
 *
 * @author Emily Björk
 */
public class SearchIndexTest {
    private final SearchIndex cut = new SearchIndex();
    private final List<Modifier> modifiers = new ArrayList<>();

    private Loadout makeLoadout() {
        return makeLoadout(Faction.CLAN);
    }

    private Loadout makeLoadout(Faction aFaction) {
        final Loadout l = mock(Loadout.class);
        final Chassis c = mock(Chassis.class);
        when(l.getChassis()).thenReturn(c);
        when(l.getAllModifiers()).thenReturn(modifiers);
        when(c.getFaction()).thenReturn(aFaction);
        return l;
    }


    @Test
    public void testModifiers() {
        final ModifierDescription description = mock(ModifierDescription.class);
        final Modifier modifier = mock(Modifier.class);
        modifiers.add(modifier);
        when(modifier.getDescription()).thenReturn(description);
        when(description.getUiName()).thenReturn("ENERGY HEAT 5%");

        final Loadout l = makeLoadout();

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("ENERGY HEAT");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryAND() {
        final Loadout l1 = makeLoadout();
        when(l1.getName()).thenReturn("def abc");
        cut.merge(l1);

        final Loadout l2 = makeLoadout();
        when(l2.getName()).thenReturn("ghi abc");
        cut.merge(l2);

        final Collection<Loadout> ans = cut.query("abc ghi");
        assertFalse(ans.contains(l1));
        assertTrue(ans.contains(l2));
    }

    @Test
    public void testQueryByChassisMass() {
        final Loadout l = makeLoadout();
        when(l.getChassis().getMassMax()).thenReturn(95);

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("95ton");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByChassisMassSpace() {
        final Loadout l = makeLoadout();
        when(l.getChassis().getMassMax()).thenReturn(95);

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("95 ton");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByChassisName() {
        final Loadout l = makeLoadout();
        when(l.getChassis().getName()).thenReturn("ILYA MUROMETS");

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("ILYA MUROMETS");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByChassisSeries() {
        final Loadout l = makeLoadout();
        when(l.getChassis().getSeriesName()).thenReturn("SERIES");

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("SERIES");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByChassisShort() {
        final Loadout l = makeLoadout();
        when(l.getChassis().getShortName()).thenReturn("CPLT-K2");

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("CPLT-K2");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByFaction() {
        final Loadout l = makeLoadout(Faction.CLAN);

        cut.merge(l);
        final Collection<Loadout> ans = cut.query(Faction.CLAN.getUiName());

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByFactionShort() {
        final Loadout l = makeLoadout(Faction.INNERSPHERE);
        cut.merge(l);
        final Collection<Loadout> ans = cut.query(Faction.INNERSPHERE.getUiShortName());

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByName() {
        final Loadout l = makeLoadout();
        when(l.getName()).thenReturn("arbitrary string");

        cut.merge(l);
        final Collection<Loadout> ans = cut.query("arbitrary string");

        assertTrue(ans.contains(l));
        assertEquals(1, ans.size());
    }

    @Test
    public void testQueryByNameCaseInsensitive() {
        final Loadout l = makeLoadout();
        when(l.getName()).thenReturn("abc");

        cut.merge(l);

        final Collection<Loadout> ans = cut.query("AB");
        assertTrue(ans.contains(l));
    }

    @Test
    public void testQueryByNamePrefix() {
        final Loadout l = makeLoadout();
        when(l.getName()).thenReturn("abc");

        cut.merge(l);

        final Collection<Loadout> ans2 = cut.query("ab");
        assertTrue(ans2.contains(l));
        final Collection<Loadout> ans1 = cut.query("a");
        assertTrue(ans1.contains(l));
        final Collection<Loadout> ans0 = cut.query("");
        assertTrue(ans0.contains(l));
    }

    @Test
    public void testQueryMultipleHits() {
        final Loadout l1 = makeLoadout();
        when(l1.getName()).thenReturn("def abc");
        cut.merge(l1);

        final Loadout l2 = makeLoadout();
        when(l2.getName()).thenReturn("ghi abc");
        cut.merge(l2);

        final Collection<Loadout> ans = cut.query("abc");
        assertTrue(ans.contains(l1));
        assertTrue(ans.contains(l2));
    }

    /**
     * A bug caused the index to be modified on queries because the smallest document set for any keyword was used
     * directly without a copy when computing the intersection of all the document sets for the keywords.
     */
    @Test
    public void testQueryNoModifyIndex() {
        final Loadout l1 = makeLoadout();
        when(l1.getName()).thenReturn("x b");
        cut.merge(l1);

        final Loadout l2 = makeLoadout();
        when(l2.getName()).thenReturn("x y");
        cut.merge(l2);

        final Loadout l3 = makeLoadout();
        when(l3.getName()).thenReturn("a y");
        cut.merge(l3);

        cut.query("x y");
        cut.query("x b");
        cut.query("a y");
        assertEquals(2, cut.query("x").size());
        assertEquals(2, cut.query("y").size());
        assertEquals(1, cut.query("a").size());
        assertEquals(1, cut.query("b").size());
    }

    @Test
    public void testRebuildEmpty() {
        cut.rebuild();
        final Collection<Loadout> ans = cut.query("");
        assertTrue(ans.isEmpty());
    }

    @Test
    public void testUnmerge() {
        final Loadout l1 = makeLoadout();
        when(l1.getName()).thenReturn("def abc");
        cut.merge(l1);

        final Loadout l2 = makeLoadout();
        when(l2.getName()).thenReturn("ghi abc");
        cut.merge(l2);

        cut.unmerge(l2);

        final Collection<Loadout> ans = cut.query("abc ghi");
        assertTrue(ans.isEmpty());
    }

    @Test
    public void testUnmergeEmptyIndex() {
        final Loadout l2 = makeLoadout();
        when(l2.getName()).thenReturn("abc");
        cut.unmerge(l2);

        final Collection<Loadout> ans = cut.query("abc");
        assertTrue(ans.isEmpty());
    }

    @Test
    public void testUpdate() {
        final Loadout l = makeLoadout();
        when(l.getName()).thenReturn("nope").thenReturn("hello");
        cut.merge(l);
        cut.update();

        assertFalse(cut.query("nope").contains(l));
        assertTrue(cut.query("hello").contains(l));
    }
}
\$\endgroup\$
2
\$\begingroup\$

Production code

  1. In addPrefixes, my suggestions would be:

    • To split into smaller private sub-methods with hierarchy:

      addPrefixes -> //performs split by " "
         addPrefixesOfWord -> //divides word into prefixes
            addParticularKeyword //adds particular prefix
      

    Also I was wondering why your program continues execution even after:
    if (aKeyword.contains(" ")) {
    before reading your explanation
    It could be more clear if you just stated: addPrefixesOfWord(longKeyword) explicitely.

    • To replace while loop with for

  1. I have noticed that lot of people use some good practice along with C&QSP (or CQRS). They simply return immutable objects from their query methods (I mean documentsByKey in your particular case).

    In your code, to add new value into invertedIndex, you queried documentsByKey method and modified its result, which is a breach of this practice.

    To introduce it in my own project, I hid Map<String, Set<Loadout>> equivalent behind separate interface/class with two methods:

    • To associate new document with particular string keyword. (If you decide to apply my previous suggestions, the addParticularKeyword method would be just moved into that class.)
    • To get all documents associated with particular keyword.
  2. From the query method it is possible to extract two smaller private sub-methods:

    • Getting set of results for each keyword.
    • Finding common subset of all previously gathered sets.
  3. I'm wondering what is the reason of sort inside query. If it is a performance adjustment, I guess that simply choosing Set<Loadout> ans to be the smallest set will be even a little bit faster.

Unit tests

  1. I might be wrong, but I believe that tests like: testQueryAND or testQueryByNamePrefix or testQueryNoModifyIndex in particular could be divided into smaller independent test cases.

  2. You can split your suite into smaller classes in the same package anyway to maintain some hierarchy. My proposition would be:

    • Simple tests that provide some loadout seeded with custom data and test if are able to be found by query. (I suppose that in reality they test merge method)
    • More complex test cases which test scenarios, what happens when an entry is overwritten by another etc.
\$\endgroup\$
5
  • \$\begingroup\$ Can you clarify your second point? I haven't heard the acronym C&QSP before and a Google search doesn't really tell me what it is. The sort of a performance optimization the number of search terms is expected low so the sort is cheap. \$\endgroup\$ – Emily L. Dec 21 '18 at 17:49
  • \$\begingroup\$ @EmilyL. Added reference to wiki. It is even more broadly known as CQRS -sorry for that. \$\endgroup\$ – mpasko256 Dec 21 '18 at 17:58
  • \$\begingroup\$ Also here it is more easily and broadly explained: dzone.com/articles/cqrs-understanding-from-first-principles \$\endgroup\$ – mpasko256 Dec 21 '18 at 18:33
  • 1
    \$\begingroup\$ Oh so it's basically interface segregation based on if the method mutates state or not. I do something similar to this for my domain model using the command pattern. I don't think it makes sense in this case as it's application would likely introduce more problems than it solves. The class as it is is fairly straight forward and doesn't mutate any global state and all methods have well defined and expected side effects. \$\endgroup\$ – Emily L. Dec 21 '18 at 19:09
  • \$\begingroup\$ To clarify, I didn't mean to apply this pattern to whole class. As I see, your query method lazy-rebuilds index. For that reason, Command/Query segregation can be troublesome. Instead, I meant to introduce this pattern for index data structure as it would apply better! \$\endgroup\$ – mpasko256 Dec 21 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.