<body><script type="text/javascript"> function setAttributeOnload(object, attribute, val) { if(window.addEventListener) { window.addEventListener('load', function(){ object[attribute] = val; }, false); } else { window.attachEvent('onload', function(){ object[attribute] = val; }); } } </script> <div id="navbar-iframe-container"></div> <script type="text/javascript" src="https://apis.google.com/js/plusone.js"></script> <script type="text/javascript"> gapi.load("gapi.iframes:gapi.iframes.style.bubble", function() { if (gapi.iframes && gapi.iframes.getContext) { gapi.iframes.getContext().openChild({ url: 'https://www.blogger.com/navbar.g?targetBlogID\758334277\46blogName\75Sriram\47s+Blog\46publishMode\75PUBLISH_MODE_BLOGSPOT\46navbarType\75BLUE\46layoutType\75CLASSIC\46searchRoot\75http://metallicatony.blogspot.com/search\46blogLocale\75en\46v\0752\46homepageUrl\75http://metallicatony.blogspot.com/\46vt\75-8718433808682107797', where: document.getElementById("navbar-iframe-container"), id: "navbar-iframe" }); } }); </script>

Thursday, June 26, 2014

A playful approach to tackle programming questions ("Phone words using dialpad" problem)

Programming questions are always tricky. It often makes you dazed and confused. Any software engineer interview for a programming position involves a couple of programming questions. After listening to a question from the interviewer, when you try to answer back and that's when you go erratic. That's pretty normal for everyone and there is no need to be worried and concerned. The objective of this post is to show a way to tackle such programming questions. It will illustrate a planned approach that you might want to tread on for easily arriving at solutions. I have taken a famous problem called "Phone words" to explain this approach.

“Phone words” is a programming question that features in many interviews to test the analytic skills of a programmer. The problem statement goes like this: You are given a 7 or 10 digit phone number. In every telephone or a cell phone, we have numbers ranging from 0 to 9 in the dial pad. Every digit in the dial pad has either 0 or 3 or 4 letters mapped for every digit. For the given phone number you need to find out all combinations of words that is possible using the letters of every digit of the phone number.

I couldn’t find a clean solution for this question anywhere and so wanted to post my solution along with the approach taken. Be it any programming question, if you work to find a solution without doing any ground work, it is not going to help at all. A step by step systematic approach is what will help you find a solution. It’s a skill to learn and acquire but an art to conquer!!

Programming problems can be addressed in the same way you prepare yourself to play a new computer game. Say, suppose you heard about a new game from a game-maniac friend of yours. He is in all praises for this game. And now, after listening to all those good stories from him, you are very desperate to play this game. You are restless. You wait with no patience for the day to arrive so that you can play this wonderful game. Imagine how you prepare yourself to play a computer game, a game that you have never played in the past. Imagine how excited you will be, sitting right before the screen waiting for the game to load. Once your game starts, your curious playful mind will begin to find out answers for the following questions

1. What exactly is the objective or mission of this game?
2. What are the aids and powers that I’m provided with as a player? Do I carry health tabs, armory, high-tech weapons?
3. Is there any specific learning or understanding that I need to do about my given aids and powers?
4. Can I play this game for the first few times just to familiarize myself without being mindful about my mission, without worrying about whether I’m winning or losing?
5. After I get a sense that I’m comfortable playing this new game, I have to think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully. What is the appropriate time to use my powers so that they can be put to best use?
6. And finally, I will try to frame a strategy to tackle all my enemies so that I can effectively accomplish the mission of the game

That’s how you plan before playing a game, isn’t it? This exactly is the thought process that is needed to solve a programming problem. Once we are able to figure out answers for the above questions, it is going to be much easier to solve the actual problem. Let us follow the above steps and figure out how helpful they are in solving our “Phone words” problem.

What is the mission of this game?
The objective of the problem is to find out all possible words that could be created out of the given numbers. This is a classic example of a permutation and combination problem.

What are the aids and powers that I’m provided with as a player?
I’m given a set of numbers that represents a phone number and a phone dial pad that has numbers running through 0 to 9. Every number is mapped to a set of characters. Any one of those characters from every digit will be considered every time I try to create a possible word

Is there any specific learning that I need to perform about the aids and powers that I’m given with?
As a player, I’m provided with a phone dial pad and a set of numbers for which I need to create possible words. When I look at the dial pad, I see that not all numbers have the same 3 characters associated with them. It appears that there can be zero or more letters for a number. Digits like 0 and 1 don’t have any letters while digits 7 and 9 are mapped to 4 characters each. Wow, that’s a good point to understand before trying to solve the problem!

Can I play this game for the first few times just to familiarize myself without being mindful about my mission and without worrying about whether I’m winning or losing?
I want to play this game for a couple of times so that I can familiarize myself. I will be happy to choose the least difficult level so that it buys me more time on stage. Likewise, when a programming problem is given, it’s important to run through the problem with a couple of easy experiments. In this case, say for example, running through the problem using an imaginary phone number “23” will make me understand that the possible words are “AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”. Running through this exercise and illustrating the samples increases the confidence.

Can I think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully?
When i'm playing a game, as soon as I spot some deadly traps, I want to think and plan a bit about them. I want to understand so that i can better tackle those traps. Likewise, there are a couple of traps in this problem. The numbers 0 or 1 do not have any characters associated with them. And there are numbers 7 and 9 that are mapped to 4 characters each, which is 1 character more than the typical 3 characters per number. This in turn means that a pure iterative solution might fail if it goes by the assumption that it is always 3 mapped characters per digit across board. I have to be careful about it. In case of 0 or 1, it will be the digits 0 and 1 used for creating a word and when it is 7 or 9, I must be careful to use all the 4 characters to create words. To re-familiarize myself, I need to run through those traps a couple of times to improve my understanding. Say, I’m now given with an imaginary number “702”. Then the possible word combinations will be “P0A”, “P0B”, “P0C”, “Q0A”, “Q0B”, “Q0C”, “R0A”, “R0B”, “R0C”, “S0A”, “S0B”, “S0C”.

