Tuesday, December 24, 2013

Static Class in Java

Consider a class with utility methods. In this case instantiating an instance every time we need those methods, does not make sense. So what exactly should be done.

Should we go with abstract class? An abstract class may not make sense as we do not expect derived classes to provide any implementation. We can go with a static class (Here I mean a class with static methods).

So, When do we need to write a static class?
When we have a bunch of utility methods and instantiation of the class seems nonsensical.

So what is the best way to write a static class?1
Enforce noninstantiability  by using private constructor (from Effective Java, Item 4)
  1. Attempting to enforce noninstantiability by making a class abstract does not work.
  2. A default constructor is generated only if a class contains no explicit constructors, so a class can be made noninstantiable by including a private constructor:
So we need: A class with private constructor and static methods.

As the constructor is private it is not accessible to outside world so there can not be any derived class. Though not needed, we can also make the class final as there is no harm in being explicit.
// Noninstantiable utility class
public class UtilityClass
{
    // Suppress default constructor for noninstantiability
    private UtilityClass() {
        throw new AssertionError();
    }
}

An Assertion Error is a good idea as it ensures us in case the constructor is invoked accidentally with in the class. As a side effect this class cannot be extended now.

We should keep in mind one thing: Static methods are death to testability. Also they do not participate in Object Oriented world and therefore are considered bad by few people.

In the above article I used the term Static class to mean the class with static methods. Otherwise only nested classes can be static.
class OuterClass{
    public static class StaticNestedClass{
    }

    public class InnerClass{
    }

    public InnerClass getAnInnerClass(){
        return new InnerClass();
    }

    //This method doesn't work
    public static InnerClass getAnInnerClassStatically(){
        return new InnerClass();
    }
}

class OtherClass{
    //Use of a static nested class:
    private OuterClass.StaticNestedClass staticNestedClass = new OuterClass.StaticNestedClass();

    //Doesn't work
    private OuterClass.InnerClass innerClass = new OuterClass.InnerClass();

    //Use of an inner class:
    private OuterClass outerclass= new OuterClass();
    private OuterClass.InnerClass innerClass2 = outerclass.getAnInnerClass();
    private OuterClass.InnerClass innerClass3 = outerclass.new InnerClass();
}
All static methods (in fact all the methods) and static variables are stored in the PermGem section of the heap, since they are part of the reflection data (class related method and not instance related). The variables (or variable definitions) are store in PermGen section but the objects they refer to get stored somewhere on the heap. More can be found here.

More about garbage collection and memory allocation can be read here and here.

Monday, December 16, 2013

Algorithms:Intersection point of two linked lists in Y shape

Algorithms Series

We are given two linked lists that intersect at a point and then become one. The number of nodes in each list before they intersect are unknown and they may be different (m and n say). We need an algorithm to find the intersection point. This can be shown by this image:
Linked Lists

The simplest is to go with brute force where each node of the first is compared with every other node of the other list. The matching node pointers will lead us to the intersecting node. 
Lame Approach

Time complexity: O (mn)             Space Complexity: O (1)




Can we use Hash Table? Yes. 
 The approach is:
  1. Select the list having less number of nodes and store it in hash table.
  2. Traverse the second list and check whether the same node pointer exists in the hash table.
  3. If it does we get intersection point.


Intersection using marker
Time complexity: Time for creating the hash table + time for scanning the second list
O (m) + O (n)

 Space Complexity: O (n) or O (m)

Can we use stacks to solve it? Yes. The approach is as:
  1. Push both the lists on stacks. The top of both will have the last element of the lists.
  2.  Compare the top elements on two stacks.
    1. If they are same pop them and store them.
    2. If they are not, it means the common element has just popped out in previous step.
  3. The value popped out in previous step can then be returned.
Time complexity:  O (m + n)                       Space complexity: O (m + n)

Can we use the first repeating number? Yes.
  1.  Create an array and keep all the next pointers of both the lists in the array.
  2.  In the array find the first repeating element in the array. The first repeating number is the intersection point.

