Why don't Lists have a Comparator?

T

Timo Nentwig

Hi!

Why do Lists not have an optional Comparator? I don't quite understand
the sense of Collections.sort() - which even does dump the list to an
array and sort that array...

Timo
 
J

Joe

Hi!

Why do Lists not have an optional Comparator? I don't quite understand
the sense of Collections.sort() - which even does dump the list to an
array and sort that array...

Timo


Say you had a List of these objects:

public class MyClass {
private int someValue;
private int anotherValue;
}

How would you sort those objects? If you look at the javadocs for the
Collections class, you'll read that "All elements in the list must
implement the Comparable interface". That's how Collections.sort() works
- by calling the compareTo() method on the members.
 
P

Phillip Lord

Joe> Say you had a List of these objects:

Joe> public class MyClass {
Joe> private int someValue; private int anotherValue;
Joe> }

Joe> How would you sort those objects? If you look at the javadocs
Joe> for the Collections class, you'll read that "All elements in
Joe> the list must implement the Comparable interface". That's how
Joe> Collections.sort() works
Joe> - by calling the compareTo() method on the members.


The OP is asking why not allow for an optional comparitor object. This
way you could change the natural sorting of Objects. This means you
could sort according objects which did not implement Comparable
directly, or sort Comparable objects in a different way.

I'm not quite sure what the OP wants though. List itself does nothing
that requires Comparision. Methods which do require this (Like
Collections.sort()) normally have an overloaded method which does take
a Comparitor object. Conversely interfaces such as SortedMap do
support an external Comparitor. As does SortedSet which is probably
what he wants. Of course a Set with an order is really a list, so
perhaps this is a misnomer. But I guess they didn't want the ordered
update (add( Object, int )) methods they would have got from List.

Phil
 
J

Joona I Palaste

Say you had a List of these objects:
public class MyClass {
private int someValue;
private int anotherValue;
}
How would you sort those objects? If you look at the javadocs for the
Collections class, you'll read that "All elements in the list must
implement the Comparable interface". That's how Collections.sort() works
- by calling the compareTo() method on the members.

Isn't the whole reason for the Comparator class to allow comparing
objects that *don't* necessarily implement the Comparable interface?
After all, objects that *do*, don't need a separate comparator at all,
as the collection can simply call their own compareTo() method.
 
C

Chris Smith

Joona said:
Isn't the whole reason for the Comparator class to allow comparing
objects that *don't* necessarily implement the Comparable interface?
After all, objects that *do*, don't need a separate comparator at all,
as the collection can simply call their own compareTo() method.

Yep... that or comparing objects that *do* implement Comparable but need
to be given a different order in the current task.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
 
D

Dale King

Timo Nentwig said:
Hi!

Why do Lists not have an optional Comparator? I don't quite understand
the sense of Collections.sort() - which even does dump the list to an
array and sort that array...


Because for some reason Sun, doesn't think anyone would ever want to
maintain a sorted list of items that may have duplicates. Your guess is as
good as mine why they think that. I have been complaining about it for
years.

They only provide sorting for sets. But they don't allow two items to
compare as equal.
 
J

Joona I Palaste

Because for some reason Sun, doesn't think anyone would ever want to
maintain a sorted list of items that may have duplicates. Your guess is as
good as mine why they think that. I have been complaining about it for
years.
They only provide sorting for sets. But they don't allow two items to
compare as equal.

Why can't you write your own subinterface of List and your own subclass
of any class implementing List to implement a sorted list?

--
/-- Joona Palaste ([email protected]) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"As a boy, I often dreamed of being a baseball, but now we must go forward, not
backward, upward, not forward, and always whirling, whirling towards freedom!"
- Kang
 
D

Dale King

Joona I Palaste said:
Why can't you write your own subinterface of List and your own subclass
of any class implementing List to implement a sorted list?

You certainly can, but it is a non-trivial task to do in an efficient
manner. You need something like a red-black tree like they used for TreeMap
(TreeSet actually uses a TreeMap). I can't go copy Sun's implementation
without violating the license agreement, so I would have to implement a
red-black tree from scratch. It can be done, but it would be a heck of a lot
easier if Sun did it. It would only be a slight tweak of the TreeMap code.
 
J

John C. Bollinger

Phillip said:
I'm not quite sure what the OP wants though. List itself does nothing
that requires Comparision. Methods which do require this (Like
Collections.sort()) normally have an overloaded method which does take
a Comparitor object. Conversely interfaces such as SortedMap do
support an external Comparitor. As does SortedSet which is probably
what he wants. Of course a Set with an order is really a list, so
perhaps this is a misnomer. But I guess they didn't want the ordered
update (add( Object, int )) methods they would have got from List.

