HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Complexity in multiple if-else algorithms

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
elsecomplexitymultiplealgorithms

Problem

I am learning Algorithms, Part I on coursera.org. I just watched the first lecture then tried to write some code in C#. The class basically stores list of connected numbers. You can add numbers that connected together by calling Union and check if they are connected by calling AreConnected. Code is as follows:

public class UnionFind
{
    private readonly List> source;

    public static UnionFind Create()
    {
        return new UnionFind();
    }

    private UnionFind()
    {
        this.source = new List>();
    }

    public void Union(int left, int right)
    {
        var isLeftExist = this.source.FirstOrDefault(o => o.Contains(left));
        var isRightExist = this.source.FirstOrDefault(o => o.Contains(right));

        if (isLeftExist == null &&
            isRightExist == null)
        {
            var hash = new HashSet();
            hash.Add(left);
            hash.Add(right);

            this.source.Add(hash);
        }
        else if (isLeftExist != null &&
            isRightExist == null)
        {
            isLeftExist.Add(right);
        }
        else if (isRightExist != null &&
            isLeftExist == null)
        {
            isRightExist.Add(left);
        }
        else
        {
            // found left and right
            this.source.Remove(isRightExist);

            foreach (var item in isRightExist)
            {
                isLeftExist.Add(item);
            }
        }
    }

    public bool AreConnected(int left, int right)
    {
        return this.source
            .Any(o => 
                o.Contains(left) &&
                o.Contains(right));
    }


To make it easier to understand, this is unit test class.

```
[TestClass]
public class UnionFindTests
{
[TestMethod]
public void SimpleUnionTest()
{
int left = 10;
int right = 20;

var uf = UnionFind.Create();

uf.Union(left, right);
Assert.IsTrue(uf.AreConnected(left, right));
}

[TestMeth

Solution

Building on @alzaimar's answer:

You can unfold the conditionals with early return. The linear flow makes it slightly easier to follow.

if (listContainingLeft == null && listContainingRight == null)
{
    AddBranch(left, right);
    return;
}

if (listContainingLeft != null && listContainingRight != null)
{
    Combine(listContainingLeft, listContainingRight);
    return;
}

if (listContainingLeft != null)
{
    listContainingLeft.Add(right);
    return;
}

if (listContainingRight != null)
{
    listContainingRight.Add(left);
    return;
}

Code Snippets

if (listContainingLeft == null && listContainingRight == null)
{
    AddBranch(left, right);
    return;
}

if (listContainingLeft != null && listContainingRight != null)
{
    Combine(listContainingLeft, listContainingRight);
    return;
}

if (listContainingLeft != null)
{
    listContainingLeft.Add(right);
    return;
}

if (listContainingRight != null)
{
    listContainingRight.Add(left);
    return;
}

Context

StackExchange Code Review Q#35120, answer score: 3

Revisions (0)

No revisions yet.