Classe di raccolta semplice simile a un database in Java

Question

Il problema: mantenere una relazione bidirezionale bidirezionale tra gli oggetti java.

qualcosa come il Google/Commons Collezioni mappe bidi, ma voglio consentire valori duplicati sul lato in avanti, e hanno set dei tasti avanti come i valori di rovescio. qualcosa di usato in questo modo:

// 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 */ } 

Le semplici approcci Java sono: 1. Per mantenere solo un lato della relazione, sia come Map<Location, Region> o un Map<Region, Set<Location>>, e raccogliere la relazione inversa per iterazione quando necessario; Oppure 2. Creare un wrapper che mantenga le mappe di entrambe le parti e intercettare tutte le chiamate mutanti per mantenere sincronizzati entrambi i lati.

1 è O (n) invece di O (log n), che sta diventando un problema. Ho iniziato il 2 e sono stato subito tra le erbacce. (Sapere quanti modi diversi ci sono per modificare una voce Mappa?)

Questo è quasi banale nel mondo sql (la tabella di posizione ottiene una colonna RegionID indicizzata). C'è qualcosa di ovvio che mi manca che lo rende banale per gli oggetti normali?

Answer 1

Penso che potresti ottenere ciò di cui hai bisogno con le seguenti due classi. Mentre coinvolge due mappe, non sono esposte al mondo esterno, quindi non ci dovrebbe essere un modo per loro di uscire dalla sincronizzazione. Per quanto riguarda la memorizzazione dello stesso "fatto" due volte, non penso che lo risolverete in qualsiasi implementazione efficiente, indipendentemente dal fatto che il fatto venga archiviato due volte esplicitamente come è qui, o implicitamente come lo sarebbe quando il database crea un indice per rendere i join più efficienti sui tuoi 2 tavoli. puoi aggiungere nuove cose al magicset e aggiornerà entrambe le mappature, oppure puoi aggiungere cose al magicmapper, che aggiornerà quindi la mappa inversa auotmaticamente. La ragazza mi sta chiamando a letto ora, quindi non posso eseguire questo attraverso un compilatore - dovrebbe essere sufficiente per iniziare. che rompicapo stai cercando di risolvere?

Answer 2

Potrei fraintendere il tuo modello, ma se la tua posizione e la tua regione hanno implementato equals() e hashCode() implementati, l'insieme di Location -> Region è solo una classica implementazione di una mappa (più chiavi distinte possono puntare al stesso valore dell'oggetto). La Regione -> Set of Location è un Multimap (disponibile in Google Coll.). È possibile comporre la propria classe con i metodi di aggiunta/rimozione appropriati per manipolare entrambi i submap.

Forse un overkill, ma è anche possibile utilizzare il server sql in-memory (HSQLDB, ecc.). Ti permette di creare indici su molte colonne.