Autocomplete Grouping

Just as its meaning implies, grouping in the world of autocompleters is to combine a bunch of related suggestions and put them under one group.

For instance, suppose that we have a list of food items to be processed by an autocompleter. An example of grouping applied here could be to put all beverages in one section, all salads in another, all sandwiches in another, and so on and so forth.

In some cases, grouping related suggestion can prove to be extremely helpful. For example, if we want to search for a beverage in a list of food items, with grouping in place, we would just need to scroll to the beverages section and select a beverage from there.

Similarly, if we were searching for universities offering computer science in an online form, we could simply go to the computer science group in a list of thousands of universities across the globe, and select our desired option from there.

Grouping surely is a useful feature to have in an autocompleter, where otherwise selecting suggestions could be a cumbersome task.

Before we begin the discussion on how to implement grouping in our autocomplete script, it would be worth a while for you to first try to code this subfeature on your own.

Try your level best and then continue on reading below; in this way you'll understand why exactly are things being done the way they are!

Assuming you've given a try, let's now decode this task together..

Starting with the most basic requirement, in order to group suggestions in an autocompleter, we only need to know which group does a suggestion lie in.

If we know this, we can simply iterate over all suggestions and place them in their respective groups, the moment a query is input in inputArea.

The main job here is to come with an algorithm that can record the respective group of each item in list. Although this is the main job, it ain't difficult at all in practice.

So how do you think can we figure out which suggestion belongs to which group? Well, we need a bit of preprocessing.

Once we've dumped all items into their respective groups, we then just need to unbox the containing object into a list.

This is useful because otherwise walking through this object of groups would be a strenous activity.

Consider the code below. Here we are assuming that the grouping is to be done according to the first character of each suggestion and that list is an array of strings, as shown:

var list = ["Pizza", "Pasta", "Donut", "Cake", "Cookie"];

var groups = {};

for (var i = 0, len = list.length; i < len; i++) {
    groupName = list[i].charAt().toLowerCase();

    // if group name doesn't exist, add it
    if (!groups[groupName]) {
        groups[groupName] = []
    }

    // push the list item into its respective group
    groups[groupName].push(list[i]);
}

The real hero over here is the object groups. Whenever a new group name is encountered i.e the name doesn't exist as a property of groups, it's made a property of groups with an array as its value, and the underlying suggestion pushed into this array.

In this way groups holds all sublists of list divided according to their groups.

At the end, every key of groups corresponds to a sublist of list, as illustrated below:

console.log(groups)

Now at this point, we finally need to join all these sublists sitting inside groups into one single list. This can be done extremely easily using the array concat() method.

All this is summed up as follows:

list = [];
for (var k = 0, keys = Object.keys(groups); k < keys.length; k++) {
    list = list.concat(groups[keys[k]]);
}

Inspecting list after this code gets executed, we see that it has been rearranged such that every suggestion of a given group lies next to one another.

The next job is to perform a couple of changes inside the onkeyup handler, precisely within the for loop to create <li> items for groups as well.

Since this tutorial aims at teaching you autocomplete, not just showing its code snippets to you, we'll first give you the task to make a log each time the group name changes while iterating over list in the for loop.

For example, given list = ["Parrot", "Dog", "Cat"] the logs should be "p", "d" and "c".

You may create new variables, lay out additional if checks to accomplish this. Once you've done your part, continue on reading below.

Recall that after executing the code laid out in the sections above, list is rearranged so that each item of a group is next to an item of the same group or another group. No item of a given group is disconnected with other items of the same group.

This means that whenever, while iterating over list, we encounter an item with a group name different than the one we knew previously, we have entered another group and so we should create a group label.

The group label is basically a visual representation of a grouped section of suggestions. We'll create it using an <li> element of class .group.

inputArea.onkeyup = function(e) {
    /* ... */
    var prevGroupName = '', g = '';

    for (var i = 0; i < list.length; i++) {
        if (nativeList[i].toLowerCase().indexOf(q.toLowerCase()) !== -1) {

            // check whether grouping is desired
            if (groups.length !== 0) {
                g = list[i].charAt().toLowerCase();
                if (g !== prevGroupName) {
                    prevGroupName = g; // point to the new group
                    suggestions.push('<li class="group">' + c.toUpperCase() + '</li>')
                }
            }

            suggestions.push('<li class="suggestion" data-index="' + i + '">' + processSuggestion(list[i]) + '</li>');
        }
    }
    
    /* ... */
}

