Comparable intervals?
Is there a way to implement the Comparable interface for sorting intervals of numbers so that two intervals are considered equal if they overlap?
Or, alternatively, is the last axiom for the compareTo method of the Comparable interface used/needed by the TreeMap/Set classes?
Background: I have a programming assignment, in a part of which "resources" (like as class rooms, video projectors etc) can be booked for "tasks" (such as holding a class). A resource can be booked for at most one task at any time.
I thought that this could be solved easily by defining a natural ordering for intervals: an interval is "greater than" another one when it begins after the first one ends, "less than" when it ends before the second one begins, and "equal to" if they overlap. Then it would be a piece of cake to store the time intervals in e.g. a SortedSet and the data structure would take care of avoiding "overbooking" for me. But nope.
The specification for Comparable says:
http://java.sun.com/j2se/1.4.1/docs/api/java/lang/Comparable.html
Finally, the implementer must ensure that x.compareTo(y)==0
implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.
Now, I cannot see a way to satisfy this. Consider three intervals x, y, and z such that y contains both x and z and x and z don't overlap, e.g. y = [0, 2), x = [0, 1), z = [1, 2). Now x.compareTo(y) == 0 but x.compareTo(z) == -1 because x is before z, and y.compareTo(z) == 0 because z and y overlap.
Any good ideas how to fix this or is this approach totally idiotic?
This course is about object oriented programming and not about data structures and algorithms and the resource booking feature is only a small part of it, so maybe I could save time and cheat a little and give them a working but potentially bogus program. Is this last axiom actually needed by Sun's implementation of java.util.TreeSet/Map? IIRC they are implemented with red-black trees which I know nothing about.
[2018 byte] By [
jsalonena] at [2007-9-29 17:44:09]
I suspect that you will be able to add, in order, x, z and y and end up with a TreeSet containing two objects.
Good point..
However, in this application, before adding an element I always check that it can actually be added, in other words that no existing reservation clashes with the new reservation. This is needed for user feedback, the user should be let to know if a resource can be reserved.
This check would fail for y after x and z have been added, so in practise y wouldn't get added. There would never be an attempt to add any elements of the set {x | x.compareTo(y) == 0, y in tree} or remove any objects that are not in the tree already, so maybe it is fine after all?
Currently I use TreeMaps and whether an element can be added is checked with containsKey. Is it possible that containsKey might return false with this violation of the contract of compareTo?
I admit it's ugly but I'm too tired to think of a proper solution and want to get this thing over with :P
You finally ask a question and with all the D$ that you have, you have the nerve not to offer any for a correct answer? :-O
I had to solve a similar set of problems and my solution was to use 2 TreeMaps. TreeMap1's comparator compared only interval start. TreeMap2's comparator compared only intarval end.
Now you won't get everything for free, but at least this lets you sort and organize data in a sensible way.
TreeMap1 gives you what intervals start before/same/after a given interval.
TreeMap2 gives you what intervals end before/same/after a given interval.
Everything else you need to know, you have to code by getting appropriate information form either TreeMap and working on those subsets of data.
> You finally ask a question and with all the D$ that> you have, you have the nerve not to offer any for a> correct answer? :-OThat's the name of the game, Rob ;-)
> Any good ideas how to fix this or is this approach totally idiotic?
Do you want an honest answer or a technical answer? :-)
Technical answer: if you have a bunch of intervals and you just want to avoid 'overbooking' there's no need to implement a Comparable interface, just implement a hashCode and an equals method, where equals returns true only if both intervals overlap. Store all intervals in a HashSet and see which of them survived, i.e. you end up with a set of non-overlapping intervals.
Now for the #1 question: would that set of intervals be an 'optimal' (mind the quotes) set, i.e. is a maximum number of resources allocated given a day (or whatever) time interval? If you want to answer this question, your proposed approach would be idiotic indeed :-)
kind regards,
Jos
mgbolusm, thank you for the suggestion. I had already considered something quite similar to that for another part of the assignment but I didn't come to think of applying it here. I didn't realise SortedMap has the headMap, subMap, and tailMap methods, they could make life sweet!
However, I think I will stick to what I already have written. I will remove the Comparable interface from the time interval class and turn it into a private Comparator in the Resource class instead. A class that publishes a broken interface is no good so I'll hide it in a private implementation; I've realised that the afore mentioned requirement can be shown to be fullfilled for every object that will be given to the single TreeMap.
> Technical answer: if you have a bunch of intervals and
> you just want to avoid 'overbooking' there's no need
> to implement a Comparable interface, just implement a
> hashCode and an equals method, where equals returns
> true only if both intervals overlap. Store all
> intervals in a HashSet and see which of them survived,
> i.e. you end up with a set of non-overlapping
> intervals.
>
Thank you but I already considered that approach, if I do that I might as well use a LinkedList with the contains method :) For correct implementation of hashCode it would have to return the same value for every interval object. Every interval would have to go to the same bin, reducing the HashMap/Set implementation to a linked list.
Not to mention that there is no way to implement transitivity as required by the equals method: with the above intervals x.equals(y) and y.equals(z) are both true but x.equals(z) should not.
> Now for the #1 question: would that set of intervals
> be an 'optimal' (mind the quotes) set, i.e. is a
> maximum number of resources allocated given a day (or
> whatever) time interval? If you want to answer this
> question, your proposed approach would be idiotic
> indeed :-)
No, the program is expected to only allocate the resource if possible and give the user a message if not possible.
> Not to mention that there is no way to implement
> transitivity as required by the equals method: with
> the above intervals x.equals(y) and y.equals(z) are
> both true but x.equals(z) should not.
You're right about that; it slipped my mind. OTOH you don't need that transitivity if all you need is the 'overbooking' test. A question for you -- what is the granularity of those start-end time intervals and for what timespan (a day, week etc.) do you need to keep track of (un)booked resources? If, say, the granularity would be 20 minutes or so in a timespan of a day, a 'long' (64 bits) would do fine representing the 'booked' property of a resource and some simple bit-fiddling could decide whether or not a resource could be booked for a certain time interval ...
kind regards,
Jos
> You're right about that; it slipped my mind. OTOH you
> don't need that transitivity if all you need is the
> 'overbooking' test.
>
True, in theory that approach could be used..
> A question for you -- what is the
> granularity of those start-end time intervals and for
> what timespan (a day, week etc.) do you need to keep
> track of (un)booked resources? If, say, the
> granularity would be 20 minutes or so in a timespan of
> a day, a 'long' (64 bits) would do fine representing
> the 'booked' property of a resource and some simple
> bit-fiddling could decide whether or not a resource
> could be booked for a certain time interval ...
>
Granularity and timespan are not specified; there is nothing in the assignment specification about managing resource bookings that I haven't already posted. I have already written code that uses java.util.Date to represent time so I guess the granularity is one millisecond and timespan from January 1, 1970, 00:00:00 GMT to.. when is it, actually? Java doesn't suffer from the "year 2038 bug" does it?
> That's the name of the game, Rob ;-)Moo! Thanks for the D$! :-)