A SortedSet is not equivalent to a List, even if you ignore the question
of duplicate elements. That is because when you add an element to a Set
(of any kind) the Set gets to choose where that element goes in the
iteration order (and for a plain Set, that position is not guaranteed by
contract to remain the same under any particular circumstances), but
when you add an element to a List it goes to a particular place (the end
of the list or the specified index) and remains at that position unless
the initial subList ending there is modified by addition or removal of
an element.

Presumably that is also why there is no SortedList in the Collections
API -- the List contract already completely specifies the order of List
elements in terms of the sequence of add(), remove(), etc. operations
performed on a List, and that's not compatible with automatically
maintaining the elements in a sorted order. A SortedList could have
been made a direct subclass of Collection, but that would have been
confusing.


John Bollinger
(e-mail address removed)
 
E

Eric Sosman

Dale said:
You certainly can, but it is a non-trivial task to do in an efficient
manner. You need something like a red-black tree like they used for TreeMap
(TreeSet actually uses a TreeMap). I can't go copy Sun's implementation
without violating the license agreement, so I would have to implement a
red-black tree from scratch. It can be done, but it would be a heck of a lot
easier if Sun did it. It would only be a slight tweak of the TreeMap code.

There are at least three ways to reduce "non-trivial" to
"not much more than trivial." These three suggestions operate
by extending TreeMap (or any other SortedMap you might have
lying about), and using different approaches to accommodate
equal target objects:

- Supply a special Comparator when you construct the
SortedMap, and make sure it never produces zero.
This may be a little dodgy since it "fails to obey
the general contract of the Map interface," but
might suffice since you explicitly desire to evade
the provisions of that contract anyhow.

- Put equal target objects into little Collections of
their own, and insert these buckets into the SortedMap.
Your Iterator would be a two-level affair, iterating
over the SortedMap and over each of its contained
Collections.

- Put each target object into a little wrapper object
along with a sequence number, and insert the wrappers
into the SortedMap. To compare two wrapper objects
first compare their targets, and if those are equal
use the sequence numbers to disambiguate.

So, maybe List ought to have this machinery already --
but it doesn't seem extravagantly difficult to cobble up a
reasonable substitute.
 
J

John C. Bollinger

Joona said:
Why can't you write your own subinterface of List and your own subclass
of any class implementing List to implement a sorted list?

Because an automatically sorted list is not a java.util.List.

That doesn't actually prevent you from doing it, of course, but it does
make it a bad idea. Make this new thing a subtype of Collection
instead, and add any additional features of List that you actually need.
Don't overlook AbstractCollection as a possible base class to
facilitate implementation.


John Bollinger
(e-mail address removed)
 
D

Dale King

Eric Sosman said:
code.

There are at least three ways to reduce "non-trivial" to
"not much more than trivial." These three suggestions operate
by extending TreeMap (or any other SortedMap you might have
lying about), and using different approaches to accommodate
equal target objects:

- Supply a special Comparator when you construct the
SortedMap, and make sure it never produces zero.
This may be a little dodgy since it "fails to obey
the general contract of the Map interface," but
might suffice since you explicitly desire to evade
the provisions of that contract anyhow.

Nope, it's not guaranteed to work. The problem is that you have to fulfill
the contract of comparator which requires that compare( a, b ) have the
opposite sign of compare( b, a ). If you cannot guarantee that then you
cannot guarantee that the code will work and in general there is no way to
guarantee that for arbitrary objects. You might be able to do it for some
objects, but there is no way to do it in all cases.
- Put equal target objects into little Collections of
their own, and insert these buckets into the SortedMap.
Your Iterator would be a two-level affair, iterating
over the SortedMap and over each of its contained
Collections.

Which goes against the notion of efficiency.
- Put each target object into a little wrapper object
along with a sequence number, and insert the wrappers
into the SortedMap. To compare two wrapper objects
first compare their targets, and if those are equal
use the sequence numbers to disambiguate.

With only a fixed number of bits your sequence numbers could eventually wrap
around and cause duplicate sequence numbers. It would be rare for this to
occur, but I would rather not bet on probabilities and have a solution that
works.
So, maybe List ought to have this machinery already --
but it doesn't seem extravagantly difficult to cobble up a
reasonable substitute.

John did a good job of explaining why it shouldn't go under list. There is
no machinery already to cobble it up.
 
R

Roedy Green

Why can't you write your own subinterface of List and your own subclass
of any class implementing List to implement a sorted list?

See http://mindprod.com/jgloss/products.html#SORTEDARRAYLIST

These are ArrayLists with Comparators and a lazy sorting algorithm
that procrastinates sorting as long as it can.

There is also a number of methods for merging two ArrayLists, deduping
etc.

Source code is included. You can see if it would be possible to do
this with just a List base. It is obviously easier to just extend
ArrayList which you can't do with List. You would need a List
delegate object.
 
E

Eric Sosman

Dale said:
With only a fixed number of bits your sequence numbers could eventually wrap
around and cause duplicate sequence numbers. It would be rare for this to
occur, but I would rather not bet on probabilities and have a solution that
works.

