How to join two Set of Objects

Question

I have two sets of objects, where there exists a common 'key' in the objects of each set. I want a resulting set/list that will have join of the properties. For example,

Set A: [{id:1,name:john,age:22},{..}]

Set B: [{id:1,phone:1234,type:mobile},{..}]

Set result : [{id:1,name:john,age:22,phone:1234,type:mobile},{..}]

Can this be achieved without using using loops or without converting the sets into Hashmap? thanks.

Answer 1

So, it looks like your concern about the loop is more about to avoid brute force approach than actually using loops.

Here's an idea, but it requires that your sets have to be ordered upfront, otherwise there is no way to merge the sets without iterating them a lot of times.

Let's say you have two sets: Users and Phones

users =  [{1, "john"}, {2, "ken"}]
phones = [{2, "555-1234"}, {4, "234-23424"}]

What you can do is to "iterate" each set while their current id's differ. Now the important point here is to iterate ONLY the set whose id is lower than the other, so if the id in the users is small you walk in the users set, if the id is lower in the phones set you walk the phones set. This way you don't iterate several times each set, but at most you iterate N number of times where N is the length of the Users set.

So in the example you start with id: 1 and 2

 users[0].id == 1
 phones[0].id == 2

Since they are different you move on the users index

 users[1].id == 2
 phones[0].id == 2

Now they are the same... in this case you merge the objects and create a new Contact

Now you move on both indexes and repeat, unless you're at the end of either of the sets, in which case you are done.

So, basically something like this pseudo-code

// while the id's are different 
while( users[usersIndex].id != phones[phoneIndex].id ) {
    if (user.id < phone.id) { usersIndex++ );
    if (phone.id < user.id) { phoneIndex++ );
}
// At this point either they are the same ... OR one we are at the end of one of the collections
if (user.id == phone.id ) { result.add( new Contact(user, phone) );}
else { we are done }

... repeat. 

Now, I was trying to do this but it gets tricky, first of all because instances java.util.Set don't use indexes, and using the iterators needs a couple of extra verifications and oh yeah, there's your requirement of NOT USING loops. Well it turns out using recursion solves the problem quite well and in a very clean way.

This algorithm using recursion would be something like this:

merge( users, phones, results ) {

    // base case, if one of them is empty
    // we're done
    if users.isEmpty() OR phones.isEmpty() 
         return results

    // take the first element on each set and compare them
    user = users.head
    phone = phones.head

    // if they're the same create a new contact and remove them
    if user.id == phone.id 
       results.add( new Contact(user, phone))
       users.remove(user) 
       phones.remove(phone)

    // iterate on the users set
    if user.id < phone.id 
       // we won't find a matching phone
      users.remove(user)

    // iterate on the phone set
    if phone.id < user.id
       // we won't find a matching user
       phones.remove(phone)

    // call again with the modified sets
    return merge(users, phones, results)
}

At this point you might think "Yeah, well this is all good but how would I know it works"

Well here's the code, merging two sets without iterating more than N times the sets and creating a new set with the results.

In this example I'm using Lombok @Data annotation... just because it's awesome, it basically created getters/setters, toString(), equals and hashCode methods for you, so you don't have to write them

package merge;

import lombok.Builder;
import lombok.Data;

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Merge m = new Merge();
        System.out.println("Result= " +
                        m.merge(
                                buildUsers(),
                                buildPhones(),
                                new TreeSet<>()
                        )
        );
    }

    private static Set<User> buildUsers() {
        Set<User> users = new TreeSet<>();
        users.add(new User(1, "j"));
        users.add(new User(3, "k"));
        return users;

    }

    private static Set<Phone> buildPhones() {
        Set<Phone> phones = new TreeSet<>();
        phones.add(new Phone(1, "123"));
        phones.add(new Phone(2, "345"));
        phones.add(new Phone(3, "678"));
        return phones;
        /// KEEP SCROLLING
    }
}

class Merge {
    public Set<Contact> merge(Set<User> users, Set<Phone> phones, Set<Contact> contacts) {

        if (users.isEmpty() || phones.isEmpty()) {
            return contacts;
        }

        User user = users.iterator().next();
        Phone phone = phones.iterator().next();

        if (user.getId() == phone.getId()) {
            addContact(contacts, user, phone);
            users.remove(user);
            phones.remove(phone);
        } else if (user.getId() < phone.getId()) {
            users.remove(user);
        } else {
            phones.remove(phone);
        }

        return merge(users, phones, contacts);
    }

    private boolean addContact(Set<Contact> contacts, User user, Phone phone) {
        return contacts.add(Contact.builder()
                .id(user.getId())
                .name(user.getName())
                .phone(phone.getPhone())
                .build());
    }
}

@Data
class User implements Comparable<User> {
    private final int id;
    private final String name;

    @Override
    public int compareTo(User o) {
        return Integer.compare(this.id, o.id);
    }
}

@Data
class Phone implements Comparable<Phone> {
    final int id;
    final String phone;

    @Override
    public int compareTo(Phone o) {
        return Integer.compare(this.id, o.id);
    }
}

@Data
@Builder
class Contact implements Comparable<Contact> {
    int id;
    String name;
    String phone;

    @Override
    public int compareTo(Contact o) {
        return Integer.compare(this.id, o.id);
    }
}

run

javac -cp lib/lombok.jar  src/merge/Main.java -d out/
java -cp lib/lombok.jar:out  merge.Main
Result= [Contact(id=1, name=j, phone=123), Contact(id=3, name=k, phone=678)]

Answer 2

I'll assume that your Sets are just a visual representation of two Java Sets:

Set<User>
Set<Phone>

Can performing operations on Sets be done without loops? Well, probably you can somehow do that with streams, but I would suggest the following:

public class UserWithPhone {
    Long id;
    String name;
    Long age;
    String number;
    PhoneType phoneType;

    UserWithPhone(){};
    UserWithPhone(User u, Phone p) {
        if (!u.id.equals(p.id))
            throw new IllegalArgumentException();
        this.id = u.id;
        this.name = u.name;
        this.age = u.age;
        this.number = p.number;
        this.phoneType = p.type;
    }

    UserWithPhone(User u) {
        this.id = u.id;
        this.name = u.name;
        this.age = u.age;
    }
    setPhoneDetails(Phone p) {
        if (!this.id.equals(p.id))
            throw new IllegalArgumentException();
        this.number = p.number;
        this.phoneType = p.type;
    }
}

Now simply perform the following code:

for (User u : users) {
    usersWithPhone.put(u.id, new UserWithPhone(u));
}
for (Phone p : phones) {
    usersWithPhone.get(p.id).setPhoneDetails(p);
}

Where usersWithPhone is a Map. Well... I know that it's not quite what you wanted... I mean there are loops, map... but it's how we do that in Java...