Wednesday, October 10, 2012

Flyod's Cycle Detection Algorithm (Tortoise and Hare Algorithm)


Recently i came across an interesting problem on "how to detect cycles in a linked list?". Digging into that i figured out this famous algorithm Flyod's cycle detection algorithm(aka Tortoise and Hare algorithm) on how to detect whether a linked list is cyclic.

What is a cycle?


Linked list is basically a serious of nodes (object) point to the other and form a chain so that you can traverse, insert or delete an element from the list. Circular linked list is a type of list where the last node points to the first node. Cycles are something different from circular list, where the last node is pointing to a different node other than the "head or start" node.

Sample cycle















How to detect this cycle?

The algorithm goes this way

1. Have two nodes "tortoise" and "hare" both holding the reference of the starting of the list.
2. Check whether "hare's" next is there or not and make the pointer to move 2 hops.
3. Make the "tortoise" to make one hop.
4. At some point of time if both "hare" and "tortoise" are same then your list is cyclic.

Code for the algorithm


public boolean hasCycle(Node first) {
            if(first == null) // list does not exist..so no loop either.
       return false;

   Node tortoise, hare; // create two references.

   tortoise = hare = first; // make both refer to the start of the list.

   while(true) {
       tortoise = tortoise.next;          // 1 hop.

       if(hare.next != null)
           hare = hare.next.next; // 2 hops.
       else
           return false;          // next node null => no loop.

       if(tortoise == null || hare == null) // if either hits null..no loop.
           return false;

       if(tortoise.equals(hare)) // if the two ever meet...we must have a loop.{
       {
        return true;
       }
       
   }
}

Note : The whole code is shared as a link below. This contains the code to create the whole linked list, making it as cyclic and then identify whether its cyclic or not.

Saturday, September 3, 2011

Spring Dependency Injection

Spring - one of the beautiful frameworks that amused me to develop some application on it. I have quite a good experience in using the framework for one of my projects and i was thrilled the way the framework seamlessly integrates with other open source as well as commercial frameworks.

There were quite a lot of samples available over the web for developing a simple sample in Spring. When i was trying to do one i struggled a bit to get it done withing minutes in doing a simple java application (not a web application) in spring. I learnt quite a few things in configuring and make it work. I don't want others to go through the same pain in doing and the result is this blog for you!!!

I love the paradigm of writing code against Interface and spring encourages you to do that (still it supports not doing so as well). Writing code against the interface is one of the awesome OO principle and it encourages the Open Closed Principle (open for extension and closed for modifications). Spring is one such framework which will allow you to follow the OO principles and make you to design in a better way. Lets gets into developing a sample java application in Spring. I am going to make it so simple that our main program just invokes a method in an interface. When you write the code against interface another pain point that follows in the instance creation. If we want to abstract things then there is no point in creating an instance like

Interface i = new InterfaceImpl() . The moment you do like this then you have created a coupling between the invoker and the actual implementation and hence creating a dependency between the invoker and the implementation which is not a good OO design. So how can we do this then!!!!!!!!!!!

We know the concept Dependency Injection(DI) - nothing but eliminating the dependencies by injecting the instances dynamically during runtime and hence eliminating the dependencies during compile time. By doing this the invoker knows only about the interface and not the actual implementation thus giving an eligibility for future extension and closed for modifications. Even in future if the implementation has to change the invoker doesn't even care for that keep running as it is. For more information on DI please refer Martin Fowlers explanation in the link (http://martinfowler.com/articles/injection.html).

Spring provides these DI's seamlessly without any effort for the developer. Spring IOC takes care of providing the instances during runtime and hence clearly seperates the invoker and the implementation.

