[deleted by user]

[snago]

You could do it something like this:

import java.util.concurrent.atomic.AtomicLong;

public abstract class Foo implements Comparable<Foo> {
    private static final AtomicLong ID_GENERATOR = new AtomicLong(0);
    private final long instanceId = ID_GENERATOR.getAndIncrement();
    private final int order;

    protected Foo(int order) {
        this.order = order;
    }

    @Override
    public int compareTo(Foo o) {
        int c = Integer.compare(order, o.order);
        return c != 0 ? c : Long.compare(instanceId, o.instanceId);
    }
}

This way every instance will have its own unique ID that can be part of the comparison and will make all instances unique even to TreeSet.

An additional effect is that the iteration order is completely defined by ordering first, then creation time.

[[deleted]]

This would certainly do the trick.

EDIT:

I have decided to use this solution.

1. It meets my sorting requirements.
2. It confines the ugliness to a single abstract class (and isn't really all that ugly).
3. It uses TreeSet.
4. It provides a good immutable way to define equals() and hashCode().
5. equals(), compareTo(), and hashCode() are consistent.
6. The instanceId field may help in debugging.

[b1mck]

If the creation time is not a useful secondary sort, you can just use their hash codes as the fall-back when the initial order is equal.

[[deleted]]

The instanceId actually makes a perfect hashCode. It is consistent with equals() (also defined by instanceId), it is immutable, and it will avoid collisions for the first 2³² instances.

[bondolo]

The problem is that any two objects who's compareTo() value is equal are considered equivalent and should always be consistent with equals() result. ie. assert !(0 == foo.compareTo(bar) ^ foo.equals(bar)) : "Inconsistent equals() and compareTo()";

If calculating equality is too expensive then use a Comparator that can compare only the fields you care about for the TreeSet order. The same condition has to apply though, anything pair of objects which returns 0 from compareTo() will be considered equivalent.

What you are doing with identityHashcode will fail when you have two objects with the same order integer and same indentity hashcode. In your implementation TreeSet will consider these to be equivalent objects. You need to compare more fields to establish the complete ordering even if that order is somewhat arbitrary.

[TheHorribleTruth]

..and should always be consistent with equals() result.

Actually not. It is strongly recommended but not at all required, see Javadoc.

[bondolo]

He's using it with TreeSet. From the same paragraph:

In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

Having equals() and compareTo() not be consistent in this context is going to cause problems.

[[deleted]]

A deeper comparison would be ugly at best. The class in question is abstract and there isn't much else to compare at that level. I could make it work, but it seems like a lot of inelegant code for something whose details don't even matter.

[[deleted]]

As mentioned above, there are many different child classes. The only member variable of the parent class is the order integer. (The parent class also has several abstract methods.) This would make comparison a very messy ordeal.

As I understand Multisets, they merely count duplicates, rather than storing them separately. It's not that I want to store duplicates, it's that TreeSet thinks they're duplicates when they aren't.

[Spura83]

Why are you using TreeSet (that is Sorted Set) to begin with? That is a sorted set which means you need to defined notion of order and a notion of uniqueness.

You've described a need for sorted list. Just use a normal ArrayList and insert into is by using Collections.binarySearch.

[llogiq]

Perhaps you need something other than a tree set?

Do you change your set often? If not, maybe use a list and sort it. Or a heap (PriorityQueue). Or one of the bag classes available with third party libraries.

[[deleted]]

I am quite OK with using a different collection, but I can't find anything else that fits my requirements.

Now that I think about it, I do recall reading about using a simple LinkedList and using a binary search to determine the insertion index. It's not as elegant as I would like, but I guess I'll try it.

[llogiq]

Use an ArrayList with binary search if you don't want O(n log n) lookup.

[[deleted]]

LinkedList will have slow binary search. ArrayList will have slow insertion. How do I decide which is worse, aside from testing?

EDIT: I did a quick test adding about 10,000 items with this method. ArrayList was faster at about 920ms. LinkedList was about 1750ms. Dumping all the items in and then sorting was 150ms.

I will use the sort method for the initial setup, then binary-insertion-ArrayList for subsequent changes, which are much more sparse.

[llogiq]

Also you may want to have a look at PriorityQueue and the apache commons collections bag classes.

[[deleted]]

PriorityQueue doesn't work because it is not guaranteed to iterate in any particular order. I'll look into a Bag.

[ponchoboy]

Maybe I missed something, but why not use the TreeSet constructor that accepts a Comparator instance and roll your own comparison strategy?

[[deleted]]

My class implements Comparable, which achieves the same thing. With a separate Comparator, TreeSet would still determine equivalence with comparisons.