Strutture dati persistenti in Java

Question

Qualcuno conosce una libreria o almeno qualche ricerca sulla creazione e l'uso di strutture di dati persistenti in Java? Non mi riferisco alla persistenza come memoria a lungo termine, ma alla persistenza in termini di immutabilità (vedi Wikipedia entry).

Attualmente sto esplorando diversi modi per modellare un'API per le strutture persistenti. Utilizzando i costruttori sembra essere una soluzione interessante:

// create persistent instance 
Person p = Builder.create(Person.class) 
      .withName("Joe") 
      .withAddress(Builder.create(Address.class) 
       .withCity("paris") 
       .build()) 
       .build(); 

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack"); 

Person p3 = Builder.update(p) 
       .withAddress(Builder.update(p.address()) 
       .withCity("Berlin") 
       .build) 
      .build(); 

Ma questo ancora si sente un po 'boilerplated. Qualche idea?

Answer 1

immagino le scelte ovvie sono:

o Passare a una struttura di dati transitoria (costruttore) per l'aggiornamento. Questo è abbastanza normale. StringBuilder per la manipolazione String ad esempio. Come esempio.

Person p3 = 
    Builder.update(p) 
    .withAddress(
     Builder.update(p.address()) 
     .withCity("Berlin") 
     .build() 
    ) 
    .build(); 

o Utilizzare sempre strutture persistenti. Anche se sembra esserci molta copia, dovresti condividere quasi tutti gli stati, quindi non è neanche lontanamente così male come sembra.

final Person p3 = p 
    .withAddress(
     p.address().withCity("Berlin") 
    ); 

o Esplodere la struttura dati in molte variabili e ricombinarsi con un costruttore enorme e confuso.

final Person p3 = Person.of(
    p.name(), 
    Address.of(
     p.house(), p.street(), "Berlin", p.country() 
    ), 
    p.x(), 
    p.y(), 
    p.z() 
); 

o Utilizzare le interfacce di richiamata per fornire i nuovi dati. Ancora più caldaia.

final Person p3 = Person.of(new PersonInfo(
    public String name () { return p.name();) 
    public Address address() { return Address.of(new AddressInfo() { 
     private final Address a = p.address(); 
     public String house () { return a.house() ; } 
     public String street() { return a.street() ; } 
     public String city () { return "Berlin" ; } 
     public String country() { return a.country(); } 
    })), 
    public Xxx  x() { return p.x(); } 
    public Yyy  y() { return p.y(); } 
    public Zzz  z() { return p.z(); } 
}); 

o Utilizzare hack brutto per rendere i campi transitoriamente disponibili per il codice.

final Person p3 = new PersonExploder(p) {{ 
    a = new AddressExploder(a) {{ 
     city = "Berlin"; 
    }}.get(); 
}}.get(); 

(Stranamente ero appena messo giù una copia di strutture di dati puramente funzionali da Chris Okasaki.)

Answer 2

E 'molto difficile, se non impossibile, per rendere le cose immutabili che non è stato progettato in modo .

Se è possibile progettare da zero:

• uso solo campi finali
• Non fare riferimento oggetti non immutabili

Answer 3

Costruttori renderanno il vostro codice di troppo prolisso per essere utilizzabili. In pratica, quasi tutte le strutture di dati immutabili che ho visto passano in stato attraverso il costruttore.Per quello che vale la pena, qui ci sono un bel serie di post che descrivono strutture di dati immutabili in C# (che dovrebbe convertire facilmente in Java):

• Part 1: Kinds of Immutability
• Part 2: Simple Immutable Stack
• Part 3: Covariant Immutable Stack
• Part 4: Immutable Queue
• Part 5: Lolz! (incluso per completezza)
• Part 6: Simple Binary Tree
• Part 7: More on Binary Trees
• Part 8: Even More on Binary Trees
• Part 9: AVL Tree Implementation
• Part 10: Double-ended Queue
• Part 11: Working Double-ended Queue Implementation

C# e Java sono estremamente prolisso, in modo che il codice in questi articoli è abbastanza spaventoso. Raccomando di imparare OCaml, F # o Scala e familiarizzare con l'immutabilità con quelle lingue. Una volta padronanza della tecnica, sarai in grado di applicare lo stesso stile di codifica a Java molto più facilmente.

Answer 4

Vuoi immutabilità:

codice

1. modo esterno non può modificare i dati?
2. quindi una volta impostato un valore non può essere modificato?

In entrambi i casi esistono modi più semplici per ottenere il risultato desiderato.

arresto codice esterno di modificare i dati è facile con interfacce:

