hashcode() Best Practice

A good hash function tends to produce unequal hash codes for unequal objects. Ideally, a hash function should distribute any reasonable collection of unequal instances uniformly across all possible hash values. Achieving this would be ideal, but can be complex. Luckily the following rules made this easy:
1. Store some constant non zero value, say, 17, in an int variable called result.
2. For each significant field f in your object (each field taken into account by the
equals method), do the following:
             a. Compute an int hash code c for the field:
                          i. If the field is a boolean, compute (f ? 1 : 0).
                          ii. If the field is a byte, char, short, or int, compute (int) f.
                          iii. If the field is a long, compute (int) (f ^ (f >>> 32)).
                          iv. If the field is a float, compute Float.floatToIntBits(f).
                          v. If the field is a double, compute Double.doubleToLongBits(f), and then hash the resulting long as in step 2.a.iii.
                          vi. If the field is an object reference and this class’s equals method, compares the field by recursively invoking equals, recursively invoke hashCode on the field. If a more complex comparison is required, compute a “canonical representation” for this field and invoke hashCode on the canonical representation. If the value of the field is null, return 0 (or some other constant, but 0 is traditional).
                          vii. If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is significant, you can use one of the Arrays.hashCode methods added in release 1.5.
             b. Combine the hash code c computed in step 2.a into result as follows:
                          result = 31 * result + c;
3. Return result.
4. Write unit tests to verify if equal instances have unequal hash codes, figure out why and fix the problem.

Read More

ReflectionUtils.doWithFields()

Spring has a nice Utility class ReflectionUtils that does just that: it defines a method to loop over all fields of all super classes with a callback: ReflectionUtils.doWithFields()

Documentation:

Invoke the given callback on all fields in the target class, going up the class hierarchy to get all declared fields.

Parameters:
- clazz - the target class to analyze

- fc - the callback to invoke for each field

- ff - the filter that determines the fields to apply the callback to

Sample Code:

Output:

Found field private int java.util.ArrayList.size in type class java.util.ArrayList

Read More

Custom Maven Plugin

When you write a custom plugin, you are going to be writing a series of Mojos (goals). Every Mojo is a single Java class which contains a series of annotations that tell Maven how to generate the Plugin descriptor. Before you can start writing Mojo classes, you will need to create Maven project with the appropriate packaging and POM.

To create a plugin project, you should use the Maven Archetype plugin. The following command-line will create a plugin with a groupId of org.tat.api and the artifactId of webapp-optimizer:

pom.xml

The most important element in a plugin project’s POM is the packaging element which has a value of maven-plugin. The other important piece of a plugin project’s POM is the dependency on the Maven Plugin API. This project depends on version 2.0 of the maven-plugin-api and it also adds in JUnit as a test-scoped dependency.

The Mojo implementation shown in the following example implements the Mojo interface by extending the org.apache.maven.plugin.AbstractMojo class. Before we dive into the code for this Mojo, let’s take some time to explore the methods on the Mojo interface. Mojo provides the following methods:

void setLog( org.apache.maven.monitor.logging.Log log )

When Maven loads and executes a Mojo, it is going to call the setLog() method and supply the Mojo instance with a suitable logging destination to be used in your custom plugin.

protected Log getLog()

Maven is going to call setLog() before your Mojo is executed, and your Mojo can retrieve the logging object by calling getLog().

void execute() throws org.apache.maven.plugin.MojoExecutionException

This method is called by Maven when it is time to execute your goal.

You can run the plug-in using the following command. The commands is as per the groupId:artifactId:version:goal format.

 When you run this command-line you should see output that contains the output of the echo goal with the default message: "Hello Maven World…". If you want to customize the message, you can pass the value of the message parameter with the following command-line:

Read More

Evaluate PreFix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a prefix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Reverse the expression.
2. Tokenize the expression depending on the delemeter.
3. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 1 and second one being operand 2.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
4. Pop the stack for the result.

Time Complexity : O(N^2)

Difference against the Post Fix Evaluation :

1. We have to reverse in the first instance.
2. In prefix evaluation we have to treat the first pop as operand 1 and second pop as operand 2 unlike post fix evaluation

Algorithm Execution:

Input Expression : + 1 * 2 3

Step 1 : + 1 * 2 3 => 3 2 * 1 +

Step 2 : Stack[3]

Step 3 : Stack[3, 2]

Step 4 : Stack[6]

Step 5 : Stack[6,1]

Step 5 : Stack[7] - Result

Time Complexity : O(N)

You can fork the source code and unit tests from github.

Read More

Evaluate Post Fix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a post fix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Tokenize the expression depending on the delemeter.
2. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 2 and second one being operand 1.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
3. Pop the stack for the result.

Time Complexity : O(N)

Algorithm Execution:

Input Expression : 1 2 3 * +

Step 1 : Stack[1]

Step 3 : Stack[1, 2]

Step 4 : Stack[1,2,3]

Step 5 : Stack[1,6]

Step 5 : Stack[7] - Result

You can fork the source code and unit tests from github.

Read More

Evaluate a mathematics expression in java

Read More

Infix to Prefix

In my previous post we evaluated the algorithm to convert a prefix expression to post fix expression. Infix to Post fix algorithm is going to be handy for writing the algorithm of Infix to Prefix. We just need few additional steps to do so. But before jumping on to the solution for computer program, let's first solve it in a mathematical way. 

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation

1. Parenthesis - ( ) { } [ ]
2. Exponent (Right to left)
3. Multiplication and Division (Left to Right)
4. Addition and Subtraction (Left to Right)

Given Infix Expression : A + B * C

Steps:

1. First manually put the parenthesis depending on the operator precedence.
2. Then start evaluating from the inner most expression.
3. Remove the parenthesis.

A + B * C -> A + ( B * C ) -> A + ( * B  C ) -> + A ( * B C )  + -> + A * B C

Final Result : + A * B C

Now let directly jump on to the computer algorithm. I will not be writing the infix to post fix algorithm here. Please refer my previous post for the same.

Algorithm:

1. Reverse the input expression
2. Change all open parenthesis to close and visa versa. 
3. Run the infix to post fix algorithm
4. Reverse the output

Time Complexity : 

Time Complexity of infix to post fix + O(n) + O(n) + O(n)

=>(O(n+m)) + O(m)) + O(n) + O(n) + O(n) where n =  no of tokens, m = stack size

You can also fork the code from github.

Read More

Infix to Post Fix

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation

1.  Parenthesis - ( ) { } [ ]
2.  Exponent (Right to left)
3. Multiplication and Division (Left to Right)
4. Addition and Subtraction (Left to Right)

Given Infix Expression : A + B * C

Steps:

1. First manually put the parenthesis depending on the operator precedence.
2. Then start evaluating from the inner most expression.
3. Remove the parenthesis.

A + B * C -> A + ( B * C ) -> A + ( B  C * ) -> A ( B C * )  + -> A B C * +

Final Result : A B C * +

Now let's solve the problem using computer language and we are going to take the help of the stack to solve this problem. Why we opted for a stack ADT? Good question and I believe, the next explanation will clarify your answer. So let's not jump on that question now. 

Given Infix Expression : A + B * C

We are going to use the following use the following components for the algorithm.

1. Stack
2. String

Algorithm :

1. Tokenize the expression depending on the delemeter.
2. Perform the steps for each of the token
1. If token is an operand append to the result string
2. If token is an operator peek the stack, check if operator and check for the operator precedence
1. pop the stack till stack has operator precedence greater than equal to token precedence and append that to string.
2. else push the operator to the stack
3. If you find an open parenthesis, push that to the stack.
4. If you find an closed parenthesis, pop and append to the string till you get a open parenthesis. Then pop the open parenthesis too.
3. Pop the entire stack and append that to result string.

Time Complexity : O(n+m)) + O(m) where n =  no of tokens, m = stack size

Execution of algorithm:

Step 1 : String : A :: Stack : []

Step 2 : String : A :: Stack : [+]

Step 3 : String : AB :: Stack : [+]

Step 4 : String : AB :: Stack : [+, *]

Step 5 : String : ABC :: Stack : [+,*]

Step 6 : String : ABC*+ :: Stack : []

I took a very easy expression to keep the post simple and more understandable. You can apply the same algorithm to process your complex expressions. Now it's time to convert this algorithm steps to a program. I am using java to do so.

The complete program with github can be forked here

Read More