How to transfer data from a Deque to a SortedSet in Java

Question

I get a Deque<Element> deque and I want to transfer all the elements to the other structure: SortedSet<Element> sortedSet.

And the sequence of elements in sortedSet is just as same as the sequences in which the elements are popped from deque.

For example: if all the elements are popped from deque in a sequence: E01, E02, ..., E10. The sequence of elements stored in sortedSet are also E01, E02, ..., E10.

I don't know how to override the comparator to let the elements store in such a sequence.

Do you know how to do that?

Answer 1

Jane, I wrote a simple code:

public static void main(String[] args) {
        SortedSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return 1;
            }
        });
        Deque<Integer> deq = new LinkedList<Integer>();
        deq.add(5);
        deq.add(1);
        deq.add(3);
        set.addAll(deq);
        System.out.println(deq); // 5,1,3
    }

The comparator should always return 1 this way the order stays the same, if this was your question. Warning: this solution violates the Comparable and Set contract. Use it with caution.

Answer 2

OK, this is most bizarre. You expect to have a SortedSet with elements in iteration order...

Here is a bizarre solution to this bizarre problem:

// final is CRITICAL here
final List<Element> list = new ArrayList<>(deque);
deque.clear();

final Comparator<Element> cmp = new Comparator<>()
{
    @Override
    public int compare(final Element a, final Element b)
    {
        return Integer.compare(list.indexOf(a), list.indexOf(b));
    }
}

return new TreeSet<>(list, cmp);

HOWEVER: this will only work reliably if no two elements in the Deque are .equals()! But this is the best you can do given the inherent incompatibility of requirements. All in all, I suspect a XY problem..

---

There is a way to make that reliable but this requires that you use Guava:

final Equivalence<Object> eq = Equivalence.identity();

final Function<Element, Equivalence.Wrapper<Object>> f = new Function<>()
{
    @Override
    public Equivalence.Wrapper<Object> apply(final Element input)
    {
        return eq.wrap(input);
    }
}

final List<Element> list = Lists.newArrayList(deque);
deque.clear();

final List<Equivalence.Wrapper<Object>> wrapped = Lists.transform(list, f);

final Comparator<Element> cmp = new Comparator<>()
{
    @Override
    public int compare(final Element a, final Element b)
    {
        return Integer.compare(wrapped.indexOf(f(a)),
            wrapped.indexOf(f(b)));
    }
};

return new TreeSet<>(list, cmp);

Answer 3

As fge already stated, you need a LinkedHashSet, a collection which keeps the insertion order:

Set<Element> convertToSet(Deque<Element> dq)
{
LinkedHashSet<Element> lhs = new LinkedHashSet<Element>():
while(!dq.isEmpty())
{
lhs.add(dq.peekFirst());
}

return lhs;
}