Spring provides couple of annotations which we need to use in our code in order to achieve the dependency injections to work in the way as expected. Following are some of the annotations that you will find it being used in the sample application


  • @Autowired - as the name goes this wires the instance of an implementation with the invoker. For more information (http://static.springsource.org/spring/docs/2.5.x/reference/beans.html)
  • @Component - this is a class level annotation. this is used to annotate the implementation class. (You will understand more when you see the code snippets of the sample application)
Basically spring recognizes the class being annotated with @Component as a good candidate for auto wiring in the invoker component or application. This kind of recognition is done by spring IOC (Inversion of Control) container.

Below is the code snippet of the interface and its implementation classes

                 public interface Sample {
                     public void invokeSample();
                   }

                @Component
                 public class SampleImpl implements Sample {
                 public void invokeSample() {
                System.out.println("Successfully invoked sampel application");
         }
                 }

You can clearly see the implementation class has the annotation @Component at the class level. Now we should have the invoker get ready to invoke this implementation (without creating an instance of using new operator...come on give me a break)...
Lets see how its being done....

@Component
public class SampleMain {
@Autowired
Sample testSample;
static ApplicationContext appCtx = new ClassPathXmlApplicationContext
                                                                     ("META-INF/webmvc-application.xml");
public static void main(String[] args){
SampleMain sampleMain = appCtx.getBean(SampleMain.class);
sampleMain.invokeSample();
}
private void invokeSample(){
testSample.invokeSample();
}
}

Seems to be a bit confusing. Let me clarify what is happening here. This is a normal java application, meaning a class with public static void main, so it can be run as a standalone application. I have explained about @Autowired so you will be sure that i will explain about that, what the heck is that "webmvc-applicationcontext.xml"? This query would have already popped up in your mind. Spring framework expects this xml (name can be anything...not to be webmvc bla bla) to define the application level bean so that it can be loaded in the application start up. In our sample this xml will refer to the spring versions xsd's and defines the component scan definition. Component scan is nothing but we are using lots of annotations like @Component and @Autowired right, we need to say to Spring framework that which packages in our application should be scanned for these kind of annotations. This i feel is a real good provision provided by Spring to overcome the performance overhead during application start up by giving specific packages for scanning. Since scanning under the hood uses java reflection and reflection being a heavy task we should be legitimate in giving this component scan feature (since this is a small app i would have declared the whole applications start package..dont worry). The xml code is as below

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
      xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
      xmlns:aop="http://www.springframework.org/schema/aop"
      xmlns:tx="http://www.springframework.org/schema/tx"
      xmlns:context="http://www.springframework.org/schema/context"
      xsi:schemaLocation="
           http://www.springframework.org/schema/beans
             http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
           http://www.springframework.org/schema/tx http://www.springframework.org/schema/tx/spring-tx-   3.0.xsd
           http://www.springframework.org/schema/aop http://www.springframework.org/schema/aop/spring-aop-3.0.xsd
           http://www.springframework.org/schema/context
            http://www.springframework.org/schema/context/spring-context-3.0.xsd">
      <context:component-scan base-package="com.spring.sample"/>
      <context:annotation-config/>
</beans>

So the above xml should be loaded in order for the spring framework to recognize the annotations and properly do an auto wiring. The loading is done using the ClassPathXmlApplicationContext class which is again a spring framework class. This loading will give exceptions if the xml is not well formed or any bean id mismatch or any class that is not loaded properly. Basically it avoids all runtime problems and list out as server start up issue.

You can notice one thing in the above code piece that i have declared the annotation @Component for the main class as well. This is because Spring can inject only in spring recognized classes. By saying this what i mean is in order to autowire a class inside another class both the classes should be part of the spring framework. So by annotating the main class with @Component we are making that as a spring recognized class. You can clearly see that main class instance itself is created using the ApplicationContext of spring because based on our @Component annotation spring would have mapped this main class with a bean id mapping and with which it creates an instance for us. You can very well the @Autowired annotation and below that we have declared a variable for the interface Sample.

Now by magic we would have got the instance of SampleImpl's instance in the declared variable of the interface Sample. How?. This is what spring does for us. It recognized the annotation @Component for SampleImpl and SampleImpl implements Sample, so spring internally associated this and have an instance created for it and have it in its container and injects that when it sees the @Autowired annotation in the invoker class. Now the invoker doesn't even know which implementation its going to invoke. It will care only about the interface. Now even if the implementation changes the invoker doesn't require any code change and no need to be tested.

This type of spring's usage makes the code more modularised and also very easy to maintain.
The whole project is uploaded as zip file with this blog. I have created a maven project in order to get all the jars instead of we downloading the jar and add it to eclipse. Pre-requisite for this project to run is to have eclipse with maven plugin.

Enjoy working with Spring!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Download Project

Thursday, August 11, 2011

CleanUp Unused Code - Eclipse rocks!!!!

We have serious discussions in our organization on cleaning up unused code.

What the heck is that unused code? 

Went back to my code and was figuring out what does that unused code mean. Then i was able to see yellow marks in my side bar in eclipse saying "The import is not used anywhere", "This local variable is never read locally", "This private method is never getting called".

Now i got what is meant by unused code. So was trying how can i remove this nonsense in few clicks as i don't want to go each file or see all the warnings and do the code cleanup. Eclipse is one such a software that i used to get amazed often. Here we go with the below steps..boommm...all the unused code is gone.


Window - > Preferences -> Java -> Code Style -> Clean Up


















Click New to create our own Custom Profile.















Since we are concentrated on removing unnecessary code we can remove the options in other tabs and just concentrate on the options in “Unnecessary Code” tab.

















By doing above we have created a profile for doing clean up and now right click on any project in eclipse, go to Source -> CleanUp. By default the project points to Eclipse-built in clean up. You can change this to your custom profile and click Next.
Here you go and it cleans hell a lot of code for us.