How to get top N items in Java

This article also covers how to write an efficient and yet genric comparator in Java.

Use case: You have to write a program to add elements to a collection and return top N items.

For e.g. let’s say the program is running for days and continuously elements are getting fed to the data-structure (the collection). The elements can have random values with no particular order. At any point of time if asked the program would return only the top 1000 records.

Let’s get to the solution…

The basic interface as the blue print of the idea.

import java.util.Collection;

public interface TopNItems<T> {
    void add(T element);
    Collection<T> getTop();
}

As we do not know the specific data type the elements to be stored, we have made the interface to be generic TopNItems<T>

How do we implement this interface?

To store the elements we need a collection which supports sorting.

As the order of adding items doesn’t matter we can use a Set to hold the elements. The sorted implementation of Set is TreeSet. Let’s use it.

Also, to have the limit of data be configurable we would be using an Integer variable.

import java.util.Collection;
import java.util.TreeSet;

public class MyCollection<T> implements TopNItems<T> {
    private TreeSet<T> data;
    private Integer limit;

    @Override
    public void add(T element) {
        //TODO: write logic of adding element
    }

    @Override
    public Collection<T> getTop() {
        //TODO: write logic of getting top elements
        return null;
    }
}

So, we have a solid class which implements our interface TopNItems<T>. It has all the data structures needed to hold data and set limit but has no logic written in the overriden method bodies yet.

Let’s modify our class to have a constructor so that we can set the value of limit when we create an object of the class: MyCollection.

Now our class looks like this:

import java.util.Collection;
import java.util.TreeSet;

public class MyCollection<T> implements TopNItems<T> {
    private TreeSet<T> data;
    private Integer limit;

    public MyCollection(Integer limit) {
        this.limit = limit;
    }

    @Override
    public void add(T element) {
        //TODO: write logic of adding element
    }

    @Override
    public Collection<T> getTop() {
        //TODO: write logic of getting top elements
        return null;
    }
}

As we are using a TreeSet to hold the elements, we expect the data to be sorted whenever we add items to it.

We do not need items which are beyond the limit of the class. So, while adding elemets to the TreeSet we would be checking the size of the collection and remove items exceeding the desired count(limit).

So, the add() method can look like this:

@Override
public void add(T element) {
    data.add(element);
    if (data.size() > limit) {
        data.remove(data.last());
    }
}

The above method makes sure that there would not be any elements above the supported limit.

As we are taking care of managing the size of the collection while adding elements the getTop() method can be as simple as just returning the data.

@Override
public Collection<T> getTop() {
    return data;
}

Till now the class MyCollection looks like this:

import java.util.Collection;
import java.util.TreeSet;

public class MyCollection<T> implements TopNItems<T> {
    private TreeSet<T> data;
    private Integer limit;

    public MyCollection(Integer limit) {
        this.limit = limit;
    }

    @Override
    public void add(T element) {
        data.add(element);
        if (data.size() > limit) {
            data.remove(data.last());
        }
    }

    @Override
    public Collection<T> getTop() {
        return data;
    }
}

If the data type of the elements in the collection were just numbers the TreeSet data-structure would have been happy to sort them on the fly. But as we are dealing with generic type of data, how would the TreeSet know how to sort the elements?

We must create a Comparator which supports comparing generic items. For objects to be used in comparing the type of the object must extend the Comparable class.

import java.util.Comparator;

public class GenericComparator<T extends Comparable<T>> implements Comparator<T> {

    @Override
    public int compare(T o1, T o2) {        
        return o1.compareTo(o2);
    }
}

The GenericComparator class supports comparing objects which are instances of classes that extends Comparable.

You might ask why T extends Comparable? Why not implements Comparable?

Please keep in mind that in the context of writting generic class the keyword extends is used in a generic sense to denote either extends (as in classes) or implements (as in interfaces).

How about making our comparator class to support reverse order as well?

import java.util.Comparator;

public class MyComparator<T extends Comparable<T>> implements Comparator<T> {
    private Boolean isReversed;

    public GenericComparator() {
        this.isReversed = Boolean.FALSE;
    }

    public GenericComparator(Boolean isReversed) {
        this.isReversed = isReversed;
    }

    @Override
    public int compare(T o1, T o2) {

        if (isReversed) {
            int result = o1.compareTo(o2);
            if (result != 0) {
                //Negating the compare value
                return -result;
            }
        }

        return o1.compareTo(o2);
    }
}

Now that our comparator class is ready let’s use it in the MyCollection class.

import java.util.Collection;
import java.util.TreeSet;

public class MyCollection<T> implements TopNItems<T> {

    private TreeSet<T> data;
    private Integer limit;

    public MyCollection(GenericComparator comparator, Integer limit) {
        this.data = new TreeSet<>(comparator);
        this.limit = limit;
    }

    @Override
    public void add(T element) {
        data.add(element);
        if (data.size() > limit) {
            data.remove(data.last());
        }
    }

    @Override
    public Collection<T> getTop() {
        return data;
    }

}

Our custom collection class is ready to hold limited data that too in a sorted way. Lets test the class!

public class Main {

    public static void main(String[] args) {
        TopNItems<Double> numbers = new CollectionWithGenericComparator<>(new GenericComparator(), 4);
        numbers.add(78.0);
        numbers.add(50.55);
        numbers.add(14.85);
        numbers.add(24.13);
        numbers.add(50.89);

        System.out.println(numbers.getTop());

        TopNItems<String> names = new CollectionWithGenericComparator<>(new GenericComparator(Boolean.TRUE), 4);
        names.add("Thor");
        names.add("Hulk");
        names.add("Iron Man");
        names.add("Black Widow");
        names.add("Captain");
        names.add("Hawk Eye");
        names.add("Loki");

        System.out.println(names.getTop());

    }

}

The above program prints results like this:

Congratulations! We have learnt how to write a generic comparator in Java.

All the wrapper classes (Boolean, Byte, Character, Double, Float, Integer, Long, Short), BigDeciml and String etc. already implements Comparable. If we want to make use of more complex and custom classes we need to implement them from the Comparable interfcae before using in the above solution.