Can i frame a strategy to tackle all the enemies so that i can accomplish the mission of the game?
Now comes the big part. I know quite a bit about the game now. I know about the powers that I’m given with, I know where to hunt for gold and I’m aware of the exact place and point at which those devils will show up. Now, it’s time for me to craft a plan, a plan that will defend me and defy all my enemies. Thinking at a very high level, there are two ways I can solve this problem.

Iterative Solution:
Let’s say I’m given with an imaginary phone number 234 ({abc}, {def}, {ghi}). Then as a first step, i have to think about the number of possible words that can be created out of that phone number. It will be 3x3x3 = 27 words.

Let me run through this solution in my mind. As the first digit of the given phone number is 2, I can have the letters - a, b and c stashed separately. Once I see the second digit 3, I can append every mapped character of 3 to the previously stashed words. Now the stashed words become ad, bd, cd and ae, be, ce and af, bf, cf. The next digit is 4 and so the stashed words will now become – adg, bdg, cdg, aeg, beg, ceg, afg, bfg, cfg, adh, bdh, cdh, aeh, beh, ceh, afh, bfh, cfh, adi, bdi, cdi, aei, bei, cei, afi, bfi, cfi. Running through this gives me a clue that this is an iterative solution. Additionally I need two lists, one with the stashed words and the other list for retaining the new words that are created by appending the stashed words with the letter that I’m iterating with. After appending all letters mapped for a digit with the stashed words, the new list becomes the stashed list after which the new list is emptied to ready for the next iteration. Simple, isn’t it?

/**
 * Returns the list of words created using phone dial pad and the given phone number
 * @param digits the phone number
 * @return list of combination of words
 */
public static ArrayList<String> getWordFromDialPad(String digits) {
  ArrayList<String> res = new ArrayList<String>();
  ArrayList<String> preres = new ArrayList<String>();
  res.add("");

  for (int i = 0; i < digits.length(); i++) {
   for (String str : res) {
    String letters = map.get(digits.charAt(i));
    for (int j = 0; j < letters.length(); j++)
     preres.add(str + letters.charAt(j));
   }
   res = preres;
   preres = new ArrayList<String>();
  }
  return res;
 }

This iterative solution looks simple but the only drawback is it needs more space to stash the list of words for every iteration. This implementation can be accessed from my github repository – Phone words iterative solution.

Recursive Solution:
This is another solution for the same problem. In fact, this solution is a blend of recursive and iterative. The best part of this solution is that it just needs a single array equal to the size of the phone number!! Awesome isn’t it? No more extra space is needed!! Recursive solutions are interesting to understand and efficient most of the times. Instead of thinking iteratively, recursion will make you think differently. It wants you to go deep down and loop through all possible combinations in the lowest possible levels and then slowly climb upper levels to repeat the same. And that’s exactly this recursive method does
/**
 * Recursive helper method to create a word from dial pad
 * @param word character array
 * @param numbers given input numbers as string
 * @param start the index of input digit that is being processed
 */
private static void getWordFromDialPad(char[] word, String numbers, int start) {
  // base case -> start is the index value of the position from the word
  if (start > (numbers.length() - 1)) {
    System.out.println(++counter + " ==> " + new String(word));
    // look up dictionary to find whether the word is meaningful or not
    return;
  }

  // Identify the number of iterations based on the digit
  Integer number = numbers.charAt(start) - '0';
  int iterations = getSizeOfFirstDimension(number);


  // Iteration in a recursive method is equal to number of possible chars a digit can take
  // for eg. digit 2 can take 3 possible chars - A, B and C where as digit 7 can take 4 different chars
  for (int j = 0; j < iterations; j++) {
    // store a possible character for the digit and move on to the next position by 
    // calling the recursive method again
    word[start] = getCharacterFromDialPad(number, j);
    getWordFromDialPad(word, numbers, start + 1);
  }
}

That’s the core part of this recursive solution. The rest of the implementation has helper methods to support the above recursion. The complete implementation can be accessed from my github repository – Phone words recursive solution.

A preface of any book will brief and summarize about what the book is about. Likewise it is very important to understand the preface of a programming problem by asking the above questions. It is very similar to the set of questions that you ask yourselves when you get ready to play a new game. Running through a couple of simple experiments will give deeper understanding and confidence. It will stand as a stepping stone to formulate the final solution!!

Labels: , ,

Wednesday, April 30, 2014

Generic Stack and Queue using Linked List and resizing Array

Stacks and Queues are one of the most basic and important data structures widely used in computer science. Understanding the operational semantics of these data structures will reward anyone. Going a step ahead and understanding the inner workings of these structures will lighten with much more knowledge. Once the mechanics of these data structures are well understood, trying to build a custom one using other foundational data structures will be a challenge. Leaping one more step ahead to build a generic version of stack and queue using the same foundational structures will not be a very easy task to do, but if you do, it sure will adorn your cerebral cortex.

This post focusses on building a generic stack and queue using two foundational structures - linked list and array. So there are going to be 4 different types of implementation.
1) Build a stack using Linked List
2) Build a stack using resizing array
3) Build a queue using Linked list
4) Build a queue using resizing array

Generic Datastructure
Stack is a LIFO data structure and Queue is a FIFO data structure. To understand more about these, I would recommend to google. A generic data structure is more like a container for any type of java object. The data structure should not depend on the type of object that one needs to use with it. The object can be anything. It is not a healthy practice to build a data structure for every type of object that you want to use with it.

The semantics of a linked list is different from an array because linked list allows accessing any element traversing from the first element while an array allows random access based on the index of the element. Underlying rules like these, pose a challenge for a developer to construct a stack or queue using the foundational structures.