Time complexity:  O (m + n)                       Space complexity: O (m + n)

Do we have any other approach? Yes by combining sorting and searching.
  1.  Create an array and keep all the next pointers of first list in the array.
  2.  Sort it (assume binary sort is used O (logn) ).
  3. Then for each element in second list, search it in this sorted array.
    1. If we find it then it is intersection point.

Time complexity:  Time for sorting + Time for searching = O (Max (mlogm, nlogn))                          
Space complexity: O (Max (m, n))

Do we have any efficient approach? Yes.
The approach is to compute lengths of the two lists in linear time. Then advance the longer list by difference in length of two lists and then start comparing.
  1.  Find lengths (L1 and L2) of both the lists. O(n) + O(m) = O( Max (m, n))
  2.  Take the difference (d) of the lengths. O(1)
  3.  Make d steps in longer list. O(d)
  4. Step in both lists in parallel until links to next node match. O (Min (m, n)).

Time complexity:  O (Max (m, n))            Space Complexity: O (1)

ListNode FindIntersectingNode(ListNode list1, ListNode list2)
{
  int L1=0, L2=0, diff=0;
  ListNode head1 = list1, head2 = list2;
  while(head1 != null) {
   L1++;
   head1 = head1.getNext();
  }
  while(head2 != null) {
   L2++;
   head2 = head2.getNext();
  }
  diff = L1 – L2;
  if( L1 < L2) {
    head1 = list2;
    head2 = list1;
    diff = L2 – L1;
  }
  for(int count = 0; count < diff; count++) head1 = head1.getNext();
  while(head1 != null && head2 !+ null) {
    if(head1 == head2) return head1.getData();
    head1 = head1.getNext();
    head2 = head2.getNext();
  }
  return null;
}

Disclaimer: The images and various examples are taken from internet. I do not claim them as my own ideas. I have tried to mark the proper references but in case anything is missing please let me know.

Saturday, December 14, 2013

Algorithms:Partition of a Number

Algorithms Series

So if you do not know what do I mean by partition of a number, then here it is:

A partition of a positive integer n is, a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition (For example 1+2+3 and 1+3+2 are same). If order matters then the sum becomes a composition.

Partition(4) = 5
 
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Then we have another related term Restricted Partition which is partition having some constraints. For example partition having only odd numbers, partition having only 1 and 2 etc.

In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is the number of distinct ways of representing n as a sum of natural numbers.
\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).

The right side term on expansion becomes:
(1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + x9 + ...) ....




Partitions can also be visualized by Young diagrams or Ferrous diagrams. 

Young Diagram makes use of boxes and Ferrous Diagrams make use of dots to represent the same information  (as shown below).


The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented by:
****
***
***
**
*
*

So the problem is to write an algorithm that will print all the partitions for a number. There is one very good implementation at Princeton university page under the topic of recursion. Here it is reproduced:

public class Partition { 

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }
  
        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}

% java Partition 4      % java Partition 6
4                       6
3 1                     5 1
2 2                     4 2
2 1 1                   4 1 1
1 1 1 1                 3 3
                        3 2 1
                        3 1 1 1
                        2 2 2
                        2 2 1 1
                        2 1 1 1 1
                        1 1 1 1 1 1

Let me know your feedback. Thanks.

Sunday, February 24, 2013

Flash Builder shortcuts and tricks

Recently I found come really interesting and useful shortcuts in Flash Builder. I always hate unnecessary imports in the code. We have a shortcut:

ctrl + shift + o (the letter is o as in orange)

This will remove all unnecessary imports. Also to indent, select the code (as or mxml) and then use shortcut:

ctrl + i to indent a piece of code.

We can also use:

ctrl + d (to delete the current line).
ctrl + space (twice) to get all code templates.

One really good article can be found here:
http://www.adobe.com/devnet/flash-builder/articles/tips-tricks.html

