Partition enumerable according to precedence

Question

I'm receiving an IEnumerable<TransactionLineDto>. A TransactionLineDto can represent either an Article or a Discount which applies on an Article.

The order matters: a Discount applies only on the preceding articles until another discount is found.

There can be no discount at all (only TransactionLineDto representing Article).

There can be many discounts in one IEnumerable<TransactionLineDto>.

There cannot be more than 1 discount applied on an article.

Examples:

1. Article1 -> Article2 -> Article3 means there are 3 articles without any discount.
2. Article1 -> Article2 -> Discount1 means Discount1 applies on both Article1 and Article2
3. Article1 -> Article2 -> Discount1 -> Article3 -> Discount2 -> Article4 means Discount1 applies on Article1 and Article2, Discount2 on Article3 and Article4 has no discount

Now I need to "partition" these sequences to be able to know which discount applies on which article (article without discount must be discarded).

The expected output for the third example should be something like that: (Discount1 -> Article1, Article2), (Discount2 -> Article3)

How can I implement a datastructure/class that would modelize this behavior ? I thought about something like that (pay attention to the ??? that I'm unable to implement yet):

public class DiscountedTransaction : ILookup<TransactionLineDto, TransactionLineDto>
{
    private readonly TransactionDto _transaction;
    private readonly IEnumerable<DiscountDto> _allDiscounts;
    public DiscountedTransaction(TransactionDto transaction, IEnumerable<DiscountDto> allDiscounts)
    {
        _transaction = transaction;
        _allDiscounts = allDiscounts;
    }
    public IEnumerable<TransactionLineDto> this[TransactionLineDto key] => _transaction.TransactionLines
                                                                                       .Reverse<TransactionLineDto>()
                                                                                       .SkipWhile(l => l != key)
                                                                                       .Skip(1)
                                                                                       .TakeWhile(l => !IsDiscount(l));
    public int Count => _transaction.TransactionLines
                                    .Where(IsDiscount)
                                    .Count();
    public bool Contains(TransactionLineDto key) => _transaction.TransactionLines
                                                                .Where(IsDiscount)
                                                                .Contains(key);
    public IEnumerator<IGrouping<TransactionLineDto, TransactionLineDto>> GetEnumerator() => ???;
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    private bool IsDiscount(TransactionLineDto line)
    {
        return _allDiscounts.Any(d => d.ID == line.Article);
    }
}

Is it a good approach or is it overkill ? (I mean is it possible to do that only with the pre-existing LINQ methods ?)

Answer 1

public static IEnumerable<List<T>> ToClusters(
  this IEnumerable<T> source, Func<T, bool> endOfClusterCriteria)
{
  var result = List<T>();
  foreach(T item in source)
  {
    result.Add(item);
    if (endOfClusterCriteria(item))
    {
      yield return result;
      result = new List<T>(); 
    }
  }
}

later:

var lookup = transactionLines
  .ToClusters(line => line.IsDiscount())
  .Where(cluster => 2 <= cluster.Count) //discard the discounts with no articles
  .SelectMany(
    cluster => cluster.Take(cluster.Count - 1),
    (cluster, article) => new { Discount = cluster.Last(), Article = article })
  .ToLookup(
    pair => pair.Discount,
    pair => pair.Article
  ).ToList();

---

I find .SelectMany calls to be difficult to read, so here's the same with query comprehension:

var lookup = (
  from cluster in transactionLines.ToClusters(line => line.IsDiscount)
  where 2 <= cluster.Count
  from article in cluster.Take(cluster.Count - 1)
  select new { Discount = cluster.Last(), Article = article }
  ).ToLookup(pair => pair.Discount, pair => pair.Article);

Answer 2

Using a (my favorite) custom extension method based on the APL scan operator (it is like Aggregate only it returns the intermediate results), you can scan across the reversed IEnumerable and gather the discount, then group by the discount.

The custom scan extension method:

public static IEnumerable<TResult> Scan<T, TResult>(this IEnumerable<T> src, TResult seed, Func<TResult, T, TResult> combine) {
    foreach (var s in src) {
        seed = combine(seed, s);
        yield return seed;
    }
}

Then you can Scan along the IEnumerable to gather the discount with each article, then group by the discount:

var discountPartitions = src.Reverse()
                            .Scan((discount: (TransactionLineDto)null, article: (TransactionLineDto)null),
                                  (daTuple, dto) => dto.IsDiscount ? (dto, (TransactionLineDto)null)
                                                                   : (daTuple.discount != null ? (daTuple.discount, dto) : daTuple)
                                 )
                            .Where(daTuple => daTuple.discount != null && daTuple.article != null)
                            .GroupBy(daTuple => daTuple.discount, daTuple => daTuple.article);