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)

Answer 1

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);
}

Answer 2

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)