Clase de colección similar a una base de datos simple en Java

Question

El problema: mantener una relación bidireccional de muchos a uno entre los objetos de Java.

Algo así como mapas de Google/bidi los Commons Collections, pero quiero permiten valores duplicados en el lado delantero, y tienen conjuntos de las claves de futuro como los valores reverso. Se utiliza algo como esto:

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

Los enfoques simples de Java son: 1. Mantener un solo lado de la relación, ya sea como un Map<Location, Region> o una Map<Region, Set<Location>>, y recoger la relación inversa por iteración cuando sea necesario; O, 2. Para crear un contenedor que mantenga los Mapas de ambos lados e interceptar todas las llamadas mutantes para mantener sincronizados a ambos lados.

1 es O (n) en lugar de O (log n), que se está convirtiendo en un problema. Empecé en 2 y estaba en las malezas inmediatamente. (¿Sabe cuántas formas diferentes hay para alterar una entrada en el Mapa?)

Esto es casi trivial en el mundo sql (la tabla de Ubicación obtiene una columna Indexada indexada). ¿Hay algo obvio que me falta que hace que sea trivial para los objetos normales?

Answer 1

Creo que puede lograr lo que necesita con las siguientes dos clases. Si bien involucra dos mapas, no están expuestos al mundo exterior, por lo que no debería haber una forma de que se desincronicen. En cuanto a almacenar el mismo "hecho" dos veces, no creo que lo solucione en una implementación eficiente, ya sea que el hecho se haya almacenado dos veces de forma explícita como lo está aquí, o implícitamente como lo estaría cuando su base de datos cree un índice para hacer combinaciones más eficientes en sus 2 tablas. puede agregar cosas nuevas al magicset y actualizará ambas asignaciones, o puede agregar cosas al magicmapper, que luego actualizará el mapa inverso de forma automática. La novia me está llamando a la cama ahora, así que no puedo ejecutar esto a través de un compilador, debería ser suficiente para que comiences. ¿Qué rompecabezas estás tratando de resolver?

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 
} 


} 

Answer 2

Podría malinterpretar su modelo, pero si su Ubicación y Región tienen equals() correctos y hashCode() implementados, entonces el conjunto de Ubicación -> Región es simplemente una implementación clásica de Mapa (varias claves distintas pueden apuntar a mismo valor de objeto). La región -> Conjunto de ubicación es una Multimap (disponible en Google Coll.). Puede componer su propia clase con los métodos adecuados de agregar/quitar para manipular ambos submapas.

Quizás una exageración, pero también podría usar el servidor sql en memoria (HSQLDB, etc.). Le permite crear índices en muchas columnas.