'Smart' grouping with LINQ

Question

I have a list of strings and I want to convert it to some kind of grouped list, whereby the values would be grouped by their location in the list (not normal grouping, but in a way, that the same items are in a group only if they are together). Consider the following example:

LinkedList<string> myList = new LinkedList<string>();
myList.AddLast("aaa");
myList.AddLast("aaa");
myList.AddLast("bbb");
myList.AddLast("bbb");
myList.AddLast("aaa");
myList.AddLast("aaa");
myList.AddLast("aaa");

LinkedList<MyTuple> groupedList = new LinkedList<MyTuple>();
groupedList.AddLast(new MyTuple("aaa", 2));
groupedList.AddLast(new MyTuple("bbb", 2));
groupedList.AddLast(new MyTuple("aaa", 3));

Can this transformation be done with LINQ or should I write the algorithm usual way with loops?

Answer 1

The extension method from this answer does pretty much what you ask (Microsoft also provide an implementation to group contiguous items in a sequence):

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 = (predicate(e, next)) ? k : k++
                 group e by key into g
                 select g;
    return ranges;
}

You could use it as follows:

void Main()
{
    LinkedList<string> myList = new LinkedList<string>();
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    myList.AddLast("bbb");
    myList.AddLast("bbb");
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    IGrouping<int,string> ggg;

    var groups=myList.GroupConsecutive((a,b)=>a==b);

    ILookup<string,int> lookup=groups.ToLookup(g=>g.First(),g=>g.Count());

    foreach(var x in lookup["aaa"])
    {
        Console.WriteLine(x); //outputs 2 then 3
    }
    foreach(var x in lookup["bbb"])
    {
        Console.WriteLine(x); //outputs 2
    }

}

Notice that the final container is an ILookup which behaves a little like a Dictionary, but allows one to store multiple values against a single key.

Answer 2

This is not possible with the Dictionary. A dictionary is associative (i.e.: each key must point to one and one only) and is by nature unordered. You'd need to use something else for that data structure. It wouldn't be terribly hard though!

Edit

A List<Tuple<string, int>> should do the trick:

List<KeyValuePair<string, int>> structure = new List<KeyValuePair<string, int>>();
structure.Add(new KeyValuePair<string, int>(myList[0], 1);
for(int i = 0; i < myList.Count; i++ )
{
    if( myList[i] == structure[structure.Count-1].Key )
    {
        structure[structure.Count-1].Value += 1;
    }
    else
    {
        structure.Add(new KeyValuePair<string, int>(myList[i], 1);
    }
}

After that you should (untested!) have what you're looking for.

Edit (one more thought)

While it may be possible with linq (using TakeWhile and counts...), I still think it makes more sense to use a loop here, it's simple. Someone more brilliant than I could try and work with Linq.