Tuesday, May 29, 2012

Object Oriented Design Principles

Object-oriented analysis and design:

This is a software engineering approach that models a system as a group of interacting objects. Each object represents some entity of interest in the system being modeled, and is characterized by its class, its state (data elements), and its behavior. Various models can be created to show the static structure, dynamic behavior, and run-time deployment of these collaborating objects

What are Software Design Principles?

Software design principles represent a set of guidelines that helps us to avoid having a bad design. Three important characteristics of a bad design that should be avoided:

Rigidity - It is hard to change because every change affects too many other parts of the system.
Fragility - When you make a change, unexpected parts of the system break.
Immobility - It is hard to reuse in another application because it cannot be disentangled from the current application.

Class Design principles:

  • Open Close Principle
  • Dependency Inversion Principle
  • Interface Segregation Principle
  • Single Responsibility Principle
  • Liskov's Substitution Principle

Open Close Principle

Software entities like classes, modules, functions should be open for extension but closed for modification.


// Open-Close Principle - Bad example
class GraphicEditor
{
    public void Draw(Shape s)
    {
        if (s.type == 1)
            DrawRectangle(s);
        else if (s.type == 2)
            DrawCircle(s);
    }

    public void DrawRectangle(Shape s){}
    public void DrawCircle(Shape s){}
}

class Shape { public int type;}

class Rectangle:Shape
{
    Rectangle() { base.type = 1; }
}

class Circle:Shape
{
    Circle() { base.type = 2; }
}

// Open-Close Principle - Good example
class GraphicEditor
    {
        public void Draw(Shape s) {s.Draw();}
    }

    abstract class Shape
    {
        public abstract void Draw();
    }

    class Rectangle : Shape
    {
        public override void Draw() { }
    }

    class Circle:Shape
    {
        public override void Draw() { }
    }

Key Points:
no unit testing required.
no need to understand the source code from Graphic Editor.
since the drawing code is moved to the concrete shape classes, it's a reduced risk to affect old functionality when new functionality is added.

Dependency Inversion Principle

High-level modules should not depend on low-level modules. Both should depend on abstractions.
Abstractions should not depend on details. Details should depend on abstractions.


