LINQ - Full External Connection

question:

How to perform a full out connection between two object lists based on the common key fields, ensuring that all records in both lists are included in the result, even if they do not have corresponding matches in the other list?

Answer:

1. Custom extension method for fully external connections

In order to implement full external connection in LINQ, we can define a custom extension method as follows:

public static IEnumerable FullOuterJoin(
    this IEnumerable a,
    IEnumerable b,
    Func selectKeyA,
    Func selectKeyB,
    Func projection,
    TA defaultA = default(TA),
    TB defaultB = default(TB),
    IEqualityComparer cmp = null)
{
    cmp = cmp ?? EqualityComparer.Default;
    var alookup = a.ToLookup(selectKeyA, cmp);
    var blookup = b.ToLookup(selectKeyB, cmp);

    var keys = new HashSet(alookup.Select(p => p.Key), cmp);
    keys.UnionWith(blookup.Select(p => p.Key));

    var join = from key in keys
               from xa in alookup[key].DefaultIfEmpty(defaultA)
               from xb in blookup[key].DefaultIfEmpty(defaultB)
               select projection(xa, xb, key);

    return join;
}

2. Implement

In the provided example, we have two lists: firstNames and lastNames. To perform a full external connection, we can use the following code:

var outerJoin = from first in firstNames
                join last in lastNames
                on first.ID equals last.ID
                into temp
                from last in temp.DefaultIfEmpty()
                select new
                {
                    id = first != null ? first.ID : last.ID,
                    firstname = first != null ? first.Name : string.Empty,
                    surname = last != null ? last.Name : string.Empty
                };

3. Explain

This code uses a left outer join, where each record in firstNames is connected to the first matching record in lastNames and connects to the default value if no match is found. The into temp statement creates a temporary collection of matching records in lastNames, allowing us to apply DefaultIfEmpty() to ensure that mismatch records are included. This actually implements a left outer connection, not a full outer connection in the full sense. To achieve full external connection, you need to use the FullOuterJoin extension method customized above.

4. Expected output

The expected output for a fully external connection is:

ID  FirstName  LastName
--  ---------  --------
1   John       Doe
2   Sue        
3             Smith

5. Customizable default value

provides an extension method that allows you to specify default values ​​for mismatched records. In the example, we specify string.Empty for the mismatched name and a negative integer for the mismatched ID.

6. Performance considerations

The run time of the fully external connection is O(n m), where n and m are the lengths of the two input lists. This is because the ToLookup() operation takes O(n) time, and subsequent operations require O(n m) time.

7. LINQ implementation

This implementation of fully external connection is not currently part of the LINQ standard, but it has been recommended to include it in future versions. Standard LINQ does not directly support full external connections, and requires a custom extension method to implement it.