Comparing two ArrayLists containing different objects with (some) shared properties

[Jesper Ragnarsson]

Hi all, I'm new here, and fairly new to programming in general.

I have a problem that I'm currently trying to tackle, and it involves ArrayLists and comparisons, both of which I have close to no experience with. The problem itself involves checking that users have received text messages sent through our messaging service, and that they have been sent at the correct time.

So I have these two objects, User and Message:

public class User {
    String CID;
    String phoneNumber;
    String timeZone;
    String deliveryTime;
    
    public User(String CID, String phoneNumber, String timeZone, String deliveryTime){
        this.CID = CID;
        this.phoneNumber = phoneNumber;
        this.timeZone = timeZone;
        this.deliveryTime = deliveryTime;
    }
}

public class Message {
    String deliveryTime;
    String phoneNumber;
    
    public Message(String deliveryTime, String phoneNumber){
        this.deliveryTime = deliveryTime;
        this.phoneNumber = phoneNumber;
    }
}

I run a method which collects information from our system, and stores that data as User objects in an ArrayList. I run another method which collects data from the messaging service we use, and store those as Message objects. If all messages have been sent properly, the lists should match perfectly. But since the objects within the ArrayLists have different properties, it's not as simple as doing userArr.equals(messageArr), from what I understand.

In short, what I'd like to code is a method which matches up entries in the two lists, using the properties they share (phoneNumber and deliveryTime), and if any entries lack a match, it prints them to the console. The current solution I have in mind is to simply iterate through the two ArrayLists at the same time (after sorting them), comparing the shared properties, and if they match up, continue the loop. The problem with that solution is that if there is a mismatch, the loop simply ends, being unable to find every missing object, but just the very first one.

Any help is appreciated. Please let me know if anything needs clarification, I'm new to all this.

[Campbell Ritchie]

Welcome to the Ranch

So, you have recipients with phone numbers, and you have messages sent to phone numbers? You want to check that the recipient't phone number matches the message's phone number, along with some other details. I have my own ideas, but I shall make you work to see if you can't get your own ideas.
I am going to suggest you draw a diagram of your recipients and messages, with phone numbers. You only need about three of each. Draw arrows showing which message links to which recipient if any.
Also go through the Java™ Tutorials and see if you can find anything that matches your diagram.

[Jesper Ragnarsson]

Campbell Ritchie wrote:Welcome to the Ranch

So, you have recipients with phone numbers, and you have messages sent to phone numbers? You want to check that the recipient't phone number matches the message's phone number, along with some other details. I have my own ideas, but I shall make you work to see if you can't get your own ideas.
I am going to suggest you draw a diagram of your recipients and messages, with phone numbers. You only need about three of each. Draw arrows showing which message links to which recipient if any.
Also go through the Java™ Tutorials and see if you can find anything that matches your diagram.

Thanks for the reply.

I drew up a quick diagram, which assumes the ideal scenario (both ArrayLists contain the same amount of objects, and each object has a match):



The problem here is quite obvious. Let's say the loop continues, but Message3 is missing. In this case, User3 will be matched against (what is actually) Message4, resulting in a mismatch. The loop will continue, matching User4 against Message5, and so forth, until the end of the ArrayList is reached (or eventual IndexOutOfBounds exceptions). That's another issue, the lists can differ in size. If the user is in our system and set to receive messages, but something is wrong and the message is not sent, the message record will not appear on the messaging service end of things, resulting in an array of Message objects that is shorter than User objects.

I had a look at the Collections tutorials, but I couldn't quite find anything that applies to my problem. Or I'm just not understanding things correctly, that seems more likely.

[Junilu Lacar]

First, good job on making your first couple of posts clear, coherent, and complete. Good job in showing some effort, too.

Get used to using List, the interface, as your primary working type instead of ArrayList, which is a specific implementation type.

List<User> users = new ArrayList<>();
List<Message> messages = getSentMessages();
...
match(messages, users);

...

List<Message> getSentMessages() {
    List<Message> messages = new ArrayList<>();
    ...
    return messages;
}

void match(List<Message>, List<User>) {
   Map<Message, User> matches = new HashMap<>();
   ...
}

These are examples of code that is programmed to the interface, not the implementation.

I have also given you a hint on where you might start looking to do a matching of messages to users.

[Campbell Ritchie]

