Custom comparator
Given the following list: "A", "B", "C", "D", "E", "F", "G"
I need a comparator that does the following sort:
- specify a specific element (for example
"D"
) - start with element
- followed by all of the following elements of the original list in original order
- followed by all previous elements of the original list in original order
Result: "D", "E", "F", "G", "A", "B", "C"
Keep in mind that I know I can just do something similar to the following:
List<String> following = myList.subList(myList.indexOf("D") + 1, myList.size());
List<String> preceding = myList.subList(0, myList.indexOf("D"));
List<String> newList = Stream.of(Collections.singletonList("D"), following, preceding)
.flatMap(List::stream)
.collect(Collectors.toList());
I mean implementation explicitly in this question Comparator
.
It is clear that it will have to have a list and an element as a parameter, I just don't understand the comparison algorithm itself:
private static class MyComparator<T> implements Comparator<T> {
private final List<T> list;
private final T element;
private MyComparator(List<T> list, T element) {
this.list = list;
this.element = element;
}
@Override
public int compare(T o1, T o2) {
// Not clear
}
}
source to share
I think this is what you want:
class ImposedOrder<T> implements Comparator<T> {
private final List<T> list;
private final int startIndex;
ImposedOrder(List<T> list, T startElement) {
this.list = new ArrayList<>(list);
this.startIndex = list.indexOf(startElement);
if (startIndex < 0) {
throw new IllegalArgumentException();
}
}
@Override
public int compare(T t1, T t2) {
int t1Index = list.indexOf(t1);
int t2Index = list.indexOf(t2);
return Integer.compare(adjust(t1Index), adjust(t2Index));
}
private int adjust(int rawIndex) {
if (rawIndex >= startIndex) {
return rawIndex;
}
return rawIndex + list.size();
}
}
Additional verification may be needed to avoid overlap with duplicate order list.
Linear search using indexOf
doesnโt give you much performance, but for a small list of orders it might be enough. Otherwise, instead of saving a copy of the overlaid order list, you can map the items to their adjusted index in the Comparator constructor.
Like this:
class ImposedOrder<T> implements Comparator<T> {
private final Map<T, Integer> map;
private final int startIndex;
ImposedOrder(List<T> list, T startElement) {
this.startIndex = list.indexOf(startElement);
if (startIndex < 0) {
throw new IllegalArgumentException();
}
this.map = IntStream.range(0, list.size())
.boxed()
.collect(Collectors.toMap(
list::get,
i -> adjust(startIndex, list.size(), i)
));
}
@Override
public int compare(T t1, T t2) {
Integer t1Index = map.get(t1);
Integer t2Index = map.get(t2);
return t1Index.compareTo(t2Index);
}
private static int adjust(int startIndex, int size, int rawIndex) {
if (rawIndex >= startIndex) {
return rawIndex;
}
return rawIndex + size;
}
}
source to share
if I asked the question correctly, what to do Collections.sort(myList, myComparator);
then I can suggest you to use a specific collator:
List<String> myList = Arrays.asList("A", "B", "C", "D", "E", "F", "G");
System.out.println(myList);
String rules = "< d,D < e,E < f,F < g,G < a,A < b,B < c,C";
RuleBasedCollator ruleBasedCollator = new RuleBasedCollator(rules);
Collections.sort(myList, ruleBasedCollator);
System.out.println(myList);
the rule is here "< d,D < e,E < f,F < g,G < a,A < b,B < c,C"
, which means the characters have a higher weight than the others ... the rest is as usual the sorting method
output
[A, B, C, D, E, F, G]
[D, E, F, G, A, B, C]
source to share
There is no point in using it here Comparator
, as that would be very inefficient (since you would have to find the indices of the 2 elements being compared in the original list, which would require each comparison to take linear time).
And it can still fail if the list contains duplicates.
However, since you asked, something like this might work:
public int compare(T o1, T o2) {
if (o1.equals(o2)
return true;
int i1 = list.indexOf(o1);
int i2 = list.indexOf(o2);
int ie = list.indexOf(element); // this can be done in the constructor of the Comparator
// now you have to check whether i1 and i2 are smaller than or larger than
// ie, and based on that determine which of the corresponding elements should come
// first
}
or just call
Collections.rotate(list,list.size() - list.indexOf(element));
source to share
I knew it was possible, but it's messy ... and unsafe
The idea to push the first block all the way to the end is to add String
to make this value larger. Thus, "A" is greater than "G" if it looks like "ZA" when it is compared.
List<String> list = Arrays.asList(new String[]{ "A", "B", "C", "D", "E", "F"});
final String split = "D";
Collections.sort(list, new Comparator<String>(){
public int compare(String o1, String o2) {
//Prepend with a big String value (like "ZZZZ") if it is before the value `split`.
if(o1.compareTo(split) < 0)
o1 = "ZZZZ" + o1;
if(o2.compareTo(split) < 0)
o2 = "ZZZZ" + o2;
return o1.compareTo(o2); //then compare
}
});
System.out.println(list);
[D, E, F, A, B, C]
This is unsafe as it might be difficult to add with a safe value to be larger, I was thinking about using it Character.MAX_VALUE
, but I'm not sure if it would be safer. Well, using the value split
might be easier.
source to share
You need to compare the indices of the elements.
private static class MyComparator<T> implements Comparator<T> {
private final List<T> list;
private final int elementIndex;
private MyComparator(List<T> list, T element) {
// keep original order
this.list = new ArrayList<>(list);
this.elementIndex = list.indexOf(element);
}
@Override
public int compare(T o1, T o2) {
int i1 = list.indexOf(o1);
int i2 = list.indexOf(o2);
if (i1 == elementIndex) {
// "shift" first element left
return -1;
} else if (i2 == elementIndex) {
// "shift" secont element left
return 1;
}
boolean left1 = i1 < elementIndex;
boolean left2 = i2 < elementIndex;
if (left1 != left2) {
// different part
return i2 - elementIndex;
} else {
// same part
return i1 - i2;
}
}
}
source to share
The idea is to compare the weights of the elements based on the original indices in the list - if the index of the current element is> = the index of the specified specific element (for example, "D"), then the index in the new list should be moved to the left, the index "D" is exactly the required offset.
int weightO1 = list.indexOf(o1) - list.indexOf(element);
otherwise (list.indexOf (o1) <list.indexOf (element)), the weight calculation should move the element to the right, eg. it could be
int weightO1 = list.indexOf(o1) + list.size();
I would encapsulate the weight calculation in a local method:
int weight (T o) {
return int weight = list.indexOf(o) < list.indexOf(element) ? list.indexOf(o) + list.size() : list.indexOf(o) - list.indexOf(element);
}
so the implementation of the comparison method would look like this:
@Override
public int compare(T o1, T o2) {
return weight(o1) - weight(o2);
}
source to share