What is the most efficient way to merge items with the same type in a generic list in C#?

Question

Example, I have the following interface and classes:

public interface IRole {
    DateTime Since {get;}
    DateTime Until {get;}
}

public class Manager : IRole {
    public DateTime Since {get; private set;}
    public DateTime Until {get; private set;}
}
public class Employee : IRole {
    public DateTime Since {get; private set;}
    public DateTime Until {get; private set;}
}
public class Ceo: IRole {
    public DateTime Since {get; private set;}
    public DateTime Until {get; private set;}
}

If a generic list contains the following items:

list[0]=new Manager();
list[1]=new Manager();
list[2]=new Employee();
list[3]=new Manager();
list[4]=new Ceo();
list[5]=new Ceo();

And I shall merge the same types, combine the Since/Until and shrink the items in list, so the output becomes:

newList[0]=new Manager() //(Since is from list[0], Until is from list[1])
newList[1]=new Employee() //(list[2])
newList[2]=new Manager() //(list[3])
newList[3]=new Ceo() //(Since is from list[4], Until is from list[5])

Please make sure you understand the question before answering as I have a history of being ambigous and I don't want to upset people. So please comment if you feel the "requirement" isn't clear.

My way is kind of dumb:

for each item in list
    the current item shall always be merged into the previous item
        check if current item has the same type as the previous item
            get last item from newList and merge last item with current item

I was just wondering there must be a better solution.

Updated:

I just realize my "dumb solution" won't cover cases like more than 2 continuous items with the same type.

Example:

list[0]=new Manager();
list[1]=new Manager();
list[2]=new Employee();
list[3]=new Manager();
list[4]=new Ceo();
list[5]=new Ceo();
list[6]=new Ceo();

Answer 1

I believe this is a very requirement specific thing. I am not sure if this is to be supported by a framework in anyway. What happens if the type is not derived from IRole directly. What if there is something like IEmployee from which IManager is derived. I am not sure how application specific symentics can be understood by framework.

If the question is very specific to application, you may be able to use linq to get this done using group clause (on type). I haven't tried this before hence can't give you the exact solution.

Answer 2

List<IRole> newList = new Lis<IRole>();
for (int i = 1; i < list.Count; i++) // Start at 1, so we can do i - 1 on the first iteration
{
  if (list[i - 1].GetType() != list[i].GetType()) // they're not the same
  {
    newList.Add(list[i - 1]); // so add the first one too
  }
  newList.Add(list[i]); // always add second one
}

Answer 3

I don't think your pseudo code is dumb at all if it works as you expect it to. I don't believe you're going to find an easy shortcut for what you're trying to do, since it's a rather unusual algorithm. Bottom line: if this algorithm is not going to be run millions of times a day and the list doesn't have millions of objects in it, I wouldn't worry about efficiency.

Answer 4

I wrote a blog post about this :-).

It feels almost like group by except, you don't want to group elements globally. Instead, you only want to group elements that are adjacent in the input list. The blog post provides some code that allows you to change the meaning of group by in the LINQ query, so you could write just:

var groups =
  from person in list.WithAdjacentGrouping()
  group person by person.GetType().Name into g
  select new { 
    Type = g.Key,
    Since = new DateTime(g.Select(p => p.Since.Ticks).Min()),
    Until = new DateTime(g.Select(p => p.Until.Ticks).Max())
  }

The call to WithAdjacentGrouping specifes that grouping should only group adjacent elements. Then we can collect adjacent groups of persons by type (using GetType().Name as the key).

Finally, we return a collection that contains the name of the type (e.g. "Ceo") and two times - Since and Until that are calculated as minimal/maximal time from the collected group.

• See Using custom grouping operators in LINQ for the implementation of WithAdjacentGrouping