I think Junilu was thinking the same way I was. You want something which maps phone number and time to something else. You will now end up with a diagram something like this:-[123, 11.00] →→→ User1 [123, 11.00] →→→ Message1 [234, 12.00] →→→ User2 [234, 12.00] →→→ Message2 [345, 12.30] →→→ Message3 [345, 12.30] →→→ ???In that scenario, maybe message 3 has got lost, a scenario similar to what you mentioned yourself.
Are you going through a List of historic message data, or are you getting real‑time input telling you that message 999 is just being delivered to phone number 987654321 or similar?

Now it seems Junilu and I were thinking differently. I was thinking to map NumberTime to Message and also to map NumberTime to User, and then see how much of an overlap there is of the two data structures. When you get to something like my line 6 above, you will start worrying that something has gone wrong.
I presume you can easily get time and phone number out of your User and Message classes, and create a NumberTime class. Note you will have to override the equals and hashCode methods on that class if you want any of the Collections classes to work correctly.

[Junilu Lacar]

Campbell Ritchie wrote:
Now it seems Junilu and I were thinking differently. I was thinking to map NumberTime to Message and also to map NumberTime to User, and then see how much of an overlap there is of the two data structures.

Yes, we were. Looks like you're already waist deep into thinking this problem through. I was only just skimming the surface -- I didn't really think it would end up being a Map<Message, User>, that was just to keep that part tied back to the rest of the example. All I really had in mind was that a Map was going to be involved somehow, and perhaps a Comparator or two as well.

[Junilu Lacar]

If using Java 8, those new default methods in the Map interface look promising: computeIfAbsent() and computeIfPresent()

[Campbell Ritchie]

I had forgotten about those methods; yes, they do look promising.

OP: Since the word Map has appeared so frequently in these posts, please go back to the tutorials link and look what it says about the Map interface (and Map implementations).

[Carey Brown]

I think your choice between: (a) comparing sorted lists vs (b) checking for presence in a map, depends on the order you want the output to be in. In approach (a) you will get users and messages interwoven depending on what your sort criteria is (e.g. time). In (b) you will get all of the missing users first followed by all the missing messages (or vice-versa).

For comparing sorted lists you need two indexes, one for users and one for messages.

LOOP as long as there is both users and messages
    IF user < message
        print user
        increment user 
    ELSE IF user > message
        print message
        increment message
    ELSE IF user == message
        increment both user and message
// consume any remaining users or messages
LOOP for all remaining users
    print user
LOOP for all remaining messages
    print message

[Jesper Ragnarsson]

Thanks for all the suggestions! Map definitely seems like what I should be looking into.

I had a go at tinkering together a solution of my own yesterday, before reading the responses here. Currently, it looks like this:

public ArrayList compareUserAndMessageArrayLists(ArrayList userArr, ArrayList messageArr) {

        ArrayList<String> missingNumbers = new ArrayList<>();

        for (int x = 0; x < userArr.size(); x++) {
            User currentUser = (User) userArr.get(x);
            String currentUserPhoneNumber = currentUser.getPhoneNumber();
            String currentUserDeliveryTime = currentUser.getDeliveryTime();
            for (int y = 0; y < messageArr.size(); y++) {
                Message currentMsg = (Message) messageArr.get(y);
                String currentMsgPhoneNumber = currentMsg.getPhoneNumber();
                String currentMsgDeliveryTime = currentMsg.getDeliveryTime();
                if (currentUserPhoneNumber.equals(currentMsgPhoneNumber)
                        && currentUserDeliveryTime.equals(currentMsgDeliveryTime)) {
                    break;
                }
            }
        }
        return missingNumbers;
    }