// Dependency Inversion Principle - Bad example
class Worker 
{
public void work() {// ....working}
}
class Manager 
{
public void manage(Worker w) {w.work();}
}
class SuperWorker 
{
public void work() {//.... working much more}
}


// Dependency Inversion Principle - Good example
interface IWorker 
{
public void work();
}
class Worker implements IWorker
{
public void work() {// ....working}
}
class SuperWorker  implements IWorker
{
public void work() {//.... working much more}
}
class Manager 
{
public void manage (IWorker w) {w. work();}
}


Manager class should not be changed.
minimized risk to affect old functionality present in Manager class.
no need to redone the unit testing for Manager class.


Interface segregation


Clients should not be forced to depend upon interfaces that they don't use


// interface segregation principle - bad example
interface IWorker 
{
public void work();
public void eat();
}
class Worker implements IWorker
{
public void work(){// ....working}
public void eat() {// ...... eating in launch break}
}
class SuperWorker implements IWorker
{
public void work() {//.... working much more}
public void eat() {//.... eating in launch break}
}
class Manager 
{
IWorker worker;
public void setWorker(IWorker w) {worker=w;}
public void manage() {worker.work(); }
}


// interface segregation principle - good example
interface IWorker extends Feedable, Workable 
{
}
interface IWorkable 
{
public void work();
}
interface IFeedable
{
public void eat();
}
class Worker implements IWorkable, IFeedable
{
public void work() {// ....working}
public void eat() {//.... eating in launch break}
}
class Robot implements IWorkable
{
public void work() {// ....working}
}
class SuperWorker implements IWorkable, IFeedable
{
public void work() {//.... working much more}
public void eat() {//.... eating in launch break}
}
class Manager 
{
Workable worker;
public void setWorker(Workable w) {worker=w;}
public void manage() {worker.work();}
}


Following it's the code supporting the Interface Segregation Principle. By splitting the IWorker interface in 2 different interfaces the new Robot class is no longer forced to implement the eat method. Also if we need another functionality for the robot like recharging we create another interface IRechargeble with a method recharge


Single responsibility



A class should have only one reason to change.


// single responsibility principle - bad example


interface IEmail 
{
public void setSender(String sender);
public void setReceiver(String receiver);
public void setContent(String content);
}
class Email implements IEmail 
{
public void setSender(String sender) {// set sender; }
public void setReceiver(String receiver) {// set receiver; }
public void setContent(String content) {// set content; }
}


// single responsibility principle - good example
interface IEmail 
{
public void setSender(String sender);
public void setReceiver(String receiver);
public void setContent(IContent content);
}
interface Content 
{
public String getAsString(); // used for serialization
}
class Email implements IEmail 
{
public void setSender(String sender) {// set sender; }
public void setReceiver(String receiver) {// set receiver; }
public void setContent(IContent content) {// set content; }
}


Key Points:
adding a new protocol causes changes only in the Email class.
adding a new type of content supported causes changes only in Content class.


Liskov’s substitution

Derived types must be completely substitutable for their base types.


// Violation of Likov's Substitution Principle
class Rectangle
{
protected int m_width;
protected int m_height;


public void setWidth(int width){m_width = width;}
public void setHeight(int height){m_height = height; }
public int getWidth(){return m_width;}
public int getHeight(){ return m_height;}
public int getArea(){return m_width * m_height;}
}
class Square extends Rectangle 
{
public void setWidth(int width){m_width = width;m_height = width; }
public void setHeight(int height){m_width = height;m_height = height;}
}
class LspTest
{
private static Rectangle getNewRectangle()
{
// it can be an object returned by some factory ... 
return new Square();
}


public static void main (String args[])
{
Rectangle r = LspTest.getNewRectangle();
        
r.setWidth(5);
r.setHeight(10);
// user knows that r it's a rectangle. 
// It assumes that he's able to set the width and height as for the base class


System.out.println(r.getArea());
// now he's surprised to see that the area is 100 instead of 50.
}
}


Below is the classic example for which the Likov's Substitution Principle is violated. In the example 2 classes are used: Rectangle and Square. Let's assume that the Rectangle object is used somewhere in the application. We extend the application and add the Square class. The square class is returned by a factory pattern, based on some conditions and we don't know the exact what type of object will be returned. But we know it's a Rectangle. We get the rectangle object, set the width to 5 and height to 10 and get the area. For a rectangle with width 5 and height 10 the area should be 50. Instead the result will be 100



Sunday, May 27, 2012

Maximum Sum Of Consecutive Numbers - O(n) solution in C#

Problem:

n numbers (both +ve and -ve) are arranged in a circle. find the maximum sum of consecutive nos. Do this in O(n) time
E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)
Explanation and algorithm:
We will discuss the problem in two steps. One where we will get the answer in O(n^2). Then we will make it efficient to bring it to O(n).

Step 1:
Let us understand given problem is not straight away Kadane algorithm. Since we need to consider all the rotations of the given array as well. If the array is linear then applying kadane algorithm would give us the largest sum of consecutive numbers.  Hence first approach is to apply Kadane algorithm for all 'n' different arrays, each array starting at 'i'th index and includes all the elements till [i%n + n - 1] elements.

e.g. if 2,3,4, 5 is the given array, {4,5,2,3} is also a possible array like other two. Hence there would be four different arrays in this case. Finding out the maximum of largest consecutive sums of each individual array.
I'm also handling two other cases where all are negative numbers and all are positive numbers.

An array starting at 'i'th location will end at 'i'+ n -1 th location. Use modulus to take care of index.


       public static void PrintHighestSum()
        {
            int[] input = {53, -8, 11 , - 9 , -11, 0, 8};
            int maxEndingHere = 0; 
            int maxTillHere = 0;
            bool isAllPositive = true;
            int sum = 0;
            for(int i=0;i< input.Length;i++)
            {
                isAllPositive = isAllPositive && (input[i] >= 0);                
                if (!isAllPositive) break;
                sum = sum + input[i];
            }
            if (isAllPositive)
            {
                Console.WriteLine(sum);
                return;
            }
            bool isAllNegative = true;


            sum = input[0];
            for (int i = 0; i < input.Length; i++)
            {
                isAllNegative = isAllNegative && (input[i] < 0);                
                if (!isAllNegative) break;
                sum = Math.Max(sum, input[i]);
            }
            if (isAllNegative)
            {
                Console.WriteLine(sum);
                return;
            }


            //Kadane's algorithm
            //maxEndingHere = Math.Max(input[i % input.Length], input[i % input.Length] + maxEndingHere);
            //maxTillHere = Math.Max(maxTillHere, maxEndingHere);
            //here there can be n arrays, since all numbers are arranged in circle
            //each rotation of the number is a different array.. 
            //find max in each array using kadane algo, stack it and then find max
            //n^s solution 


            Stack<int> maxs = new Stack<int>();
            
            for (int i = 0; i < input.Length; i++)
            {
                maxEndingHere = maxTillHere = 0;
                for (int j = i; j < input.Length + i; j++)
                {
                    maxEndingHere = Math.Max(input[j % input.Length], input[j % input.Length] + maxEndingHere);
                    maxTillHere = Math.Max(maxTillHere, maxEndingHere);
                }
                maxs.Push(maxTillHere);
            }
           
            int tempMax = 0;
            maxTillHere = 0;
            for (int i = 0; i < maxs.Count; i++)
            {
                tempMax = maxs.Pop();
                if (tempMax > maxTillHere)
                    maxTillHere = tempMax;
            }
            Console.WriteLine(maxTillHere);
        }




Step 2: (Making the solution efficient) - Linear O(n) solution
This solution is quite tricky not straight forward approach. Once we apply Kadane algorithm for given array we get maximum consecutive sum. When there are negative elements in the array, we can also find out negative consecutive sum. Maximum of (max consecutive sum, sum of all elements - maximum negative consecutive sum) will the expected output. 


To illustrate we will take example of given array itself,  
{8,-8,9,-9,10,-11,12}


Here Max consecutive sum from (0, n-1) we get is  12
Max negative sum is (-11) 
Sum of all elements is  11.


Required Maximum Consecutive Sum  = Max (max cons sum, (sum of all elements - max negative cons sum))
=> Max(12, (11-(-11)) => Max(11, 22) = 22


Below code computes largest consecutive sum of the array from 0,n-1 and also negative consecutive sum(uses easy manipulation using -1 as sign i.e. multiplying max sum with -1 and then comparing max consecutive sum till now). We will call it twice once with 1 to find out consecutive sum and once with -1 to find max negative consecutive sum.


=================================================================================

static int MaximumConsecutiveSum(int[] input, int sign)
{
            int max_so_far = 0, max_ending_here = 0, i;
            for (i = 0; i < input.Length; i++)
            {
                max_ending_here = max_ending_here + input[i];
                if (sign * max_ending_here < 0)
                    max_ending_here = 0;
                if (sign * max_so_far < sign * max_ending_here)
                    max_so_far = max_ending_here;
            }
            return max_so_far;
}

 public static void PrintHighestSum()
 {



            int[] input = { -2, -1, 9, -9, 10,  12 };
            int maxEndingHere = 0; 
            int maxTillHere = 0;
            bool isAllPositive = true;
            int sum = 0;
            for(int i=0;i< input.Length;i++)
            {
                isAllPositive = isAllPositive && (input[i] >= 0);                
                if (!isAllPositive) break;
                sum = sum + input[i];
            }
            if (isAllPositive)
            {
                Console.WriteLine(sum);
                return;
            }
            bool isAllNegative = true;


            sum = input[0];
            for (int i = 0; i < input.Length; i++)
            {
                isAllNegative = isAllNegative && (input[i] < 0);                
                if (!isAllNegative) break;
                sum = Math.Max(sum, input[i]);
            }
            if (isAllNegative)
            {
                Console.WriteLine(sum);
                return;
            }


            sum = 0;
            for (int i = 0; i < input.Length; i++) sum += input[i];
                
            int max = MaximumConsecutiveSum(input, 1);
            int negativeMax = MaximumConsecutiveSum(input, -1);


            max = Math.Max(max, (sum - negativeMax));
            Console.WriteLine(max);
}


=================================================================================
Reference: GeeksforGeeks.org






Friday, May 25, 2012

Prefer Properties over public data members - C#

Public data members in a class is not a good design idea. When properties expose data members publicly with more control over access, properties can replace data members at every stage. Below points support the fact why properties must be preferred over public data members.

è Properties can access control even over set and get. Few properties can only be "gettable" for other classes or only "settable".

è Properties are first class language elements, anything that we can do with member functions we can also do with properties.
public virtual string Name
{
get;
protected set;
}
è Properties are data bound to controls not the public data members. This is as designed by framework that only Properties can be set as data source to control's like textbox but not the public data members.
è Properties are easier to change as to cover new requirements or behaviors in future. e.g. We can change logic over get to return a value only if that value's some condition is met.
è Properties can contain thread safe logic. E.g. a setter or getter can be locked by an object to avoid multi-thread access at a single time.

public class Customer
{
private object syncHandle = new object();
private string name;
public string Name
{
get
{
lock (syncHandle)
return name;
}
set
{
if (string.IsNullOrEmpty(value))
throw new ArgumentException(
"Name cannot be blank",
"Name");
lock (syncHandle)
name = value;
}
}

è Properties can do basic validation on the data before set or data. This avoids us from adding validation logic throughout the code when we access that data.
è Properties can be Virtual. They are allowed to be overridden unlike public data members.
è Properties can be abstract and also can be part of interface. 
è Properties can be parameterized . e.g. while implementing indexers, Properties will accept index to return item at that index.

public Address this[string name]
{
get { return adressValues[name]; }
set { adressValues[name] = value; }
        }

è Properties can invoke other methods in Set or Get just like from any other member method.

There can be many other advantages of Properties which we find out while coding.
   
References: Book - Effective C# - Version 4