Can you use ta jodatime DateTime List with a binary search?

Question

I have a list of holiday objects which include a jodatime DateTime field. This list is manually ordered from the earliest date to the latest date.

I would like to use a binary search to search for a match. I implemented a comparator, but the algorithm doesn't seem to go in the right direction. Are jodatime DateTimes not amenable to binary searches or is there something else I need to do get this working?

Note that I am using the Collections.binarySearch tool and following this example: http://java2novice.com/java-collections-and-util/collections/binary-search/

Here is the search output:

Date 1:
2015-02-16T00:00:00.000-08:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2016-10-10T00:00:00.000-07:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2017-03-31T00:00:00.000-07:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2017-10-12T00:00:00.000-07:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2017-11-23T00:00:00.000-08:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2017-11-24T00:00:00.000-08:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
Date 1:
2017-12-25T00:00:00.000-08:00
Target date:
2014-12-25T00:00:00.000-08:00
no match
-71

Comparator:

 class HolidayComparator implements Comparator<Holiday> {
        public int compare(Holiday h1, Holiday h2) {
            System.out.println("Date 1:");
            System.out.println(h1.getDate());
            System.out.println("Target date:");
            System.out.println(h2.getDate());
            if(h1.getDate().equals(h2.getDate())) {
                return 0;
            }
            else {
                System.out.println("no match");
                return -1;
            }
        }
    };

Adding some other classes:

public static List<Holiday> getAllHolidays() {
    return allHolidays;
}

Holiday object:

public static class Holiday {
    DateTime date;
    String name;

    Holiday(int i, int j, int k, String x) {
        date = new DateTime (i, j, k, 0, 0);
        name = x;
    }

    public DateTime getDate() {
        return date;
    }
}

List:

private static List<Holiday> allHolidays = Arrays.asList(new Holiday(2012, 12, 25, "Christmas 2012"), etc.)

Binary search:

int index = Collections.binarySearch(Holidays.getAllHolidays(), new Holidays.Holiday(2014, 12, 25, null));

Returns:

The method binarySearch(List<? extends Comparable<? super T>>, T) in the type Collections is not applicable for the arguments (List<Holidays.Holiday>, Holidays.Holiday)

possible duplicate of [How to sort a List of objects by their date (java collections, List — Joe, Mar 23 '14 at 05:06
@Joe do I have to sort the list when it is manually put in order? — CarbonandH20, Mar 23 '14 at 05:09

Erwin Bolwidt · Accepted Answer · 2014-03-23T05:35:53.970

The JodaTime DateTime class implements the Comparable interface itself, so you don't need to implement a Comparator.

Rather, use Collections.binarySearch with just 2 arguments: list and key.

There may be a mistake in your implementation of the Comparator, and if you post it, we may be able to identify it.

However your question was whether it is possible to use DateTime in a binary search, and the answer is: yes. Let the built-in DateTime.compareTo function (implemented in superclass AbstractInstant) do its work.

Addendum

As your code shows, you're not directly comparing DateTime objects, but you're comparing Holiday objects using your HolidayComparator.

The Javadoc of the class Comparator describes what the compare method should return:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Your method only returns 0 if the objects are equal and -1 if they are not. That's incorrect and it confuses the Collections.binarySearch method.

Try this instead:

class HolidayComparator implements Comparator<Holiday> {
    public int compare(Holiday h1, Holiday h2) {
        return h1.getDate().compareTo(h2.getDate());
    }
}

That is the best way to do it, because it re-uses existing code in JodaTime and it doesn't make you depend on its internals. To make it nicer, you should add checks for null though, if you can ever have a null value in your list of Holidays, or if you ever have a null date in one of the Holiday objects.

If you want to look more to the internals: the compareTo method in DateTime (superclass AbstractInstant) actually compares the result of the method getMillis(), so an alternative way of writing this is:

public int compare(Holiday h1, Holiday h2) {
    long millis1 = h1.getDate().getMillis();
    long millis2 = h2.getDate().getMillis();
    return Long.compare(millis1, millis2);
}

And Long.compare is implemented as:

Long.compare:

public static int compare(long x, long y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

Thanks. When I run it with two arguments, I get an eclipse error. (Added to original post). — CarbonandH20, Mar 23 '14 at 05:16
Added more information to the answer in response to your addition — Erwin Bolwidt, Mar 23 '14 at 05:36
Thanks for the very comprehensive answer! It works. So is this still a situation where I can use only two arguments for Collections.binarySearch or do you need a Comparator to use JodaTime's camparison code? Returning less than or greater than makes sense for the algorithm to work, but it makes me wonder how the example (also added to post) works. — CarbonandH20, Mar 23 '14 at 05:46
You can choose either. You can also make your Holiday class comparable: `class Holiday implements Comparable` and implement a `compareTo` method using the code that is now in the `HolidayComparator`. I would do that, because it is easier to use. Comparators are useful when you want an ordering that is different than the normal ordering for the class. Example: if you wanted to sort DateTime objects by the day of the week, then it would be good to implement a new Comparator. — Erwin Bolwidt, Mar 23 '14 at 05:49
Hopefully I'm not pushing my luck, but what would be a smart way to make this comparison without having to pass the "null" to Holiday so that I could directly compare the DateTimes in Holiday to the DateTimes that my user will give me? Create a new array from Holidays that removes the name field? (Or maybe the cost of passing nulls isn't a big deal?) — CarbonandH20, Mar 23 '14 at 06:31

score 1 · Answer 2 · answered Mar 23 '14 at 05:31

Based on your updated code, `Holiday isn't comparable, so you can't use

int index = Collections.binarySearch(Holidays.getAllHolidays(), new Holidays.Holiday(2014, 12, 25, null));

Instead, you changed your HolidayComparator to use DateTime's inbuilt comparability, for example...

class HolidayComparator implements Comparator<Holiday> {
    public int compare(Holiday h1, Holiday h2) {
        return h1.getDate().compareTo(h2.getDate());
    }
};

You should be able to use Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

Can you use ta jodatime DateTime List with a binary search?

2 Answers2