Eric Sosman said:
[trying to extend TreeSet but ensure that two and only two
objects are ever inserted into it]
This is the current version of my Range.add() method; it works fine, even if
the design is bad:
public boolean add(Object object) {
if (size() >= 2) {
return false;
} else {
return super.add(object);
}
}
I'm not quite clear why this is a bad design. It certainly feels kludgey to
have code like 'if (size() >= 2)' but what are the risks and dangers of
leaving this as it is?
... and you've overridden addAll() as well, to make sure nobody
can insert an unwanted object into your TreeSet that way, either.
Fine, you've locked all the doors.
... except that TreeSet offers clear() and remove() methods
that a client could use to delete one or both of the "two and
only two" objects after your Range is constructed. Do you
want to prevent that? Then get busy and write a few more
overrides to lock those two doors. TreeSet also has iterator(),
and a client could use the returned Iterator object to muck
with your Range. Do you want to prevent that? More busy work.
And what about the subSet(), tailSet(), and headSet() methods?
Haul out your editor and write still more overrides ...
Eventually, after many overrides, you'll have locked all
the doors and made your Range unmodifiable. But wait! Acceding
to enormous community pressure, Java 1.7 comes along and defines
a new addFiltered(Collection, Filter) method to all the modifiable
collections. A new door has suddenly opened in your fortress
wall, and the Orcs are charging through it ... Your nightmare
never ends.
Ok, you've made your point
I see the dangers now.
If Range extends TreeSet, it automatically exposes all of
TreeSet's behaviors and characteristics that you don't explicitly
override. If Range instead *contains* a TreeSet instance, you
can choose to expose only those characteristics you want. In
particular, if the TreeSet instance is private within Range and
if Range offers no method that lets a client get hold of the
TreeSet reference, there is no way the client can call any methods
on the TreeSet; only your Range class itself has the means to
modify the TreeSet, and there's no way to do an end-run around
your protective blockade.
Excellent! That answers my question very clearly. That makes a great deal of
sense.
For some reason, I got it into my head that using a TreeSet as my foundation
was bad at least partially because it had so much overhead so that using
composition reduced that overhead somehow; I was trying to figure out how
that would work. Now I see that the real benefit is that you get far better
security/stability since the TreeSet is totally internal to the Range.
- Why in the ever-lovin' blue-eyed mornin' do you want
to drag out the entire machinery of a TreeSet just to
keep track of two count them two objects? Canaricide
by cannon, that's what it is.
[trying to do something analogous to SQL's IN and BETWEEN]
Since the IN operator can have a (virtually) unlimited number of values in
its argument list, I decided that the Java equivalent of that argument list
would be a Collection, specifically a TreeSet since the algorithm to
determine if a given value was in the Collection seemed likely to be more
efficient if the Collection values were in order. I developed a class
containing static methods that did a variety of INs.
Having decided that the set required by an IN was suited to a TreeSet, it
seemed a logical extension to store the range implied by the BETWEEN
Here, I think, is where you go wrong. What's sauce for the
goose is sauce for the gander, but tastes perfectly awful atop
calamari. It is true you could model a range as the set of all
elements within the range (back off, mathematicians: there are
no non-denumerable sets on a finite computer), but that's not a
great model. All you really care about are the endpoints of the
range, and you'll use comparisons to decide whether a test item
does or doesn't lie between them. Note, too, that a range requires
an ordering notion while a set does not: you could speak of a set
of points on the plane, but you cannot speak of a range of points
on the plane (mathematicians: anybody who mentions space-filling
curves is out of, er, line).
Since ranges and sets are different in so many ways, there
seems little reason to base them on the same data structure.
Start by deciding on the behaviors you want; then and only
then start thinking about the data structures to support them.
Fair enough; as I said, I didn't really think it through very thoroughly
before going with a TreeSet: I just got the notion that a Range was a very
specialized set and therefore merited being a TreeSet just like the IN sets.
I didn't realize all the consequences that you have pointed out so well.
For what it's worth, I now have a SimpleRange class, which subclasses
Object, that does all of what I need it to do to meet my needs without
carrying around all the baggage of the TreeSet. Just for the heck of it,
here it is. If you can see any problems or omissions in it, I'd be delighted
to hear about it. I'm not sure I've covered everything we've talked about
but I tried. I've also used JUnit to test everything; I probably haven't
thrown as many exotic cases at it as I should but every test I have given it
passed. By the way, I initially assumed that my Range or SimpleRange class
would have to be further subclassed to handle specific datatypes but I'm
starting to think that won't be necessary; thanks to polymorphism, this baby
might just do the whole job ;-)
/**
* Class SimpleRange describes the behaviour of all ranges, regardless of
the class of
* data stored in it.
*
* <p>A SimpleRange is a class containing exactly two elements of the same
type. These
* elements represent the end-points of a range of values, e.g. 18 to 21 or
A to E.</p>
*
* @author Rhino
*
*/
public class SimpleRange {
public static int NUMBER_OF_ELEMENTS = 2;
Comparable lowValue = null;
Comparable highValue = null;
/**
* Constructor SimpleRange(Comparable, Comparable) creates an instance
of the class.
*
* @param Comparable
* firstObject one of the two Object values that will
encompass
* the range
* @param Comparable
* secondObject the other of the two Object values that will
encompass
* the range
*/
public SimpleRange(Comparable firstObject, Comparable secondObject) {
/* Verify that neither object is null. */
if (firstObject == null) {
throw new IllegalArgumentException("The first Object cannot be
null.");
}
if (secondObject == null) {
throw new IllegalArgumentException("The second Object cannot be
null.");
}
/*
* Since only Comparable objects are permitted by this constructor,
compare them
* and store the lower one in the lowValue class variable. Store the
other one in the
* highValue class variable.
*/
try {
if (firstObject.compareTo(secondObject) > 0) {
highValue = firstObject;
lowValue = secondObject;
} else {
lowValue = firstObject;
highValue = secondObject;
}
} catch (ClassCastException cc_excp) {
throw new IllegalArgumentException("The first Object, " +
firstObject.toString() + ", belongs to class " +
firstObject.getClass().getName() + ". The second Object, " +
secondObject.toString() + ", belongs to class " +
secondObject.getClass().getName() + ". Both Objects implement the Comparable
interface but they cannot be compared with each other.");
}
}
/**
* Constructor SimpleRange(Comparable[]) creates an instance of the
class.
*
* @param Object[]
* range an array of Comparables
*/
public SimpleRange(Comparable[] range) {
/* Verify that the array is not null. */
if (range == null) {
throw new IllegalArgumentException("The range array cannot be
null.");
}
/* Verify that the array contains exactly two elements. */
if (range.length != 2) {
throw new IllegalArgumentException(
"The range array must contain exactly two elements.");
}
/* Verify that the array elements aren't null. */
if (range[0] == null) {
throw new IllegalArgumentException("The first array element
cannot be null.");
}
if (range[1] == null) {
throw new IllegalArgumentException("The second array element
cannot be null.");
}
/*
* Since only Comparable objects are permitted by this constructor,
compare them
* and store the lower one in the lowValue class variable. Store the
other one in the
* highValue class variable.
*/
try {
if (range[0].compareTo(range[1]) > 0) {
lowValue = range[1];
highValue = range[0];
} else {
lowValue = range[0];
highValue = range[1];
}
} catch (ClassCastException cc_excp) {
throw new IllegalArgumentException("The first Object, " +
range[0].toString() + ", belongs to class " + range[0].getClass().getName()
+ ". The second Object, " + range[1].toString() + ", belongs to class " +
range[1].getClass().getName() + ". Both Objects implement the Comparable
interface but they cannot be compared with each other.");
}
}
/**
* Method size() returns the size of this SimpleRange; the value will
always be 2.
*
* @return the size of this SimpleRange (always 2)
*/
public int size() {
return NUMBER_OF_ELEMENTS;
}
/**
* Method getValues() returns all of the values in this SimpleRange.
*
* @return all of the values in this SimpleRange
*/
public Comparable[] getValues() {
Comparable[] values = new Comparable[size()];
values[0] = lowValue;
values[1] = highValue;
return values;
}
/**
* Method getLow() returns the lower of the two values in the
SimpleRange.
*
* @return Comparable the lower of the two values in the SimpleRange
*/
public Comparable getLow() {
return lowValue;
}
/**
* Method getHigh() returns the higher of the two values in the
SimpleRange.
*
* @return Comparable the higher of the two values in the SimpleRange
*/
public Comparable getHigh() {
return highValue;
}
/**
* This version of between() is a convenience method that determines if
a given int
* value is within a range of int values.
*
* <p>This version of between() will return true if the input value
matches
* either end-point of the range or lies anywhere between them.</p>
*
* @param Comparable input the value which is being compared to the
range
* @return boolean true if the input value is equal to either endpoint
or lies between them, otherwise false
*/
public boolean between(Comparable input) {
return between(true, input, true);
}
/**
* This version of between() determines if a given value is within a
range of values.
*
* <p>Since different users have different expectations about the
behaviour of a
* between method, this method provides two booleans that control which
behaviour
* will be experienced. For example, if the user desires between to be
true if the input
* value is strictly between the two endpoints but not equal to any of
them, both booleans
* should be set to false.</p>
*
* @param includesLow if true the low end of the range should include
the low value, otherwise the low end of the range starts just above the low
value
* @param input the value that is being compared to the range
* @param includesHigh if true the high end of the range should include
the high value, otherwise the high end of the range ends just below the high
value
* @return true if the input value is in the range, otherwise false
*/
public boolean between(boolean includesLow, Comparable input, boolean
includesHigh) {
/*
* If 'includesLow' and 'includesHigh' are both true, return true if
'input'
* satisfies this condition: lowValue <= input <= highValue.
*/
if (includesLow && includesHigh) {
try {
if (input.compareTo(lowValue) >= 0 &&
input.compareTo(highValue) <= 0) {
return true;
} else {
return false;
}
} catch (ClassCastException cc_excp) {
throw new IllegalArgumentException("The input value, " +
input.toString() + ", belongs to class " + input.getClass().getName() + ".
Although the end-points of the range can be compared with each other, they
cannot be compared with the input value.");
}
}
else
/*
* If 'includesLow' and 'includesHigh' are both false, return true
if 'input'
* satisfies this condition: lowValue < input < highValue.
*/
if (!includesLow && !includesHigh) {
try {
if (input.compareTo(lowValue) > 0 &&
input.compareTo(highValue) < 0) {
return true;
} else {
return false;
}
} catch (ClassCastException cc_excp) {
throw new IllegalArgumentException("The input value, " +
input.toString() + ", belongs to class " + input.getClass().getName() + ".
Although the end-points of the range can be compared with each other, they
cannot be compared with the input value.");
}
}
else
/*
* If 'includesLow' is true and 'includesHigh' is false, return true
if 'input'
* satisfies this condition: lowValue <= input < highValue.
*/
if (includesLow && !includesHigh) {
try {
if (input.compareTo(lowValue) >= 0 &&
input.compareTo(highValue) < 0) {
return true;
} else {
return false;
}
} catch (ClassCastException cc_excp) {
throw new IllegalArgumentException("The input value, " +
input.toString() + ", belongs to class " + input.getClass().getName() + ".
Although the end-points of the range can be compared with each other, they
cannot be compared with the input value.");
}
}
else
/*
* If 'includesLow' is false and 'includesHigh' is true, return true
if 'input'
* satisfies this condition: lowValue < input <= highValue.
*/
if (!includesLow && includesHigh) {
try {
if (input.compareTo(lowValue) > 0 &&
input.compareTo(highValue) <= 0) {
return true;
} else {
return false;
}
} catch (RuntimeException excp) {
throw new IllegalArgumentException("The input value, " +
input.toString() + ", belongs to class " + input.getClass().getName() + ".
Although the end-points of the range can be compared with each other, they
cannot be compared with the input value.");
}
}
else {
return false;
}
}
}
