patterncsharpMinor
Complexity in multiple if-else algorithms
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
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
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.
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.