Live stock quote listing using GWT and Spring

In two of the previous posts (XML response, JSON response) I shared my learning about implementing a spring based client application that interacts with yahoo finance API using YQL(Yahoo Query Language), gets finance quotes from the web server for a given symbol.

In this post i would like to share how i use the Google Web Toolkit (GWT) as the front end to display the stock quotes, retrieved by the spring based client application from yahoo finance API. By integrating GWT front end with my spring client application i am showing live stock listing and updates every few minutes for stock symbols entered by the user. Check out my live stock listing application at work that is hosted on google appengine.

Assuming you already have a GWT application with the UI design as per your needs(look at GWT for guidance), the specific steps taken in integrating GWT with the spring application that knows to retrieve stock quotes are shown below:

Step1: Dependency: Add “gwtrpcspring-.jar” to the libraries folder in the project, and make sure CLASSPATH can access this libraries folder. This dependency helps me to use the GWT RPC mechanism to talk to the Spring implementation.

Step2: Define an interface to retrieve stock quotes that extends RemoteService (from GWT) both synchronous and Asynchronous version on GWT client side. The actual implementation of this interface is provided by the spring client application on the GWT server side. Edit the spring client implementation to implement this interface. Also make sure the spring implementation is exported as a service with the “@service” annotation.
Code is shown below with all the required annotations.

Define RPC service to retrieve stock quotes on the GWT Client side

package <packageName>.client
import com.google.gwt.user.client.rpc.RemoteService;

@RemoteServiceRelativePath("stockRetrieve")
public interface StockRetrieveService extends RemoteService{
  Query retrieve(String[] symbols);
}

NOTE: @RemoteServiceRelativePath annotation associates the service identified by “stockRetrieve” with a default path relative to GWT module base URL. Supporting configuration needed for this in web.xml and applicationContext.xml, explained below.

Define Asynchronous service:

import com.google.gwt.user.client.rpc.AsyncCallback;

public interface StockRetrieveServiceAsync {
  void retrieve(String[] symbols, AsyncCallback<Query> callback);
}

NOTE: As part of the GWT client module, the callback procedure has to be implemented for its success and failure scenarios. The sucess scenario will be able to unwrap the Query object to populate the UI with stock quote data.

RPC service implementation to retrieve stock quotes on GWT Server side

package <packageName>.server
@Service
public class StockRetrieveServiceImpl implements StockRetrieveService {
  private final RestTemplate rTemplate;
  private XPathOperations xpathTemplate;
	  
  @Autowired
  StockRetrieveServiceImpl(RestTemplate restTpl) {
    rTemplate = restTpl;  
  }
	  
  @Autowired
  public void setXPathTemplate(XPathOperations xpTemplate) {
    xpathTemplate = xpTemplate;
  }
	
  @Override
  public Query retrieve(String[] symbols) {
  ....
  
  }

Step 3: web.xml in the GWT project:
Edit web.xml in the GWT application to add listener to listen to Spring application context

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

Edit web.xml in GWT application to define GWT RemoteServiceDispatcher servlet and its servlet mappings. Here the url-pattern shows the GWT module base URL followed by the service

  <!-- Servlets -->
  <servlet>
    <servlet-name>dispatcher</servlet-name>
    <servlet-class>org.gwtrpcspring.RemoteServiceDispatcher</servlet-class>
  </servlet>
  
  <servlet-mapping>
    <servlet-name>dispatcher</servlet-name>
    <url-pattern>/stockquotegwt/stockRetrieve</url-pattern> 
  </servlet-mapping> 

Step 4:applicationContext.xml in GWT project:
Edit applicationContext.xml to add the annotation-config and component-scan elements so the annotations will get picked up automatically by spring.

