LINQ ordina un elenco semplice in base all'infanzia

Question

Attualmente sto cercando di capire un buon modo per ordinare i miei elementi con LINQ e C#, ma non riesco a farlo.

Per il problema cerchiamo suppone che si abbia la seguente tabella

---TempTable 
ID (int) 
ParentID (int) 
Name (varchar) 
SortOrder (int) 

L'ID e ParentID sono legati gli uni agli altri e mi danno una struttura di dati gerarchica sé. Gli elementi radice hanno un valore null nel campo ID. Il SortOrder è solo una parte dell'intera tabella e basato sul ParentID, quindi gli elementi che condividono lo stesso ParentID hanno 1, 2, 3 in esso.

lascia supporre ulteriormente i seguenti dati:

ID = 1 
ParentID = null 
Name = Test 1 
SortOrder = 1 

ID = 2 
ParentID = 1 
Name = Test 2 
SortOrder = 1 

ID = 3 
ParentID = 1 
Name = Test 3 
SortOrder = 2 

ID = 4 
ParentID = 2 
Name = Test 4 
SortOrder = 1 

Mia lista piatto desiderato dovrebbe avere il seguente ordine:

Test 1 //root element with sort order 1 = very top 
Test 2 //child element of root with sort order 1 
Test 4 //child element of test 2 with sort order 1 
Test 3 //child element of root with sort order 2 

Inoltre mi piace per ottenere l'oggetto in sé, senza ottenere solo una parte delle informazioni ha gettato l'uso di selezionare nuovo ...

Questo è uno dei miei tentativi falliti:

from x in EntityModel.TempTables //DbSet<TempTable> by EntityFramework - which already holds all elements 
    orderby x.SortOrder 
    from y in x.TempTableChildren //Navigation Property by EntityFramework 
    orderby y.SortOrder 
    select y 

Grazie in anticipo per il vostro aiuto.

Edit:

L'ordine con il ParentID forse disponibile, con il dato TestData, l'ID, ParentIDs sono in perfetto ordine, ma questo non è il caso in un'applicazione reale dal vivo in quanto i suoi dati driven, qualcuno potrebbe eliminare una voce di crearne uno nuovo e metterlo in un certo ordine sotto un genitore e si dovrebbe avere qualcosa di simile:

ID = 193475037 
ParentID = 2 
Name = Test 192375937 
SortOrder = 25 

Ora nell'applicazione sarebbe possibile spostare questa e la ParentID e SortOrder cambierebbe in modo casuale a qualcosa di simile:

ID = 193475037 
ParentID = 456798424 
Name = Test 192375937 
SortOrder = 4 

Per spiegare furhter il problema qui è un codice - come farei senza 1 bellissima Linq Query ma con 2 e alcuni dei rendimenti:

public class LinqTestDemo 
{ 
    Random rand = new Random(); 
    List<TempTable> list = new List<TempTable>(); 

    public List<TempTable> GetFlatData() 
    { 
     list = GetTestData(); 

     var rootElement = (from x in list 
          where x.ParentID == null 
          orderby x.SortOrder 
          select x).ToList(); 

     var flatList = OrderChilds(rootElement).ToList(); 

     foreach (var tempTable in flatList) 
     { 
      Console.WriteLine(string.Format("ID = {0} - ParentID = {1} - Name = {2} - SortOrder = {3}", tempTable.ID, tempTable.ParentID, tempTable.Name, tempTable.SortOrder)); 
     } 

     return flatList; 
    } 

    private IEnumerable<TempTable> OrderChilds(List<TempTable> enumerable) 
    { 
     foreach (var tempTable in enumerable) 
     { 
      yield return tempTable; 

      TempTable table = tempTable; 
      var childs = OrderChilds((from x in list 
             where x.ParentID == table.ID 
             orderby x.SortOrder 
             select x).ToList()); 

      foreach (var child in childs) 
      { 
       yield return child; 
      } 
     } 
    } 

    public List<TempTable> GetTestData() 
    { 
     var returnValue = new List<TempTable>(); 
     for (int i = 0; i < 50; i++) 
     { 
      var tempTable = new TempTable(); 
      tempTable.ID = i; 
      if (i == 0) 
       tempTable.ParentID = null; 
      else 
       tempTable.ParentID = rand.Next(0, i); 

      var maxSortOrder = (from x in returnValue 
           where x.ParentID == tempTable.ParentID 
           select (int?)x.SortOrder).Max(); 

      if (maxSortOrder.HasValue) 
       tempTable.SortOrder = maxSortOrder.Value + 1; 
      else 
       tempTable.SortOrder = 1; 

      tempTable.Name = string.Format("Test {0:00}", i); 
      returnValue.Add(tempTable); 
     } 

     return returnValue; 
    } 

    public class TempTable 
    { 
     public int ID { get; set; } 
     public int? ParentID { get; set; } 
     public string Name { get; set; } 
     public int SortOrder { get; set; } 
    } 
} 

@ breadth-first vs Depth-First Traversal: Dopo alcune letture direi che il mio risultato desiderato sarebbe Attraversamento di profondità, dove gli elementi alla stessa profondità di livello dovrebbero essere ordinati dalla proprietà SortOrder.

Answer 1

