How to group consecutive similar items of a collection?

Question

Consider the following collection.

• True
• False
• False
• False
• True
• True
• False
• False

I want to display it in a structured way, say, in a TreeView. I want to be able to draw borders around entire groups and such.

• True Group
  • True
• False Group
  • False
  • False
  • False
• True Group
  • True
  • True
• False Group
  • False
  • False

How do I accomplish this with as little procedural code as possible?

Parang

Answer 1

This does what you're looking for and is generic:

private static IEnumerable<IGrouping<int, T>> GroupConsecutive<T>(this IEnumerable<T> set, Func<T, T, bool> predicate)
{
    var i = 0;
    var k = 0;
    var ranges = from e in set
                 let idx = ++i
                 let next = set.ElementAtOrDefault(idx)
                 let key = (predicate(e, next)) ? k : k++
                 group e by key into g
                 select g;
    return ranges;
}

Usage:

var set = new List<bool>
            {
                true,
                false,
                false,
                false,
                true,
                true,
                false,
                false,
            };
var groups = set.GroupConsecutive((b1, b2) => (b1 == b2));
foreach (var g in groups)
{
    Console.WriteLine(g.Key);
    foreach (var b in g)
        Console.WriteLine("\t{0}", b);
}

Output:

0
        True
1
        False
        False
        False
2
        True
        True
3
        False
        False

Battik

Kudos for using fancy language features. – Parang

Isn't there O(n^2) performance because of accessing IEnumerable elements by index in line 7 ("let next = set.ElementAtOrDefault(idx)")? – Apoloniaapolune

Answer 2

While the code in the accepted answer meets the needs of the original question, it will fall over when handling IEnumerables of more complex objects (since the predicate will tend to throw an exception when comparing the last item in the enumerable with the "next" item [which, by definition, will always be null]).

This version handles more complex objects:

   public static IEnumerable<IGrouping<int, T>> GroupConsecutive<T>(this IEnumerable<T> set, Func<T, T, bool> predicate)
    {
        var i = 0;
        var k = 0;
        var ranges = from e in set
                     let idx = ++i
                     let next = set.ElementAtOrDefault(idx)
                     let key = next == null ? k : (predicate(e, next)) ? k : k++
                     group e by key into g
                     select g;
        return ranges;
    } 

Tamikatamiko

Answer 3

last = null;
foreach (var option in list)
{
   if (last != option)
      newlist.Add(new Group(option, new[]));
   newlist.Last().Add(option);
   last = option;
}

Wolfie

Answer 4

public class GroupConsecutiveEqualItemsConverter : IValueConverter
{
    static readonly object UnsetValue = new object();

    public object Convert(object value, Type targetType, object parameter, CultureInfo culture)
    {
        IEnumerable source = value as IEnumerable;
        if (source == null) return DependencyProperty.UnsetValue;
        string propertyName = parameter as string;
        var result = new ObservableCollection<List<object>>();

        var notify = value as INotifyCollectionChanged;
        if (notify != null) notify.CollectionChanged += delegate { Reload(result, source, propertyName); };

        Reload(result, source, propertyName);
        return result;
    }

    public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
    {
        throw new NotSupportedException();
    }

    void Reload(ObservableCollection<List<object>> result, IEnumerable source, string propertyName)
    {
        result.Clear();
        object previous = UnsetValue;
        List<object> group = null;
        foreach (object i in source)
        {
            object current = UnsetValue;
            if (propertyName == null)
            {
                current = i;
            }
            else
            {
                try
                {
                    var property = i.GetType().GetProperty(propertyName);
                    if (property != null) current = property.GetValue(i, null);
                }
                catch (AmbiguousMatchException) { }
            }
            if (!object.Equals(previous, current))
            {
                if (group != null) result.Add(group);
                group = new List<object>();
            }
            group.Add(i);
            previous = current;
        }
        if (group != null && group.Count > 0) result.Add(group);
    }
}

Parang

Answer 5

You may wanna check out the pseudo TreeGrid on Delay's blog at http://blogs.msdn.com/delay/archive/2009/09/23/if-it-walks-like-a-duck-and-talks-like-a-duck-it-must-be-a-treegrid-a-simple-xaml-only-treegrid-ui-for-wpf.aspx

_{(source: msdn.com)}

Erick