[C#/Vari] - Merge di N alberi con mapping table

[Kralizek]

Prima di tutto, ho taggato il topic come "vari" perché mi interessa anche un semplice consiglio algoritmico, al di lá della pura implementazione in C#.

Problema:
nel database ho una view che é composta dai field ( IndexID, PlaceID, Name, ParentID, SiteID ) e che, per ciascun valore di IndexID, puó contenere diversi alberi univoci per SiteID.
in breve, un Index puó essere genereato da diversi Site e ogni Site ha il suo proprio albero (di fatto esiste una "Stoccolma" per ciascun Site).

Ora sto scrivendo una funzione che, per ciascun Index, dati gli alberi di ciascun Site, genera un unico albero utilizzando una tabella di mapping.

La logica del merge dovrebbe essere la seguente:
- se il nodo C1 é mappato al nodo D1, si usa il nodo D1 e si attaccano i figli del nodo C1 al nodo D1

fin qui tutto facile vero?

bene, ora considerate questo, il nodo C13 (ovvero il terzo sottonodo del nodo C1), puó essere mappato al nodo D2. In questo caso deve essere rimosso dalla lista dei sottonodi D1.

Piú interessante ora vero? ;)

Ed ora del sano codice.

Iniziamo con le classi "contenitore"


public class PlaceRow
{
public int IndexID { get; set; }
public int PlaceID { get; set; }
public string Name { get; set; }
public int? ParentID { get; set; }
public int SiteID { get; set; }
}

public class Place
{
public int ID { get; set; }
public string Name { get; set; }
public IEnumerable<Place> Places { get; set; }
}

public class Mapping
{
public int SourceID { get; set; }
public int DestinationID { get; set; }
}


Riporto una versione "concettuale" del Main


void Main()
{
IEnumerable<PlaceRow> placeRows = GetPlaceRows(93);

IEnumerable<IEnumerable<Place>> placeTrees = LoadTrees(placeRows);

IEnumerable<Mapping> mappings = GetMappings();

IEnumerable<Place> mergedTrees = MergeTrees(placeTrees, mappings);
}


ovviamente il tutto sta nella funzione MergeTrees.


public IEnumerable<Place> MergeTrees (IEnumerable<IEnumerable<Place>> places, IEnumerable<Mapping> mappings)
{
var map = mappings.ToDictionary(k => k.SourceID, v => v.DestinationID);
throw new NotImplementedException("Epic fail");
}


come giá detto, non é che sto a chiedere codice. Mi basta qualche suggerimento sull'algoritmo da seguire.

La prima parte é banale. Per ciascuna lista, la si cicla e si controlla se qualche elemento é mappato. nel caso si aggiunge la lista di sottonodi al nodo di destinazione.

Il problema é con i sottonodi mappati :S

Grazie :)

[Kralizek]

Risolto! Cambiando totalmente approccio il problema era letteralmente banale.


void Main()
{
IEnumerable<PlaceRow> placeRows = GetPlaceRows(93);

IEnumerable<Mapping> mappings = GetMappings();

IEnumerable<PlaceRow> mergedRows = MergeRows(placeRows, mappings);

IEnumerable<Place> placeTree = LoadTrees(mergedRows);
}

public IEnumerable<Place> LoadTrees(IEnumerable<PlaceRow> rows)
{
Func<PlaceRow, ILookup<int?, PlaceRow>, Place> transform = null;

transform = (row, grp) =>
{
Place place = new Place
{
ID = row.PlaceID,
Name = row.Name,
Places = from gr in grp[row.PlaceID]
select transform(gr, grp)
};

return place;
};

var lookup = rows.ToLookup( k=> k.ParentID);

return from row in lookup[null]
select transform(row, lookup);
}

public IEnumerable<PlaceRow> MergeRows(IEnumerable<PlaceRow> rows, IEnumerable<Mapping> mappings)
{
var map = mappings.ToDictionary(k => k.SourceID, v => v.DestinationID);

List<PlaceRow> newRowSet = new List<PlaceRow>();

foreach (var row in rows)
{
if (!map.ContainsKey(row.PlaceID))
{
newRowSet.Add(row);

if (row.ParentID.HasValue && map.ContainsKey(row.ParentID.Value))
row.ParentID = map[row.ParentID.Value];
}
}

return newRowSet;
}


Come potete vedere, lavorando sui dati estratti dal database anzicché sugli alberi, la situazione é molto piú facile da gestire

In realtá mentre lo commentavo con un collega, per un nanosecondo avevo intravisto uno scenario non gestito. Ma me lo sono perso :muro: