1
\$\begingroup\$

I have got a list of Users that I want to filter using text typed in TextView. I want it to be a smart filter, something like searching contacts in contact book on smartphones.
Based on example list of users I want it to work like this:

LIST = "Bob Dylan", "Mariah Carey", "Bob Ross", "Barrack Obama"

Then when I will type in filter TextView b (case insensitive) it will result Bob Dylan, Bob Ross, Barrack Obama as all of them contain b.
For bba it will return Bob Dylan and Barrack Obama as regardles of missing letters - bba appears in this order in these two options.
For mcy we would get Mariah Carey as it only matches her.

For the simplicity of the example I did not added to list a reversed LastName FirstName options, but this is the case in my code.

First of my attempts was to use regex. To create from typed text a regex expression which would work like I want - it wasn't hard to do, but I found it time consuming.

Here's a code I have used for regex filtering:

public static boolean matchesPattern(String string, String pattern)
{
    if (Objects.equals(pattern, ""))
    {
        return true;
    }
    string = string.toLowerCase();
    pattern = pattern.toLowerCase();
    String newPattern = ".*";
    for (int i = 0; i < pattern.length(); ++i)
    {
        newPattern += pattern.charAt(i) + ".*";
    }
    return Pattern.matches(newPattern, string);
}

public void filter(String pattern)
{
    filteredUsers.clear();
    long start1 = System.nanoTime();
    List<User> tmpList = new ArrayList<>();
    for (User user : allUsers)
    {
        String concatenated = StringUtils.stripAccents(user.getLastName()) + " ";
        concatenated += StringUtils.stripAccents(user.getFirstName());
        String concat = StringUtils.stripAccents(user.getFirstName()) + " ";
        concat += StringUtils.stripAccents(user.getLastName());

        if (Tools.matchesPattern(concatenated, pattern) || Tools.matchesPattern(concat, pattern))
        {
            tmpList.add(user);
        }
    }
    long end1 = System.nanoTime();
    long duration1 = end1 - start1;
    filteredUsers = tmpList;
    notifyDataSetChanged();
}

Second thought was to use a radix trie, from names create a tree with letters as nodes and search through these nodes for matching my typed text.

public class Trie
{
    private static class TrieNode
    {
        Map<Character, TrieNode> children = new HashMap<>();

        boolean isEndOfWord;
        Object key;
        Character letter;

        TrieNode(Character letter)
        {
            isEndOfWord = false;
            this.letter = letter;
        }

        private List<TrieNode> getAllLeaves()
        {
            List<TrieNode> tmpList = new ArrayList<>();
            if (isEndOfWord)
            {
                tmpList.add(this);
                return tmpList;
            }
            for (TrieNode child : this.children.values())
            {
                tmpList.addAll(child.getAllLeaves());
            }
            return tmpList;
        }
    }

    private TrieNode root = new TrieNode(null);

    public void insertUsers(List<User> userList)
    {
        for (User user : userList)
        {
            insert(user);
        }
    }

    public void insertAssets(List<Asset> assetList)
    {
        for (Asset asset : assetList)
        {
            insert(asset);
        }
    }

    private void insert(User user)
    {
        insert(StringUtils.stripAccents(user.getFirstName() + " " + user.getLastName()).toLowerCase(), user);
        insert(StringUtils.stripAccents(user.getLastName() + " " + user.getFirstName()).toLowerCase(), user);
    }

    private void insert(Asset asset)
    {
        insert(StringUtils.stripAccents(asset.getType() + " " + asset.getBarcode()).toLowerCase(), asset);
        insert(StringUtils.stripAccents(asset.getBarcode() + " " + asset.getType()).toLowerCase(), asset);
    }

    private void insert(String key, Object keyObj)
    {
        TrieNode currentNode = root;

        for (int i = 0; i < key.length(); ++i)
        {
            Character letter = key.charAt(i);
            //noinspection Java8CollectionsApi
            if (currentNode.children.get(letter) == null)
            {
                currentNode.children.put(letter, new TrieNode(letter));
            }

            currentNode = currentNode.children.get(letter);
        }
        currentNode.isEndOfWord = true;
        currentNode.key = keyObj;
    }

    private List<TrieNode> foundNodes = new ArrayList<>();

    private void checkNode(Character character, TrieNode node)
    {
        List<TrieNode> children = new ArrayList<>();
        children.addAll(node.children.values());
        TrieNode presentNode = node.children.get(character);
        if (presentNode != null)
        {
            foundNodes.add(presentNode);
            children.remove(presentNode);
        }

        for (TrieNode child : children)
        {
            checkNode(character, child);
        }
    }

    public List<Object> search(String key)
    {
        key = StringUtils.stripAccents(key).toLowerCase();
        foundNodes.clear();
        foundNodes.add(root);
        int length = key.length();
        List<TrieNode> currentNodes = new ArrayList<>();

        for (int i = 0; i < length; ++i)
        {
            currentNodes.clear();
            currentNodes.addAll(foundNodes);
            foundNodes.clear();
            for (TrieNode node : currentNodes)
            {
                checkNode(key.charAt(i), node);
            }
        }
        List<Object> tmpList = new ArrayList<>();
        for (TrieNode node : foundNodes)
        {
            for (TrieNode leaf : node.getAllLeaves())
            {
                tmpList.add(leaf.key);
            }
        }
        return tmpList;
    }
}

And use it:

public void filter(String pattern)
{
    filteredUsers.clear();
    long start2 = System.nanoTime();
    Trie trie = new Trie();
    trie.insertUsers(allUsers);
    List<User> result = (List<User>)(List<?>) trie.search(pattern);
    long end2 = System.nanoTime();

    long duration2 = end2 - start2;
    filteredUsers = result;
    notifyDataSetChanged();
}

After few tests (with 9 users) it came out that regex method is faster for less than 25 letters in 95%. For 25 and more letters radix method gain advantage over regex.

I believe there is something I can do with my radix code to improve optimization?


Edit 2017-10-12 14:00
It came out it is quicker than regex when I have moved Users inserting to Adapter constructor and in filter method I have left only searching. But I find this still taking too long. I have tested for 100 random users, and it takes approx 0.6 to 1.0 sec for 1-5 letters.

\$\endgroup\$
  • \$\begingroup\$ Anybody? please help \$\endgroup\$ – Marek Oct 12 '17 at 17:35

Your Answer

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

Browse other questions tagged or ask your own question.