2
\$\begingroup\$

In answering a question on StackOverflow, it occurred to me that a more generic version of GroupBy for C# that delegated membership in each group to a class could be useful.

This is my attempt, but I am unsatisfied with a few things. I don't particularly like the need to constrain the element type to IOrderable - I feel like it should be possible to delegate ordering to the group type somehow (I really wanted a static method constraint in the IGGrouping interface).

public interface IOrderable<T> {
    double ordering();
}

public interface IGGrouping<T> : IEnumerable<T> where T : IOrderable<T> {
    bool BelongsToGroup(T aT);
    IGGrouping<T> Add(T aT);
}

public static class IEnumerableExt {
    public static IEnumerable<IGGrouping<T>> GroupBy<TG,T>(this IEnumerable<T> src) where TG : IGGrouping<T>, new() where T : IOrderable<T> {
        var groups = new List<IGGrouping<T>>();
        void Add(T aT) {
            var found = false;
            foreach (var g in groups) {
                found = g.BelongsToGroup(aT);
                if (found) {
                    g.Add(aT);
                    break;
                }
            }
            if (!found)
                groups.Add(new TG().Add(aT));
        }

        foreach (var s in src.OrderBy(s => s.ordering()))
            Add(s);

        return groups;
    }
}

Here's a sample class to group by distance from center of current groups:

public class gRectangleGroup : IGGrouping<Rectangle> {
    List<Rectangle> members;
    public Point center;

    public gRectangleGroup() {
        members = new List<Rectangle>();
    }

    public gRectangleGroup Add(Rectangle r) {
        members.Add(r);
        center = new Point(members.Average(m => m.Loc.X), members.Average(m => m.Loc.Y));
        return this;
    }

    public bool BelongsToGroup(Rectangle r) => center.Distance(r.Loc) <= 5;

    public Rectangle Middle() => members.OrderBy(m => m.Loc.Distance(center)).First();

    public IEnumerator<Rectangle> GetEnumerator() => members.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    IGGrouping<Rectangle> IGGrouping<Rectangle>.Add(Rectangle aT) => Add(aT);
}

You use gRectangleGroup like so:

List<Rectangle> list;

var ans2 = list.GroupBy<gRectangleGroup, Rectangle>().Cast<gRectangleGroup>().Select(rg => rg.Middle());

I don't like having to list the group type and the element type explicitly in the call to GroupBy. I don't like the Cast to gRectangleGroup when the type is passed to the GroupBy, but if GroupBy returns TG then I have to give up the fluent Add call for new groups.

I also don't like how a class that implements IGGrouping (like gRectangleGroup) and has a fluent Add that returns this, must also have another Add to return IGGrouping<T> because of the interface.

Can anyone suggest how this might be improved, or what they would change to solve the same issue?

\$\endgroup\$
  • \$\begingroup\$ Could you post the code for gRectangleGroup? With your current design, it's not clear how BelongsToGroup could be implemented, given that all the groupings will be identical. It's also not clear what the purpose of ordering the items via IOrderable is. \$\endgroup\$ – Errorsatz Sep 22 '18 at 0:47
  • 1
    \$\begingroup\$ And I'd like to ask you to explain what your GroupBy is actually doing? I cannot figure this out. How is it different from the original one? \$\endgroup\$ – t3chb0t Sep 22 '18 at 8:26
  • \$\begingroup\$ @t3chb0t The original GroupBy groups according to a key calculated from a single item. This GroupBy groups according to a rule specified in each group, which could involve calculating across all previous group members. The example is about clustering points into groups that are "nearby" the centroid of the group. \$\endgroup\$ – NetMage Sep 24 '18 at 17:58
  • \$\begingroup\$ @Errorsatz Done. Ordering is so my example grouping won't create unnecessary groups. Imagine a 1D grouping rule: distance apart is less than 5. If you group 1,5,7 you get one group, if you group 1, 7, 5 you get two groups. \$\endgroup\$ – NetMage Sep 24 '18 at 19:27
1
\$\begingroup\$

You don't need the type parameter on IOrderable:

  public interface IOrderable
  {
    double Ordering();
  }

I don't like that you sort the source vector without notifying the client. In this way mysterious things are going on and the method does more than one thing. At least you should have a flag argument that lets the client determine if the source should be sorted or not before grouping:

