Confused about sorting and searching list of objects by date range

I have a list of objects containing a date range (..and other props) ie

           |-(1) MyClass  (BeginDate=01/01/2005 EndDate=03/16/2005)
           |-(2) MyClass  (BeginDate=05/08/2005 EndDate=07/26/2005)
           |-(3) MyClass  (BeginDate=02/12/2006 EndDate=09/05/2006)
           |-(4) MyClass  (BeginDate=04/26/2007 EndDate=10/17/2007)

What is the best way to store these objects that will allow me to

          A) Search by date  ie A search for "08/17/2006" => would return:

                     (3) MyClass  (BeginDate=02/12/2006 EndDate=09/05/2006)

          B) Iterate through all objects by date range (both ascending
               and descending order)?

I thought about using a java.util.List with a  Comparator. But it seems like I would have to resort the list every time I wanted to switch from ascending to descending order. I also considered using a TreeSet, but I am unsure how to search it by date.

Any advice would be appreciated :)
LVL 53
_agx_Asked:
Who is Participating?
 
_agx_Connect With a Mentor Author Commented:
Right, but I need to perform both operations on a single collection:

      a) search by date range   <=== examines both dates
      b) sort by date                <=== only needs to examine beginDate

I don't think Comparable alone or NavigableSet can do that. Seems like I need to implement Comparable and have a custom Comparator to achieve both, correct?

          // pseudo code
          MyClass implements Comparable<MyClass>  {
              ... 
              public int compareTo(MyClass o) {
                 ...
                 return this.startDate.compareTo(o.getStartDate());
              }
          }

          MyCustomComparator implements Comparator {
              public int compare(MyClass obj, Calendar searchDate) {
                   ...
                   // range is later than the search date
                   if (obj.getBeginDate().after( searchDate )) {
                         return obj.getBeginDate().compareTo(searchDate);
                   }
                   // range is earlier than search date
                   else if (obj.getEndDate().before( searchDate )) {
                         return obj.getEndDate().compareTo(searchDate);
                   }
                   // search date falls within this range
                   else {
                        return 0; 
                   }
              }  
          }
/code]

So if used Comparable to sort the collection, can I still use the custom comparator with binarySearch? 

[code]
          List<MyClass> myCollection = ....;
          // ... populate 
          Collections.sort(myCollection);
          int foundAt = Collections.binarySearch(myCollection, calendar, new MyCustomComparator ());

Open in new window


Logically, it should work - and it certainly seems to in my tests. BUT .. the binarySearch docs say:
 
"...The list must be sorted into ascending order according to the specified comparator (as by the sort(List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined."

.. making this approach seem unreliable.  So the question is - is this approach sound, or do I just need to loop one by one?

Thoughts?
0
 
CEHJConnect With a Mentor Commented:
a.
boolean inRange = x.getBeginDate().before(val) && x.getEndDate().after(val); // (val of type Date)

Open in new window

b. that would depend on your criteria. Descending/Ascending order of beginDate?
0
 
_agx_Author Commented:
Yes, for b) it's by beginDate (the ranges won't overlap).   But I guess my real question is more about how to store them. I'm confused about the best way to store them so I can easily search AND switch back and forth between ascending and descending order.
0
Cloud Class® Course: Ruby Fundamentals

This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

 
CEHJConnect With a Mentor Commented:
Make the class Comparable by the preferred order of the two. Then use http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#reverseOrder() to get a Comparator that will give you reverse sorting
0
 
_agx_Author Commented:
Ok, so if I make it comparable then I can use a List or TreeSet. Is either one better/worse for this scenario?  

Say I used a TreeSet, how do you find objects within range of date X? I have used binarySearch with lists, but I do not quite understand how things works with TreeSets.
0
 
CEHJCommented:
Comparable is there for ordering. A Set is for containing unique objects so doesn't have much relevance to searching.

I would forget about the Collection type for the moment. Just implement as i mentioned above and then we can look further into your use case
0
 
_agx_Author Commented:
Yep, I understand sets are primarily designed for uniqueness. But that fits with my scenario (date ranges must be unique). Given that TreeSets are sorted (and added objects are automatically re-sorted) I'm just trying to understand if it would be simpler than rolling my own with a List. Edit or if it's just an unnecessary complication.  


         >  boolean inRange = x.getBeginDate().before(val) && 
         >    x.getEndDate().after(val); // (val of type Date)

I understand the date logic, but where would that be implemented? In a separate comparator ..?
0
 