The idea is to take one user at a time, then compare it to every entry in the Message ArrayList. If a match is found, break from the nested loop, and continue the process for the next user in the ArrayList. If a match is not found, the phone number should be added to the ArrayList missingNumbers (which I haven't implemented in this code snippet).

While this does work in theory (if my nested loop is correct, very little experience with this), there's a scalability issue (in addition to there probably being a million other ways to do this task more efficiently than in my example, heh). This solution would work fine if we're just iterating through a handful of users/messages, but if we have thousands, it suddenly becomes pretty inefficient. And if the lists are sorted to boot, the whole "iterate through every single message looking for a match" part of the code would only execute if a message is actually missing, making it pretty pointless.

I'll try to work out a solution using mapping and post another reply if I need any help. Thanks again, everyone.

[Liutauras Vilda]

Another idea, if you'd manage to override equals and hashCode in certain way (I tried, worked for me), you could create a Set or List and do similarly (it is just an idea, ignore poor style)

User u = new User("dummy1", "number44", "dummy2", "delivery44");
User u1 = new User("dummy", "dummy3", "dummy", "dummy4");
Message m = new Message("delivery44", "number44");
Message m1 = new Message("dummy5", "dummy6");

List<Object> potentialMatches = new ArrayList<>();
potentialMatches.add(u);
potentialMatches.add(u1);
potentialMatches.add(m);
potentialMatches.add(m1);

Set<Object> notMatched = new HashSet<>();

for (Object o : potentialMatches) {
    if (notMatched.contains(o)) {
        notMatched.remove(o);
    } else {
        notMatched.add(o);
    }
}
    
for (Object o : notMatched) {
    print o; // prints u1, m1
    // add number to missing numbers
}

[Junilu Lacar]

I have a hard time understanding how there is any equivalence between User and Message in the way OP seems to be comparing them. Namely,

a User and Message match if:
user.phoneNumber equals message.phoneNumber
AND user.deliveryTime equals message.deliveryTime

How in the world does a User have a deliveryTime? There seems to be some kind of conceptual anomaly there that leads me to think the class/object design is not quite right.

[Campbell Ritchie]

Maybe the User class is badly named; it appears to represent the event of somebody receiving a message.

[Jesper Ragnarsson]

Sorry, I should've clarified that bit.

In our system, the user should receive their message at 10 AM local time, depending on where in the world they are located. In the messaging system logs (the ones retrieved to make Message objects), this delivery time appears in my local timezone (CET). So if a user is in Los Angeles, for instance, the delivery time in the logs would be 7 PM.

When creating the User object, the user's time zone is taken into consideration, and their expected delivery time for the message is generated through another method. This expected delivery time is then compared to the actual delivery time, which is retrieved from the messaging service logs and stored in the Message object(s).

Hope that clears things up.

[Junilu Lacar]

So, on the "User" object, the time indicates the time when a message was last successfully delivered to that user?  And that time would match the Message.deliveryTime to indicate successful delivery. Otherwise, the user didn't get the Message that's in the list of Messages that you're trying to match up. Is this correct?

[Campbell Ritchie]

In which case the time field in the User class represents the time of the most recently‑received message. You would therefore have to update such message times frequently on a real‑time basis. If you have millions of messages, you might get so many messages to the same user that you miss the last‑but‑one time like that.

[Jesper Ragnarsson]

Junilu Lacar wrote:So, on the "User" object, the time indicates the time when a message was last successfully delivered to that user?  And that time would match the Message.deliveryTime to indicate successful delivery. Otherwise, the user didn't get the Message that's in the list of Messages that you're trying to match up. Is this correct?

The deliveryTime in the User object only indicates when the message should have been received, calculated using the user's time zone. If this matches up to the Message.deliveryTime, that indicates that the message delivery was done on time. If the message failed to deliver altogether, there would simply not be a Message object that corresponds to the User object, since the message itself wouldn't appear in the logs of the messaging service.

So, ideally, the end goal of my code is to (a) ensure that the message has been delivered, and (b) ensure that it has been delivered on time (or within a reasonable time-frame).

I hope that clarifies things.

[Junilu Lacar]

Since a program needs to deterministic, what exactly is the definition of "within a reasonable timeframe"? I don't see anything in the code you posted that looks like it represents that idea.

[Junilu Lacar]

Also, matching by phone number and time seems to be a brittle design to me. If we pull data modeling practices into the picture, you'd want to normalize and give a unique message Identifier to each Message. Then the User object would just have the message Id instead of a set of multiple fields that could change in the future. In this case, the name User becomes obviously misleading and we'd be compelled to change it to something that correctly describes its role/purpose: something like ExpectedDelivery instead perhaps.

[Jesper Ragnarsson]

Junilu Lacar wrote:Also, matching by phone number and time seems to be a brittle design to me. If we pull data modeling practices into the picture, you'd want to normalize and give a unique message Identifier to each Message. Then the User object would just have the message Id instead of a set of multiple fields that could change in the future. In this case, the name User becomes obviously misleading and we'd be compelled to change it to something that correctly describes its role/purpose: something like ExpectedDelivery instead perhaps.

In this scenario, the only unique identifier for a message in the logs is the phone number. One thing I forgot to specify is that this test is only to check deliveries done within the last day, meaning that there should only be one message per phone number (so the same number can't possibly appear twice), so I think it should be fine as a unique identifier. I do agree that the naming is a bit confusing, but it's named like that because the User objects are pulled from our User database, making User the most reasonable name.

As for the reasonable timeframe, plus/minus an hour of the expected delivery time is deemed acceptable, according to the specifications. I haven't implemented this yet, which is why it's missing from my code. At this moment in time, it's higher priority to build something that determines if messages have been sent at all. This is simply a secondary requirement.

[Carey Brown]

If you are only looking for log entries for a single day and there should only be one entry per phone number, then it seems like you could ignore whatever the received time was set to and only have to compare lists/sets of phone numbers.

[Junilu Lacar]

I don't agree with the reasoning that just because the data in those objects is pulled from your User database, that makes "User" a reasonable name for the objects representing that data. If I create a bunch of objects that hold data about home addresses pulled from a Student database, that doesn't make it reasonable to name those objects "Students" -- they're addresses, so the logical name to use would be StudentAddress or something like that. It's the semantics and the idea behind the objects that count, not where the data is coming from.

Carey is right. It seems you only need the phone numbers to match delivered messages with expected deliveries. The time data will only be used to determine if the delivery was "reasonable timely". If you're using Java 8, then the Map's default interface methods I mentioned earlier should give you a way to easily process the lists. -- (Edit: forgot to go back and update that -- I'm not so sure those default methods will be useful after all)

Here's the process I have in mind:

Create a list of ExpectedDelivery objects out of your current "User" objects. It would look something like this:

class ExpectedDelivery {
    private String phoneNumber;
    private LocalDateTime expectedTime;
    private Message message;
    ...

    private static final DateTimeFormatter TIME_FORMAT = ...;

    ExpectedDelivery(User data) {
         this.phoneNumber = data.getPhoneNumber();
         this.expectedTime = LocalDateTime.parse(data.getDeliveryTime(), TIME_FORMAT);
    }

    boolean wasDelivered() {
         return this.message != null;
    }

    boolean wasNotDelivered() {
         return !wasDelivered();
    }

    boolean wasLate() {
         return !wasTimely();
    }

    boolean wasTimely() {
         return wasDelivered() && wasWithinReason();
    }

    private LocalDateTime actualDeliveryTime() {
         return LocalDateTime.parse(...);
    }

    private boolean wasWithinReason() {
         return Duration.between(expectedTime, actualDeliveryTime()).toMinutes() <= timelinessThresholdMinutes();
    }

    // or just define a static constant value
    private long timelinessThresholdMinutes() {
         ...
    }
}

1. Create a Map<String, ExpectedDelivery> - iterate over the ExpectedDelivery list and add a map entry for each one, using the phoneNumber as the key and the object itself as the value.
2. Iterate over the Messages list and see if the map.get(message.phoneNumber) returns a valid ExpectedDelivery object. If it does, then set the ExpectedDelivery object's message property. Otherwise, do nothing.
3. Iterate over the Map entries and see which ones have values where wasNotDelivered() or wasLate() is true. There may seem to be some redundancy between wasTimely() and wasDelivered() but I see wasTimely as a more nuanced indication of whether the message was delivered.

Mind you this is just off the top of my head. I haven't tried this in actual code but I hope it gives you a general idea of the algorithm I have in mind.

[Jesper Ragnarsson]

Sorry for the lack of a response, been busy over the holidays. I greatly appreciate all the input, however, thanks for spending so much time trying to help me solve my problem!

Here's what my current implementation looks like (assuming ArrayLists have already been populated):

HashMap<String, ExpectedDelivery> map = new HashMap<>();
        for(int i = 0; i < listOfExpectedDeliveries.size(); i++){
            map.put(listOfExpectedDeliveries.get(i).getPhoneNumber(), listOfExpectedDeliveries.get(i));
        }
        
        for(int i = 0; i < listOfMessages.size(); i++){
            if(map.get(listOfMessages.get(i).getPhoneNumber()) == null){
                //add missing phone number to a list, which is then printed in report
            }
        }

And since the whole process is a JUnit test, I would end the test case by simply asserting that the list of missing numbers doesn't contain any entries.

Note that this code lacks the functionality which checks for timely delivery, but I just want to make sure that I have the general idea down before I start implementing the rest of the features. First time using HashMaps, after all.