Saturday, 10 October 2015

Observer pattern or Publish-subscribe pattern

Motivation

Let's assume we have a channel on YouTube which is subscribed by many users. Now any new video uploaded on that channel should be notify to all subscribers by SMS or mail alerts.

Observer pattern: we need to separate the subject (YouTube channel) from its observers (subscribers) in such a way that adding new observer (subscription for new user) will be transparent for the server.


Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

In observer pattern, the objects that watch on the state of another object are called Observers and the object that is being watched is called Subject. The Subject, maintains a list of its dependents, called observers, and notifies them automatically of any state changes, usually by calling one of their methods.

It is mainly used to implement distributed event handling systems.





public interface Observer {

      public void update();

      public void setSubject(Subject subject);
}

public interface Subject {

      public void registerObserver(Observer observer);

      public void notifyObserver();

      public void unRegisterObserver(Observer observer);

      public Object getUpdate();
}

import java.util.ArrayList;
import java.util.List;
public class Blog implements Subject {

      List<Observer> observersList;
      private boolean stateChange;

      public Blog() {
            this.observersList = new ArrayList<Observer>();
            stateChange = false;
      }

      public void registerObserver(Observer observer) {
            observersList.add(observer);
      }

      public void unRegisterObserver(Observer observer) {
            observersList.remove(observer);
      }

      public void notifyObserver() {

            if(stateChange) {
                  for (Observer observer : observersList) {
                        observer.update();
                  }
            }
      }

      public Object getUpdate() {
            Object changedState = null;
            // should have logic to send the
            // state change to querying observer
            if (stateChange) {
                  changedState = "Observer Design Pattern";
            }
            return changedState;
      }

      public void postNewArticle() {
            stateChange = true;
            notifyObserver();
      }
}

public class User implements Observer {
      public User(String userName) {
            this.userName = userName;
      }

      private String userName;
     
      private String article;
      private Subject blog;

      public void setSubject(Subject blog) {
            this.blog = blog;
            article = "No New Article!";
      }

      @Override
      public void update() {
            System.out.println("State change reported by Subject "+ userName);
            article = (String) blog.getUpdate();
      }

      public String getArticle() {
            return article;
      }
}

public class ObserverDesignPattern {
      public static void main(String args[]) {
            Blog blog = new Blog();
            User user1 = new User("user 1");
            User user2 = new User("user 2");
           
            blog.registerObserver(user1);
            blog.registerObserver(user2);
           
            user1.setSubject(blog);
            user2.setSubject(blog);
     
            System.out.println(user1.getArticle());        
            blog.postNewArticle();
            System.out.println(user1.getArticle());
      }
}
Output:
No New Article!
State change reported by Subject to user 1
State change reported by Subject to user 2
Observer Design Pattern


Usage of Observer design pattern

Java Message Service (JMS)uses Observer pattern along with Mediator pattern to allow applications to subscribe and publish data to other applications.

MVC frameworks also use Observer pattern where Model is the Subject and Views are observers that can register to get notified of any change to the model.

The observer pattern is implemented in numerous programming libraries and systems, including almost all GUI toolkits.

Java provides inbuilt platform for implementing Observer pattern through java.util.Observable class and java.util.Observer interface.

Monday, 5 October 2015

Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

For graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

1.  Start at any node in the graph.
Mark the starting node as reached.
Mark all the other nodes in the graph as unreached.

#Minimum cost Spanning Tree (MST) consists of the starting node.

2. Find an edge e with minimum cost in the graph that connects a reached node x to an unreached node y.

3. Add the edge e found in the previous step to the MST.
Mark the unreached node y as reached.

4. Repeat the steps 2 and 3 until all nodes in the graph have become reached.


Pseudo code

ReachSet = {0};                    // You can use any node...
UnReachSet = {1, 2, ..., N-1};
SpanningTree = {};

while ( UnReachSet ≠ empty ) {
              Find edge e = (x, y) such that:
                    x  ReachSet
                    y  UnReachSet
                    e has smallest cost

              SpanningTree = SpanningTree  {e};
              ReachSet   = ReachSet  {y};
              UnReachSet = UnReachSet - {y};
}

Do you know it?


Developed by: Czech mathematician Vojtěch Jarník in 1930.

Rediscovered and republished by: computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.

Factory Method Pattern (Virtual Constructor)

When we want to return one sub-class object from multiple sub-classes using an input, should use Factory design pattern. Factory class takes responsibility of instantiation the class (We can return Singleton instance from static factory method).

In Factory pattern, we create object without exposing the creation logic to the client and refer to newly created object using a common interface.



       

Example:Coffee/Vending machine, give input from options and as per input coffee, lemon tea, plain milk or hot water will be an output.

interface Drink {
       void prepare();
}

class Coffee implements Drink {
       @Override
       public void prepare() {
              System.out.println("Coffee is prepared !!");
       }
}

class LemonTea implements Drink {
       @Override
       public void prepare() {
              System.out.println("Lemon Tea is prepared !!");
       }
}

class PlainWater implements Drink {
       @Override
       public void prepare() {
              System.out.println("Plain Water is prepared !!");
       }
}

class VedingMachine {
       public static Drink getDrink(String str) {
              if("PlainWater".equals(str)) {
                     return new PlainWater();
              } else if("Coffee".equals(str)) {
                     return new Coffee();
              } else if("LemonTea".equals(str)) {
                     return new LemonTea();
              }
              return null;
       }
}

public class FactoryPatternTest {
       public static void main(String[] args) {
              Drink drink = VedingMachine.getDrink("Coffee");
              drink.prepare();
       }
}

Output: Coffee is prepared !!


Benefits of Factory Method Pattern

Factory Method Pattern provides approach to code for interface rather than implementation and it provides abstraction between implementation and client classes through inheritance.

Factory Method Pattern allows the sub-classes to choose the type of objects to create.

We can easily change the implementation of sub-class because client program is unaware of this. It makes code more robust, less coupled and easy to extend (client interacts solely with the resultant interface or abstract class).

Usage in JDK

java.util.Calendar, ResourceBundle and NumberFormat getInstance() methods uses Factory pattern.

valueOf() method in wrapper classes like Boolean, Integer etc.

Spring and hibernate frameworks.



Related Posts Plugin for WordPress, Blogger...