LEFT INTERACTION OF TWO COLLECTIONS

Question

The question is largely in the title. I am looking for an algorithm that is more efficient than a complete search through collections.

I have two collections:

List<Map<TypeId, Object> > col1; List<Entity> col2; 

Where

 public enum TypeId{ PLAYER, PARTNER, PLATFORM, AMOUNT } 

and

 public class Entity{ private int player_id; private int platform_id private BigDecimal amount; //GET, SET } 

The col1 collection, which is of type List<Map<TypeId, Object> > , contains only PLAYER, PARTNER, PLATFORM TypeId s.

I need to write a method:

 public List<Map<TypeId, Object> > merge(List<Map<TypeId, Object> > col1, List<Entity> col2){ //Impl } 

What List<Map<TypeId, Object> > will create, each entry on the map contains an additional key value (AMOUNT, AMOUNT value) , where AMOUNT value is the value of the amount field of the e of Entity instance if e.player_id = entry.get(PLAYER) && e.platform_id = entry.get(PLATFORM) and null otherwise.

In fact, the operation will be the same as

 col1 LEFT OUTER JOIN col2 ON e.player_id = entry.get(PLAYER) && e.platform_id = entry.get(PLATFORM) 

SAMPLE:

 col1: [{PLATFORM: 1, PARTNER: 1, PLAYER: 1}, {PLATFORM: 1, PARTNER: 3, PLAYER: 1}, {PLATFORM: 2, PARTNER: 1, PLAYER: 2} {PLATFORM: 3, PARTNER: 4, PLAYER: 5}] col2: [Entity(platform_id = 1, player_id = 1, amount = 100), Entity(platform_id = 2, player_id = 2, amount = 200), Entity(platform_id = 3, player_id = 4, amount = 300)] result: [{PLATFORM: 1, PARTNER: 1, PLAYER: 1, AMOUNT: 100}, {PLATFORM: 1, PARTNER: 3, PLAYER: 1, AMOUNT: 100}, {PLATFORM: 2, PARTNER: 1, PLAYER: 2, AMOUNT: 200}, {PLATFORM: 3, PARTNER: 4, PLAYER: 5, AMOUNT: null}] 

Answer 1

It’s easier to make changes in place by changing col1 instead of creating a new List . Here's the Java-8 solution:

 public List<Map<TypeId, Object> > merge(List<Map<TypeId, Object> > col1, List<Entity> col2){ col1.forEach(map -> map.put(TypeId.AMOUNT, col2.stream() .filter(e -> e.player_id == (int)map.get(TypeId.PLAYER) && e.platform_id == (int)map.get(TypeId.PLATFORM)) .findFirst().map(e -> e.amount).orElse(null) )); return col1; } 

I believe that replacing col1 in place is satisfactory in this case. Please note that even if you save the result to a new list, it will be useless if you modify existing maps. Thus, to make the result completely independent of col1 , you have to copy all the cards.

Also note that this is not very efficient, since for each col1 it intersects col2 , so the complexity is approximately equal to col1.size()*col2.size() . It is probably better in your case to throw away the Entity class and create a new one that will only store platformId and playerId (with correctly implemented equals and hashCode ) and use it as a map key:

 public static class PlatformAndPlayer { private final int playerId, platformId; public PlatformAndPlayer(int playerId, int platformId) { this.playerId = playerId; this.platformId = platformId; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + platformId; result = prime * result + playerId; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; PlatformAndPlayer other = (PlatformAndPlayer) obj; if (platformId != other.platformId) return false; if (playerId != other.playerId) return false; return true; } } 

In this case, instead of col2 list you get Map :

 Map<PlatformAndPlayer, BigDecimal> col2 = new HashMap<>(); col2.put(new PlatformAndPlayer(1, 1), BigDecimal.valueOf(100)); col2.put(new PlatformAndPlayer(2, 2), BigDecimal.valueOf(200)); col2.put(new PlatformAndPlayer(3, 4), BigDecimal.valueOf(300)); 

Now your task can be solved easily and efficiently (even with Java 5):

 public static List<Map<TypeId, Object>> merge( List<Map<TypeId, Object>> col1, Map<PlatformAndPlayer, BigDecimal> col2) { for (Map<TypeId, Object> map : col1) { map.put(TypeId.AMOUNT, col2.get(new PlatformAndPlayer( (int) map.get(TypeId.PLAYER), (int) map.get(TypeId.PLATFORM)))); } return col1; } 

Answer 2

The Guava library provides functional idioms that are ideal for such transformations. Here is an example implementation of your method using Guava that does not require a change in the method signature:

 public List<Map<TypeId, Object>> merge(List<Map<TypeId, Object>> col1, List<Entity> col2) { // create a lookup table for getting the amounts // based on entities (entity keys) final Map<Entity, BigDecimal> entityLookupTable = Maps.toMap(col2, new Function<Entity, BigDecimal>() { @Override public BigDecimal apply(Entity entity) { return entity.getAmount(); } }); // transform the col1 list using a transform function // that adds the AMOUNT fetched from the lookup table to each entry map return Lists.transform(col1, new Function<Map<TypeId, Object>, Map<TypeId, Object>>() { @Override public Map<TypeId, Object> apply(Map<TypeId, Object> typeToValueMap) { Entity keyWrapper = new Entity( new EntityKey( (Integer) typeToValueMap.get(TypeId.PLAYER), (Integer) typeToValueMap.get(TypeId.PLATFORM)), null); typeToValueMap.put(TypeId.AMOUNT, entityLookupTable.get(keyWrapper)); return typeToValueMap; } }); } 

However, you must create an EntityKey class that identifies the object (similar to the primary key in the database). Then this class can be used to implement equals (and hashCode ) in Entity , which allows you to store objects on the search map.

 public class EntityKey { private int player_id; private int platform_id; public EntityKey(int player_id, int platform_id) { this.player_id = player_id; this.platform_id = platform_id; } /* Generated by Eclipse */ @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + platform_id; result = prime * result + player_id; return result; } /* Generated by Eclipse */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; EntityKey other = (EntityKey) obj; if (platform_id != other.platform_id) return false; if (player_id != other.player_id) return false; return true; } } public class Entity { private EntityKey key; private BigDecimal amount; public Entity(EntityKey key, BigDecimal amount) { this.key = key; this.amount = amount; } /* Generated by Eclipse */ /* Simply delegates to EntityKey */ @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((key == null) ? 0 : key.hashCode()); return result; } /* Generated by Eclipse */ /* Simply delegates to EntityKey */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Entity other = (Entity) obj; if (key == null) { if (other.key != null) return false; } else if (!key.equals(other.key)) return false; return true; } /** * @return the amount */ public BigDecimal getAmount() { return amount; } }