Simple database-like collection class in Java.

Question

The problem: Maintain a bidirectional many-to-one relationship among java objects.

Something like the Google/Commons Collections bidi maps, but I want to allow duplicate values on the forward side, and have sets of the forward keys as the reverse side values. Used something like this:

// maintaining disjoint areas on a gameboard. Location is a space on the
// gameboard; Regions refer to disjoint collections of Locations.

MagicalManyToOneMap<Location, Region> forward = // the game universe
Map<Region, <Set<Location>>> inverse = forward.getInverse(); // live, not a copy
Location parkplace = Game.chooseSomeLocation(...);
Region mine = forward.get(parkplace); // assume !null; should be O(log n)
Region other = Game.getSomeOtherRegion(...);
// moving a Location from one Region to another:
forward.put(parkplace, other);
// or equivalently:
inverse.get(other).add(parkplace); // should also be O(log n) or so
// expected consistency:
assert ! inverse.get(mine).contains(parkplace);
assert forward.get(parkplace) == other;
// and this should be fast, not iterate every possible location just to filter for mine:
for (Location l : mine) { /* do something clever */ }

The simple java approaches are: 1. To maintain only one side of the relationship, either as a Map<Location, Region> or a Map<Region, Set<Location>>, and collect the inverse relationship by iteration when needed; Or, 2. To make a wrapper that maintains both sides' Maps, and intercept all mutating calls to keep both sides in sync.

1 is O(n) instead of O(log n), which is becoming a problem. I started in on 2 and was in the weeds straightaway. (Know how many different ways there are to alter a Map entry?)

This is almost trivial in the sql world (Location table gets an indexed RegionID column). Is there something obvious I'm missing that makes it trivial for normal objects?

Answer 1

I might misunderstand your model, but if your Location and Region have correct equals() and hashCode() implemented, then the set of Location -> Region is just a classical simple Map implementation (multiple distinct keys can point to the same object value). The Region -> Set of Location is a Multimap (available in Google Coll.). You could compose your own class with the proper add/remove methods to manipulate both submaps.

Maybe an overkill, but you could also use in-memory sql server (HSQLDB, etc). It allows you to create index on many columns.

Answer 2

I think you could achieve what you need with the following two classes. While it does involve two maps, they are not exposed to the outside world, so there shouldn't be a way for them to get out of sync. As for storing the same "fact" twice, I don't think you'll get around that in any efficient implementation, whether the fact is stored twice explicitly as it is here, or implicitly as it would be when your database creates an index to make joins more efficient on your 2 tables. you can add new things to the magicset and it will update both mappings, or you can add things to the magicmapper, which will then update the inverse map auotmatically. The girlfriend is calling me to bed now so I cannot run this through a compiler - it should be enough to get you started. what puzzle are you trying to solve?

public class MagicSet<L> {
   private Map<L,R> forward;
   private R r;
   private Set<L> set;

   public MagicSet<L>(Map forward, R r) {
       this.forward = map;
       this.r = r;
       this.set = new HashSet<L>();
   }

   public void add(L l) {
       set.add(l);
       forward.put(l,r);
   }

   public void remove(L l) {
       set.remove(l);
       forward.remove(l);
   }

   public int size() {
       return set.size();
   }

   public in contains(L l){
       return set.contains(l);
   }

   // caution, do not use the remove method from this iterator. if this class was going
   // to be reused often you would want to return a wrapped iterator that handled the remove method properly.  In fact, if you did that, i think you could then extend AbstractSet and MagicSet would then fully implement java.util.Set.
   public Iterator iterator() {
       return set.iterator();  
   }
}



public class MagicMapper<L,R> { // note that it doesn't implement Map, though it could with some extra work.  I don't get the impression you need that though.
 private Map<L,R> forward;
 private Map<R,MagicSet<L>> inverse;

 public MagicMapper<L,R>() {
       forward = new HashMap<L,R>;
       inverse = new HashMap<R,<MagicSet<L>>;
 }


 public R getForward(L key) {
       return forward.get(key);
 }


 public Set<L> getBackward(R key) {
       return inverse.get(key);  // this assumes you want a null if
                               // you try to use a key that has no mapping.  otherwise you'd return a blank MagicSet
 }

 public void put (L l, R r) {

       R oldVal = forward.get(l);

       // if the L had already belonged to an R, we need to undo that mapping
       MagicSet<L> oldSet = inverse.get(oldVal);

       if (oldSet != null) {oldSet.remove(l);}

       // now get the set the R belongs to, and add it.
       MagicSet<L> newSet = inverse.get(l);

       if (newSet == null) {
               newSet = new MagicSet<L>(forward, r);
               inverse.put(r,newSet);
       }
       newSet.add(l);  // magically updates the "forward" map
 }


}