The below illustrated "isEmpty" and "iterator" methods are common for both Stacks and queues. As the name illustrates, isEmpty tells whether the structure is empty and the iterator method returns an iterator to run through the elements. The beauty is that a user does not need to understand the underlying data structure if he has to iterate through the elements.

Following is the code snippet for all the above mentioned data structures. Most part of the code is not that difficult to understand though I have some inline comments wherever I felt some explanation is necessary.

Stack using Linked List
A single linked list always has a series of elements chained together. Every element has data and a reference to the next element. The first element is called head and the last element in the chain is called tail. That in turn does not mean all the data structures that are built using linked list need to have 2 references internally maintained for head and tail. It is totally up to the data structure that is built out of linked list. Take for example, the stack needs to internally preserve just one reference which is "head", so that it can perform its day to day work. This is because both operations “push” and “pop” that are exposed from a stack happens from the top aka head element. Push adds a new element at the head and pop returns and removes the element at the head of the linked list.

/**
  * Returns true or false based on whether the stack is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Push data to stack
  * @param data
  * @return true if push was successful else false
  */
 public boolean push(T data) {
  if (null != data) {
   Element prevHead = head;
   head = new Element();
   head.data = data;
   head.next = prevHead;
   return true;
  } else {
   return false;
  }
 }
 
 /**
  * Pops data from stack
  * @return data if pop was successful else null
  */
 public T pop() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private Element current = head;

   @Override
   public boolean hasNext() {
    return current != null;
   }

   @Override
   public T next() {
    final T data = current.data;
    current = current.next;
    return data;
   }

   @Override
   public void remove() {
   }
  };
}

Here is the github link to the code for Stack built using Linked List - Github - Stack using Linked List

Stack using resizing Array
Stack using array might look simple at the first sight. However, it is definitely not if you are implementing a self-resizing array. A self-resizing array is the one that can modify its size based on the usage. This ensures an optimum usage of memory based on the number of elements in the stack.

Push operation always happens at the end of the array. It is not a good idea to add the new element at the first index because a stack is a FIFO data structure. The new element needs to be added to the end of array and the actual number of elements in the stack is maintained internally in a variable. The stack needs to be resized to twice its capacity if it was found to be already full. This in turn means that for N elements added to the stack, the array needs to be resized logarithmic times.

 /**
  * Returns true if the stack is empty
  * @return
  */
 public boolean isEmpty() {
  return (n == 0);
 }

