Come posso creare una lista doppiamente immutabile in C#?

Question

È più una questione teorica: è possibile con C# in qualsiasi modo creare una lista doppiamente immutabile? Un problema, a mio avviso, è nella reciproca dipendenza di 2 nodi adiacenti.

Con "veramente" intendo utilizzare campi di sola lettura.

Answer 1

Questo è possibile fare con la logica del costruttore difficile. Per esempio

public sealed class Node<T> { 
    readonly T m_data; 
    readonly Node<T> m_prev; 
    readonly Node<T> m_next; 

    // Data, Next, Prev accessors omitted for brevity  

    public Node(T data, Node<T> prev, IEnumerator<T> rest) { 
    m_data = data; 
    m_prev = prev; 
    if (rest.MoveNext()) { 
     m_next = new Node(rest.Current, this, rest); 
    } 
    } 
} 

public static class Node {  
    public static Node<T> Create<T>(IEnumerable<T> enumerable) { 
    using (var enumerator = enumerable.GetEnumerator()) { 
     if (!enumerator.MoveNext()) { 
     return null; 
     } 
     return new Node(enumerator.Current, null, enumerator); 
    } 
    } 
} 

Node<string> list = Node.Create(new [] { "a", "b", "c", "d" }); 

Answer 2

Sì, si può fare un oggetto "link-setter" utilizzato per l'impostazione dei collegamenti, che si invia al costruttore del nodo, o hanno metodo che restituisce il "link-setter uno statico creare ". I collegamenti nel nodo sono privati ​​e sono accessibili solo tramite "link-setter" e, quando li hai utilizzati per impostare l'elenco, li butti via.

Tuttavia, questo è un esercizio piuttosto inutile. Se la lista è immutabile, è inutile usare una lista doppiamente collegata quando un array semplice funziona meglio.

Answer 3

Hai stuzzicato la mia curiosità. La classe di un ReadOnlyNode è abbastanza semplice da definire:

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    public Node(T value, ReadOnlyNode<T> next, ReadOnlyNode<T> prev) 
    { 
     Value = value; 
     Next = next; 
     Prev = prev; 
    } 
} 

Il problema con readonly in una lista doppiamente concatenata è che, per ogni nodo, è necessario specificare i nodi precedenti e successivi di quel nodo nel costruttore, in modo se sono passati dall'esterno del costruttore, devono già esistere. Ma, il nodo M ha bisogno di un nodo N preesistente come nodo "successivo" quando si chiama il costruttore, ma quel nodo N ha bisogno di M come nodo "precedente" per essere costruito. Ciò crea una situazione di "gallina e uovo" in cui sia N che M hanno bisogno che l'altro nodo venga istanziato per primo.

Tuttavia, c'è più di un modo per skinare questo gatto. Cosa accadrebbe se ogni nodo di una lista fosse istanziato ricorsivamente dal costruttore di un ReadOnlyNode? Fino a quando ogni costruttore era completo, le proprietà a ogni livello sarebbero ancora mutabili e il riferimento a ciascun nodo esisterebbe nel suo costruttore, quindi non importa che non sia stato impostato tutto fino a quando non è stato impostato tutto. Il seguente codice compilato, e dato un pre-esistente IEnumerable produrrà un immutabile lista doppiamente collegata:

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    private ReadOnlyNode(IEnumerable<T> elements, ReadOnlyNode<T> prev) 
    { 
     if(elements == null || !elements.Any()) 
      throw new ArgumentException(
       "Enumerable must not be null and must have at least one element"); 
     Next = elements.Count() == 1 
      ? null 
      : new ReadOnlyNode<T>(elements.Skip(1), this); 
     Value = elements.First(); 
     Prev = prev; 
    } 

    public ReadOnlyNode(IEnumerable<T> elements) 
     : this(elements, null) 
    { 
    } 
} 


//Usage - creates an immutable doubly-linked list of integers from 1 to 1000 
var immutableList = new ReadOnlyNode<int>(Enumerable.Range(1,1000)); 

è possibile utilizzare questo con qualsiasi collezione che implementa IEnumerable (praticamente tutto built-in collezioni fare, e si può usare OfType() per trasformare ICollections e IEnumerables non generici in IEnumerables generici). L'unica cosa di cui preoccuparsi è lo stack delle chiamate; c'è un limite al numero di chiamate al metodo che è possibile annidare, il che può causare un SOE su un elenco limitato ma di input.

MODIFICA: JaredPar mostra un ottimo punto; questa soluzione usa Count() e Any() che devono prendere in considerazione i risultati di Skip(), e quindi non possono usare le "scorciatoie" incorporate in questi metodi che possono usare la proprietà di cardinalità di una classe di raccolta. Quelle chiamate diventano lineari, che quadrano la complessità dell'algoritmo. Se si utilizza i componenti di base di IEnumerable, invece, questo diventa molto più performante:

public class ReadOnlyNode<T> 
{ 
    public readonly T Value; 
    public readonly ReadOnlyNode<T> Next; 
    public readonly ReadOnlyNode<T> Prev; 

    private ReadOnlyNode(IEnumerator<T> elements, ReadOnlyNode<T> prev, bool first) 
    { 
     if (elements == null) throw new ArgumentNullException("elements"); 

     var empty = false; 
     if (first) 
      empty = elements.MoveNext(); 

     if(!empty) 
     { 
      Value = elements.Current; 
      Next = elements.MoveNext() ? new ReadOnlyNode<T>(elements, this, false) : null; 
      Prev = prev; 
     } 
    } 

    public ReadOnlyNode(IEnumerable<T> elements) 
     : this(elements.GetEnumerator(), null, true) 
    { 
    } 
} 

Con questa soluzione, si perde un po 'di più elegante di controllo degli errori, ma se l'IEnumerable è nullo un'eccezione avrebbe stato comunque lanciato.