Merge elements in list by property

Question

Context

I have a list of time intervals. Time interval type is HistoMesures.

Each HistoMesure is defined by a Debut (begin) property, a Fin (end) property, and a Commentaires (a little note) property.

My list is made in such a way that :

• All HistoMesure are exclusive, I mean that they can't be overlapping each other.
• The list is sorted by Debut, so by the beggining of the interval.
• Edit : All HistoMesure are contiguous in this configuration.

Question

I want to merge (transform two little intervals in one big interval) all adjacent HistoMesure which have the same Commentaires. Currently I achieve this that way :

//sortedHistos type is List<HistoMesure>
int i = 0;
while (i < sortedHistos.Count - 1)
{
    if (sortedHistos[i].Commentaires == sortedHistos[i + 1].Commentaires)
    {
        sortedHistos[i].Fin = sortedHistos[i + 1].Fin;
        sortedHistos.RemoveAt(i + 1);
    }
    else
    {
        ++i;
    }
}

But I feel that it exists a more elegant way to do this, maybe with LINQ. Do you have any suggestion ?

Answer 1

This code will produce overlapping merged intervals. I.e. if you have intervals A, B, C where A and C have same commentaries, result will be AC, B:

var result = from h in sortedHistos
             group h by h.Commentaires into g
             select new HistoMesure {
                 Debut = g.First().Debut, // thus you have sorted entries
                 Fin = g.Last().Fin,
                 Commentaires = g.Key
             };

You can use Min and Max if intervals are not sorted.

---

UPDATE: There is no default LINQ operator which allows you to create adjacent groups. But you always can create one. Here is IEnumerable<T> extension (I skipped arguments check):

public static IEnumerable<IGrouping<TKey, TElement>> GroupAdjacent<TKey, TElement>(
    this IEnumerable<TElement> source, Func<TElement, TKey> keySelector)
{
    using (var iterator = source.GetEnumerator())
    {
        if(!iterator.MoveNext())
        {
            yield break;
        }
        else
        {
            var comparer = Comparer<TKey>.Default;
            var group = new Grouping<TKey, TElement>(keySelector(iterator.Current));
            group.Add(iterator.Current);

            while(iterator.MoveNext())
            {
                TKey key = keySelector(iterator.Current);
                if (comparer.Compare(key, group.Key) != 0)
                {
                    yield return group;
                    group = new Grouping<TKey, TElement>(key);
                }

                group.Add(iterator.Current);                        
            }

            if (group.Any())
                yield return group;
        }
    }
}

This extension creates groups of adjacent elements which have same key value. Unfortunately all implementations of IGrouping in .NET are internal, so you need yours:

public class Grouping<TKey, TElement> : IGrouping<TKey, TElement>
{
    private List<TElement> elements = new List<TElement>();

    public Grouping(TKey key)
    {
        Key = key;
    }

    public TKey Key { get; private set; }

    public IEnumerator<TElement> GetEnumerator()
    {
        return elements.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Add(TElement element)
    {
        elements.Add(element);
    }
}

And now your code will look like:

var result = sortedHistos.GroupAdjacent(h => h.Commentaries)
                         .Select(g => new HistoMesure {
                              Debut = g.Min(h => h.Debut),
                              Fin = g.Max(h => h.Fin),
                              Commentaries = g.Key
                          });

Answer 2

Your solution works fine, I would keep it.

Don't try too hard to use LINQ if it doesn't match your requirements. LINQ is great to write queries (this is the Q of LINQ), not so great to modify existing lists.

Answer 3

Using Linq and borrowing from this article to group by adjacent values, this should work:

Your query:

var filteredHistos = sortedHistos
    .GroupAdjacent(h => h.Commentaires)
    .Select(g => new HistoMesure
    {
        Debut = g.First().Debut,
        Fin = g.Last().Fin,
        Commentaires = g.Key
    });

And copying from the article, the rest of the code to group by:

public class GroupOfAdjacent<TSource, TKey> : IEnumerable<TSource>, IGrouping<TKey, TSource>
{
    public TKey Key { get; set; }
    private List<TSource> GroupList { get; set; }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.Generic.IEnumerable<TSource>)this).GetEnumerator();
    }
    System.Collections.Generic.IEnumerator<TSource> System.Collections.Generic.IEnumerable<TSource>.GetEnumerator()
    {
        foreach (var s in GroupList)
            yield return s;
    }
    public GroupOfAdjacent(List<TSource> source, TKey key)
    {
        GroupList = source;
        Key = key;
    }
}
public static class LocalExtensions
{
    public static IEnumerable<IGrouping<TKey, TSource>> GroupAdjacent<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector)
    {
        TKey last = default(TKey);
        bool haveLast = false;
        List<TSource> list = new List<TSource>();
        foreach (TSource s in source)
        {
            TKey k = keySelector(s);
            if (haveLast)
            {
                if (!k.Equals(last))
                {
                    yield return new GroupOfAdjacent<TSource, TKey>(list, last);
                    list = new List<TSource>();
                    list.Add(s);
                    last = k;
                }
                else
                {
                    list.Add(s);
                    last = k;
                }
            }
            else
            {
                list.Add(s);
                last = k;
                haveLast = true;
            }
        }
        if (haveLast)
            yield return new GroupOfAdjacent<TSource, TKey>(list, last);
    }
}

Answer 4

If I understood you correctly, you need something like this:

        var mergedMesures = mesures
            .GroupBy(_ => _.Commentaires)
            .Select(_ => new HistoMesures
            {
                Debut = _.Min(item => item.Debut),
                Fin = _.Max(item => item.Fin),
                Commentaires = _.Key
            });