/**
  * Pushes object to stack. Resizes if needed.
  * Note that resize operation happens before push.
  * @param data
  * @return
  */
 public boolean push(T data) {
  if (null != data) {
   if (n == list.length) {
    resize(list.length * 2);
   }
   list[n++] = data;
   return true;
  } else {
   return false;
  }
 }

 /**
  * Resizes the existing stack by creating a new stack
  * and copying all the elements from existing stack.
  * 
  * In case of a growing stack, the source of data is small
  * In case of a shrinking stack, the new target is small
  * And so the copying operation has been restricted to number of elements
  * 
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  for (int i = 0; i < n; i++) {
   newlist[i] = list[i];
  }
  list = newlist;
 }

Pop operation always happens from the last element as that is the most recently added element to the stack. After a pop is complete, the stack is resized to a half of its capacity if the utilization is found to be quarter or less than the current capacity.

 /**
  * Pops out from stack. Resizes if needed.
  * Note that resize operation happens after pop.
  * @return
  */
 public T pop() {
  if (!isEmpty()) {
   T data = list[--n];
   list[n] = null;
   if (n <= list.length/4 && n > 0) {
    // resize the stack if the utilization is lesser than or equal to quarter of the capacity
    // not needed to resize if number of elements in stack was 1 and that element was popped (the new n will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack
 @Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   // as array data structure stores in the order of push but stack is a LIFO data structure
   // the iterator runs reverse
   private int i = (n-1);
   
   @Override
   public boolean hasNext() {
    return (i >= 0);
   }
   
   @Override
   public T next() {
    return list[i--];
   }

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Stack built using Array - Github - Stack using Resizing Array

Queue using Linked List
Queues using linked list needs two references – "head" pointing to the first element of the queue and "tail" pointing to the last element of the queue. Enqueue adds an element to the end of the queue and dequeue returns and removes an element from the start of the queue.

The enqueue operation has a special case when the first element is added to an empty queue. When the queue has just one element, both head and tail need to point to the same element which will be the first element in the queue.

/**
  * Returns true or false based on whether the queue is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Enqueues or adds the element to the end of queue
  * If the queue is empty before enqueue, the head and tail of the queue will point to the new element enqueued
  * @param data
  * @return true if enqueue was successful else false
  */
 public boolean enqueue(T data) {
  if (data != null) {
   Element prevTail = tail;
   tail = new Element();
   tail.data = data;
   tail.next = null;
   if (isEmpty()) {
    head = tail;
   } else {
    prevTail.next = tail;
   }
   return true;
  } else {
   return false;
  }
 }
Dequeue has a special case as well. When the queue becomes empty after the last element is dequeued, the head and tail references should point to null.
/**
  * Dequeues element from the start of the queue and returns the element's data. Returns null if there are no elements in queue.
  * If the queue is empty after a successful dequeue, head and tail will be reset to null
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   if (isEmpty()) {
    tail = head;
   }
   return data;
  }
  return null;
 }

The iterator is simple for a queue built using linked list. It has to run from the first element to the end.
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private Element current = head;

   @Override
   public boolean hasNext() {
    return current != null;
   }

   @Override
   public T next() {
    final T data = current.data;
    current = current.next;
    return data;
   }

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Queue built using Linked List - Github - Queue using Linked List

Queue using resizing Array
Queue using array is possible using two indexes – headIndex and a tailIndex. headIndex points to the first valid element in the queue. Remember a dequeue operation removes the element from the head. So a dequeue operation can leave "holes" in the queue. tailIndex points to the last valid element in the queue. This in turn means that the length of the queue will be the tailIndex value. Not to forget that the underlying array has to be resized for an optimal usage of memory.
A push operation happens at the tailIndex. If the queue is full, the capacity is resized to twice

 /**
  * Returns true if queue is empty
  * @return
  */
 public boolean isEmpty() {
  return (0 == tailIndex);
 }

/**
  * Enqueues to queue, resizes if needed
  * @param data
  * @return
  */
 public boolean enqueue(T data) {
  if (data != null) {
   if (!isEmpty()) {
    // queue is full
    if ((tailIndex - headIndex) == list.length) {
     resize(2*list.length);
    }
   }
   // if the queue is empty or if the queue is not full
   list[tailIndex++] = data;
   return true;
  } else {
   return false;
  }
 }


 /**
  * Resizes the queue to the provided capacity
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  int i = headIndex;
  int j = 0;
  for (; i < tailIndex; i++, j++) {
   newlist[j] = list[i];
  }
  headIndex = 0;
  tailIndex = j;
  list = newlist;
 }


A pop operation pops an element from the head of the queue. After the operation, if the utilization of the queue is found to be quarter the capacity or lesser, then the current capacity is resized to half. The queue need not be resized if the length of the queue is already 1. It is ok to have a space readily available for the first element of the queue.
/**
  * Dequeues from queue, resizes if needed
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = list[headIndex];
   list[headIndex++] = null;
   if ( ((tailIndex - headIndex) <= list.length/4) && list.length > 1) {
    // resize the queue to half it's capacity, if the utilization is lesser than or equal to quarter of the capacity
    // do not resize if number of elements in queue was 1 and that element was dequeued (the new number of elements will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }



The iterator for a queue built using array is not difficult as the iteration has to run from the element at headIndex to tailIndex.
@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private int i = headIndex;
   
   @Override
   public boolean hasNext() {
    return (i < (tailIndex - headIndex));
   }

   @Override
   public T next() {
    return list[i++];
   }

   @Override
   public void remove() {
   }
  };
 }

Here is the github link to the code for Queue built using array - Github - Queue using Resizing Array

Feel free to download or browse through the entire source for this project from github repository - Github - Basic Datastructures

Labels: , ,

Friday, December 20, 2013

Binary Tree Traversals

Binary tree is a special case of a tree in which there are no more than 2 children for any node. The children are called left and right nodes respectively based on the fact whether they are located on the left or right side of the parent node. Binary trees are extensively used in software engineering because it just takes O(log n) for doing most of the day to day operations – insert, update, delete and search. Traversal algorithms are very important concepts in binary trees because if you want to do any type of operation on a binary tree then as a first step, the tree needs to be traversed to find the nodes on which the desired operation need to be performed. The three widely used binary tree traversal algorithms are

1) Preorder traversal
Processing order of the nodes are – parent, all its left descendants and then the right descendants. In other words, Parent is processed before left sub-tree and right sub-tree are processed.

2) Inorder traversal
Processing order of the nodes are – all left descendants, parent and then the right descendants. In other words, left sub-tree is processed before parent and right sub-tree are processed.

3) Postorder traversal
Processing order of the nodes are – all left descendants, right descendants and then finally the parent descendants. In other words, all the children are processed before the parent is processed.

For the impatient code readers, the entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms.

Recursive Solution
A recursive solution best suits the situation where there is a bigger problem that can be broken down into smaller and similar sub problems and so the same solution can be applied over the sub-problems. It is imperative to have a base case after which the solution should start winding up. Recursion can be best understood when the whole process can be visualized with a stack.

Iterative Solution
An iterative solution best suits the situation where there is a bigger problem that can be broken down into smaller problems and every such smaller problem is iteratively solved one after another. There is no connection between an iteration and its successive iterations. As in the case of recursion, an iteration does not pause or wait until all the sub-iterations are complete. And that’s why we need an additional tool(aka data structure) so that we can adapt an iterative solution for tree-traversals. A stack is needed in an iterative solution so that it can be used to temporarily store the nodes in the needed order and then apply the solution or process the node that comes out of the stack.

Preorder traversal
Recursive solution is simple and self-explanatory.

public void preOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  System.out.println(node);
  if (node.getLeft() != null) {
   preOrderTraversalIterative(node.getLeft());
  }
  if (node.getRight() != null) {
   preOrderTraversalIterative(node.getRight());
  }
 }

Iterative solution for any traversal needs at least a stack. Preorder traversal is the simplest among all the traversal iterative algorithms. To start with, the root node is added to stack. From there on, we navigate deep into the left-most sub-tree. And while doing so, we keep processing the node that we are navigating through and we keep adding the right child of the node (if exists) to the stack. The left child is added too but it is popped out in the next iteration, and that’s how we navigate down the tree. While we pop out the nodes from the stack, we go over the same process – navigate, process and add the right child to stack if it exists.

public void preOrderTraversalIterative(Node node) {
Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  
  while (!stack.isEmpty()) {
   Node poppedNode = stack.pop();
   System.out.println(poppedNode);
   if (poppedNode.getRight() != null) {
    stack.add(poppedNode.getRight());
   }
   
   if (poppedNode.getLeft() != null) {
    stack.add(poppedNode.getLeft());
   }
  }
}


Inorder traversal
The recursive solution is pretty simple. Given a node, keep navigating to the left-most node until a leaf node is reached. Once reached, process the leaf node, its parent and then the right sub-tree (again go through the same above process).

public void inOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   inOrderTraversalRecursive(node.getLeft());
  }
  System.out.println(node);
  if (node.getRight() != null) {
   inOrderTraversalRecursive(node.getRight());
  }
 }

As expected the iterative solution uses a single stack. The in-order traversal algorithm processes the left sub-tree first from deep down node => which in turn means, navigate to the left-most leaf node. So, as a first step, navigate deep down into the left sub-tree. We keep pushing all the left-nodes to the stack when we navigate, so that when we pop out of the stack for the first time, it’s going to be the left-most leaf node. For every popped node, we check whether there is a right node, if there is, then we add that node and then followed by all left-nodes (if there are) for the right node (that we are working on) to the stack. Once that is done, we pop out a node from the stack and then repeat the same above process until the stack goes empty.

public void inOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }

  Stack<Node> stack = new Stack<Node>();
  // Navigate to the left most node of the left sub-tree. During that process, push all the navigating nodes to the stack.
  while (node != null) {
   stack.push(node);
   node = node.getLeft();
  }
  
  while (!stack.isEmpty()) {
   Node currNode = stack.pop();
   System.out.println(currNode);
   
   /* If the current node has a right child, push it to stack and navigate to the left node of that right child if it exists. 
   Remember we need to process the right sub-tree of any parent node. So, add all left nodes of the right child to stack and 
   keep navigating to left till the leaf node */ 
   if (currNode.getRight() != null) {
    Node rightnode = currNode.getRight();
    stack.push(rightnode);
    if (rightnode.getLeft() != null) {
     Node rightsLeftnode = rightnode.getLeft();
     while (rightsLeftnode != null) {
      stack.push(rightsLeftnode);
      rightsLeftnode = rightsLeftnode.getLeft();
     }
    }
   }
  }
 }


Postorder traversal
As always the recursive solution is simple. Given a node, the left descendants are processed first followed by the right descendants and then the node in consideration is processed. It looks pretty simple to do using a recursive approach.

public void postOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   postOrderTraversalRecursive(node.getLeft());
  }
  
  if (node.getRight() != null) {
   postOrderTraversalRecursive(node.getRight());
  }
  System.out.println(node);
 }

