?
Solved

Confused about sorting and searching list of objects by date range

Posted on 2012-08-23
17
Medium Priority
?
454 Views
Last Modified: 2012-08-29
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 :)
0
Comment
Question by:_agx_
  • 9
  • 8
17 Comments
 
LVL 86

Assisted Solution

by:CEHJ
CEHJ earned 2000 total points
ID: 38325848
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
 
LVL 52

Author Comment

by:_agx_
ID: 38325961
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
 
LVL 86

Assisted Solution

by:CEHJ
CEHJ earned 2000 total points
ID: 38325972
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 52

Author Comment

by:_agx_
ID: 38326009
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 38326045
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
 
LVL 52

Author Comment

by:_agx_
ID: 38326296
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 38326831
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
 
LVL 52

Author Comment

by:_agx_
ID: 38327074
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
 
LVL 86

Assisted Solution

by:CEHJ
CEHJ earned 2000 total points
ID: 38327276
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
 
LVL 52

Author Comment

by:_agx_
ID: 38327317
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 38327353
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
 
LVL 52

Accepted Solution

by:
_agx_ earned 0 total points
ID: 38327734
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 38328504
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
 
LVL 52

Author Comment

by:_agx_
ID: 38329830
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 38330167
:)

I should think your objects should work properly as you wish in any Collection actually
0
 
LVL 52

Author Comment

by:_agx_
ID: 38331641
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
 
LVL 52

Author Closing Comment

by:_agx_
ID: 38344702
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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Suggested Courses
Course of the Month15 days, 9 hours left to enroll

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question