Remove every duplicate element by a condition in a List

Question

I have a List of my class Edge:

public class Edge
{
    public Vector3 a;
    public Vector3 b;

    public Edge(Vector3 a, Vector3 b)
    {
        this.a = a;
        this.b = b;
    }
}

I want ALL my duplicates to be removed from my list, an element is considered duplicated if

(edge1.a == edge2.a && edge1.b == edge2.b)

or

(edge1.a == edge2.b && edge1.b == edge2.a)

I've tried to use the Disctinct() method with an equality comparer and some other LINQ variants, they work as they are supposed to, but that is not the result I want. All the solutions I've found always leave one of the duplicate elements inside the list, when I need every duplicate to be removed from it.

public class SomeClass: MonoBehaviour
{
    [SerializeField] private List<Edge> edges;

    private void Start()
    {
        edges = edges
            .Distinct(new EdgeComparer())
            .ToList();
        // This removes the duplicates except for one,
        // I need that one to be removed as well.
    }
}

public class EdgeComparer : IEqualityComparer<Edge>
{
    public bool Equals(Edge x, Edge y)
    {
        return
            (x.a.Equals(y.a) && x.b.Equals(y.b)) ||
            (x.a.Equals(y.b) && x.b.Equals(y.a));
    }

    public int GetHashCode(Edge obj)
    {
        int a = obj.a.GetHashCode();
        int b = obj.b.GetHashCode();

        return a ^ b;
    }
}

Welcome to Stack Overflow! I guess the algorithm you need is 1) Build a new list of `Edge` containing any combinations of a and b which occur more than once in the original list, and 2) Remove any items from the original list where the combination of a and b appears in the new list. — sbridewell, Jan 05 '23 at 17:51
Your `Equals` method can return `true` for objects that produce different hash codes. Is that intentional? Typically `Equals` and `GetHashCode` should use the same properties and logic to generate a value. — Rufus L, Jan 05 '23 at 18:16
@Rufus L: looks like a typo (copy + paste is evel): `(x.a.Equals(y.b) && x.b.Equals(y.a));` - is a very strange - `x.a` is compared with `y.b` (`a` vs `b`) — Dmitry Bychenko, Jan 05 '23 at 18:19
@DmitryBychenko I would have thought so also, except he has the `||` operator in there. It seems like he wants to consider them equal if they have the same two vectors, regardless of which field they're assigned to? — Rufus L, Jan 05 '23 at 18:35
@Rufus L: you are quite right, I see; that's why I've provide two implementations of `EdgeComparer` — Dmitry Bychenko, Jan 05 '23 at 18:36
Related: [Remove List elements that appear more than once, in place](https://stackoverflow.com/questions/36415957/remove-listt-elements-that-appear-more-than-once-in-place) — Theodor Zoulias, Jan 05 '23 at 21:26
@DmitryBychenko It is intentional ^.^, I do want them to be consider equal if they have the two same vectors, regardless of the field. — Ari Éowyn, Jan 05 '23 at 21:39
@Ari Éowyn: then you should edit the equality criteria, it should be "element considered to be duplicated if `(edge1.a == edge2.a && edge1.b == edge2.b) || (edge1.a == edge2.b && edge1.b == edge2.a)`" — Dmitry Bychenko, Jan 05 '23 at 22:08
@Ari Éowyn: I think I finally understood the solution you are looking for: we should remove all the item which appear *two or more times* in the list, e.g. (let the items to be ints for the sake of simplicity): `[2, 3, 1, 2, 2, 3, 4, 1, 5] => [4, 5]` (all `1`, `2`, `3` are removed since they appear more than once in the list) — Dmitry Bychenko, Jan 05 '23 at 22:27

Dmitry Bychenko · Answer 1 · 2023-01-06T10:27:08.897

I think I got the question: we should remove all items which appear two or more times in the list; e.g.

(a:3, b:4), (a:5, b:6), (a:0, b:8) (a:3, a:4), (a:6, b:5) => (a:0, b:8)

If it's your problem the code that does it in place can be

var unique = new HashSet<edge>(new EdgeComparer());
var remove = new HashSet<edge>(new EdgeComparer());

// Collect what items to remove
foreach (var edge in edges)
  if (!unique.Add(edge))
    remove.Add(edge);

// remove items
if (remove.Count > 0) {
  int writeIndex = 0;

  for (int readIndex = 0; readIndex < edges.Count; ++readIndex)
    if (!remove.Contains(edges[readIndex]))
      edges[writeIndex++] = edges[readIndex];

  edges.RemoveRange(writeIndex, edges.Count - writeIndex);
}

Linq solution is based on GroupBy, not Distinct:

edges = edges
  .GroupBy(edge => edge, new EdgeComparer())
  .Where(group => group.Count() == 1) // items that appear just once
  .Select(group => group.First())
  .ToList();

Side note: EdgeComparer with a better GetHashCode can be

public sealed class EdgeComparer : IEqualityComparer<Edge> {
    public bool Equals(Edge x, Edge y) =>
        ReferenceEquals(x, y) ? true
      : x is null || y is null ? false
      : x.a.Equals(y.a) && x.b.Equals(y.b) || x.a.Equals(y.b) && x.b.Equals(y.a)

    public int GetHashCode(Edge obj) => obj is null
      ? -1
      : a.GetHashCode() < b.GetHashCode() 
          ? HashCode.Combine(a, b)
          : HashCode.Combine(b, a); 
}

Remove every duplicate element by a condition in a List

1 Answers1