CEHJCommented:
We're going to have to thin this out as there are too many (potentially complicating, mutually exclusive etc) factors involved at present. Let's get back to your basic use case:

'Search to see if a certain date is in a certain object's date range attribute(s)'

Correct?
0
 
_agx_Author Commented:
Right, but by that I mean search my collection of objects to find the one that matches the supplied date.  Using the original example, if this is the collection of objects:

     |-(1) MyClass  (BeginDate=01/01/2005 EndDate=03/16/2005)
     |-(2) MyClass  (BeginDate=05/08/2005 EndDate=07/26/2005)
     |-(3) MyClass  (BeginDate=02/12/2006 EndDate=09/05/2006)
     |-(4) MyClass  (BeginDate=04/26/2007 EndDate=10/17/2007)

Searching for "08/17/2006" => would return:

     (3) MyClass  (BeginDate=02/12/2006 EndDate=09/05/2006)

...because "08/17/2006"  falls within the object's date range ie 02/12/2006 to 09/05/2006.  I understand how to compare 2 calendar objects. It's the next level up ie searching" of a collection I'm struggling with.
0
 
CEHJConnect With a Mentor Commented:
I think it's time for an example:
import java.util.ArrayList;
import java.util.Date;
import java.util.List;


public class X {
    private int id;
    private Date beginDate;
    private Date endDate;

    public X() {
    }

    public X(Date beginDate, Date endDate, int id) {
        this.beginDate = beginDate;
        this.endDate = endDate;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Date getBeginDate() {
        return this.beginDate;
    }

    public void setBeginDate(Date beginDate) {
        this.beginDate = beginDate;
    }

    public Date getEndDate() {
        return this.endDate;
    }

    public void setEndDate(Date endDate) {
        this.endDate = endDate;
    }

    public String toString() {
        return String.format("id=%d,beginDate=%s,endDate=%s", id, beginDate,
            endDate);
    }

    /**
     * Check if a given date is within range
     */
    public boolean isInRange(Date d) {
        return d.after(beginDate) && d.before(endDate);
    }

    // TESTING ONLY
    public static void main(String[] args) {
        List<X> xList = new ArrayList<X>();
        xList.add(new X(java.sql.Date.valueOf("2005-01-01"),
                java.sql.Date.valueOf("2005-03-16"), 0));
        xList.add(new X(java.sql.Date.valueOf("2005-05-08"),
                java.sql.Date.valueOf("2005-07-26"), 1));
        xList.add(new X(java.sql.Date.valueOf("2006-02-12"),
                java.sql.Date.valueOf("2006-09-05"), 2));
        xList.add(new X(java.sql.Date.valueOf("2007-04-26"),
                java.sql.Date.valueOf("2007-10-17"), 3));

        Date test = java.sql.Date.valueOf("2006-06-06");

        for (X x : xList) {
            if (x.isInRange(test)) {
                System.out.printf("Date %s in the range of %s\n", test, x);
            }
        }
    }
}

Open in new window

0
 
_agx_Author Commented:
Yep, that's exactly what I was doing before I raised the question.  Looping through the elements one at a time to "search by date".  (I experimented w/a bunch of stuff). I just thought there might be a slicker method out there than my looping one by one, since the collection is already sorted by date range (ascending) so I can achieve B)
0
 
CEHJCommented:
Well if you're looking just at the beginDate, then a Comparable on that will give you a binarySearch capability with O(log n), better than O(n)

You also might consider http://docs.oracle.com/javase/6/docs/api/java/util/NavigableSet.html
0
 
CEHJCommented:
Well you said that date ranges don't overlap, so isn't that tantamount to saying that the range search can largely operate by beginDate?
0
 
_agx_Author Commented:
Yeah, that's what I meant by "logically it should work" ie IMO it should work. But that's not what the api says & I've no experience with it beyond a single test case... Hence the question to a java expert :) Are my assumptions sound or flawed?

(Edit:) Gah... I messed up the code tags in the last post. So the question's text is mixed in with the code.  But you got the gist.
0
 
CEHJCommented:
:)

I should think your objects should work properly as you wish in any Collection actually
0
 
_agx_Author Commented:
when I get time I'll have to try it with different collection types to see how it plays out. Just wanted to confirm I wasn't making silly newbie mistakes with the logic ;-)
0
 
_agx_Author Commented:
I've got to move on to something else, but I think it'll work.  Marking the final code as the the solution for the archives and awarding points for assist.  Thanks.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.