CODEWITHSUNDEEP
javasortingcollectionstree
Raevik
Raevik

Reputation: 1991

Controller ordering in TreeSet to List conversion

I have 2 lists coming into my method sorted in a certain order (either ascending or descending based on an ID field)

I have a custom comparator implementation that allows me to throw both lists into the treeset and achieve the desired results.

My issue is after the treeset is loaded, I need to return a single list back from the method. My first implementation didn't care about ordering so I did this (composite is my named TreeSet):

    composite.addAll(custom);
    composite.addAll(reference);    

    Iterator<MyObject> anIter = composite.iterator();
    ArrayList<MyObject> returnVal = new ArrayList<MyObject>();
    while(anIter.hasNext()) 
        returnVal.add(anIter.next());

Once I execute this, the two lists "custom" and "reference" are back to the default ordering. The Javadocs for Collection's iterator() method state that will return the list in ascending order, which is likely where my trouble is coming from.

So...is there no way to return the content of a TreeSet while protecting the original list ordering? A treeset is what came to mind because I wanted to use the power of the comparator interface over the two collections to union them with addAll() and throw out the dupes.

Any suggestions on protecting the ordering would be appreciated.

EDIT*

Set<MyObject> composite = new TreeSet<MyObject>(new Comparator<MyObject>(){
        @Override
        public int compare(MyObject arg0, MyObject arg1) {
            int arg0ID = arg0.getObjID();
            int arg1ID = arg1.getObjID();                
            if(arg0ID < arg1ID) return -1;
            else if(arg0ID> arg1ID) return 1;
            else return 0;
        }           
    });

Upvotes: 2

Views: 2453

Answers (1)

Matt Ball
Matt Ball

Reputation: 359906

is there no way to return the content of a TreeSet while protecting the original list ordering?

No, of course not. TreeSet is the wrong tool for this job. The point of using a TreeSet is that it applies a Comparator-based ordering on the objects that the set contains. Use a different data structure — how about a LinkedHashSet? — if you want to remove duplicate objects while retaining insertion order.

I don't see how your statement refutes my decision. I intentionally CHOSE the TreeSet because I wanted to exercise the comparator interface. ... My comparator let me identify what components of the object to filter on. I don't want to lose that capability

In a TreeSet: "The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used." You cannot pick any order ordering (particularly one like insertion ordering) with a TreeSet. If you can't use equals() and hashCode() to pick the object fields that represent identity, use a decorate-dedup-undecorate pattern with a LinkedHashSet, where the decorator contains equals() and hashCode() implementations. Comparator/Comparable is for specifying ordering, not identity or equality.

You're suggesting I need to abandon it and move to something like LinkedHashSet?

Yes, exactly. Either make MyObject implement the .equals() and .hashCode() that you mean:

class MyObject {
    // snip

    @Override
    public boolean equals(Object o) {
        // boilerplate junk here
        if (!o instanceof MyObject) return false;
        MyObject other = (MyObject) o;
        return this.getObjID() == other.getObjID();
    }

    @Override
    public int hashCode() {
        return this.getObjID();
    }

    // snip
}

and dedup like so:

List<MyObject> custom = /* snip */;
List<MyObject> reference = /* snip */;

Set<MyObject> uniques = new LinkedHashSet<>(custom.size() + reference.size());
uniques.addAll(custom);
uniques.addAll(reference);
List<MyObject> deduped = new ArrayList<>(uniques);

Or use the decorate–dedup–undecorate pattern that I mentioned. The decorator class would look something like this:

class Decorator {
    private final MyObject value;

    public Decorator(MyObject value) {
        this.value = value;
    }

    public MyObject getValue() {
        return value;
    }

    @Override
    public boolean equals(Object o) {
        // boilerplate junk here
        if (!o instanceof Decorator) return false;
        Decorator other = (Decorator) o;
        return this.value.getObjID() == other.value.getObjID();
    }

    @Override
    public int hashCode() {
        return this.value.getObjID();
    }
}

and here's roughly how you'd use it:

List<MyObject> custom = /* snip */;
List<MyObject> reference = /* snip */;

Set<Decorator> uniques = new LinkedHashSet<>(custom.size() + reference.size());
for (MyObject m : custom) uniques.add(new Decorator(m));
for (MyObject m : reference) uniques.add(new Decorator(m));

List<MyObject> deduped = new ArrayList<>(uniques.size());
for (Decorator d : uniques) deduped.add(d.getValue());

Upvotes: 3

Related Questions