¿cómo puedo crear una lista doblemente inmutable verdaderamente inmóvil en C#?

Question

Es más una pregunta teórica: ¿es posible por cualquier medio en C# crear una lista doblemente inmutable verdaderamente inmóvil? Un problema que veo es la dependencia mutua de 2 nodos adyacentes.

Por "verdad" me refiero al uso de campos readonly.

Answer 1

Esto es posible hacer con lógica de constructor complicada. Por ejemplo

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í, se puede hacer un objeto "link-setter" que se utiliza para establecer los enlaces, que se envía al constructor del nodo, o tener una estática crean método que devuelve el "eslabón sets ". Los enlaces en el nodo son privados, y solo se puede acceder a ellos a través del "establecedor de enlaces", y cuando los ha utilizado para configurar la lista, los descarta.

Sin embargo, es un ejercicio bastante inútil. Si la lista es inmutable, no tiene sentido utilizar una lista doblemente vinculada cuando una matriz simple funciona mejor.

Answer 3

Has despertado mi curiosidad. La clase de ReadOnlyNode es lo suficientemente simple para definir:

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; 
    } 
} 

El problema con readonly en una lista doblemente enlazada es que, para cada nodo, se tiene que especificar los nodos anteriores y siguientes de ese nodo en el constructor, por lo si se pasan desde fuera del constructor, ya deben existir. Pero, el nodo M necesita un nodo N preexistente como su "siguiente" nodo cuando llama al constructor, pero ese nodo N necesita M como su nodo "anterior" para poder construirse. Esto crea una situación de "gallina y huevo" donde tanto N como M necesitan que el otro nodo sea instanciado primero.

Sin embargo, hay más de una manera de despellejar a este gato. ¿Qué ocurre si cada nodo de una lista se instancia de manera recursiva desde el constructor de un ReadOnlyNode? Hasta que cada constructor estuviera completo, las propiedades en cada nivel seguirían siendo mutables, y la referencia a cada nodo existiría en su constructor, por lo que no importaría que no todo se haya configurado hasta que todo esté configurado. El código siguiente se compila, y se le dio un pre-existente IEnumerable producirá un inmutable lista doblemente enlazada:

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)); 

Usted puede usar esto con cualquier colección que implementa IEnumerable (casi todos los incorporados en las colecciones de hacer, y usted puede usar OfType() para convertir ICollections e IEnumerables no genéricos en IEnumerables genéricos). Lo único de lo que preocuparse es la pila de llamadas; hay un límite en la cantidad de llamadas a métodos que puede anidar, lo que puede causar una SOE en una lista finita pero grande de entradas.

EDITAR: JaredPar trae a colación un muy buen punto; esta solución usa Count() y Any() que tienen que tener en cuenta los resultados de Skip(), por lo que no pueden usar los "accesos directos" integrados en estos métodos que pueden usar la propiedad de cardinalidad de una clase de colección. Esas llamadas se vuelven lineales, lo que cuadra la complejidad del algoritmo. Si sólo utiliza los miembros básicos de IEnumerable en su lugar, esto se convierte en mucho más 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 esta solución, se pierde un poco de la más elegante de comprobación de errores, pero si el IEnumerable es nula una excepción tendría sido arrojado de todos modos.