The iterative solution for postorder traversal is the most difficult of all. The below iterative solution uses a single stack. This algorithm may not look same as other solutions provided in internet. This solution worked well for the usecases that I tested and hopefully it works for everyone. The tough part of this solution is: Determining whether we are currently navigating down the tree or up the tree. If we don’t determine that, we might end up looping back and forth in an endless loop. How to identify whether we are going up or down? If we remember the previous node that was processed or added to the stack then based on that, we can tell the relationship of the current node to the previous node. It can be a child node or the parent node!! This determination would help us making a decision whether to move up or down.

On a broad view, there are 2 cases that need to be covered in this algorithm
1) If the current node is the parent of the previously processed node (the previously processed node could either be a left or right child) then it means we are going up the tree. That in turn means we have already processed the child sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
2) The other situations could be:
a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree.
b) The current node is the root node.
c) The current node can be the right companion of the previously processed node.

For all the above usecases (a), (b) and (c), we call the special private method “navigateAndProcessNodesInPostOrder” method. navigateAndProcessNodesInPostOrder method takes care of pushing the current node, left child and right child (in that order) to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold the previous processed node, the current node and the stack.

/**
  * An iterative solution for postorder traversal of a binary tree.
  * 
  * On a broad view, there are 2 cases that need to be covered in this algorithm
  * 1) If the current node is the parent of the previously processed node (the previously processed node could either be a 
  *   left or right child) then it means we are going up the tree. That in turn means we have already processed the child 
  *  sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
  * 2) The other situations could be: 
  *  a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree. 
  *  b) The current node is the root node. 
  *  c) The current node can be the right companion of the previously processed node. 
  *  For all the above usecases, we call the special private method “navigateAndProcessNodesInPostOrder” method. 
  *  navigateAndProcessNodesInPostOrder  method takes care of pushing the current node, left child and right child (in that order) 
  *  to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given 
  *  to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes 
  *  it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold 
  *  the previous processed node, the current node and the stack.
  * @param node Node Object
  * 
  */
 public void postOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }
  
  Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  Node prevNode = null;
  Node currNode = null;
  
  while (!stack.isEmpty()) {
   currNode = stack.pop();
   
   if (currNode.getLeft() == prevNode || currNode.getRight() == prevNode) {
    // If the current node is the parent of previously processed node. Navigating up the tree. So its enough just to process the node
    System.out.println(currNode);
    prevNode = currNode;
   } else {
    // If previously processed node was the parent of current node. i.e currently processing either the left or right child (navigating down).
    // If the node is the root node.
    // If the current node is the leaf node of a sub-tree. In this case previously processed node and current node are same.
    // If the current node being processed is the right companion of the previously processed node
    
    NodeWrapper nodeWrapper = new NodeWrapper(prevNode, currNode, stack);
    nodeWrapper = navigateAndProcessNodesInPostOrder(nodeWrapper);
    prevNode = nodeWrapper.getPrevNode();
    currNode = nodeWrapper.getCurrNode();
    stack = nodeWrapper.getStack();
   }
  }
 }
 
 /**
  * A helper method for post-order traversal - if given a node, it traverses and processes the sub-tree
  * NodeWrapper object is used to exchange prev, curr nodes and stack between the calling and called method
  * @param nodeWrapper
  * @return
  */
 private NodeWrapper navigateAndProcessNodesInPostOrder(NodeWrapper nodeWrapper) {
  Node currNode = nodeWrapper.getCurrNode();
  Node prevNode = nodeWrapper.getPrevNode();
  Stack<Node> stack = nodeWrapper.getStack();
  
  Node leftNode = currNode.getLeft();
  Node rightNode = currNode.getRight();
  if (leftNode != null  || rightNode != null) {
   // current node (if its a parent) is the last to be processed and so it has to be pushed to stack first
   stack.push(currNode);
   if (rightNode != null) {
    // If there is a right node, push it to stack
    stack.push(rightNode);
   }
   // If there is a left node, push it to stack
   if (leftNode != null) {
    stack.push(leftNode);
   }
   prevNode = currNode;
   
   // Left takes precedence. If there is a left node, go left else go right 
   if (leftNode != null) {
    currNode = currNode.getLeft();
   } else if (rightNode != null) {
    currNode = currNode.getRight();
   }
  } else { // its a leaf node, so process it
   System.out.println(currNode);
   prevNode = currNode;
  }
  nodeWrapper.setPrevNode(prevNode);
  nodeWrapper.setCurrNode(currNode);
  return nodeWrapper;
 }
 
  /**
  * An inner class NodeWrapper to encompass prevNode, currNode and stack for post-order traversal
  *
  */
 class NodeWrapper {
  private Node prevNode;
  private Node currNode;
  private Stack<Node> stack;
  
  NodeWrapper(Node prevNode, Node currNode, Stack<Node> stack) {
   this.prevNode = prevNode;
   this.currNode = currNode;
   this.stack = stack;
  }

  private Node getPrevNode() {
   return prevNode;
  }

  private Node getCurrNode() {
   return currNode;
  }

  private Stack<Node> getStack() {
   return stack;
  }

  private void setPrevNode(Node prevNode) {
   this.prevNode = prevNode;
  }

  private void setCurrNode(Node currNode) {
   this.currNode = currNode;
  }

  private void setStack(Stack<Node> stack) {
   this.stack = stack;
  }
  
 }


The entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms. I have added as many comments as possible in the code. Hope it will help everyone!!

Labels: , ,

Monday, December 16, 2013

Linked List

Linked lists are the most important type of data structure. It contains a series of special elements. These special elements are called special because they hold the data and a pointer to the next element. This pointer is usually called as next pointer. The root element is the starting point of the linked list and the tail element is the last element in the linked list. After the tail element there are no more elements and so the last element’s next pointer has a null reference.

There are 3 types of linked lists
1) Single Linked List – There is one next reference per element
2) Double Linked List – There are two references per element called prev and next. The prev reference points to the previous element and the next reference points to the next element as always
3) Circular Linked List – This is a special type of linked list and they can be of Single or double linked list. The important property that differentiates them is that they do not have the end elements. Yes, there are no head or tail elements. It means that if you start from any element and traverse, you will end up in going circles and never end.

This project illustrates the various operations that can be done on a Single Linked List. Additionally it also shows a special stack implementation using Single Linked List.

Traverse and Print All Elements
Traverses the entire linked list and prints all elements.
 /**
  * Prints all elements in the linked list to out stream
  * @param void
  * @return void
  */
 public void print() {
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext();
  }
 }


Add an element to the end
This adds the given data as an element to the end of the linked list. Now the new element becomes the tail element.
 /**
  * Adds the provided Integer object data to the end of linked list
  * @param data Integer
  * @return boolean
  */
 public boolean add(Integer data) {
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  } else {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    prevElement = currElement;
    currElement = currElement.getNext();
   }
   if (prevElement != null) {
    prevElement.setNext(newElement);
    return true;
   }
  }
  return false;
 }


Add an element at the specified position
Given an integer data, this method creates an element out of it and adds at the specified position of the list.
 /**
  * Inserts the provided Integer object data at the requested position of linked list.
  * If insert was successful it returns true else returns false
  * 
  * 
  * Implementation Details:
  * Though the iteration variable tracks the position of current Element pointer, if a position
  * is found where the new element needs to be inserted, it is implicit that the position is going to be
  * in between the prevElement and curreElement. Idea is to visualize the position (input) to be in between 
  * prevElement and currElement
  * 
  * Say if the position is after the last element then it means you have to insert after the prevElement(pointing last element)
  * but before the curreElement (which is pointing a virtual non-existent element - beyond last element). So its imperative that 
  * the while loop runs until the prevElement is pointing the last element
  * 
  * @param data Integer
  * @param position Long
  * @return boolean
  * 
  */
 public boolean add(Integer data, Long position) {
  
  if (position == null || position.intValue() < 1) {
   return false;
  }
  
  if (head != null) {
   Element newElement = new Element(data);
   if (position.intValue() == 1) {
    newElement.setNext(head);
    head = newElement;
   } else {
    Element prevElement = head;
    Element currElement = head.getNext();
    int iteration = 2;
    while (prevElement != null) {
     if (iteration == position.intValue()) {
      newElement.setNext(currElement);
      prevElement.setNext(newElement);
      return true;
     } else {
      prevElement = currElement;
      currElement = currElement.getNext();
      iteration++;
     }
    }
   }
  }
  
  return false;
 }



Delete an element from the given position
Given a position in linked list, this deletes the element at that position. If there is no such position in the list, then it does not delete anything from the linked list.
 /**
  * This method deletes all elements in the linked list that have the provided Integer data. 
  * If one or many elements are deleted, this method returns true else it returns false
  * @param data Integer
  * @return boolean
  */
 public boolean delete(Integer data) {
  Element givenElement = new Element(data);
  boolean deleted = false;
  
  // Special case if the head element needs to be deleted
  if (head.equals(givenElement)) {
   Element temp = head;
   head = head.getNext();
   temp.setNext(null);
   deleted = true; 
  }
  
  if (head != null) {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    if (currElement.equals(givenElement)) {
     prevElement.setNext(currElement.getNext());
     currElement = currElement.getNext();
     deleted = true;
    }
    prevElement = currElement;
    currElement = currElement.getNext();
   }
  }
  return deleted;
 }


Delete all elements with a given data
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.
 /**
  * This method deletes the element at requested position of the linked list. 
  * If deletion happens, this method returns true else it returns false
  * @param position Long
  * @return boolean
  */
 public boolean delete(Long position) {
  if (position == null || position.intValue() < 1) {
   return false;
  }

  if (head != null) {
   if (position.intValue() == 1) {
    Element temp = head;
    head = head.getNext();
    temp.setNext(null);
    return true;
   } else {
    int iteration = 2;
    Element prevElement = head;
    Element currElement = head.getNext();
    while (currElement != null) {
     if (iteration == position.intValue()) {
      prevElement.setNext(currElement.getNext());
      currElement.setNext(null);
      return true;
     }
     prevElement = currElement;
     currElement = currElement.getNext();
     iteration++;
    }
   }
  }

  return false;
 }


