3
\$\begingroup\$

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<HashSet<int>> source;

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

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

    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<int>();
            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));
    }

    [TestMethod]
    public void DuplicateUnionTest()
    {
        int left = 10;
        int right = 10;

        var uf = UnionFind.Create();

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

    [TestMethod]
    public void MultipleLinksUnionTest()
    {
        int left1 = 10;
        int left2 = 20;
        int left3 = 30;

        int right1 = 15;
        int right2 = 25;
        int right3 = 35;

        var uf = UnionFind.Create();
        uf.Union(left1, right1);
        uf.Union(left2, right2);
        uf.Union(left3, right3);

        uf.Union(left1, right2);
        Assert.IsTrue(uf.AreConnected(left2, right1));
    }
}

UnionFind works find and pass all tests in unit test. The problem is I found method Union has many if-else and I want to get rid of it. Is there a simpler way of implementing Union method?

\$\endgroup\$
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ This doesn't look good at all. There is a principle that a function should have only one return point. This seems simple now, but once the logic gets more complicated these returns out of nowhere can make for some nasty misunderstandings and fitful bug-tracing. \$\endgroup\$ – Andyz Smith Dec 7 '13 at 16:18
  • \$\begingroup\$ Is there? Why should you have unreadable and complicated if..else constructs just to follow that principle? The only principle there is and which has to be followed every time (except for the exception) is: Make it correct, readable, simple, maintainable and sustainable. There are various ways helping programmers to achieve these only valid principles, and one of them (more like a rule of thumb:) have one return value. But it's not a must, believe me. Imho early and multiple returns make the rest of the code more readable. \$\endgroup\$ – alzaimar Dec 7 '13 at 23:08
3
\$\begingroup\$

I find these practices helpful:

  • Buy a licence of Resharper or something similar. It points out potential improvements ;-)
  • Extract all conditions as variables and name them after their meaning.
  • Check all positives first, then it's easier to understand the following ifs.
  • As a bonus, I can remove the comment in the (initial) last branch

    public void Union(int left, int right)
    {
        var lefts = source.FirstOrDefault(o => o.Contains(left));
        var rights = source.FirstOrDefault(o => o.Contains(right));
    
        var foundRight = rights != null;
        var foundLeft = lefts != null;
    
        if (foundLeft && foundRight)
        {
            source.Remove(rights);
    
            foreach (var item in rights)
            {
                lefts.Add(item);
            }
        }
        else if (foundRight)
        {
            rights.Add(left);
        }
        else if (foundLeft)
        {
            lefts.Add(right);
        }
        else
        {
            var hash = new HashSet<int> {left, right};
            source.Add(hash);
        }
    }
    
\$\endgroup\$
2
\$\begingroup\$

Your naming of isLeftExist is not correct. The variable holds a list containing th number left. So its name should be listContainingLeft. The same applies to the isRightExist list.

Regarding the if-else construct: One clause is redundant (the second isRightExist) so you my either omit this or rewrite the conditions like this.

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

  if (listContainingLeft == null)
    if (listContainingRight == null)
      AddBranch(left, right);
    else
      listContainingRight.Add(left);
  else if (listContainingRight == null)
    listContainingLeft.Add(right);
  else
    Combine(listContainingLeft, listContainingRight);
}

private void AddBranch(int left, int right)
{
  var hash = new HashSet<int>();
  hash.Add(left);
  hash.Add(right);
  this.source.Add(hash);
}

private void Combine(HashSet<int> isLeftExist, HashSet<int> isRightExist)
{
  this.source.Remove(isRightExist);
  foreach (var item in isRightExist)
  {
     isLeftExist.Add(item);
  }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ I think that whenever you're writing multiline if bodies, you should always use braces, even if they are not necessary. \$\endgroup\$ – svick Nov 10 '13 at 11:19
  • 2
    \$\begingroup\$ That's a matter of taste. I tend not do do things which are unnecessary. One exception: If it increases readability. In this special case (as all conditional actions are one-liners) I did not use braces. \$\endgroup\$ – alzaimar Nov 10 '13 at 12:01
  • 1
    \$\begingroup\$ Without becoming a bashing exercise, in my experience the braces on 1-liners are important. They do two things: Stop bugs appearing when someone adds something to the 'block' (yeah, it's a stupid thing to do but I have seen it often). The second thing is that adding 1 line to a brace-less if statement now becomes a 3-line diff (including the line with the conditional) whereas if there were already braces there, the 1-line added becomes a 1-liner diff. \$\endgroup\$ – rolfl Nov 10 '13 at 13:22
  • 1
    \$\begingroup\$ If you define useful as "creates customer value", then braces are useless. But if you add "or makes development easier/safer/faster", then suddenly those braces have value. "Pay attention" is a kind of effort, and that part of your brain is no longer available for thinking about other things. \$\endgroup\$ – Jay Bazuzi Nov 10 '13 at 23:45
  • 1
    \$\begingroup\$ I am writing software for 32 years and I am sure I have quite an understanding in what is valuable for programmers and what not. Most of my programmer colleagues tend to use the braces like I do (i.e. whenever necessary), and they're all 10+ years in the business. In my eyes, vertical formatting (e.g. emtpy lines, braces) makes the code harder to read but that is a matter of taste. Some programmers use == false instead of ! while others don't. Some programmers use braces in one liners, others don't. Just accept it. Thanks. \$\endgroup\$ – alzaimar Nov 11 '13 at 7:28
0
\$\begingroup\$

Here is my code for Union method:

public class UnionFind
{
    private readonly List<HashSet<int>> source;

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

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

    private readonly HashSet<int> selfConnectedSet = new HashSet<int>();

    private HashSet<int> AddSet() {
        var hash = new HashSet<int>();
        this.source.Add(hash);
        return hash;
    }

    public void Union(int left, int right)
    {
        if (left == right)
        {
            selfConnectedSet.Add(left);
        }
        else
        {
            var leftSet = this.source.FirstOrDefault(o => o.Contains(left));
            var rightSet = this.source.FirstOrDefault(o => o.Contains(right));
            if (leftSet != null && rightSet != null)
            {
                // found left and right
                this.source.Remove(rightSet);
                leftSet.UnionWith(rightSet);
            }
            else
            {
                var hash = leftSet ?? (rightSet ?? AddSet());
                hash.Add(left);
                hash.Add(right);
            }
        }
    }

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

Few points for my refactoring

  • is should be used for boolean variable only, as some already mentioned earlier.
  • Except the first if, the logic just to find the target HashSet to add the values to, so I normalised that by using conditional operator. We can add left and right no matter it's leftSet or rightSet because it's a HashSet so the value could never be duplicated.
  • Same value for left and right has to be supported according to the unit test, so I add a separated HashSet to keep self-connected number
\$\endgroup\$
  • \$\begingroup\$ Be sure that the caller of Union is well aware that you are throwing an exception. At least in the test case presented, the caller will be blythely unaware and totally unprepared to catch such an exception, and attempt to do something meaningful. The point is be careful and have a plan before adding NEW exceptions and using exceptions as a 'escape hatch' to your architecture \$\endgroup\$ – Andyz Smith Dec 7 '13 at 16:17
  • \$\begingroup\$ Thanks for comment. I just found out the test case of duplication. I will fix accordingly. \$\endgroup\$ – tia Dec 7 '13 at 21:24

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.