14

Is there a way to write custom comparator, following this example:

There are at most 10 items coming in at a random order i.e. 

first item:  item_one
second:      second_one
third:       third_one

I want result them to be sorted like : second_one, third_one, first_one. I'd like to pull this order from configuration file, sort of like template for sorting.

Am I using the wrong data structure, does anyone have experience with this?

aioobe
  • 413,195
  • 112
  • 811
  • 826
London
  • 14,986
  • 35
  • 106
  • 147
  • 3
    I don't see what ordering this is. Can you elaborate on what you mean by the ordering? – templatetypedef Mar 29 '11 at 18:59
  • @templatetypedef there is no logical explanation for this sorting flow, thats why I'd like to create comparator which uses some kind of template so it knows how to sort. – London Mar 29 '11 at 19:02
  • If it has an order, it is not a `Set` but a `List`. And you can use `Comparator`s on `List`s as you wish. – Bombe Mar 29 '11 at 19:04
  • I guess I don't understand your question, then. What does sorted order mean for these objects? The sorted ordering you gave above doesn't look sorted at all. – templatetypedef Mar 29 '11 at 19:05
  • @London: its not clear even after your reply. Define the "order" on the elements. i.e. given two elements x and y, how do you decide whether x – MAK Mar 29 '11 at 19:05
  • 1
    @Bombe, which `List` takes a `Comparator`? Quite the opposite, if you need to provide a `Comparator`, use a `TreeSet` which is a `Set`. – Steve Kuo Mar 29 '11 at 19:08
  • @templatetypedef if it did have some logic to it, I'd simply write a method in which I'd determine some logic to decide in which order to sort, however this may not be sorting, but I want the order to be decided based on anything I provide as a template. @MAK that is the deal, I can't think of algorithm/logic to determine how this should be sorted, I just want to sort it based on what I provide in my template. – London Mar 29 '11 at 19:09
  • What do you mean by "template?". Are you given the ordering explicitly in another location and then want to keep everything sorted by the order from that template? – templatetypedef Mar 29 '11 at 19:10
  • @Steve, `Collections.sort()` takes a `List` and a `Comparator`. – Bombe Mar 29 '11 at 19:10
  • @Bombe I was thinking the same, maybe I'm using a wrong data structure, but than again I don't know how to do it using a list as well at this time – London Mar 29 '11 at 19:11
  • @templatetypedef yes that is exactly what I mean – London Mar 29 '11 at 19:12
  • @London: Can you give your specific case? Maybe someone here can see a logical way to sort your data. – Jeremy Mar 29 '11 at 19:13
  • @Jeremy Heiler that is the case I provided in the question .. you might think middle one +1 then middle one -1 .. but it gets weird later on .. no logic what so ever – London Mar 29 '11 at 19:16
  • @London ... then if you know the indexes, why can't you just keep a list of those indexes in the order you want and iterate over it, using each index to access that position in the collection. – Jeremy Mar 29 '11 at 19:18

4 Answers4

19

Sure. Here is an "OrderedComparator" that compares elements according to a predefined order:

class OrderedComparator implements Comparator<String> {

    List<String> predefinedOrder;

    public OrderedComparator(String[] predefinedOrder) {
        this.predefinedOrder = Arrays.asList(predefinedOrder);
    }

    @Override
    public int compare(String o1, String o2) {
        return predefinedOrder.indexOf(o1) - predefinedOrder.indexOf(o2);
    }

}

And here is some test code. (I used a List instead of a Set since it 1) seem more natural when talking about the order of the elements and 2) better illustrate what happens with duplicate elements upon sorting using this comparator.)

class Test {

    public static void main(String[] args) {

        // Order (could be read from config file)
        String[] order = { "lorem", "ipsum", "dolor", "sit" };


        List<String> someList = new ArrayList<String>();

        // Insert elements in random order.
        someList.add("sit");
        someList.add("ipsum");
        someList.add("sit");
        someList.add("lorem");
        someList.add("dolor");
        someList.add("lorem");
        someList.add("ipsum");
        someList.add("lorem");


        System.out.println(someList);

        Collections.sort(someList, new OrderedComparator(order));

        System.out.println(someList);
    }

}

Output:

[sit, ipsum, sit, lorem, dolor, lorem, ipsum, lorem]
[lorem, lorem, lorem, ipsum, ipsum, dolor, sit, sit]
aioobe
  • 413,195
  • 112
  • 811
  • 826
2

Take a look at TreeSet (http://download.oracle.com/javase/6/docs/api/java/util/TreeSet.html). You can provide a custom Comparator in a constructor. This Comparator will take into account your config. file . The logic of the comparator will not be pretty though since you want arbitrary order. You will most probably end up enumerating all possible comparisons.

David Soroko
  • 8,521
  • 2
  • 39
  • 51
  • can you give an example please, I don't know what you mean. – London Mar 29 '11 at 19:10
  • So your text file has a row for every pair, let's say the values are ABCD, and lets say that the order is A > B > C > D A B A C A D B C B D C D every line means that the first value is greater then the second value. You will read the file into your comparator and create a table which you will consult every time you need to do compare(). For example you can have a hashmap with keys like "AB", "BD" end so on and values -1 or 1 to indicate if the first part of the key is less then the second. wish I knew how to add line breaks here – David Soroko Mar 29 '11 at 19:21
  • But for a small set of values, aioobe's solution is much better, You can still use the comparator he provided in a tree set – David Soroko Mar 29 '11 at 19:29
1

A set stores unordered elements. If you want to compare and sort, you should probably go with a list. Here's a quick snippet for you:

List<X> sorted = new ArrayList<X>(myset);
Collections.sort(sorted, new Comparator<X>() {
    public int compare(X o1, X o2) {
        if (/* o1 < o2 */) {
            return -1;
        } else if (/* o1 > o2 */) {
            return 1;
        } else {
            return 0;
        }
    }
});

Now you've got sorted, which has all the same elements of myset, which was unordered by virtue of being a set.

You can also look at TreeSet, which orders its elements, but it's generally not a good idea to rely on a set being ordered.

Jonathan
  • 13,354
  • 4
  • 36
  • 32
  • >> generally not a good idea to rely on a set being ordered. why do you say that? – MeBigFatGuy Mar 29 '11 at 19:28
  • Because it's a set, not a list. Maybe it's just my math background, but I don't like it. – Jonathan Mar 29 '11 at 19:30
  • -1 It's not a good idea to rely on a generic set being ordered but the whole point of the SortedSet interface(which TreeSet extends) is to guarentee an ordering – gcooney Mar 29 '11 at 19:42
  • @gcooney I didn't say you shouldn't rely on a `SortedSet` being sorted. I said that you shouldn't rely on a `Set` being sorted, and that I do not personally like the idea of a sorted set. – Jonathan Mar 29 '11 at 20:00
  • @Jonathon Considering the fact that the OP can choose the type of Set he wants to use, I find it misleading to use the unreliable ordering of generic Sets as an argument against using any set. – gcooney Mar 29 '11 at 20:49
  • @Jonathon, so if you wanted a sorted collection that had no duplicates, you still recommend Lists? That's really inefficient especially as the collection gets large. – MeBigFatGuy Mar 30 '11 at 04:10
  • Perhaps my opinion comes from never having needed a sorted collection without duplicates. `TreeSet` does seem to solve the problem in this case, so it probably is the correct tool. – Jonathan Mar 30 '11 at 13:18
0

Use Guava's com.google.common.collect.Ordering:

Ordering.explicit(second_one, third_one, first_one);
Andrew Ko
  • 291
  • 3
  • 2