Clear all elements (delete all)
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.
 /**
  * Deletes all elements in the linked list. 
  * If all elements are deleted, this method returns true else it returns false
  * @param void
  * @return boolean
  */
 public boolean clear() {
  if (head == null) {
   return false;
  }
  
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }


Get Element At
Gets the data from the element at the specified position. If there are no elements at the given position, then this method returns null.
 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the head element.
  * @param position Long
  * @return Element
  */
 public Element getElementAt(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  int iteration = 1;
  Element currElement = head;
  while (currElement != null) {
   if (position.intValue() == iteration) {
    return currElement;
   }
   currElement = currElement.getNext();
   iteration++;
  }

  return null;
 }


Get Nth Element From Last
Get Nth element from the tail element of the linked list. The first thought that strike's everyone is – Navigate to the tail element of the linked list and return the Nth previous element from there. But the point that we all tend to forget is - we can traverse only forward in a single linked list. We cannot traverse backwards, and so it makes the solution pretty tricky. The idea is to have two references in the linked list, say A and B. As a first step, have them separated by N elements. This is done by forwarding the B reference by N elements and thereafter keep traversing both references until B reaches tail element. When B is referring the tail element, this in turn means that A is N elements before the tail element.
 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the tail or last element of the linked list.
  * @param position Long
  * @return Element
  */
 public Element getNthFromLastElement(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  Element currElement = head;
  Element nthBehindElement = head;
  int iteration = 1;
  
  while (currElement != null && iteration <= position.intValue()) {
   if (iteration++ == position.intValue()) {
    break; 
   }
   currElement = currElement.getNext();
  }
  
  if (currElement == null) {
   System.out.println("** Error: Current Element is past tail element");
   return null;
  }
  
  while (currElement.getNext() != null) {
   currElement = currElement.getNext();
   nthBehindElement = nthBehindElement.getNext();
  }
  
  return nthBehindElement;
 }


Stack Implementation
This implementation of Stack is done using a linked list. Stack is a simple LIFO data structure. There are two major actions that you can perform on a stack. Push and Pop. Additionally we have a clear operation that deletes all elements in the stack. And lastly we have print operation that prints all elements in the stack.
 /**
  * Returns true if stack is empty else returns false
  * @return boolean
  */
 public boolean isEmpty() {
  if (this.head == null) {
   return true;
  }
  return false;
 }
 
 /**
  * Returns true if the method was able to push data to the stack. Else returns false.
  * @param data Integer
  * @return boolean
  */
 public boolean push(Integer data) {
  if (data == null) {
   return false;
  }
  
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  }
  
  if (head != null) {
   Element temp = head;
   head = newElement;
   head.setNext(temp);
   return true;
  }
  
  return false;
 }
 
 
 /**
  * Pops and returns the last element that was pushed to the stack
  * @return stackElement
  */
 public Element pop() {
  Element element = null;
  if (head == null) {
   System.out.println("Stack is empty!! Cannot pop anything out of it!!");
   return element;
  }
  
  Element firstElement = head;
  Element secondElement = head.getNext();
  head = secondElement;
  firstElement.setNext(null);
  return firstElement;
 }
 
 
 /**
  * Returns true if stack was cleared or if it was empty already
  * @return boolean
  */
 public boolean clear() {
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }
 
 
 /**
  * Iterates over the stack and prints all its elements
  */
 public void printAll() {
  if (head == null) {
   System.out.println("Stack is empty currently!!");
   return;
  }
  
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext(); 
  }
 }


The entire code base for this project can be accessed from my Github repository – Linked List algorithms. I have added as many comments as possible in the code. Hope it helps!!

Labels: , ,

Friday, November 08, 2013

CRUD Services (REST/SOAP) using Java, Apache CXF, Spring, Hibernate, Maven and Log4J

This sample project is an extension to the previous project CRUD using Java Spring and Hibernate. This project focuses on building a web application to expose the already developed features from the previous project as REST and SOAP webservices. To accomplish this task, Apache CXF was used. CXF makes the development of RESTful and SOAPful services simple by using java annotations. It internally uses HTTP binding to map a java method (service or operation) to any given URI and HTTP verb. Spring framework is internally used by CXF to create spring beans and inject those beans in the web application to service the incoming requests.

What’s new in this project?
1) Creation of a web application
2) Integration and configuration of Apache CXF to expose web services
3) Annotations to configure REST services @Path, @Produces, @GET, @POST, @PUT and @DELETE
4) Annotations to configure SOAP services @WebService, @WebMethod and @WebParam
5) REST and SOAP endpoint declarations and web.xml configurations

pom.xml
As a first step, the pom.xml of previous project was taken and added with the following dependencies
 
<dependency>
 <groupId>org.apache.cxf</groupId>
 <artifactId>cxf-rt-frontend-jaxrs</artifactId>
 <version>${cxf.version}</version>
</dependency>
<dependency>
 <groupId>org.apache.cxf</groupId>
 <artifactId>cxf-rt-frontend-jaxws</artifactId>
 <version>${cxf.version}</version>
</dependency>
<dependency>
 <groupId>org.apache.cxf</groupId>
 <artifactId>cxf-rt-transports-http</artifactId>
 <version>${cxf.version}</version>
</dependency>
<dependency>
 <groupId>org.apache.cxf</groupId>
 <artifactId>cxf-rt-rs-extension-providers</artifactId>
 <version>${cxf.version}</version>
</dependency>
<dependency>
 <groupId>org.codehaus.jackson</groupId>
 <artifactId>jackson-jaxrs</artifactId>
 <version>${jackson.version}</version>
</dependency>
<dependency>
 <groupId>org.springframework</groupId>
 <artifactId>spring-web</artifactId>
 <version>${spring.version}</version>
</dependency>