Take all your focus over lines 9 - 15.

First we check whether grouping is desired, in line 9, using groups.length !== 0.

If yes, then we further check if the group name g of the current item is different than the previously known group name, saved in the global variable prevGroupName. If it's different, this means that the current item is from a new group and so we must first create its group label.

The group label is created in line 13, by putting the group name in an <li> element of class .group. To distinguish group labels from suggestions, we'll give the class .group a different CSS style:

.group {
    color: #ccc;
    padding: 10px;
    font-weight: 900
}

And to prevent :hover style changes on group labels, we'll modify our old li:hover rule to .suggestion:hover, to take into account only suggestions:

.suggestion:hover {
    background-color: orange
}

Having coded a lot, an autocompleter with grouped suggestions awaits us.

Live Example

As with all the subfeatures we've been developing so far, grouping messes around with other sub features of our autocompleter.

Revisit the link above, and try to figure out the affected subfeatures.

Grouping has messed around with arrow navigation, as well as suggestion selection.

The rectification of this is superbly easy - change the value of suggestionElements to point to only the suggestions:

inputArea.onkeyup = function(e) {
    /* ... */

    if (suggestions.length === 0) {
        suggestionsBox.innerHTML = "<div>No results found!</div>";
    }
    else {
        suggestionsBox.innerHTML = '<ul>' + suggestions.join('') + '</ul>';
        suggestionElements = suggestionsBox.getElementsByClassName("suggestion");
        lastSuggestionIndex = suggestionElements.length - 1;
        sIndex = -1;
    }

    /* ... */
}

Isn't this easy?

Talking about suggestion selection, the moment we click a group label, some change happens in inputArea that's undesirable.

The rectification of this is also pretty straightforward - change the if's condition inside suggestionsBox.onclick, that checks whether the click target is a suggestion or not.

suggestionsBox.onclick = function (e) {
    // if clicked on a suggestion, select it
    if (e.target.nodeName === "LI" && e.target.classList.contains("suggestion")) {
        selectSuggestion(e.target);
    }
}

Both rectifications being made, now our grouping works harmoniously.

Live Example

In the sections above we grouped items in list based on their initial characters. What if we want to change this?

What if we have a different list and want to group items based on some other thing. Suppose that list is as shown below:

var list = [
    {chapter: 'Variables', unit: 'Basics'},
    {chapter: 'Data Types', unit: 'Basics'},
    {chapter: 'Input and Output', unit: 'Basics'},
    {chapter: 'Constants', unit: 'Basics'},
    {chapter: 'Comments', unit: 'Basics'},
    {chapter: 'Prototypes', unit: 'Objects'},
    {chapter: 'Constructors', unit: 'Objects'},
    {chapter: 'Getters and Setters', unit: 'Objects'},
    {chapter: 'Inheritance', unit: 'Objects'},
    {chapter: 'Offsets', unit: 'Dimensions'},
    {chapter: 'Bounding Boxes', unit: 'Dimensions'},
    {chapter: 'Viewport', unit: 'Dimensions'}
]

Let's say we want to group all items based on their unit.

To accomplish this we only need to change the following two highlighted statements:

for (var i = 0, len = list.length; i < len; i++) {
    groupName = list[i].unit;

    if (!groups[groupName]) {
        groups[groupName] = []
    }

    groups[groupName].push(list[i]);
}

inputArea.onkeyup = function(e) {
    /* ... */

    for (var i = 0; i < list.length; i++) {
        if (nativeList[i].toLowerCase().indexOf(q.toLowerCase()) !== -1) {

            if (groups.length !== 0) {
                g = list[i].unit;
                if (g !== prevGroupName) {
                    prevGroupName = g;
                    suggestions.push('<li class="group">' + c.toUpperCase() + '</li>')
                }
            }
            
            /* ... */
        }
    }
    
    /* ... */
}

In both these statements we try to deduce the group name of given item of list.

Noting that these statements will always be exactly the same, we can instead create a function, put the statement within it, and invoke the function in place of these statements.

