0

I have a setup where each of my "People" map to a specific "Room".

However, multiple people can map to the same room.

If an existing person is seen, their room should be updated to the new value.

So this is the traditional use case for Map<Person, Room>.put(Person, Room)

However, the lookup is always going to be "Which people are in this room?" Set<People> get(Room q){}

I can obviously craft my own datastructure or simply iterate over the key-value pairs; but does one of the Java collections libraries have a good structure to support both the referential integrity and lookup I need?

deworde
  • 2,679
  • 5
  • 32
  • 60
  • 1
    Seems that you should have a `Map>` (ie, not just a multi-map, but your key/value must be swapped) – ernest_k Jan 27 '20 at 15:12
  • Does this help : https://stackoverflow.com/questions/1383797/java-hashmap-how-to-get-key-from-value – Shubham Jan 27 '20 at 15:13
  • @ernest_k No, because that doesn't enforce the constraint (e.g. you can have R1->(1,2,3) / R2->(2,4,5)) – deworde Jan 27 '20 at 15:13
  • @Shubham No, because the accepted answer literally says "There is a caveat though, bidi maps cannot have multiple values mapped to keys, and hence unless your data set has 1:1 mappings between keys and values, you cannot use bidimaps." – deworde Jan 27 '20 at 15:14
  • @Shubham Alternatively, you could argue [this answer](https://stackoverflow.com/a/2904266/14250) answers my question with "No, there is no such data structure" – deworde Jan 27 '20 at 15:15
  • @deworde I think you're saying the samething as I. What's the difference? – ernest_k Jan 27 '20 at 15:15
  • You could use a Guava table . The third value isn't useful, but you could call row(R1) to get all people in a room R1 or column(1) to get all rooms (only one of course) for person 1. – Chris94 Jan 27 '20 at 15:16
  • @ernest_k For my solution I need it to be impossible for the same person to be in two different rooms (e.g. in a map, the key "2" can't appear twice for different rooms). With your proposal, 2 can appear in every single List. – deworde Jan 27 '20 at 15:17
  • @deworde I get it. – ernest_k Jan 27 '20 at 15:18
  • 2
    Can't you just add a Room property to each People? No need for extra storage except the People list, unicity enforced. – StephaneM Jan 27 '20 at 15:22
  • Okay, the Guava table facilitates lookup but not one room person. You can store Room as a People property as suggested but to get a list of all People in a Room you will need to iterate through all People. Will that work? – Chris94 Jan 27 '20 at 15:24
  • @StephaneM How do I then look up by Room without doing a full pass, in which case I could just use Map.entrySet().filter()? – deworde Jan 27 '20 at 17:49
  • @Chris94 It will, but not sure it's better than Map.entrySet().filter() – deworde Jan 27 '20 at 17:49
  • @deworde you will have to scrutinize every people, but as I do not know how many there are (dozens? hundreds? millions? more?) I cannot tell if it's a good solution or not. – StephaneM Jan 28 '20 at 12:50

3 Answers3

5

To answer your specific question, no, you can't do it all with one data structure. I would solve it with

Map<Person,Room> personRoom;
SetMultimap<Room,Person> roomPeople;
void addPersonToRoom(Person p,Room r){
    Room currentRoom = personRoom.get(p);
    if (currentRoom != null)
        roomPeople.remove(currentRoom, p);
    personRoom.put(p,r);
    roomPeople.put(r,p);
}
Set<Person> getPeopleInRoom(Room r){
    return roomPeople.get(r);
}
Room getRoomForPerson(Person p){
    return personRoom.get(p);
}
Chris94
  • 312
  • 1
  • 12
  • 1
    well, and `addPersonToRoom` would need to remove that person from all other rooms (or rather "the potential other room") they're in currently. Potentially more business requirements. The comments on the question get quite excessive on possible options, I'm not sure I've identified all secondary requirements. – Olaf Kock Jan 27 '20 at 15:34
  • ...as I've just added concurrency to my answer, I'd just like to point out that this should be taken as pseudocode: Whatever happens concurrently can easily mess with the stored data. Unless concurrency is not an issue - but in 2020 probably everything is concurrent... – Olaf Kock Jan 27 '20 at 15:42
  • Right the user will have to enforce synchronization here or somewhere, and I did not specify the full class structure but the data structures should certainly be private so that they are only updated in addPersonToRoom to maintain integrity. – Chris94 Jan 27 '20 at 15:46
  • Marking this as correct for being the only person to have the decency to answer "No" clearly. – deworde Feb 07 '20 at 10:52
2

With additional business requirements, e.g. one person can only be in one room at a time (from comments to your question), you'll have to revert to a custom abstraction of the data storage.

I'd recommend to not expose the data structure, but provide the appropriate business level abstractions for Rooms and People. In the implementation, you'll have to do more than just store stuff in simple collections, e.g. check business rules. Comments already give some pointers, but my recommendation is to stop thinking about the problem in terms of standard collections.

Notice that with concurrency in mind, you can still end up with a person appearing in two rooms:

List<Person> people1 = ...getPeopleInRoom(1);
// concurrent changes here, in a different thread: somebody changes rooms
List<Person> people2 = ...getPeopleInRoom(2);

// you now may have the same person in two different lists - 
// because when you asked for the occupants in a room, they 
// were in the given room, but no longer are.
Olaf Kock
  • 46,930
  • 8
  • 59
  • 90
  • I appreciate the concept of wrapping the basic data structure in an abstraction, but the fundamental constraint/lookup pair in the question seems to be a low-level enough concept that it might/should be supported, even if I then wrap it in higher level business logic. – deworde Jan 27 '20 at 16:00
  • well - see the concurrency issues discussed in the comments to @Chris94's answer. They're surely easier to encapsulate with a custom data structure (which he also proposes implicitly). Looking at David Soroko's answer (and the comments), he also states: _"In which case multimap is an OK starting point. You will need to wrap it in your custom logic."_ – Olaf Kock Jan 27 '20 at 16:07
  • The "constraint" is not low level at all once you spell out how you want to handle a "constraint violation". – David Soroko Jan 27 '20 at 16:32
  • @davidSoroko It's the same constraint as expressed in util.Map – deworde Jan 27 '20 at 17:01
  • 1
    I am suggesting that the separation you make between the constraint and what to do when it is violated is to a large extent artificial. Anyway, I think that your original question has been pretty unanimously answered. – David Soroko Jan 27 '20 at 17:06
  • @DavidSoroko I think Chris94's "No" was the clearest, to be honest – deworde Jan 27 '20 at 17:52
  • @OlafKock I'm not sure "roll your own" is the best solution to concurrency problems, historically speaking. – deworde Jan 27 '20 at 17:53
  • Roll your own is for business problems. Use appropriate libraries and implementation for concurrency, data storage and others, but it's up to your knowledge of the business problem to apply those constructs. It all depends on the level of abstraction. – Olaf Kock Jan 27 '20 at 20:00
  • 1
    On top of my previous comment: your original problem was not a concurrency problem, but a data /storage related one. I came up with concurrency as a hidden extra problem that needs to be solved on top. As there's no built in type solving your problem, you'll have to roll some aspect on your own, this way or another. Just don't forget to do so – Olaf Kock Jan 27 '20 at 22:13
0

I believe that Guava's Multimap [1] does what you want. You can use Rooms as keys and Persons as values. You then can have get(someRoom) to return a collection of people in that room.

[1] https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap

David Soroko
  • 8,521
  • 2
  • 39
  • 51
  • On its own this will not enforce the referential integrity. – Chris94 Jan 27 '20 at 15:39
  • True - it is not clear from the question what should happen if an attempt is made to add the same person to more than one room. Options include: throwing an exception, silently ignoring the put, moving a person from room to room. Each of those may require a custom implementation at which point one might as well iterate over all the rooms and implement the required logic – David Soroko Jan 27 '20 at 15:50
  • Added clarification. Should be moved to the new room (as in `Map.put(...)`) – deworde Jan 27 '20 at 15:55
  • In which case multimap is an OK starting point. You will need to wrap it in your custom logic. – David Soroko Jan 27 '20 at 15:58
  • By the same token, Map is a good starting point, I just wrap it in boilerplate efficiency lookups. – deworde Jan 27 '20 at 17:50
  • There is a bit of a tradeoff between how simple it is to implement the get an the put. With multimap get is trivial, with stock hashmap a bit more work is required. – David Soroko Jan 27 '20 at 17:59