6
\$\begingroup\$

I have a search box for searching for people in a list of names. Here is the code that runs every time the query changes. I could not find anything open-sourced for this, so I wanted to make sure this looks good and efficient.

How does it look?

private final List<String> mTotalNames = ............ // some ArrayList<String> with all the names
private final List<String> mAvailableNames = new ArrayList<String>(mTotalNames);

private void doOnQueryTextChange(final String s) {
    mAvailableNames.clear();
    if (s.length() <= 0) {
        mAvailableNames.addAll(mTotalNames);
    } else {
        final String query = s.toLowerCase();
        for (String name : mTotalNames) {
            name = name.toLowerCase();
            final List<String> partNameList
                    = new LinkedList<String>(Arrays.asList(name.split("\\s+")));
            if (helper0(query, partNameList)) {
                mAvailableNames.add(user);
            }
        }
    }
    // yeah, out mAvailableNames is all updated
}

private static boolean helper0(final String query, final List<String> partNameList) {
    for (String partQuery : query.split("\\s+")) {
        if (!helper1(partQuery, partNameList)) {
            return false;
        }
    }
    return true;
}

private static boolean helper1(final String partQuery, final List<String> partNameList) {
    if (partQuery.trim().length() <= 0) return true;
    final Iterator<String> iterator = partNameList.iterator();
    while (iterator.hasNext()) {
        final String partName = iterator.next();
        if (partName.startsWith(partQuery)
                || partName.trim().length() <= 0) {
            iterator.remove();
            return true;
        }
    }
    return false;
}
\$\endgroup\$
5
\$\begingroup\$

Note: The concepts presented in this answer have been implemented in the following 'alternate' implementation in this question: Name Filtering using a Trie

Interesting problem. Your code is hard to read, not because it is unstructured, or messy, but because the helper function names are hard to grasp.... what do they do?

So, on the good side, your 'visual' style is consistent, and neat. All your lines are indented well, and braced, etc. Well, except for this line:

if (partQuery.trim().length() <= 0) return true;

Naming

The first issue is naming..... Four things:

  1. helper0 and helper1 .... do not help, despite the name.
  2. Not a big deal, it's probably a 'local rule', but it is unconventional to use 'prefixes' in Java for variable names. What does the m mean? mTotalNames should just be totalNames. You are using "Hungarian" notation of some sort, and that is not good practice in Java
  3. 'Part' is overloaded in too many places. partQuery, partName, partNameList, it becomes hard to remember which variables are which.
  4. iterator is a horrible name. We know it is an iterator, but what does it iterate?

Algorithm

This is a situation where the right data structure will help a lot. You are doing and repeating too much work. Consider this:

  1. you convert names to lower case often.
  2. you split names.... often.
  3. you get prefixes... often.

What you need is a better algorithm, and the right one, is to build a trie.

The trie will be indexed by the characters in the names. This will allow you to search for names in a very fast way, and not do any of the overhead processing repeatedly. Build the trie once, and then use it repeatedly when you type to filter the names.

Bug

Your code will not process things correctly for a certain subset of names/queries.

Consider the name "Andy Anderson", and the search query "And Andy".... this will not match, because the search query word 'And' will match against 'Andy' first, and then that leaves the search term 'Andy', which will not match against the word 'Anderson'.

You need to sort the search terms in decreasing-length order, and always search with the longest query term first.

Follow Up

This subject intrigues me, I may implement my recommended solution myself... in a day or so.

\$\endgroup\$
  • \$\begingroup\$ Wow, nice find there with the bug. Thanks for this. Also, the reason I use the "m" prefix is the Android convention for "member" variables. \$\endgroup\$ – Eric Cochran Dec 31 '14 at 20:22
2
\$\begingroup\$

A few to start with:

  • mFriendsList? Should it be mTotalNames.
  • This can be initialized to just new ArrayList<>(mTotalNames.size()); since you are already taking care of this in your function.

    private final List<String> mAvailableNames = new ArrayList<String>(mTotalNames);
    
  • Your helper functions ends up with the following results which seems erroneous

    Name List: {"Nightly Nexus", "You Next", "thepace"};
    Query String: y nex Your result: You Next.
    Expected: The whole name should start with the given string irrespective of the space or the whole name should contain the string irrespective of the name.`

  • Naming: Please add some value either in name or comments, former preferred, so that it imparts individuality to the funciton. Correct this: helper0, helper1.

  • Use StringUtils.isBlank() instead of this to check null, empty and blank query string:

    if (s.length() <= 0)
    
  • Collective overuse of collections:

    new LinkedList<String>(Arrays.asList(name.split("\\s+")));
    

    Link

\$\endgroup\$
  • \$\begingroup\$ Actually, that is the intended behavior. I guess I should ask the ux.stackexchange.com if that is good, though. I didn't know about the Apache StringUtils; cool, thanks. \$\endgroup\$ – Eric Cochran Dec 31 '14 at 5:35
  • \$\begingroup\$ So you mean it should return "You Next" even if the searched string is "Y Nex"? What if the list had "Next You"? \$\endgroup\$ – thepace Dec 31 '14 at 5:39
  • \$\begingroup\$ Yes, that is what I want for now. Also, is that overuse of Collections? Because, I later use the Iterator to remove from that LinkedList. \$\endgroup\$ – Eric Cochran Dec 31 '14 at 5:40
  • \$\begingroup\$ String.split returns a String array. Now you are converting it into a List. Later you are converting it into a Linked List. So in this process you have actually created 2 intermediate replica to get the third one. Correct me if I am wrong. \$\endgroup\$ – thepace Dec 31 '14 at 5:44
  • \$\begingroup\$ So, instead of Arrays.asList, I could just do addAll(splitStringArray). That would save the creation of one extra List. \$\endgroup\$ – Eric Cochran Dec 31 '14 at 5:47

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.