  <context:annotation-config/>
  <context:component-scan base-package="<packageName>.server"/>

Knapsack problem – A Java implementation

Knapsack is a well known problem of packing the knapsack with maximum amount of items within the given weight constraint however of higher value among the available items. The problem description and some of the approaches to solve the problem are laid out in the following wikipedia page “http://en.wikipedia.org/wiki/Knapsack_problem”

Here are Java implementation of two of the approaches. To download the source code visit my github account @ https://github.com/sangs/knapsack-ads

Meet in the middle approach to solving 0-1 knapsack problem:

0-1 knapsack problem is where item of each type are either avaiable or not available for packaging. Also, there are not more than one item of each type. By type here i refer to weight, value combination of the item.

void ksZeroOne(int targetWeight, int nItems, int[] iWeights, int[] iValues) {

//Algo: Meet in the middle approach
//Step1: make two lists "s1", "s2" of item ID's
//Step2: Get a list of all subsets of each set "s1", "s2" and
  //maintain one cache each for the two subset lists - "m1", "m2", s.t. only those subsets based on dominance condition
  //(subsets of equal weight however more value) gets into the cache
  //"m1" -- Weight indexed map "m1" of subsets from list "s1". Holds subsets of equal or more value for the given weight and
  //"m2" -- Weight indexed map "m2" of subsets from list "s2". Holds subsets of equal or more value for the given weight
//Step3: For each subset in map1 find corresponding subset in map2 that satisfies
  //the weight criteria however has a highest value so far.
  //Upon finding the items pack it in the "knapsackContents"

itemW = iWeights;
itemV = iValues;
//Items list with maximum value
ArrayList<ArrayList<Integer>> knapsackContents = new ArrayList<ArrayList<Integer>>();
int m = nItems/2;
int remainingWt = 0;

//Step1:
ArrayList<Integer> s1 = new ArrayList<Integer>(); //First half of items IDs
ArrayList<Integer> s2 = new ArrayList<Integer>(); //Second half of item IDs
Map<Integer, ArrayList<ArrayList<Integer>>> m1 = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();
Map<Integer, ArrayList<ArrayList<Integer>>> m2 = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();

for(int i = 0; i < m; i++) {
  s1.add(i);
}
for(int i = m; i <= nItems-1; i++) {
  s2.add(i);
}

//Step2:
ArrayList<ArrayList<Integer>> ld1 = getAllSubsetsByDominance(s1, 0, 0, m1);
ArrayList<ArrayList<Integer>> ld2 = getAllSubsetsByDominance(s2, 0, m, m2);

//Step3:
Set<Map.Entry<Integer, ArrayList<ArrayList<Integer>>>> kvSet1 = m1.entrySet();
Set<Integer> keySet2 = m2.keySet();
ArrayList<Integer> mylst = null;
ArrayList<Integer> blist = null;
int val1 = 0, val2 = 0, maxval = 0;

for(Map.Entry<Integer, ArrayList<ArrayList<Integer>>> elem : kvSet1) {
  val1 = val2 = maxval = 0;
  Integer elemK = elem.getKey();
  ArrayList<Integer> elemVlist = (elem.getValue()).get(0);
  remainingWt = targetWeight-(elem.getKey());
  for(Integer ix : elemVlist) {
    val1 += itemV[ix.intValue()];
  }
  if(!knapsackContents.isEmpty()) {
    for(Integer ix : knapsackContents.get(0)) {
      maxval += itemV[ix.intValue()];
    }
  }
  for(Integer k : keySet2) {
    if(k.intValue() <= remainingWt) {
      ArrayList<Integer> ls = (m2.get(k)).get(0);
      for(Integer ix : ls) {
        val2 += itemV[ix.intValue()];
      }
      //If combined value is higher than what is already chosen to be in knapsack choose this set instead
      if((val1+val2) > maxval) {
        knapsackContents.clear();
        //Get all possible combinations that makes your knapsack rich !!
        for(ArrayList<Integer> l1 : elem.getValue()) {
          mylst = new ArrayList<Integer>();
          mylst.addAll(l1);
          for(ArrayList<Integer> l2 : m2.get(k) ) {
            blist = new ArrayList<Integer>();
            blist.addAll(mylst);
            blist.addAll(l2);
            knapsackContents.add(blist);
          }
        }
      } // List of Maximum value
    } //List with matching wt constraint found in the other half
  } //for
} //for

  //Printout knapsack contents
  System.out.println("Pack the following items in knapsack that is of highest " +
    "total value and within weight constraint of " + targetWeight);

  int tW = 0, tV = 0;
  //Looking at all possible options in the ZERO-ONE knapsack
  for(ArrayList<Integer> l : knapsackContents) {
    System.out.println("Choose items");
    for(Integer e : l) {
      tW += itemW[e];
      tV += itemV[e];
      System.out.println("Weight: " + itemW[e] + ", Value: " + itemV[e]);
    }
    System.out.println("Total weight: " + tW + " Total value: " + tV);
  }
} //ksZeroOne

//offset to indicate which half we are looking at: 0 - first half, m - second half.
ArrayList<ArrayList<Integer>> getAllSubsetsByDominance(ArrayList<Integer> s, int index, int offset, Map<Integer, ArrayList<ArrayList<Integer>>> cache) {
  ArrayList<ArrayList<Integer>> allss;
  if(s.size() == index) {
    allss = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> emptysubset = new ArrayList<Integer>();
    allss.add(emptysubset);
  }
  else {
    allss = getAllSubsetsByDominance(s, index+1, offset, cache);
    ArrayList<ArrayList<Integer>> myallss = new ArrayList<ArrayList<Integer>>();
    int itemId = -1;
    for(ArrayList<Integer> lst : allss) {
      ArrayList<Integer> mysubset = new ArrayList<Integer>(); //itemIDWt
      mysubset.addAll(lst);
      itemId = offset+index;
      mysubset.add(0, itemId);

      //Run dominance procedure starts
      int wt = 0, newval = 0, val = 0;
      if(!mysubset.isEmpty()) { //If not an empty list
      for(Integer i : mysubset) {
        wt += itemW[i];
        newval += itemV[i];
      }

      ArrayList<ArrayList<Integer>> alist;
      if(cache.containsKey(wt)) {
        //OK to get first list as it only holds list of equal value when there is more than one
        //of them of given weight
        alist = cache.get(wt);
        for(Integer i : (alist).get(0)) {
          val += itemV[i];
        }
        if(newval > val) {
          alist.clear();
        }
        if(newval >= val) {
          alist.add(mysubset);
          cache.put(wt, alist);
        }
      }
      else { //Add it if not in the cache
        alist = new ArrayList<ArrayList<Integer>>();
        alist.add(mysubset);
        cache.put(wt, alist);
      }
    }
    //Run dominance procedure ends

    myallss.add(mysubset);
  } //for

  allss.addAll(myallss);
} //else

return allss;
} //getAllSubsetsByDominance

Dynamic programming approach to solving unbounded knapsack problem:

Unbounded knapsack problem is where the number of items of each type can be more than one. Again, by type we refer to the item of a particular weight and value combination.

//Dynamic Programming
void ksUnbounded(int targetWeight, int nItems, int[] iWeights, int[] iValues) {
//Algo: Dynamic Programming/Memoizing
//Step1: Maitain a two-dimensional array, Array[0...nItems][0...targetWeight]
  //Note: Weight increses upto targetWeight
//Step2: Also maintain a ksTrackArray[0...nItems-1][0...targetWeight] to track which items are
  //part of the solution satisfying the weight value constraint
//Step3: At any point in dynamic programming find: maximum combined weight of any subsets of items, o...currentItem
  //of weight atmost iw (the ith weight in the 2-dimensional array)

int[][] ksItemCapacity = new int[nItems+1][targetWeight+1];
int[][] ksTrack = new int[nItems+1][targetWeight+1];

for(int w = 0; w <= targetWeight; w++) {
  ksItemCapacity[0][w] = 0;
}

for(int item = 1; item < nItems; item++) {
  for(int w = 0; w <= targetWeight; w++) {
    //last known Maximum value of KS contents s.t. their weight totals to atmost w-iWeights[item]
    int eItemValue = (iWeights[item] <= w)? ksItemCapacity[item-1][w-iWeights[item]] : 0;
    if( (iWeights[item] <= w) && (iValues[item]+eItemValue) > ksItemCapacity[item-1][w] ) {
      ksItemCapacity[item][w] = eItemValue+iValues[item]; //current item included
      ksTrack[item][w] = 1;
    }
    else {
      ksItemCapacity[item][w] = ksItemCapacity[item-1][w]; //current item not included
      ksTrack[item][w] = 0;
    }
  }
}

//Print KS contents
ArrayList<Integer> ksContents = new ArrayList<Integer>();
int tW = targetWeight;
for(int item = nItems; item >= 0; item--) {
  if(ksTrack[item][tW] == 1) {
    tW -= iWeights[item];
    ksContents.add(item);
  }
}

System.out.println("Items choosen are:");
int W = 0, V = 0;
for(Integer e : ksContents) {
  W += iWeights[e];
  V += iValues[e];
  System.out.println("Weight: " + iWeights[e] + ", Value: " + iValues[e]);
}
System.out.println("Total weight: " + W + " Total value: " + V);
} //ksUnbounded