We'll call the function getGroupName(), as it takes in a list item and returns its group name.

function getGroupName(item) {
    return item[i].unit;
}

for (var i = 0, len = list.length; i < len; i++) {
    groupName = getGroupName(list[i]);

    if (!groups[groupName]) {
        groups[groupName] = []
    }

    groups[groupName].push(list[i]);
}

inputArea.onkeyup = function(e) {
    /* ... */

    for (var i = 0; i < list.length; i++) {
        if (nativeList[i].toLowerCase().indexOf(q.toLowerCase()) !== -1) {

            if (groups.length !== 0) {
                g = getGroupName(list[i]);
                if (g !== prevGroupName) {
                    prevGroupName = g;
                    suggestions.push('<li class="group">' + c.toUpperCase() + '</li>')
                }
            }
            
            /* ... */
        }
    }
    
    /* ... */
}

Now that we've created a function that can figure out the group of a given suggestion, why not rephrase it in such a way that we only need to specify the type of grouping we wish for, and in turn the function figures out group names accordingly.

This will make our code really flexible - just change one thing and get everything else to adapt likewise.

To start with, we'll create a variable groupBy that specifies whether grouping should be done or not.

1. If groupBy is false, grouping isn't desired.
2. If it's equal to 0, then grouping should be done according to the initial character of each suggestion.
3. If it's some string, then grouping should be done according to that property name.

For instance, in the sections above where we grouped items based on their initial characters, groupBy would be equal to 0. Similarly, in the code above where we grouped items based on their unit property, groupBy would be equal to "unit".

Apart from in getGroupName(), we'll use groupBy in two places:

1. In checking whether or not to perform the processing of list
2. In place of our old groups.length !== 0 expression

Both these places are illustrated below:

if (groupBy !== false) {
    for (var i = 0, len = list.length; i < len; i++) {
        groupName = getGroupName(list[i]);

        if (!groups[groupName]) {
            groups[groupName] = []
        }

        groups[groupName].push(list[i]);
    }

    list = [];
    for (var k = 0, keys = Object.keys(groups); k < keys.length; k++) {
        list = list.concat(groups[keys[k]]);
    }
}

inputArea.onkeyup = function(e) {
    /* ... */

    for (var i = 0; i < list.length; i++) {
        if (nativeList[i].toLowerCase().indexOf(q.toLowerCase()) !== -1) {

            if (groupBy !== false) {
                g = getGroupName(list[i]);
                if (g !== prevGroupName) {
                    prevGroupName = g;
                    suggestions.push('<li class="group">' + c.toUpperCase() + '</li>')
                }
            }
            
            /* ... */
        }
    }
    
    /* ... */
}

Let's now pay attention to getGroupName().

Given groupBy, the function getGroupName() will read its value, and use it to ultimately figure out the group name of a given item.

Consider the following definition of getGroupName():

function getGroupName(item) {
    if (groupBy === 0) {
        return itemPropName ? item[itemPropName].charAt().toLowerCase() : item.charAt().toLowerCase();
    }
    else {
        return item[groupBy];
    }
}

If groupBy is 0, the function will return the first character of list[itemPropName] if itemPropName is set, or else the first character of list. Otherwise, the function returns the value of the item's [groupBy] property.

Once we put all this code in action, we only need to change groupBy depending on the value of list and all the grouping logic will adapt to it.

An example follows:

var list = [
    {chapter: 'Variables', unit: 'Basics'},
    {chapter: 'Data Types', unit: 'Basics'},
    {chapter: 'Input and Output', unit: 'Basics'},
    {chapter: 'Constants', unit: 'Basics'},
    {chapter: 'Comments', unit: 'Basics'},
    {chapter: 'Prototypes', unit: 'Objects'},
    {chapter: 'Constructors', unit: 'Objects'},
    {chapter: 'Getters and Setters', unit: 'Objects'},
    {chapter: 'Inheritance', unit: 'Objects'},
    {chapter: 'Offsets', unit: 'Dimensions'},
    {chapter: 'Bounding Boxes', unit: 'Dimensions'},
    {chapter: 'Viewport', unit: 'Dimensions'}
]

var groupBy = "unit";

Live Example