public lEnumerable<TempTable> GetList(int? parentID = null){ 

    foreach (var item in Context.TempTables 
     .Where(x => x.ParentID == parentID) 
     .OrderBy(x=> x.SortOrder) 
     .ToList() { 

     yield return item; 

     foreach(var child in GetList(item.ID)) 
     { 
      yield return child; 
     } 

    } 
    } 


    var sortedList = GetList(); 

È simile al tuo metodo ma è più piccolo & ricorsiva. E funziona per molti livelli di profondità. Preferisco chiamare ToList perché chiuderà il set di risultati prima di eseguire una query successiva.

Non esiste un modo per farlo in una singola query al momento.

Con singola query come richiesto

Entity Framework riempirà automaticamente tutti i bambini.

public IEnumerable<TempTable> PrepareList(IEnumerable<TempTable> list){ 
    list = list.OrderBy(x=> x.SortOrder); 
    foreach(var item in list){ 
     yield return item; 
     foreach(var child in PrepareList(item.ChildTempTables)){ 
      yield return child; 
     } 
    } 
} 

// since EF will automatically fill each children on fetch 
// all we need is just a top level nodes 
// which we will pass to PrepareList method 
var list = Context.TempTables.ToList().Where(x=> x.ParentID == null); 
var sortedList = PrepareList(list).ToList(); 

// it is good to create list at the end if you are going to 
// iterate it many times and logic will not change. 

Answer 2

Prova questo:

public class Item 
{ 
    public int ID { get; set; } 
    public int? ParentID { get; set; } 
    public string Name { get; set; } 
    public int SortOrder { get; set; } 
} 

public void DoWork() 
    { 
     Item[] data = new Item[] { 
      new Item() { ID = 2, ParentID = 1, Name = "Test 2", SortOrder = 1}, 
      new Item() { ID = 3, ParentID = 1, Name = "Test 3", SortOrder = 2}, 
      new Item() { ID = 4, ParentID = 2, Name = "Test 4", SortOrder = 1}, 
      new Item() { ID = 1, ParentID = null, Name = "Test 1", SortOrder = 1}, 
     }; 

     var result = from x in data 
        orderby x.SortOrder, x.ParentID 
        select x; 

     foreach (var row in result.ToArray()) 
     { 
      Console.WriteLine(row.Name); 
     } 
    } 

Credo che sia tutta una questione di buon ordinamento

Answer 3

Ecco una soluzione semplice:

public class TempTable 
{ 
    public int ID {get;set;} 
    public int? ParentID {get;set;} 
    public String Name {get;set;} 
    public int SortOrder {get;set;} 
} 

public List<TempTable> GetTempData() 
{ 
    var temp = new List<TempTable>(); 
    temp.Add(new TempTable { ID = 1, ParentID = null, Name = "Test 1", SortOrder = 1 }); 
    temp.Add(new TempTable { ID = 2, ParentID = 1, Name = "Test 2", SortOrder = 1 }); 
    temp.Add(new TempTable { ID = 3, ParentID = 1, Name = "Test 3", SortOrder = 3 }); 
    temp.Add(new TempTable { ID = 4, ParentID = 2, Name = "Test 4", SortOrder = 1 }); 
    temp.Add(new TempTable { ID = 5, ParentID = 1, Name = "Test 5", SortOrder = 2 }); 
    return temp; 
} 

Usage:

var data = GetTempData(); 
var result = data.OrderBy(d => d.SortOrder).ThenBy(d => d.ParentID); 
//Do something with result 

Answer 4

Ecco una versione non ricorsiva. Non verrà ripetuto più e più volte nell'elenco iniziale. Invece mantiene un dizionario per la relazione genitore-figlio e memorizza la posizione corrente della traversata dell'albero in pre-ordine in corso negli enumeratori.

public static IEnumerable<TempTable> PreorderForest(IEnumerable<TempTable> list) 
{ 
    var nodesByParent = list.GroupBy(x => x.ParentID.GetValueOrDefault(-1)) 
     .ToDictionary(xs => xs.Key, 
         xs => xs.OrderBy(x => x.SortOrder).GetEnumerator()); 

    var stack = new Stack<IEnumerator<TempTable>>(); 
    stack.Push(nodesByParent[-1]); 

    while (stack.Count > 0) 
    { 
     var nodes = stack.Peek(); 
     if (nodes.MoveNext()) 
     { 
      yield return nodes.Current; 
      IEnumerator<TempTable> children; 
      if (nodesByParent.TryGetValue(nodes.Current.ID, out children)) 
       stack.Push(children); 
     } 
     else 
      stack.Pop(); 
    } 
} 

Answer 5

In realtà io non so se potrebbe essere fatto da eleganti query LINQ. Ecco la versione ricorsiva della DFS, si costruisce di ricerca per accelerare la ricerca per ParentID

public static IEnumerable<TempTable> SortedList(IEnumerable<TempTable> list = null, int? ParentID = null, ILookup<int?, TempTable> lookup = null) 
{ 
    if (lookup == null) 
     lookup = list.ToLookup(x => x.ParentID, x => x); 

    foreach (var p in lookup[ParentID].OrderBy(x => x.SortOrder)) 
    { 
     yield return p; 
     foreach (var c in SortedList(lookup: lookup, ParentID: p.ID)) 
      yield return c; 
    } 
}