Skip to content

Instantly share code, notes, and snippets.

@ndandoulakis
Last active November 10, 2018 16:44
Show Gist options
  • Save ndandoulakis/e91addb3e17cf99f82e159930ff5a04e to your computer and use it in GitHub Desktop.
Save ndandoulakis/e91addb3e17cf99f82e159930ff5a04e to your computer and use it in GitHub Desktop.
/**
* Building Maintainable Software - Ten Guidelines for Future Proof Code
* https://www.amazon.com/Building-Maintainable-Software-Java-Future-Proof/dp/1491953527
*
* Write Simple Units of Code - Dealing with Nesting, page 36.
*
* I like the example on page 36 because it's simple and just enough to demonstrate how hard is
* to write straightforward code, or how easy is to increase the Accidental Complexity of the code.
*
* There are 4 implementations of the same functionality. The first one is the original code,
* the next two are refactorings from the authors of the book based on the "Cyclomatic Complexity" metric.
* The 4th implementation is a refactoring by me and it's based on the "Separation of Concerns" design principle.
*/
/**
* 1st implementation - original code.
*
* Given a binary search tree root node and an integer, the calculateDepth method determines
* whether the integer occurs in the tree. If so, the method returns the depth of the integer
* in the tree; otherwise, it throws a TreeException.
*
* Authors: book.
*/
public static int calculateDepth(BinaryTreeNode<Integer> t, int n) {
int depth = 0;
if (t.getValue() == n) {
return depth;
} else {
if (n < t.getValue()) {
BinaryTreeNode<Integer> left = t.getLeft();
if (left == null) {
throw new TreeException("Value not found in tree!");
} else {
return 1 + calculateDepth(left, n);
}
} else {
BinaryTreeNode<Integer> right = t.getRight();
if (right == null) {
throw new TreeException("Value not found in tree!");
} else {
return 1 + calculateDepth(right, n);
}
}
}
}
/**
* 2nd implementation - "Replace Nested Conditional with Guard Clauses" pattern.
*
* To improve the readability, we can get rid of the nested conditional by identifying
* the distinct cases and insert 'return' statements for these.
*
* Authors: book.
*/
public static int calculateDepth_2(BinaryTreeNode<Integer> t, int n) {
int depth = 0;
if (t.getValue() == n)
return depth;
if (n < t.getValue() && t.getLeft() != null)
return 1 + calculateDepth_2(t.getLeft(), n);
if (n > t.getValue() && t.getRight() != null)
return 1 + calculateDepth_2(t.getRight(), n);
throw new TreeException("Value not found in tree!");
}
/**
* 3rd implementation - "Extract method" refactoring.
*
* Although calculateDepth_2 is now easier to understand, its complexity has not
* decreased. In order to reduce the complexity, you should extract the nested
* conditionals to separate methods.
*
* Authors: book.
*/
public static int calculateDepth_3(BinaryTreeNode<Integer> t, int n) {
int depth = 0;
if (t.getValue() == n)
return depth;
else
return traverseByValue(t, n);
}
private static int traverseByValue(BinaryTreeNode<Integer> t, int n) {
BinaryTreeNode<Integer> childNode = getChildNode(t, n);
if (childNode == null) {
throw new TreeException("Value not found in tree!");
} else {
return 1 + calculateDepth_3(childNode, n);
}
}
private static BinaryTreeNode<Integer> getChildNode(BinaryTreeNode<Integer> t, int n) {
if (n < t.getValue()) {
return t.getLeft();
} else {
return t.getRight();
}
}
/**
* 4th implementation - "Separation of Concerns" design principle.
*
* Here we broke the original control statements to make each concern of the algorithm explicit.
* The hard part was to come up with the idea of "next node", where the book authors came very
* close to it with the getChildNode method.
*
* Think SoC like this:
*
* "So much complexity in software comes from trying to make one thing do two things."
* ~ Ryan Singer (37signals)
*
* SoC can be applied to every abstraction level:
* - control statements and loops
* - types
* - components
* - packages
* - systems
*
* Author: Nick Dandoulakis.
*/
public static int calculateDepth_4(BinaryTreeNode<Integer> t, int n) {
// concern #1, look for 'n'
BinaryTreeNode<Integer> nextNode;
if (n == t.getValue())
nextNode = t;
else if (n < t.getValue())
nextNode = t.getLeft();
else
nextNode = t.getRight();
// concern #2, are we done?
if (nextNode == null)
throw new TreeException("Value not found in tree!");
else if (nextNode == t)
return 0;
// concern #3, search deeper
return 1 + calculateDepth_4(nextNode, n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment