Making a Groovy class a range
February 7, 2009 2 Comments
In a recent post, I used the Date class in a range. This always jumps out at Java developers, who aren’t used to seeing it.
def now = new Date() def then = now + 9 assert 10 == (now..then).size()
It’s really cool you can do that in Groovy. That example illustrates both the concept of a range as a collection of values, and that Groovy can add methods to an existing library class — in this case, java.util.Date.
As Groovy in Action (GinA) points out, any class can be used in a range if:
- It has a
next()method to determine the following element, - It has a
previous()method to determine the preceding element, and - It implements the
java.util.Comparableinterface.
The Comparable interface, from Java, has a single method called compareTo(obj). It should return a positive value if the current object is greater than the argument, a negative number if the current object is less than the argument, and zero otherwise. Any class that implements the Comparable interface should also override the equals(obj) method in a consistent way, i.e., if compareTo returns zero, the equals method ought to return true.
There’s an example in GinA, but I decided to try to put something a bit more nontrivial together as an illustration.
I started with a class representing a train station:
class TrainStation {
String name
String toString() { name }
boolean equals(Object o) {
return this.name == o.name
}
int hashCode() { name.hashCode() }
// ... more to come
So my station has a name field, and the equals and hashCode methods both delegate to that field.
Since I needed the TrainStation class to have a next() and a previous() method, I decided the easiest way to do that was to give the station a reference to the surrounding stations:
// ... from above, then
TrainStation nextStation
TrainStation previousStation
TrainStation next() { nextStation }
TrainStation previous() { previousStation }
// ...
So far, so good. I needed to initialize the next and previous station values, so I created a constant called END and assigned both pointers to that value in the constructor.
//...
public static final TrainStation END = new TrainStation(name:'END')
TrainStation() {
nextStation = END
previousStation = END
}
(If this is starting to resemble a “circular doubly-linked list” to you, the resemblance is purely intentional.)
The hard part was implementing Comparable. If a station is in the “next” direction, it’s considered greater, and if it’s in the “previous” direction, it should be less than the current station. The problem is, if all I have available is pointers to the immediate neighbors, how can I compare to stations that could be many steps away?
There are probably lots of ways to do it, but the technique that occurred to me was recursion. I also needed to check in both directions, because I don’t know whether the supplied argument will be greater, lesser, or equal. After a lot of playing around, I eventually implemented it this way.
// ...
int compareTo(Object o) {
boolean greater = false
boolean lesser = false
greater = isGreater(o)
if (greater) { return 1 }
lesser = isLesser(o)
if (lesser) { return -1 }
return 0
}
boolean isLesser(TrainStation ts) {
if (this.equals(END)) { return false }
if (this.next().equals(END)) { return false }
if (this.next().equals(ts)) { return true }
return nextStation.isLesser(ts)
}
boolean isGreater(TrainStation ts) {
if (this.equals(END)) { return false }
if (this.previous().equals(END)) { return false }
if (this.previous().equals(ts)) { return true }
return this.previous().isGreater(ts)
}
In each direction, I check the current node against its neighbor. If that isn’t conclusive, then I move from the current node to the next or previous node and check again, continuing until either I reach the desired node or I hit the end of the line.
Now, to test all this, I needed a Track class (if the TrainStation is a node in a linked list, the Track class is the linked list itself). The only complicated part of that is the method to add a new TrainStation, as shown below.
import java.util.List
import java.util.LinkedList
public class Track {
List<TrainStation> stations = new LinkedList<TrainStation>()
Track() {
// all new stations need a boundary on each end
stations.add(TrainStation.END)
}
void addStation(TrainStation ts) {
// play with pointers to append the new station
TrainStation last = stations.last()
ts.previousStation = last
ts.nextStation = TrainStation.END
last.nextStation = ts
// might as well store the stations, too
stations.add(ts)
}
def visitStations(TrainStation from, TrainStation to) {
def result = []
// Whoo hoo! TrainStations are a range!
for (station in (from..to)) {
result << station
}
return result
}
String toString() {
return stations.toString()
}
}
[/sourcecode]
The <code>visitStations</code> method is where the <code>TrainStation</code> class, at long last, is used in a range. A client asks the track to visit stations from a beginning station to an ending station. The intermediate stations are all added to an <code>ArrayList</code> (i.e., the <code>[]</code> value), which is then returned to the client.
If it's not tested, it's broken. I'll omit the <code>TrainStationTests</code> class, which just verified that <code>next()</code>, <code>previous()</code>, and <code>compareTo()</code> worked, but here's the <code>TrackTests</code> class.
public class TrackTests extends GroovyTestCase {
Track acela
TrainStation bos = new TrainStation(name:'Boston')
TrainStation nh = new TrainStation(name:'New Haven')
TrainStation ny = new TrainStation(name:'New York')
TrainStation ph = new TrainStation(name:'Philadelphia')
TrainStation dc = new TrainStation(name:'Washington')
void setUp() throws Exception{
acela = new Track()
acela.addStation(bos)
acela.addStation(nh)
acela.addStation(ny)
acela.addStation(ph)
acela.addStation(dc)
}
void testVisitOneStation() {
def expected = [bos].toArray()
def result = acela.visitStations(bos,bos).toArray()
assertArrayEquals(expected,result)
}
void testVisitTwoStations() {
def expected = [bos,nh].toArray()
def result = acela.visitStations(bos,nh).toArray()
assertArrayEquals(expected,result)
}
void testVisitManyStations(){
def acela_sb = [bos, nh, ny, ph, dc]
def result = acela.visitStations(bos,dc)
assertArrayEquals(acela_sb.toArray(),result.toArray())
def acela_nb = [dc, ph, ny, nh, bos]
result = acela.visitStations(dc,bos)
assertArrayEquals(acela_nb.toArray(),result.toArray())
}
}
Using GroovyTestCase gives me the convenient assertArrayEquals method, which is also cool.
So the result is that I have a new class that I can use in a range. Maybe the GinA authors were right not keep their example simpler than this, but I had fun. 🙂
As an aside, it should be noted that computing the size of a range is not an efficient operation. The implementation requires the loop to traverse the range, element by element, using the next() method, counting elements as it goes. So a date range spanning years is going to look at every single day in between. It’s worth keeping that in mind when you want to compute how many elements are traversed.
RSS
Atom
Recent Comments