Problem with ObjectUtil copy

We all have used this wonderful method copy() in ObjectUtil class. It does a deep copy of the object using the following lines of code:
public static function copy(value:Object):Object
    {
        var buffer:ByteArray = new ByteArray();
        buffer.writeObject(value);
        buffer.position = 0;
        var result:Object = buffer.readObject();
        return result;
    }

As the code implies it does not copy each and every property recursively but the object is serialized into a array of bytes which is then de-serialized to get a new object. It makes use of built in Flash player AMF capabilities and it is exactly the same serialization mechanism that is used for remoting. When we send an object using remoting we send an AMF array of bytes which is de-serialized at the other end. As AMF is used to copy few things happen:

1. If we try to cast the result of copy to a class it may fail. For example when I tried to use 'as' operator to cast the result it failed.
2. Also when we use transient metadata tag output gets affected.

When the object gets de-serialized it does not create an instance of the class automatically. The object may have all the properties but still not a true instance (rather an object of class Object or ObjectProxy) unless the AMF packet includes type information about the object. This information gets added to the packet in two ways:

1. If the remoting tag is used: [RemoteClass]
2. If the class is registered using registerClassAlias() method

If we use remoting tag then it is easy. For example:

//assume employee has [RemoteClass] metadata.
var employee:Employee = Employee (ObjectUtil.copy(emp));

We may not always have this tag. In one of my project I was having a class ProfileMetaData which was making use of various properties of other value objects and was not sent back to business layer. So there was no question of remoting. And as expected after copy() I was not able to cast the result. So we need to register the class against a string alias. For example:

registerClassAlias("com.app.vo.ProfileMetaData",ProfileMetaData);
//Now we can copy and caste
var profileCopy:ProfileMetaData = ProfileMetaData (ObjectUtil.copy (report) );

What about the transient? If a property is transient it gets removed from the AMF packet during serialization. The reason they are not sent over the network via Flash Remoting is because  they are not included in the AMF packet. So there is no question of reading them back. In some cases it is useful.

More:
http://archive.darronschall.com/weblog/2007/08/on-transient-objectutilcopy-and-casting.html
http://stackoverflow.com/questions/14576627/how-to-work-registerclassalias-method-for-custom-mxml-components

Saturday, January 19, 2013

Flex is Dead ?

Few days back I was delivering one presentation on Flex to few of the new comers, then suddenly one of the guys asked me one question:
'What is the advantage of learning a technology that is already dead?'

I was shocked by that question. I don't know why people think Flex is dead. May be announcement of Adobe to donate Flex to Apache, may be over hype of HTML5 replacing Flex (well I am doubtful about it in near future at least), may be other reasons. But whatever be the reasons, I thought about writing one small post about it. I did some googling for dead technologies and found the following:
“.NET is dead” is the big winner with 576000 search results on Google. Congratulations J

“JAVA is dead” is following with 138.000 results. I can hardly feel this!!
“PHP is dead” is a little child with only 35.600 results.
“Ruby is dead” is in the same range with 30.700 results.
“AJAX is dead” generates 6500 results.



So what do we say? Adobe donated Flex to Apache and HTML5 may seem promising, but that does not mean Flex is dead. My opinion is that the decision to donate Flex was really a good one. As it is open source now and Apache has lots of good developers working on Flex SDK, it may result in brighter future for it. The bugs may be fixed quickly now. Well the future will unfold the real picture. I believe that the following links will provide proper direction:
http://www.riagora.com/2011/11/flex-is-open/
http://blogs.adobe.com/flex/2011/11/your-questions-about-flex.html
http://www.mikechambers.com/blog/2011/11/11/clarifications-on-flash-player-for-mobile-browsers-the-flash-platform-and-the-future-of-flash/
http://www.universalmind.com/mindshare/entry/html5-for-the-enterprise
http://masuland.wordpress.com/2011/11/28/where-could-flash-coding-be-in-the-year-2050/

Let me know your thoughts on it.