Workshop 03

Workshop 03 - Design Patterns Basics

← Home →

Singleton (Creational Design Pattern)

Consider the case of one class having a single private constructor. Apparently, it is impossible or, at least, useless.
Analyze the below Singleton thread safe implementation:

public class Singleton
{
	private static object _lockObject = new object();
	private static Singleton _instance;

	// private constructor => will block class instantiation
	private Singleton() { }

	public static Singleton Instance 
	{ 
		get 
		{ 
			if (_instance == null)
			{
				lock(_lockObject)
				{
					if (_instance == null)
					{
						_instance = new Singleton();
					}
				}
			}
			return _instance; 
		} 
	}
}

Generic singleton implementation:

public class Singleton<T> where T : class, new()
{
	private static T _instance = null;

	public static T Instance
	{
		get
		{

			if (_instance == null)
			{
				_instance = new T();
			}
			return _instance;
		}
	}

}

public class SingletonExample: Singleton<SingletonExample>
{
	public SingletonExample()
	{ }
}

public static class ExampleOfUse
{
	public static void Test()
	{
		var instance = SingletonExample.Instance;
	}
}

Proxy (Structural Design Pattern)

Multiple inheritance is not allowed in .Net. However, when necessary, it could be simulated using the Proxy pattern

interface IBaseClass
{
	double f(double x);
	double g(double x);
}

class BaseClass : IBaseClass
{
	public double f(double x)
	{
		return 2 * x;
	}

	public double g(double x)
	{
		return 3 * x;
	}
}

class DerivedClass : IBaseClass
{
	private BaseClass _base = new BaseClass();

	public double f(double x)
	{
		return _base.f(x);
	}

	public double g(double x)
	{
		return _base.g(x);
	}
}

Strategy (Behavioral Design Pattern)

Allows selecting an algorithm at runtime.

public interface ISet
{
	double ContainsPoint(int shadeOfGray);
}

public class ClassicalSet : ISet
{
	public double ContainsPoint(int shadeOfGray)
	{
		if (shadeOfGray == 0) return 0;
		return 1;
	}
}

public class FuzzySet : ISet
{
	public double ContainsPoint(int shadeOfGray)
	{
		var degree = shadeOfGray / 255;
		return degree;
	}
}

public class ImgProcessing
{
	private ISet _set;
	public ImgProcessing(ISet set)
	{
		_set = set;
	}

	public void Process(int[] shadeOfgrayArr)
	{
		foreach (var shadeOfGray in shadeOfgrayArr)
		{
			var setContainsElement = _set.ContainsPoint(shadeOfGray);
		}
	}
}

Factory (Creational Design Pattern)

The Strategy pattern is often used in combination with Factory.

public enum SetType
{
	Classical,
	Fuzzy
}

public static class SetFactory
{
	public static ISet? Create(SetType setType)
	{
		switch (setType)
		{
			case SetType.Classical:
				return new ClassicalSet();
			case SetType.Fuzzy:
				return new FuzzySet();
			default:
				return null;
		}
	}
}

Side note - Recursion

Consider the Manna-Pnueli function:

1) Calculate f(8);
2) Implement an iterative solution.

f(8) = f(f(10)) = f(f(f(12))) = f(f(11)) = f(f(f(13))) = f(f(12)) = f(11) = f(f(13)) = f(12) = 11

Let's write the same thing... vertically. The "floor" corresponds to the number of "f"-s:

One can notice only 2 variables are necessary: the current value, and the number of calls (the number of "f"-s). The algorithm ends when the "floor" becomes 0.

public long Manna(long x)
{
	long level = 1;
	while (level > 0)
	{
		if (x >= 12)
		{
			level--;
			x = x - 1;
		}
		else
		{
			level++;
			x = x + 2;
		}
	}
	return x;
}

The Manna-Pnueli recursive solution is immediate: just "copy" the function definition...

Observation! Although it is sometimes easier to implement, the recursive method could be less efficient than the iterative one.
- For example, in the Manna-Pnueli case, only 2 variables are necessary in the iterative approach (instead of a stack).
- Fibonacci series is an example of highly unrecommended, CASCADE RECURSION, when implemented by directly employing the recurrent expression: Fib(n) = Fib(n-2) + Fib(n-1)

Consider below, a correct Fibonacci recursive implementation at O(n)!

	
public static Tuple<int, int> Fibonacci(int n)
{
	if (n == 1)
	{ 
		return new Tuple<int, int>(0, 1);
	}
	var prv = Fibonacci(n - 1);
	var crtItem1 = prv.Item2;
	var crtItem2 = prv.Item1 + prv.Item2;
	var crt = new Tuple<int, int>(crtItem1, crtItem2);
	return crt;
}

One should also pay an important attention to indirect recursion [f() calls g() - g() calls f()], as it could result in unwanted "stack overflow exceptions":

private void buttonTest_Click(object sender, EventArgs e)
{
	textBoxTest.Text += "a";
}

private void textBoxTest_TextChanged(object sender, EventArgs e)
{
	buttonTest_Click(null, null);
}

Template Method (Behavioral Design Pattern)

Consider the below Template design pattern used for implementing the Backtracking programming technique:

public abstract class BacktrackingTemplate<T>
{
	protected Stack<T>? Stack { get; set; }

	protected abstract T NullValue { get; }
	protected abstract bool IsNull(T element);
	// Backtracking applies to an ordered set e.g.A = { 1, 2, ..., n}
	protected abstract T GetNext(T current);
	protected abstract bool IsValid(T element);
	protected abstract bool IsSolution();

	protected T GetNextValid(T current)
	{
		var nextElement = GetNext(current);
		if (IsNull(nextElement)) return NullValue;
		if (IsValid(nextElement)) return nextElement;

		var nextValid = GetNextValid(nextElement);
		return nextValid;
	}

	public List<T[]> Run()
	{
		var solution = new List<T[]>();
		Stack = new Stack<T>();
		Stack.Push(NullValue);

		while (Stack.Count > 0)
		{
			var currentElement = Stack.Pop();

			var nextValid = GetNextValid(currentElement);
			if (IsNull(nextValid))
			{
				continue;
			}

			Stack.Push(nextValid);
			if (IsSolution())
			{
				var elements = Stack.ToArray();
				solution.Add(elements);
			}
			Stack.Push(NullValue);
		}

		return solution;
	}
}

Inherit the previous abstract class for implementing various problems: generating permutations, cartesian product, etc.

public class Permutations : BacktrackingTemplate<int>
{
	protected int N { get; set; }

	public Permutations(int n)
	{
		N = n;
	}

	protected override int NullValue => 0;

	protected override bool IsNull(int element)
	{
		return element == NullValue;
	}

	protected override int GetNext(int current)
	{
		if (current == N) return NullValue;
		var next = ++current;
		return next;
	}

	protected override bool IsValid(int element)
	{
		if (Stack.Count >= N) return false;
		if (element <= NullValue || element > N) return false;
		var valid =  !Stack.Contains(element);
		return valid;
	}


	protected override bool IsSolution()
	{
		var isSolution = Stack.Count == N;
		return isSolution;
	}
}

References:

Design Patterns

← Home →