eficientemente ordenar un IList <T> sin copiar la lista de fuentes

Question

Dado el caso de prueba a continuación cómo puede I:

1. Ordenar la IList<TestObject> basado en el índice de un juego Id en la lista IList<int>.
2. Los valores no coincidentes se mueven al final de la lista y se ordenan por su índice original. En este caso, dado que 3 y 4 no existen en la lista de índice, esperamos ver list[3] == 3 y list[4] == 4.
3. Aunque sé que esto se puede lograr con linq, necesito recurrir a la lista original en lugar de crear una nueva (debido a cómo se almacena la lista).
4. La lista de origen debe ser un IList (no puedo usar List<T>)

Aquí está la prueba:

public class TestObject 
    { 
     public int Id { get; set; } 
    } 

    [Test] 
    public void Can_reorder_using_index_list() 
    { 
     IList<TestObject> list = new List<TestObject> 
     { 
      new TestObject { Id = 1 }, 
      new TestObject { Id = 2 }, 
      new TestObject { Id = 3 }, 
      new TestObject { Id = 4 }, 
      new TestObject { Id = 5 } 
     }; 

     IList<int> indexList = new[] { 10, 5, 1, 9, 2 }; 

     // TODO sort 

     Assert.That(list[0].Id, Is.EqualTo(5)); 
     Assert.That(list[1].Id, Is.EqualTo(1)); 
     Assert.That(list[2].Id, Is.EqualTo(2)); 
     Assert.That(list[3].Id, Is.EqualTo(3)); 
     Assert.That(list[4].Id, Is.EqualTo(4)); 
    } 

Actualización:

Conforme a lo solicitado, esto es lo que lo probé , pero 1) solo funciona con List<T> y 2) No estoy seguro de que sea la manera más eficiente:

 var clone = list.ToList(); 
     list.Sort((x, y) => 
     { 
      var xIndex = indexList.IndexOf(x.Id); 
      var yIndex = indexList.IndexOf(y.Id); 

      if (xIndex == -1) 
      { 
       xIndex = list.Count + clone.IndexOf(x); 
      } 
      if (yIndex == -1) 
      { 
       yIndex = list.Count + clone.IndexOf(y); 
      } 

      return xIndex.CompareTo(yIndex); 
     }); 

Actualización 2:

Gracias a @leppie, @jamiec, trigo @mitch - este es el código de trabajo:

public class TestObjectComparer : Comparer<TestObject> 
    { 
     private readonly IList<int> indexList; 
     private readonly Func<TestObject, int> currentIndexFunc; 
     private readonly int listCount; 

     public TestObjectComparer(IList<int> indexList, Func<TestObject, int> currentIndexFunc, int listCount) 
     { 
      this.indexList = indexList; 
      this.currentIndexFunc = currentIndexFunc; 
      this.listCount = listCount; 
     } 

     public override int Compare(TestObject x, TestObject y) 
     { 
      var xIndex = indexList.IndexOf(x.Id); 
      var yIndex = indexList.IndexOf(y.Id); 

      if (xIndex == -1) 
      { 
       xIndex = listCount + currentIndexFunc(x); 
      } 
      if (yIndex == -1) 
      { 
       yIndex = listCount + currentIndexFunc(y); 
      } 

      return xIndex.CompareTo(yIndex); 
     } 
    } 

    [Test] 
    public void Can_reorder_using_index_list() 
    { 
     IList<TestObject> list = new List<TestObject> 
     { 
      new TestObject { Id = 1 }, 
      new TestObject { Id = 2 }, 
      new TestObject { Id = 3 }, 
      new TestObject { Id = 4 }, 
      new TestObject { Id = 5 } 
     }; 

     IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 }; 

     ArrayList.Adapter((IList)list).Sort(new TestObjectComparer(indexList, x => list.IndexOf(x), list.Count)); 

     Assert.That(list[0].Id, Is.EqualTo(5)); 
     Assert.That(list[1].Id, Is.EqualTo(1)); 
     Assert.That(list[2].Id, Is.EqualTo(2)); 
     Assert.That(list[3].Id, Is.EqualTo(3)); 
     Assert.That(list[4].Id, Is.EqualTo(4)); 
    } 

Answer 1

estado mirando esto para un poco, y de hecho dijo anteriormente, el va a necesitar ArrayList.Adapter, sin embargo se le nota que tarda un IList no genérico por lo que algunos se requerirá de calidad:

ArrayList.Adapter((IList)list) 

también debes escribir un comparador, de los cuales la lógica para hacer su clasificación willl ser contenida.Disculpe el nombre, pero:

public class WeirdComparer : IComparer,IComparer<TestObject> 
{ 
    private IList<int> order; 
    public WeirdComparer(IList<int> order) 
    { 
     this.order = order; 
    } 
    public int Compare(object x, object y) 
    { 
     return Compare((TestObject) x, (TestObject) y); 
    } 

    public int Compare(TestObject x, TestObject y) 
    { 
     if(order.Contains(x.Id)) 
     { 
      if(order.Contains(y.Id)) 
      { 
       return order.IndexOf(x.Id).CompareTo(order.IndexOf(y.Id));  
      } 
      return -1; 
     } 
     else 
     { 
      if (order.Contains(y.Id)) 
      { 
       return 1; 
      } 
      return x.Id.CompareTo(y.Id); 
     } 
    } 
} 

EDIT: Añadido aplicación a comparerr anterior

A continuación, el uso sería la siguiente:

IList<int> indexList = new[] { 10, 5, 1, 9, 2 }; 
ArrayList.Adapter((IList)list).Sort(new WeirdComparer(indexList)); 

Por cierto, this thread explica un bonito forma de convertir esto en un método de extensión que hará que su código sea más reutilizable y más fácil de leer IMO.

Answer 2

Usted puede intentar lo siguiente:

ArrayList.Adapter(yourilist).Sort(); 

actualización :

Un comparador genérico:

class Comparer<T> : IComparer<T>, IComparer 
{ 
    internal Func<T, T, int> pred; 

    public int Compare(T x, T y) 
    { 
    return pred(x, y); 
    } 

    public int Compare(object x, object y) 
    { 
    return Compare((T)x, (T)y); 
    } 
} 

static class ComparerExtensions 
{ 
    static IComparer Create<T>(Func<T, T, int> pred) 
    { 
    return new Comparer<T> { pred = pred }; 
    } 

    public static void Sort<T>(this ArrayList l, Func<T, T, int> pred) 
    { 
    l.Sort(Create(pred)); 
    } 
} 

Uso:

ArrayList.Adapter(list).Sort<int>((x,y) => x - y); 

Answer 3

Aquí hay una versión genérica del comparador. IEntity<TId> es sólo una interfaz sencilla que tiene una propiedad "ID" de tipo TId:

public class IndexComparer<T, TId> : Comparer<T> where T : IEntity<TId> where TId : IComparable 
{ 
    private readonly IList<TId> order; 
    private readonly int listCount; 
    private readonly Func<T, int> currentIndexFunc; 

    public IndexComparer(Func<T, int> currentIndexFunc, IList<TId> order, int listCount) { 
     this.order = order; 
     this.listCount = listCount; 
     this.currentIndexFunc = currentIndexFunc; 
    } 

    public override int Compare(T x, T y) 
    { 
     var xIndex = order.IndexOf(x.Id); 
     var yIndex = order.IndexOf(y.Id); 

     if (xIndex == -1) 
     { 
      xIndex = listCount + currentIndexFunc(x); 
     } 
     if (yIndex == -1) 
     { 
      yIndex = listCount + currentIndexFunc(y); 
     } 

     return xIndex.CompareTo(yIndex); 
    } 
} 

prueba de trabajo:

[TestFixture] 
public class OrderingTests 
{ 
    public class TestObject : IEntity<int> 
    { 
     public int Id { get; set; } 
    } 

    [Test] 
    public void Can_reorder_using_index_list() 
    { 
     IList<TestObject> list = new List<TestObject> 
     { 
      new TestObject { Id = 1 }, 
      new TestObject { Id = 2 }, 
      new TestObject { Id = 3 }, 
      new TestObject { Id = 4 }, 
      new TestObject { Id = 5 } 
     }; 

     IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 }; 
     ArrayList.Adapter((IList)list) 
      .Sort(new IndexComparer<TestObject, int>(x => list.IndexOf(x), indexList, list.Count)); 

     Assert.That(list[0].Id, Is.EqualTo(5)); 
     Assert.That(list[1].Id, Is.EqualTo(1)); 
     Assert.That(list[2].Id, Is.EqualTo(2)); 
     Assert.That(list[3].Id, Is.EqualTo(4)); 
     Assert.That(list[4].Id, Is.EqualTo(3)); 
    } 
} 

Esto cumple con los requisitos descritos más en mi pregunta original. Los elementos no coincidentes se mueven al final de la lista y luego se ordenan por su índice original.