public static IEnumerable<IGGrouping<T>> GroupBy<TG, T>(this IEnumerable<T> src, bool sortBeforeGrouping = false) where TG : IGGrouping<T>, new() where T : IOrderable
{
  var groups = new List<IGGrouping<T>>();

  ...
}

Alternatively you should rename the method to SortAndGroupBy(...). But I would let it total up to the client if the source should be sorted or not.


I think the inner of the internal Add(...) function can be simplified a bit:

  void Add(T aT)
  {
    var group = groups.FirstOrDefault(g => g.BelongsToGroup(aT));
    if (group == null)
    {
      group = new TG();
      groups.Add(group);
    }
    group.Add(aT);
  }

On way to get rid of the custom interfaces is to let the group type implement ICollection<T> and then inject the belongsToGroup function:

public static IEnumerable<TKey> GroupBy<TKey, TElement>(this IEnumerable<TElement> source, Func<TElement, TKey, bool> belongsToGroup) where TKey : ICollection<TElement>, new()
{
  return source.Aggregate(new List<TKey>(), (groups, e) =>
  {
    TKey group = groups.FirstOrDefault(g => belongsToGroup(e, g));
    if (group == null)
    {
      group = new TKey();
      groups.Add(group);
    }
    group.Add(e);
    return groups;
  });

}

Usage

  Func<Rectangle, RectangleGroup, bool> belongsToGroup = (r, gr) => gr.BelongsToGroup(r);
  var midPoints = list.OrderBy(r => r).GroupBy(belongsToGroup).Select(gr => gr.Middle());
  foreach (var middle in midPoints)
  {
    Console.WriteLine(middle);
  }

If that isn't good enough then you can inject the addToGroup function too:

public static IEnumerable<TKey> GroupBy<TKey, TElement>(this IEnumerable<TElement> source, Func<TElement, TKey, bool> belongsToGroup, Action<TElement, TKey> addToGroup) where TKey : new()
{
  List<TKey> groups = new List<TKey>();

  foreach (TElement element in source)
  {
    TKey group = groups.FirstOrDefault(g => belongsToGroup(element, g));
    if (group == null)
    {
      group = new TKey();
      groups.Add(group);
    }

    addToGroup(element, group);
  }

  return groups;
}

Usage

  Func<Rectangle, RectangleGroup, bool> belongsToGroup = (r, gr) => gr.BelongsToGroup(r);
  Action<Rectangle, RectangleGroup> adder = (r, gr) => gr.Add(r);
  var midPoints= list.OrderBy(r => r).GroupBy(belongsToGroup, adder).Select(gr => gr.Middle());
  foreach (var middle in midPoints)
  {
    Console.WriteLine(middle);
  }
\$\endgroup\$
  • \$\begingroup\$ It looks like you have figured out what this question is about ;-) would you share this knowledge? What is this GroupBy actually doing? \$\endgroup\$ – t3chb0t Sep 23 '18 at 7:27
  • \$\begingroup\$ @t3chb0t: As I understand it, it's about grouping a data set according to the elements relation to an existing (and growing) set of groups: you want to cluster a set of points according to the distance to the first point in a cluster. If no existing cluster (group) is in a position with a distance smaller than a certain distance, the current point becomes the first point in a new cluster. Else it is added to the existing cluster. This seems not to be possible with the existing GroupBy() extensions - or it is possible, but this extension encapsulates in one method. \$\endgroup\$ – Henrik Hansen Sep 23 '18 at 7:53
  • 1
    \$\begingroup\$ oh, this is way too complex without OP showing any examples... next question please ;-] \$\endgroup\$ – t3chb0t Sep 23 '18 at 11:01
  • 1
    \$\begingroup\$ @HenrikHansen Your explanation is close as far as the example goes, but the point is to make a generic version that handles any type of clustering rules. My class actually groups by distant from the current center of the group, but your rule would just require a difference class to be passed to the GroupBy, which is the point. \$\endgroup\$ – NetMage Sep 24 '18 at 17:53
  • 1
    \$\begingroup\$ @HenrikHansen The thing about sorting is the client knows that, because they must implement the IOrderable interface. If Ordering returned a single value, wouldn't that skip sorting? \$\endgroup\$ – NetMage Sep 24 '18 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.