public interface Person { 
    String getName(); 
    Address getAddress(); 
} 
public interface PersonImplementor extends Person { 
    void setName(String name); 
    void setAddress(Address address); 
} 

public interface Address { 
    String getCity(); 
} 


public interface AddressImplementor { 
    void setCity(String city); 
} 

per interrompere modifiche a un valore impostato volta è anche "easy" utilizzando java.util.concurrent.atomic.AtomicReference (sebbene sospensione o qualche altro la persistenza utilizzo strato può essere necessario modificare):

class PersonImpl implements PersonImplementor { 
    private AtomicReference<String> name; 
    private AtomicReference<Address> address; 

    public void setName(String name) { 
     if (!this.name.compareAndSet(name, name) 
      && !this.name.compareAndSet(null, name)) { 
      throw new IllegalStateException("name already set to "+this.name.get()+" cannot set to "+name); 
     } 
    } 
    // .. similar code follows.... 
} 

Ma perché avete bisogno di qualcosa di più di una semplice interfaccia per realizzare il compito?

Answer 5

Dai un'occhiata allo Functional Java. Datastructures persistenti attualmente forniti includono:

• lista semplicemente legata (fj.data.List)
• Pigro lista semplicemente legata (fj.data.Stream)
• lista non vuota (fj.data.NonEmptyList)
• valore facoltativo (un contenitore di lunghezza 0 o 1) (fj.data.Option)
• Set (fj.data.Set)
• Multi-modo di albero (albero rosa aka) (fj.data.Tree
• Mappa immutabile (fj.data.TreeMap)
• Prodotti (tuple) di genere 1-8 (fj.P1 ..P8)
• Vettori di arietà 2-8 (fj.data.vector.V2..V8)
• lista punta (fj.data.Zipper)
• albero di punta (fj.data.TreeZipper)
• type-safe, generico lista eterogenea (fj.data.hlist.HList)
• array immutabili (fj.data.Array)
• Disgiunte unione tipo di dati (fj.data.Either)

Un certo numero di esempi di utilizzo sono forniti con la distribuzione binaria. La fonte è disponibile con una licenza BSD da Google Code.

Answer 6

seguire una molto semplice provvisorio con delega dinamica:

class ImmutableBuilder { 

    static <T> T of(Immutable immutable) { 
     Class<?> targetClass = immutable.getTargetClass(); 
     return (T) Proxy.newProxyInstance(targetClass.getClassLoader(), 
      new Class<?>[]{targetClass}, 
      immutable); 
    } 

    public static <T> T of(Class<T> aClass) { 
     return of(new Immutable(aClass, new HashMap<String, Object>())); 
    } 
} 

class Immutable implements InvocationHandler { 

    private final Class<?> targetClass; 
    private final Map<String, Object> fields; 

    public Immutable(Class<?> aTargetClass, Map<String, Object> immutableFields) { 
     targetClass = aTargetClass; 
     fields = immutableFields; 
    } 

    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable { 
     if (method.getName().equals("toString")) { 
      // XXX: toString() result can be cached 
      return fields.toString(); 
     } 

     if (method.getName().equals("hashCode")) { 
      // XXX: hashCode() result can be cached 
      return fields.hashCode(); 
     } 

     // XXX: naming policy here 
     String fieldName = method.getName(); 

     if (method.getReturnType().equals(targetClass)) { 
      Map<String, Object> newFields = new HashMap<String, Object>(fields); 
      newFields.put(fieldName, args[0]); 
      return ImmutableBuilder.of(new Immutable(targetClass, newFields)); 
     } else { 
      return fields.get(fieldName); 
     } 
    } 

    public Class<?> getTargetClass() { 
     return targetClass; 
    } 
} 

di utilizzo:

interface Person { 
    String name(); 
    Person name(String name); 
    int age(); 
    Person age(int age); 
} 

public class Main { 

    public static void main(String[] args) { 
     Person mark = ImmutableBuilder.of(Person.class).name("mark").age(32); 
     Person john = mark.name("john").age(24); 
     System.out.println(mark); 
     System.out.println(john); 
    } 
} 

crescere direzioni:

• denominazione politica (getName, withName, nome)
• caching toString(), hashCode()
• equals() implementazioni dovrebbe essere semplice (anche se non implementato)

Speranza che aiuta :)

Answer 7

ho implementato un paio di strutture di dati persistenti in Java. Tutti open source (GPL) su Google Code per chiunque sia interessato:

http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent

I principali quelli che ho finora sono:

• prova mutevole persistente oggetto
• hash persistente Mappe
• Vettori/elenchi persistenti
• Set persistenti (incluso un set persistente specializzato di interi)

Answer 8

Google Guava ora ospita una varietà di immutable/persistent data structures.