Tuesday, July 22, 2008

Generic implementation of sorting algorithms and using Strategy pattern - End

This is the last part of the Sorting algorithm implementation series. In this post i will show the implementation of Strategy pattern and how to use the pattern for accessing the sorting implementations we had created.


Strategy pattern defines a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it. The Strategy pattern enables a client to choose which algorithm to use from a family of algorithms and gives it a simple way to access it.

To implement a Strategy I will create an Interface ISortStrategy that exposes a Sort method for any collection that implements IComparable.

public interface ISortStrategy where T : IComparable

{

List Sort(IEnumerable input);

}

And each of the classes that have different sorting algorithm implementations will be implemented from this interface

Eg:

public class BubbleSorter : ISortStrategy where T : IComparable

{

#region ISortStrategy Members

public List Sort(IEnumerable input)

{

List sortItems = new List(input);

Int32 right = sortItems.Count - 1;

do

{

Int32 lastSwap = 0;

for (Int32 i = 0; i <>

{

if (sortItems[i].CompareTo(sortItems[i + 1]) > 0)

{

T temp = sortItems[i];

sortItems[i] = sortItems[i + 1];

sortItems[i + 1] = temp;

lastSwap = i;

}

}

right = lastSwap;

}

while (right > 0);

return sortItems;

}

#endregion

}

In the client code I can access a strategy like

ISortStrategy<Employee> sortStrategy = default(ISortStrategy<Employee>);

String category = "Heap";

switch (category)

{

case "Bubble":

sortStrategy = new BubbleSorter<Employee>();

break;

case "Merge":

sortStrategy = new MergeSorter<Employee>();

break;

case "Heap":

sortStrategy = new HeapSorter<Employee>();

break;

case "Quick":

sortStrategy = new QuickSorter<Employee>();

break;

case "Selection":

sortStrategy = new SelectionSorter<Employee>();

break;

}

List<Employee> sortedList = sortStrategy.Sort(emps);

Thursday, July 17, 2008

Generic implementation of sorting algorithms and using Strategy pattern - Part 3

After implementation of the Insertion and Shell Sort, this article explains the implementation of the other three famous sorting algorithms (Merge sort, Heap sort and Quick sort).

Merge Sort

Merge sort works by comparing every two elements and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Merge sort uses recursion for sorting the list.

The implementation of MergeSorter class

public class MergeSorter where T : IComparable

{

List tempList;

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

tempList = new List(inputItems.Count);

for (int i = 0; i <>

tempList.Add(default(T));

MergeSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void Merge(ref List inputList, int left, int middle, int right)

{

int i;

int j;

for (i = middle + 1; i > left; i--)

{

tempList[i - 1] = inputList[i - 1];

}

for (j = middle; j <>

{

tempList[right + middle - j] = inputList[j + 1];

}

for (int k = left; k <= right; k++)

{

// Less Than

if (tempList[j].CompareTo(tempList[i]) == -1)

{

inputList[k] = tempList[j--];

}

else

{

inputList[k] = tempList[i++];

}

}

}

private void MergeSort(ref List a, int left, int right)

{

if (right <= left) return;

int middle = (right + left) / 2;

//recursive sorting

MergeSort(ref a, left, middle);

MergeSort(ref a, middle + 1, right);

Merge(ref a, left, middle, right);

}

}

Heap Sort

The heap sort works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a binary tree (heap). Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.

The implementation of HeapSorter class

public class HeapSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

HeapSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void HeapSort(ref List items, Int32 start, Int32 end)

{

int left = start + ((end - start) >> 1);

int right = end;

int offset = start;

while (left >= start)

{

SiftDown(items, offset, left, end);

left -= 1;

}

while (right > start)

{

Swap(items, right, start);

right -= 1;

SiftDown(items, offset, start, right);

}

}

private void SiftDown (List inputItems, int offset, int start, int end)

{

int root = start;

int child;

while (((root - offset) * 2 + 1) <= (end - offset))

{

child = ((root - offset) * 2 + 1) + offset;

if (child <>

{

child += 1;

}

if (inputItems[root].CompareTo(inputItems[child]) <>

{

Swap(inputItems, root, child);

root = child;

}

else

{

break;

}

}

}

private void Swap (List inputItems, int i, int k)

{

T swap = inputItems[i];

inputItems[i] = inputItems[k];

inputItems[k] = swap;

}

}

Quick Sort

Quick sort uses the algorithm that partitions an array to choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. It then uses recursion to follow the same algorithm to finally create a sorted list of elements.

The implementation of QuickSorter class

public class QuickSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List sorteditems = new List(input);

QuickSort(ref sorteditems, 0, sorteditems.Count - 1);

return sorteditems;

}

private void QuickSort(ref List sortedItems, int left, int right)

{

if (right <= left) return;

int i = Partition(ref sortedItems, left, right);

QuickSort(ref sortedItems, left, i - 1);

QuickSort(ref sortedItems, i + 1, right);

}

private int Partition(ref List a, int l, int r)

{

T tmp;

int i = l - 1;

int j = r;

T v = a[r]; for (; ; )

{

while (a[++i].CompareTo(v) == -1)

{

}

while (v.CompareTo(a[--j]) == -1)

{

if (j == l) break;

}

if (i >= j) break;

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

a[r] = a[i];

a[i] = v;

return i;

}

}

In the next series of this article, i will show how to use strategy pattern to select the sorting algorithms we have implemented.

Wednesday, July 16, 2008

Model View Controller - C# implementation

Model view controller is a classic pattern that is used in applications that need ability to maintain multiple views with same data. It can be used as an architectural pattern as well as a design pattern. MVC helps us to decouple the presentation layer and business layer (domain logic layer). The presentation layer is further divided into the View and Controller.

The MVC abstraction can be graphically explained as given below:

The main participants are

Model: The business entity/ domain data on which the application operates. Many applications use a persistent storage mechanism (such as a database) to store data. MVC does not specifically mention the data access layer because it is understood to be underneath or encapsulated by the Model.

View: The user interface that renders the model into a form of interaction.

Controller: Handles a request from a view and updates the model resulting a change in Model’s state.

To implement MVC in .NET we need mainly three classes (View, Controller and the Model). This example is implemented using interfaces that will allow me to make my application loosely coupled.

I have the interfaces (IView, IModel, IController) implemented as

public interface IView

{

//Method to change the state of view according to the model changes

void UpdateView(IModel model);

//These methods are used by the controller to change the state of view

void SalaryIncreased(Boolean increased);

void CompanyChanged(Boolean changed);

void DesignationChanged(Boolean changed);

}

public interface IModel

{

String UserName { get; set; }

String Company { get; set; }

String Designation { get; set; }

Int32 Salary { get; set; }

//Implementing the observer pattern. The model uses an observer

//pattern implementation to notify the views about the changes in the

//model

void AddObserver(IView view);

void RemoveObserver(IView view);

void Notify();

//Observer pattern implementation methods. End

}

public interface IController

{

//The methods to change the state of Model

void ChangeSalary(Int32 salary);

void ChangeCompany(String company);

void ChagneDesignation(String designation);

//Storing the Model and View instances in the controller

IModel Model { get; set; }

IView View { get; set; }

}

In my sample application I have a User class (Model) and a Form that helps users to change the User properties (View). I also have a UserController class that acts as a controller for the View.

The model

public class User: IModel

{

private String userName;

private String company;

private String designation;

private Int32 salary;

//List of observers. You can add the views that should be notified the change on Model in this

//collection.

List<IView> observers = new List<IView>();

public User() { }

public User(String userName, String company, String designation, Int32 salary)

{

this.userName = userName;

this.company = company;

this.designation = designation;

this.salary = salary;

}

#region IModel Members

public string UserName

{

get

{

return this.userName;

}

set

{

this.userName = value;

}

}

public string Company

{

get

{

return this.company;

}

set

{

this.company = value;

this.Notify();

}

}

public string Designation

{

get

{

return this.designation;

}

set

{

this.designation = value;

this.Notify();

}

}

public int Salary

{

get

{

return this.salary;

}

set

{

this.salary = value;

this.Notify();

}

}

//Adding the View into the Observer collection

public void AddObserver(IView view)

{

observers.Add(view);

}

public void RemoveObserver(IView view)

{

if (observers.Contains(view))

observers.Remove(view);

}

//Iterates through the observers and notify them about the model change.

public void Notify()

{

foreach (IView view in observers)

{

view.UpdateView(this);

}

}

#endregion

}

The View

public partial class UserView : Form, IView

{

//The controller instance for the View.

private IController Controller = new UserController();

//Creating a model. (Sample).

private IModel Model = new User("Arun", "EDS", "Tech Lead", 50000);

public UserView()

{

InitializeComponent();

//Wire the controller and model to the View

WireUpControllerModel(Model, Controller);

//Update the View with the model's current state

this.UpdateView(Model);

}

private void _companycomboBox_SelectedIndexChanged(object sender, EventArgs e)

{

Controller.ChangeCompany(_companycomboBox.Text);

}

private void _designationComboBox_SelectedIndexChanged(object sender, EventArgs e)

{

Controller.ChagneDesignation(_designationComboBox.Text);

}

private void _changeSalaryButton_Click(object sender, EventArgs e)

{

Controller.ChangeSalary(Convert.ToInt32(_newSalaryTextBox.Text));

}

#region IView Members

public void UpdateView(IModel model)

{

_userNameTextBox.Text = model.UserName;

_designationTextBox.Text = model.Designation;

_companyTextBox.Text = model.Company;

_salaryTextBox.Text = model.Salary.ToString();

}

private void WireUpControllerModel(IModel model, IController controller)

{

if (Model != null)

Model.RemoveObserver(this);

Model = model;

Controller = controller;

Controller.Model = this.Model;

Controller.View = this;

Model.AddObserver(this);

}

public void SalaryIncreased(bool increased)

{

if (increased)

_salaryChangeLabel.Text = "Salary Increased!!!";

else

_salaryChangeLabel.Text = "Salary Decreased!!!";

}

public void CompanyChanged(bool changed)

{

if (changed)

_companyChangeLabel.Text = "Company Changed!!!";

}

public void DesignationChanged(bool changed)

{

if (changed)

_designationChangeLabel.Text = "Designation Changed!!!";

}

#endregion

}

The controller:

public class UserController : IController

{

private IView view;

private IModel model;

public UserController(IView view, IModel model)

{

this.view = view;

this.model = model;

}

public UserController() { }

#region IController Members

public void ChangeSalary(int salary)

{

if (Model.Salary > salary)

View.SalaryIncreased(false);

else

View.SalaryIncreased(true);

Model.Salary = salary;

}

public void ChangeCompany(string company)

{

if (Model.Company == company)

View.CompanyChanged(false);

else

View.CompanyChanged(true);

Model.Company = company;

}

public void ChagneDesignation(string designation)

{

if (Model.Designation == designation)

View.DesignationChanged(false);

else

View.DesignationChanged(true);

Model.Designation = designation;

}

public IModel Model

{

get

{

return this.model;

}

set

{

this.model = value;

}

}

public IView View

{

get

{

return this.view;

}

set

{

this.view = value;

}

}

#endregion

}