It's not really a probabilistic situation. Initialize a
`long' to zero, and you can increment it more than 9e18 times
before it turns negative. The probability of failure before
that point is zero, exactly.

Now, it's easy to write "9e18" and this may give the idea
that it's easy to increment a sequence number that many times.
Let's say, for purposes of estimation, that we want to run the
application for ten uninterrupted years, counting all the time.
Ten years comprise roughly 3652 days, or about 316e6 seconds.
The counter can't overflow unless we're incrementing it faster
than 9e18/316e6 ~= 29e9 times per second -- for ten solid years.

Moore's Law suggests we'll see 30GHz machines in about 2010.
Put the first one to work incrementing a counter at full
nominal speed (doing nothing much else, I'd guess), and you'll
need to think about scheduling a restart sometime in 2020.
Or 2030, if you were smart enough to initialize the counter
to Long.MIN_VALUE instead of to zero.

Overflowing a `long' by repeated incrementation is not a
matter of any practical concern whatsoever. But if you're
still worried, use a `BigNumber': not only will it handle any
overflow that might occur, but it will also slow down the
counting rate just a trifle ;-)
 
D

Dale King

Eric Sosman said:
It's not really a probabilistic situation. Initialize a
`long' to zero, and you can increment it more than 9e18 times
before it turns negative. The probability of failure before
that point is zero, exactly.

No, it is not zero. It is infinitesimally small, but still non-zero. I
already acknowledged that.

Changing the size just changes the probability. Many people might implement
that with an int rather than a long and the odds are much greater.

All I am saying is that I would rather have the more efficient red-black
tree implementation than a less efficient one that has a non-zero
probability of breaking.
 
B

Brian Cole

Dale King said:
Because for some reason Sun, doesn't think anyone would ever want to
maintain a sorted list of items that may have duplicates. Your guess is as
good as mine why they think that. I have been complaining about it for
years.

They only provide sorting for sets. But they don't allow two items to
compare as equal.

Actually, I once had to implement a sorted list even though I still
didn't allow duplicates. I needed the random access properties of
lists, such as indexing.

I extended ArrayList and implemented the SortedSet interface.
 
J

John C. Bollinger

Brian said:
Actually, I once had to implement a sorted list even though I still
didn't allow duplicates. I needed the random access properties of
lists, such as indexing.

I extended ArrayList and implemented the SortedSet interface.

Ack! It's bad enough to violate the constracts of several List-specific
methods by making an auto-sorted "List", but you have furthermore
violated the contracts for Set.hashCode and one or more of
Object.equals, List.equals, and Set.equals. Consider this excerpt from
the Javadocs for Collection.equals, which explains it fairly succinctly:

"The general contract for the Object.equals method states that equals
must be symmetric (in other words, a.equals(b) if and only if
b.equals(a)). The contracts for List.equals and Set.equals state that
lists are only equal to other lists, and sets to other sets. Thus, a
custom equals method for a collection class that implements neither the
List nor Set interface must return false when this collection is
compared to any list or set. (By the same logic, it is not possible to
write a class that correctly implements both the Set and List interfaces.)"

No doubt you ended up with something that served your immediate needs,
but it was the wrong thing to do. For about the same amount of effort
you probably could have made the thing a direct implementation of
Collection, or perhaps an indexed SortedSet implementation. You gain
nothing that you really want to have when you pretend that your clever
hack-together is a List when it doesn't behave as a List is documented
to do.


John Bollinger
(e-mail address removed)
 
X

xarax

John C. Bollinger said:
Ack! It's bad enough to violate the constracts of several List-specific
methods by making an auto-sorted "List", but you have furthermore
violated the contracts for Set.hashCode and one or more of
Object.equals, List.equals, and Set.equals. Consider this excerpt from
the Javadocs for Collection.equals, which explains it fairly succinctly:

"The general contract for the Object.equals method states that equals
must be symmetric (in other words, a.equals(b) if and only if
b.equals(a)). The contracts for List.equals and Set.equals state that
lists are only equal to other lists, and sets to other sets. Thus, a
custom equals method for a collection class that implements neither the
List nor Set interface must return false when this collection is
compared to any list or set. (By the same logic, it is not possible to
write a class that correctly implements both the Set and List interfaces.)"

No doubt you ended up with something that served your immediate needs,
but it was the wrong thing to do. For about the same amount of effort
you probably could have made the thing a direct implementation of
Collection, or perhaps an indexed SortedSet implementation. You gain
nothing that you really want to have when you pretend that your clever
hack-together is a List when it doesn't behave as a List is documented
to do.

Clearly, it was an example of how NOT to use inheritance.
A better solution would be to have an internal ArrayList
for the implementation and only publicize the appropriate
interfaces.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,900
Latest member
Nell636132

Latest Threads

Top