Problem Statement
Given a list of items each having a type associated with it, group them by the below mentioned rule
- The list should not contain consecutive items that violate the
Groupsetting. For example. An item of "Type1" can have a group setting of 3. This means that there cannot be more than 3 consecutive items of "Type1" - Any items that violate the group setting (mentioned above) should be moved down the collection. The position of insertion is determined by the
Skipsetting for that type. For example, an item of "Type 1" can have a group setting of 3 and a skip setting of 2. This means that when we encounter more than 3 consecutive items of "Type 1" then the next available point of insertion can only be after two items (Skip = 2) of type that is not of type "Type 1" - Each item also has a weight associated with it. While moving down items by the above rule, ensure that weighting is respected except in cases where you have to break items because of grouping rule.
Models
public class Setting
{
public string Id { get; set; }
public int GroupSize { get; set; }
public int Skip { get; set; }
}
public class Entity
{
public string Id { get; set; }
public string Type { get; set; }
public int Skip { get; set; }
public double Weight { get; set; }
}
public class TimelineViewModel
{
public TimelineViewModel()
{
this.Items = new List<Entity>();
}
public string SnapshotId { get; set; }
public IList<Entity> Items { get; set; }
public IList<Entity> UnmatchedItems { get; set; }
}
Grouping Class
public class GroupingHelper
{
private static Dictionary<string, int> GroupSizes;
private List<Setting> settings;
private List<Entity> input = new List<Entity>();
private List<Entity> temp = new List<Entity>();
private List<Entity> output = new List<Entity>();
//Setting class. Contains group size for each type
public GroupingHelper(List<Setting> systemSettings)
{
settings = systemSettings;
GroupSizes = new Dictionary<string, int>();
for (int i = 0; i < settings.Count; i++)
{
GroupSizes.Add(settings[i].Id, settings[i].GroupSize);
}
}
public TimelineViewModel RearrangeTimeline(TimelineViewModel param)
{
try
{
input = new List<Entity>(param.Items);
temp = new List<Entity>();
output = new List<Entity>();
string previous = "";
while (input.Count != 0)
{
Entity item = input[0];
var temp_item = temp.Where(x => (x.Skip <= 0) || (x.Type == item.Type && x.Weight >= item.Weight)).OrderByDescending(y => y.Weight).FirstOrDefault();
if (temp_item != null)
{
if (Validate(temp_item, ref previous))
{
if (temp_item.Type != previous)
{
Reset();
}
previous = temp_item.Type;
temp_item.Id = temp_item.Id + " - G"; //- G appeneded only to indicate this item was moved down
Add(temp_item);
temp.Remove(temp_item);
continue;
}
}
if (Validate(item, ref previous))
{
if (item.Type != previous)
{
previous = item.Type;
Reset();
}
Add(item);
}
else
{
previous = item.Type;
Setting setting = settings.Where(c => c.Id.Equals(item.Type)).FirstOrDefault();
item.Skip = setting.Skip;
temp.Add(item);
input.Remove(item);
}
}
return new TimelineViewModel()
{
Items = output,
SnapshotId = param.SnapshotId,
UnmatchedItems = temp
};
}
catch (Exception ex)
{
throw;
}
finally
{
Reset();
}
}
#region Private Methods
private void Add(Entity temp_item)
{
//decrement skip
for (int i = 0; i < temp.Count; i++)
{
var k = temp[i].Skip--;
}
output.Add(temp_item);
GroupSizes[temp_item.Type]--;
input.Remove(temp_item);
}
private bool Validate(Entity entity, ref string previous)
{
if (entity.Type != previous)
{
return true;
}
if (GroupSizes[entity.Type] <= 0)
{
return false;
}
else
{
return true;
}
}
private void Reset()
{
GroupSizes = new Dictionary<string, int>();
for (int i = 0; i < settings.Count; i++)
{
GroupSizes.Add(settings[i].Id, settings[i].GroupSize);
}
}
#endregion
}
Test Case
[TestMethod()]
public void RearrangeTimelineTest()
{
List<Setting> setting = new List<Setting>() {
new Setting() { Id="Type1", GroupSize = 3, Skip =2 },
new Setting() { Id="Type2", GroupSize = 2, Skip =1 },
new Setting() { Id="Type3", GroupSize = 1, Skip =1 },
new Setting() { Id="Type4", GroupSize = 3, Skip =2 }
};
TimelineViewModel viewModel = new TimelineViewModel();
viewModel.SnapshotId = "test_id";
viewModel.Items = new List<Entity>() {
new Entity() { Id = "1", Type = "Type1", Weight = 100 },
new Entity() { Id = "2", Type = "Type1", Weight = 90 },
new Entity() { Id = "3", Type = "Type2", Weight = 80 },
new Entity() { Id = "4", Type = "Type2", Weight = 70 },
new Entity() { Id = "5", Type = "Type2", Weight = 60 },
new Entity() { Id = "6", Type = "Type2", Weight = 50 },
new Entity() { Id = "7", Type = "Type3", Weight = 40 },
new Entity() { Id = "8", Type = "Type3", Weight = 30 },
new Entity() { Id = "9", Type = "Type4", Weight = 20 },
new Entity() { Id = "10", Type = "Type3", Weight = 10 }
};
GroupingHelper g = new GroupingHelper(setting);
TimelineViewModel output = g.RearrangeTimeline(viewModel);
//This is how the final result would look
List<Entity> output_items = new List<Entity>() {
new Entity() { Id = "1", Type = "Type1", Weight = 100 },
new Entity() { Id = "2", Type = "Type1", Weight = 90 },
new Entity() { Id = "3", Type = "Type2", Weight = 80 },
new Entity() { Id = "4", Type = "Type2", Weight = 70 },
new Entity() { Id = "7", Type = "Type3", Weight = 40 },
new Entity() { Id = "5", Type = "Type2", Weight = 60 },
new Entity() { Id = "6", Type = "Type2", Weight = 50 },
new Entity() { Id = "8", Type = "Type3", Weight = 30 },
new Entity() { Id = "9", Type = "Type4", Weight = 20 },
new Entity() { Id = "10", Type = "Type3", Weight = 10 }
};
CollectionAssert.AreEqual(output.Items.Select(x=>x.Id).ToList(), output_items.Select(x => x.Id).ToList());
}
viewModel.Items. How can you tell the sort worked? \$\endgroup\$