Autocomplete Sorting

In the last chapter, we explored a particularly important and challenging-to-code subfeature of our autocompleter - grouping. Grouping is to simply combine related suggestions into a single unit, denoted by a grouped label.

As we learnt, grouping can be a pretty handy subfeature. It can drastically reduce the time required to find a given suggestion - just go to the group and search a suggestion from there.

In this chapter, we shall explore yet another such handy subfeature - sorting.

We'll specifically see how to sort all suggestions in ascending or descending order, and even how to sort group labels. In the end, we'll gather all these code bits and make them depend on a handful of global variables. This will in turn make sorting a matter of seconds.

So without wasting any more time, let's begin!

Sorting is to rearrange a given list such that all its underlying items are in increasing or decreasing, or equivalently, ascending or descending order.

In the case of our autocompleter, sorting can be applied to two things:

1. Suggestions
2. Groups labels

If suggestions are sorted, then they'll appear in ascending or descending order (whichever is chosen) in suggestionsBox. If group labels are sorted, then they'll appear ordered in whichever way is chosen in suggestionsBox.

Both suggestions and group labels can also be sorted together, in which cases each group label will be ordered and its underlying group of suggestions too.

For example, consider the autocompleter below. The list passed to it was ["JavaScript", "Dart", "HTML", "TypeScript"], however when suggestions are shown to us, they are in another order, specifically in ascending order.

Having understood what exactly does the term 'sorting' mean in the dictionary of autocomplete, as always it's now time to code it.

We'll start by solving a simple case of sorting, and then tackle more involved cases of it in our autocompleter.

The simple case is described as follows:

Start by thinking how to solve this simple problem; where exactly should the sorting logic go; should it before the block of code creating a native list or after it; and so on.

Well, since list in this case is simply an array of strings, we can directly sort it and then construct a native list out of it.

In other words, the sorting logic will go before the block of code creating a native list.

Consider the code below:

/* ... more code above */

if (groupBy) {
    /* ... */
}

// sort list
list.sort(function(a, b) {return a > b});

var nativeList = [];
function normaliseList() {
    /* ... */
}
normaliseList();

/* ... more code follows */

In line 8, we call sort() on list and pass it a function that sorts items in list in ascending order.

Live Example

Note that in the example above, there was no grouping applied in the autocompleter. What if we now want to group (according to the first character), as well as sort all items.

Can you figure out the solution to this problem?

What comes to the mind rightaway is that we first fill up groups as usual with all the group names and then sort the sublist of each group individually.

However, there is one better way than this.

Recall from the previous chapter, that our grouping code preserves the original order of items in list.

This means that if list is sorted in ascending (or descending) order before grouping is performed, then the sublists stored within groups will remain in that same order.

In terms of code this means that our old sort() call will come before the conditional block holding the grouping code:

/* ... more code above */

// sort list
list.sort(function(a, b) {return a > b});

if (groupBy) {
    /* ... */
}

var nativeList = [];
function normaliseList() {
    /* ... */
}
normaliseList();

/* ... more code follows */

In the example below, we group suggestions based on their initial character, and sort them in ascending order.

Live Example

Two problems solved, let's now consider another interesting problem - sorting group labels.

Suppose that in the second example above, where we grouped suggestions based on their initial characters, we want to sort the group labels in descending order. However, we want to keep each group's underlying suggestions in ascending order.

How will you approach this problem?

Since all the group names are represented by all the keys of the groups object, the solution to this problem is also pretty straightforward.

Consider the code below:

if (groupBy !== false) {
    /* ... */

    var keys = Object.keys(groups);
    keys.sort(function(a, b) {return a < b});

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

In line 4, we create a list of all the keys in groups (which was previously done inside the for loop's header in line 8) and then in line 5, sort this list in descending order.

Live Example

So uptil this point we know how to solve each case of sorting i.e sorting suggestion or sorting group labels or both.

However, what's still left is a consideration of the fact that list can be an array of objects in which case the sorting functions won't work.

Not only this, but we also need to have some way of specifying what type of sorting do we want for suggestions and/or group labels - ascending or descending.

Let's first tackle with the problem one.

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'}
]

With this list, the following statement won't work because the arguments a and b passed to the sort() method would be objects, not strings!

// won't work :(
list.sort(function(a, b) {return a > b});

What's the solution - our old itemPropName variable.

This leads to the following function for sorting suggestions in ascending order:

function sortSuggestionsInAsc(a, b) {
    if (itemPropName) return a[itemPropName] > b[itemPropName];
    return a > b;
}

For the descending order function, just replace the > (greater than) symbol with < (lesser than):

function sortSuggestionsInDesc(a, b) {
    if (itemPropName) return a[itemPropName] < b[itemPropName];
    return a < b;
}

Now just bring on whichever function you desire:

list.sort(sortSuggestionsInAsc);

Over to problem number two.

Just like we created a global groupBy variable in the previous chapter to specify whether we wanted to perform grouping or not, we'll do the same for sorting now.

The three possible values of either of these variables are as follows:

1. false - no sorting is desired
2. "asc" - sort in ascending order.
3. "desc" - sort in descending order.

Consider the following code, with demo values for the variables sortSuggestions and sortGroups:

var sortSuggestions = "asc",
     sortGroups = "desc";

/* ... */

if (sortSuggestions) {
    list.sort(sortSuggestions === "asc" ? sortSuggestionsInAsc : sortSuggestionsInDesc);
}
if (groupBy !== false) {
    /* ... */

    var keys = Object.keys(groups);
    if (sortGroups) {
        keys.sort(sortGroups === "asc" ? function(a, b) {return a > b} : function(a, b) {return a < b});
    }
    list = [];
    for (var k = 0; k < keys.length; k++) {
        list = list.concat(groups[keys[k]]);
    }
}

If sortSuggestions is truthy, we sort list based on the desired sorting type specified in sortSuggestions. Similarly, if sortGroups is truthy, we sort keys based on the desired sorting type specified in sortGroups.

Note that with sortGroups, in line 15, we don't use the functions sortSuggestionsInAsc and sortSuggestionsInDesc since we know for sure that keys is an array of strings and hence the comparison must be done between args a and b.

Let's test all this with the following configuration:

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 itemPropName = "chapter";
     groupBy = "unit";

Here we sort suggestions in ascending order and groups in descending order:

var sortSuggestions = "asc",
     sortGroups = "desc";

Live Example

Following we sort both suggestions and groups in descending order:

var sortSuggestions = "desc",
     sortGroups = "desc";

Live Example