Update a list from another list

Question

I have a list of users in local store that I need to update from a remote list of users every once in a while. Basically:

1. If a remote user already exists locally, update its fields.
2. If a remote user doesn't already exist locally, add the user.
3. If a local user doesn't appear in the remote list, deactivate or delete.
4. If a local user also appears in the remote list, update its fields. (Same as 1)

Eg. Remote List: User(1, true), User(2, true), User(4, true), User(5, true)

Local List: User(1, true), User(2, false), User(3, true), User(6, true)

New Local List: User(1, true), User(2, true), User(3, false), User(4, true), User(5, true), User(6, false),

Just a simple case of syncing the local list. Is there a better way to do this in pure Java than the following? I feel gross looking at my own code.

public class User {
    Integer id;
    String email;
    boolean active;

    //Getters and Setters.......

    public User(Integer id, String email, boolean active) {
        this.id = id;
        this.email = email;
        this.active = active;
    }

    @Override 
    public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof User) {
            User that = (User) other;
            result = (this.getId() == that.getId());
        }
        return result;
    }

}




public static void main(String[] args) {

    //From 3rd party
    List<User> remoteUsers = getRemoteUsers();

    //From Local store
    List<User> localUsers =getLocalUsers();     

    for (User remoteUser : remoteUsers) {
        boolean found = false;
        for (User localUser : localUsers) {
            if (remoteUser.equals(localUser)) {
                found = true;
                localUser.setActive(remoteUser.isActive());
                localUser.setEmail(remoteUser.getEmail());
                //update
            } 
            break;
        }
        if (!found) {
            User user = new User(remoteUser.getId(), remoteUser.getEmail(), remoteUser.isActive());
            //Save
        }
    }

    for(User localUser : localUsers ) {
        boolean found = false;
        for(User remoteUser : remoteUsers) {
            if(localUser.equals(remoteUser)) {
                found = true;
                localUser.setActive(remoteUser.isActive());
                localUser.setEmail(remoteUser.getEmail());
                //Update
            }
            break;
        }
        if(!found) {
            localUser.setActive(false);
            // Deactivate
        }
    }
}

Answer 1

The best way is to switch to a different data structure. A Map<Integer, User> will be best, because presumably users have uniquely identifying IDs. Your choice of Map implementation can be either a HashMap (expected O(1) for basic operations) or a TreeMap (O(log N)).

IMPORTANT: You @Override equals(Object) without @Override hashCode()!!! This is dangerous! You should always get into the habit of overriding neither or both! (see: Overriding equals and hashCode in Java )

So, let's say you have Map<Integer, User> remoteUsers and Map<Integer, User> localUsers.

1.) If a remote user already exists locally, update its fields.
4.) If a local user also appears in the remote list, update its fields. (same as 1)
2.) If a remote user doesn't already exist locally, add the user.

Finding if a User from remoteUsers is in localUsers can be answered in O(1) or O(log N) with a simple containsKey and get.

for (int id : remoteUsers.keys()) {
   User local;
   if (localUsers.containsKey(id)) {
      local = localUsers.get(id);
   else {
      localUsers.put(id, local = new User(id));
   }
   local.updateFrom(remoteUsers.get(id));
}

3.) If a local user doesn't appear in the remote list, deactivate or delete.

The following solution shows how powerful these more advanced data structures can be:

Set<Integer> toDeactivate = new TreeSet<Integer>();
toDeactivate.addAll(localUsers.keySet());
toDeactivate.removeAll(remoteUsers.keySet());

for (int id : toDeactivate) {
   User local = localUsers.get(id);
   local.deactivate();
   localUsers.remove(id);
}

---

Additionally, if you are stuck with List<User>, you can still use Map<Integer, User> as an intermediary data structure for this processing (basically transform List<User> to Map<Integer, User> and then back to List<User>). It will still be faster, since it's O(N log N) or O(N), compared to the O(N^2) that you have right now.

If you insist on using only lists, then you might want to look at making it a Collections.sort-ed list, so you can do a Collections.binarySearch on it. You'd need to provide a Comparator<User>, or make User implements Comparable<User>, naturally ordering by id. This too will be O(N log N).

Answer 2

Langali:

Assuming that the Id uniquely identify an User, I have a few suggestions for you:

• Create a class User.Key (an inner class of your User class), and move the id field into there. Make it final. Override the hashcode and equals method on the User.Key class just using the id:

    public User {
       private final Key key;
       ... other variables

       public static class Key {
       private final int id;
          public Key(final int id) {

          }
          // hashcode (can be the id)
          // equals (as you had implemented)
       }
    }

• Create a map to hold your users.

  Map<User.Key, User>

  ;
• Use this map to hold your users, and then use the get and containsKey methods to find what you are looking for.

The problem with List.contains is that, on an ArrayList, it performs a full scan of the list contents. If you are doing that for each item of a second list, your performance is O (n^2), which means that when you double the items you multiply by four the time required to run your method. A HashMap has a performance of O (log(n)), which means that if you 1000 objects, the time required to run it is just 10 times slower (approximately).

Answer 3

You could use List.indexOf() instead of iterating through the list:

for (User remoteUser : remoteUsers) {
    int index = localUsers.indexOf(remoteUser);
    if (index >= 0) {
        User localUser = localUsers.get(index);
        localUser.setActive(remoteUser.isActive());
        localUser.setEmail(remoteUser.getEmail());
        //update
    } else {
        User user = new User(remoteUser.getId(), remoteUser.getEmail(), remoteUser.isActive());
        //Save
    }
}