cxf-rt-transports-http is the transport layer of CXF which abstracts the binding and transport details to the rest of the layers. cxf-rt-frontend-jaxws and cxf-rt-frontend-jaxrs are the frontends of CXF that are used to expose SOAP and REST services respectively. cxf-rt-rs-extension-providers has optional extensions that may or may not be needed. jackson-jaxrs is needed for adding JSON functionality to the needed webservices. These two artifacts will be configured as extensions in CXF that will be covered later. Spring-web is internally used by CXF and so its needed. The complete version of pom.xml can be located in the project which can be downloaded from the link provided at the bottom of this post.

Apart from the above dependencies there is one more important addition to pom.xml. Its plugins. There are 2 plugins added – one for the maven-war-plugin. This is used to build a war artifact out of the project. The web.xml relative path need to be mentioned in this plugin so that it picks it up properly. Second plugin is about adding tomcat plugin to the project so that the built webapp artifact (war file) can be automatically deployed in a light-weight tomcat by just executing a simple maven goal. Had this option not available, it would be time consuming to have tomcat installed separately and to deploy the built war file every time a change was made in the code. Maven goals are essentially tasks (Mojos) which can be used effectively to execute something. These goals are configured as plugins for maven.
<build>
<pluginManagement>
  <plugins>
  <plugin>            
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-war-plugin</artifactId>
    <version>2.3</version>
    <configuration>
    <webXml>src/main/webapp/WEB-INF/web.xml</webXml>        
   </configuration>
   </plugin>
    <plugin>
      <groupId>org.apache.tomcat.maven</groupId>
      <artifactId>tomcat7-maven-plugin</artifactId>
      <version>2.1</version>
                <configuration>
                    <path>/</path>
                    <port>8090</port>
    </configuration>
    </plugin>
  </plugins>
</pluginManagement>
</build>

Once this configuration is done, running
1) mvn clean install will clean and then build the project to produce a war file.
2) mvn tomcat7:run will deploy the built war file and start the light-weight tomcat server.

web.xml
The next important configuration is the web application descriptor – web.xml. A folder WEB-INF is created under src/main/webapp where this file is created. This is the configuration that any application server is going to parse as a first step to know what to do.

As expected “org.springframework.web.context.ContextLoaderListener” is provided as a listener class. This is the spring context of our web application. When the application loads into memory, Spring creates the context by creating beans that are mentioned in the configuration files. These configuration file names are the params for “contextConfigLocation” param (here it is applicationContext.xml and cxf-bean.xml).

The most important configuration is for CXF. CXF is a servlet. A web servlet is something that keeps waiting and listening for requests at the configured URL. Once it receives a request, it serves them and continues to listen till it is brought down. That’s exactly what CXF does. It keeps listening at the root URL(/) wherever this application is deployed. Once it gets a request, it invokes the corresponding Spring beans to serve the request accordingly. Here is the complete web.xml file

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<web-app xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"
 version="2.5">
 <display-name>Employee Service</display-name>
 <context-param>
  <param-name>contextConfigLocation</param-name>
  <param-value>
  classpath*:cxf-bean.xml,
  classpath*:applicationContext.xml
  </param-value>
 </context-param>

 <context-param>
  <param-name>initializeContextOnStartup</param-name>
  <param-value>true</param-value>
 </context-param>

 <listener>
  <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
 </listener>

 <servlet>
  <servlet-name>CXFServlet</servlet-name>
  <servlet-class>org.apache.cxf.transport.servlet.CXFServlet</servlet-class>
  <load-on-startup>1</load-on-startup>
 </servlet>

 <servlet-mapping>
  <servlet-name>CXFServlet</servlet-name>
  <url-pattern>/*</url-pattern>
 </servlet-mapping>
</web-app>

applicationContext.xml
This contains the configuration for all the spring beans needed for our application. This is exactly the same configuration what was used in the previous project. If you want to, please refer the explanation here

cxf-bean.xml
This is the master configuration file for apache cxf. This file is referred from web.xml. This means that web.xml file is parsed by the application server before even this file is parsed. This again in turn means all the spring beans are instantiated and readily available in the spring context before this step. This file is used to configure the jaxrs (rest) or jaxws(soap) service endpoints and map them to the corresponding spring beans. Any providers or extensions if any needed are also configured here. If you have a look at the file , its pretty much understandable. We ignore the built-in CXF JSON feature but instead use Jackson JSON and so its configured as a provider.

Employee Services (REST)
Apart from the above configurations, rest all is self-explanatory. I have created Employee Service interface (com.samples.service package) and exposed some HTTP operations. The corresponding Employee Service Impl (com.samples.service.impl package) has the implementation details. Things to note are the annotations that are used to map the HTTP methods of a specific URL to a specific method of a spring service bean. These annotations (@Path, @PathParam, @GET, @POST etc) are in the Interface (EmployeeService.java) These service beans internally call the BO beans which in turn call the DAO beans. The BO beans also depend on adapter beans to convert the hibernate entity objects to web response objects as needed by the service beans.

The REST services exposed (wadl) from this webapp can be seen by hitting the endpoint http://localhost:8090/?_wadl

Employee Services (SOAP)
A sample SOAP service is exposed in EmployeeServiceWS interface. The corresponding implementation can be found in EmployeeServiceWSImpl. This is different from REST services in just the annotations (@WebService, @WebMethod, @WebParam) that are used. An additional configuration is provided in cxf-bean.xml file to refer the bean name(employeeServiceWS) of SOAP service and the endpoint where it serves.
<jaxws:endpoint id="employeeServiceSOAP" implementor="#employeeServiceWS" address="/soapservices" />

The SOAP services exposed (wsdl) from this webapp can be known by hitting the endpoint http://localhost:8090/soapservices?wsdl

The above two endpoints can be imported in SOAP UI and the services can be validated easily. Below is a screenshot of the imported wadl and wsdl in SOAP UI



This project can be downloaded from my Git repository EmployeeWebApp Project @ Github and feel free to play around with it.

Labels: ,