I have a random unsorted ArrayList of objects A, which have common fields with object B, and another ArrayList of objects B.
I want to order the elements in ArrayList of objects A based on those common fields.
My code:
public class Protocol {
@Override
public String toString() {
return "Protocol [referenceName=" referenceName ", value=" value "]";
}
private String referenceName = "314596";
private String value = "12345";
public Protocol(String referenceName, String value) {
super();
this.referenceName = referenceName;
this.value = value;
}
public String getValue() {
return value;
}
public String getReferenceName() {
return referenceName;
}
// other stuff
}
public class Sensor {
private String referenceName = "314596";
private String value = "12345";
public Sensor(String referenceName, String value) {
this.referenceName = referenceName;
this.value = value;
}
public String getValue() {
return value;
}
public String getReferenceName() {
return referenceName;
}
@Override
public String toString() {
return "Sensor [referenceName=" referenceName ", value=" value "]";
}
// other stuff
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class SortingTest {
public static void main(String[] args) {
Protocol protocol1 = new Protocol("31543678", "09866546534");
Protocol protocol2 = new Protocol("343443678", "09866567897874334");
Protocol protocol3 = new Protocol("41563678", "0663846546534");
Protocol protocol4 = new Protocol("9876543", "009876546546534");
List<Protocol> protocolList = new ArrayList<>();
protocolList.add(protocol4);
protocolList.add(protocol1);
protocolList.add(protocol3);
protocolList.add(protocol2);
for (int i =0; i < protocolList.size(); i ) {
System.out.println(protocolList.get(i));
}
System.out.println("*******************************************************");
Sensor sensor1 = new Sensor("31543678", "09866546534");
Sensor sensor2 = new Sensor("343443678", "09866567897874334");
Sensor sensor3 = new Sensor("41563678", "0663846546534");
Sensor sensor4 = new Sensor("9876543", "009876546546534");
List<Sensor> sensorList = new ArrayList<>();
sensorList.add(sensor1);
sensorList.add(sensor3);
sensorList.add(sensor2);
sensorList.add(sensor4);
List<Sensor> sensorList1 = new ArrayList<>(sensorList);
for(int i =0; i < sensorList.size(); i ) {
System.out.println(sensorList.get(i));
}
System.out.println("*******************************************************");
for (int i = 0; i < sensorList.size(); i ) {
for (int j = 0; j < protocolList.size(); j ) {
if (sensorList.get(i).getReferenceName() == protocolList.get(j).getReferenceName()) {
if (sensorList.get(i).getValue() == protocolList.get(j).getValue()) {
sensorList1.set(j, sensorList.get(i));
}
}
}
}
for (int i = 0; i < sensorList1.size(); i ) {
System.out.println(sensorList1.get(i));
}
}
}
Expected output :
Protocol [referenceName=9876543, value=009876546546534]
Protocol [referenceName=31543678, value=09866546534]
Protocol [referenceName=41563678, value=0663846546534]
Protocol [referenceName=343443678, value=09866567897874334]
*******************************************************
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
*******************************************************
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Based on the common fields, I want to sort ObjectBList so that the sequence matches ObjectAList.
This logic works correctly, but I feel there might some faster or easier way to do this.
CodePudding user response：
The key is obtaining order strategy from protocolList
1.Implement equals & hashCode for Protocol, e.g.,
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Protocol)) return false;
Protocol protocol = (Protocol) o;
return Objects.equals(getReferenceName(), protocol.getReferenceName()) && Objects.equals(getValue(), protocol.getValue());
}
@Override
public int hashCode() {
return Objects.hash(getReferenceName(), getValue());
}
2.Sort sensorList using custom Comparator
sensorList.sort(Comparator.comparingInt(one -> protocolList.indexOf(new Protocol(one.getReferenceName(), one.getValue()))));
P.S.hashCode() is optional if u don't put Protocol into hash collections
CodePudding user response：
This logic works correctly but I feel there might some faster or easier way to do this.
Your current solution utilizes brute force approach, repeatedly checking the position of every protocol (which doesn't change) multiple times, and has a time complexity of O(n * m).
We can improve it by indexing the position of each protocol in a list.
The simplest case
Let's start with the simplest case that corresponds to the example of data you've provided:
- list of
Protocols and list ofSensors are of the same size; - each sensor has a matching pair (by
referenceNameandvalue) in the list of protocols; - each combination of the
referenceNameandvalueis unique.
In this case, sorting can be done in linear time O(n).
We need a single iteration over the list of protocols to index the position of each protocol. We can store it in the map.
And for that we need an intermediate object that would be used as a key. The simplest approach to obtain the key is to concatenate the referenceName and value. A more generalized approach will be to use a record (or class) for that purpose. For now, I'll go with the simplest one - a map Map<String,Integer>, index of each protocol by key.
The next step is to order sensors in accordance with the map of indices. We can create an array of length equal to the size of the list of sensors and then iterate over the list of sensors by placing every sensor at a position retrieved from a map.
In order to turn the array of sensors into a list, we can use static method List.of() available with Java 9, or Arrays.asList() for earlier versions.
That's how it might look like:
public static void main(String[] args) {
List<Protocol> protocols =
List.of(new Protocol("343443678", "09866567897874334"),
new Protocol("41563678", "0663846546534"),
new Protocol("31543678", "09866546534"),
new Protocol("9876543", "009876546546534"));
List<Sensor> sensors =
List.of(new Sensor("31543678", "09866546534"),
new Sensor("343443678", "09866567897874334"),
new Sensor("41563678", "0663846546534"),
new Sensor("9876543", "009876546546534"));
Sensor[] orderedSensors = new Sensor[sensors.size()];
Map<String, Integer> positionByKey = new HashMap<>();
for (int i = 0; i < protocols.size(); i ) {
Protocol next = protocols.get(i);
positionByKey.put(getKey(next.getReferenceName(), next.getValue()), i);
}
for (Sensor next: sensors) {
int position = positionByKey.get(getKey(next.getReferenceName(), next.getValue()));
orderedSensors[position] = next;
}
List<Sensor> result = List.of(orderedSensors); // or for Java 8 and earlier Arrays.asList(orderedSensors);
}
public static String getKey(String first, String second) {
return first ":" second;
}
General case
General case solution doesn't require any assumption, i.e. it should be capable to deal with the following scenarios:
- the sizes of the lists might be unequal;
- combinations of the
referenceNameandvalueare not guaranteed to be unique; - a sensor might have no matching pair in the list of protocols.
The overall approach remains the same: we need to index the position of each protocol and store it in a map.
But we will not access this map directly, instead it will be used by the comparator. And in this solution, a custom object will be used as a key. To avoid the necessity to override equals and hashCode it's implemented as a Java 16 record:
public record Key(String first, String second) {
public Key(Bill.Sensor item) {
this(item.getReferenceName(), item.getValue());
}
public Key(Bill.Protocol item) {
this(item.getReferenceName(), item.getValue());
}
}
To create a comparator, first we have to build a map, and then we can make use of the static method Comparator.comparingInt:
public static Comparator<Sensor> compareByKey(List<Protocol> base) {
Map<Key, Integer> orderByKey = new HashMap<>();
for (int i = 0; i < base.size(); i ) {
Protocol next = base.get(i);
orderByKey.put(new Key(next), i);
}
return Comparator.comparingInt((Sensor item) ->
orderByKey.getOrDefault(new Key(item), -1)); // sensors that have no matching pair in the list of protocols will be grouped at the beginning of the resulting list
}
The main method will require only one line to do the sorting because the comparator does all the heavy lifting. And because now we are dealing with the sorting, the time complexity would be linear-logarithmic.
public static void main(String[] args) {
List<Protocol> protocols = // initializing the list of protocols
List<Sensor> sensors =// initializing the list of sensors
List<Sensor> orderedSensors = new ArrayList<>(sensors);
orderedSensors.sort(compareByKey(protocols);
}
Note: that this approach can be generalized further by making use of generic type parameters, so that it would be possible to apply it to any pair of objects. That would require making the Key class generic, and the method responsible for generating the comparator in order to be able to extract the needed attributes from an arbitrary object should be provided with a couple of functions.