Small Description on Java WURFL Api

WURFL Java API

The API is simple. You have basically three objects which give you all the methods to obtain the info you need:
CapabilityMatrix , UAManager and ListManager.

CapabilityMatrix:
getCapabilityForDevice() requires a DeviceID and a capability name and it will return the value of the capability.

UAManager:
getDeviceIDFromUA() and getDeviceIDFromUALoose() require a User-Agent string and return the WURFL device ID.
It comes with two flavors: strict matching and loose matching. If in doubt, use the loose matching.

ListManager:
contains method that return lists of WURFL related data, such as list of capabilities, list of devices, etc.

To add to that, you have a singleton (ObjectsManager) that makes sure that all the WURFL data is initialized at least once and only once.
The three objects above are returned by the ObjectsManager() with calls like:

CapabilityMatrix cm = ObjectsManager.getCapabilityMatrixInstance();

One important aspect of this API is that you need *no* XML knowledge whatsoever to use it.
You just deal with strings and lists of different kinds (ArrayLists and HashMaps).

Here is a simple example of how to use the library


import net.sourceforge.wurfl.wurflapi.*;
import java.io.*;
import java.util.*;
import javax.servlet.*;
import javax.servlet.http.*;

public class Test extends HttpServlet {

public void doGet(HttpServletRequest request, HttpServletResponse response)
throws IOException, ServletException
{
response.setContentType("text/html");
PrintWriter out = response.getWriter();

//HTML Syntax
out.println("");

out.println("

Request Information Example

");

UAManager uam = ObjectsManager.getUAManagerInstance();
CapabilityMatrix cm = ObjectsManager.getCapabilityMatrixInstance();
out.println(uam.getDeviceIDFromUA("MOT-T720/05.08.41R MIB/2.0 Profile/MIDP-1.0 Configuration/CLDC-1.0"));

out.println("loose matching MOT-T720/G_05.01.43R");
out.println(uam.getDeviceIDFromUALoose("MOT-T720/G_05.01.43R"));

out.println(uam.getDeviceIDFromUALoose("UP.Browser"));
out.println(uam.getDeviceIDFromUALoose("Nokia7650"));

out.println("Capability Matrix:");
out.println("Device ID: telit_gm822_ver1_sub302_5017 , Capability Name: mms_wbxml")
out.println(cm.getCapabilityForDevice("telit_gm822_ver1_sub302_5017","mms_wbxml"));
out.println("");
out.println("");


}

This will produce:

mot_t720_ver1_sub050841r

loose matching MOT-T720/G_05.01.43R
mot_t720_ver1_subg050143r

samsung_r200s_ver1_sub4119kxxxx
nokia_7650_ver1_subnover
Capability Matrix:
Device ID: telit_gm822_ver1_sub302_5017 , Capability Name: mms_wbxml
false


One important aspect to note is that the results of your queries are cached. This speeds up WURFL access enormously.
The cache is the same for all of the servlet/JSP pages running inside the same webapplication.

Of course, any WURFL-based application will need to be initialized with a wurfl.xml file. This may happen in two different ways,
depending on wether you are deploying in a web (Servlet/JSP) environment or it's a stand-alone application.

Initializing stand-alone application
You can explicitly initialize the WURFL by telling the system where to find the file:

ObjectsManager.getWurflInstance("C:\wurfl_stuff\wurfl.xml");

if you don't tell the library where to find the wurfl programmatically using the method above, the API will initially look for a file
called wurfl.properties to see if the location of the wurfl is specified there: sample wurfl.properties:

wurflpath = file://C:\\projects\\wurfl\\antbuild\\resources\\wurfl.xml

If the property file is not found, the API will look for "C:\temp\wurfl.xml" on Windows and "/tmp/wurl.xml" on UNIX.

If nothing is found, an exception is thrown and a message is printed.




Retrieving a Device ID through the User-Agent

Two different methods in the UAManager class can do the job:

* getDeviceIDFromUA(String user-agent)
returns a String representing a WURFL device ID. This function looks in the WURFL for an exact match. If you don't get it, you will receive "generic" (i.e. the ID of the unrecognized device).
* getDeviceIDFromUALoose (String user-agent)
also returns a string representing a WURFL device ID. The difference is that this method won't take no for an answer nearly as easily. In case an exact match is not found, a few heuristics are applied to find a device that's reasonably similar.

At the time of this writing, the heuristics are the following:

1. Chars are removed one at the time from the end of the string. At each step a match is attempted between the string and the first part of each existing user-agent. This ends when either a match is found or the query string has become five chars.
2. Vodafone has introduced on its network a bunch of devices that add the "Vodafone/" string at the beginning of the user-agent. Those devices are listed in the WURFL. In case of a miss, the "Vodafone/" string is removed and the matching algorithm is applied from start.
3. If a match is not found, the matching algorithm looks for hints that still can lead to some useful assumptions: "UP.Browser/4","UP.Browser/5","UP.Browser/6", "Series60","Mozilla/4.0" and so on.
4. Defeat! return "generic".

If you wonder about the performance of this animal, don't worry. Queries are cached, so any subsequent query with the same data is resolved with a simple HashMap lookup.

Retrieving Capability Values

Once you have a device ID, you are ready to rock and roll: just use getCapabilityForDevice() to retrieve the value of any capability. This is a method of the CapabilityMatrix class.

- getCapabilityForDevice(String deviceID, String capabilityName)
Returns the value of a capability for a given device. There is not much to add here:

System.out.println(cm.getCapabilityForDevice("sie_m50_ver1","resolution_width"));
Q: Excuse me, Mr. Capability Matrix, how many horizontal pixels can I rely on for a Siemens M50?
A: 110 pixels, Sir.



Simple and powerful.

Setting up the Singletons

The methods above are simple to use, but there is a tiny bit of work you need to do before you can use them. Parsing the WURFL and traversing it to retrieve information is heavy stuff. The API is architected in a way that time-consuming operations are performed either at start-up or only once.

For this reason, you need to create a UAManager and CapabilityMatrix before you invoke the corresponding methods above. For the same reason, you don't just create a UAManager and CapabilityMatrix using 'new()', rather you request ObjectsManager to give them to you. ObjectsManager will make sure that a new object is created only if you are the first to request. Otherwise, you get the existing one (or better a reference to it, but I assume you have a smattering of Java from before). UAManger and CapabilityMatrix are examples of Singletons, in case you are familiar with pattern-theory parlance. If you are not, there's no need to worry: Just make sure that you have these two lines in your code, and you will have someone to talk to when you need to make a query:

UAManager uam = ObjectsManager.getUAManagerInstance();
CapabilityMatrix cm = ObjectsManager.getCapabilityMatrixInstance();

A link to a resource about Singletons can be found in the references.

Time for an another Example

The java snippet at the end of the WURFL intro last month was an example of usage of the Java API. Let's have a look at something more practical here: the implementation of the 'br' tag of the WALL library. There is no common 'br' (breakline) tag for CHTML, XHTML MP and WML, but ... almost.

* Most CHTML devices honor the
tag and simply ignore
tags
* Most XHTML MP devices will honor both
and
tags.
* Some XHTML MP device will throw an error if a single unslashed
is found and no information will be displayed (except a pretty useless error message)

This is a job for WALL, the Wireless Abstraction library:

------------------------------------------------------------------------------
public int doStartTag() throws JspException {

try {
cm = ObjectsManager.getCapabilityMatrixInstance();
uam = ObjectsManager.getUAManagerInstance();
request = (HttpServletRequest) pageContext.getRequest();

//get the user agent
UA = TagUtil.getUA(this.request);

//Check the capability string
warning = TagUtil.checkCapability("preferred_markup");
if (warning.length() > 0) {
throw new JspException(warning);
}

device_id = uam.getDeviceIDFromUALoose(UA);

capability_value = cm.getCapabilityForDevice(device_id, "preferred_markup");
capability_value = TagUtil.getWallMarkup(capability_value);

if ( capability_value.startsWith("xhtmlmp") ) {
try {
JspWriter out = pageContext.getOut();
out.print("
");
} catch(IOException ioe) {
throw new JspException("Error in WALL tag 'br': " + ioe.getMessage());
}
}

if ( capability_value.startsWith("wml") ) {
try {
JspWriter out = pageContext.getOut();
out.print("
");
} catch(IOException ioe) {
throw new JspException("Error in WALL tag 'br': " + ioe.getMessage());
}
}

//CHTML
without trailing slash
if ( capability_value.startsWith("chtml") ) {
try {
JspWriter out = pageContext.getOut();
out.print("
");
} catch(IOException ioe) {
throw new JspException("Error in WALL tag 'br': " + ioe.getMessage());
}

}

return (SKIP_BODY);

} catch (Exception e) {
throw new JspException("Error in WALL tag 'br': " + e.getMessage());
}

}
------------------------------------------------------------------------------



As usual, real apps need to spend much time in managing errors, so, here is an abridged version that shows the relevant parts:

------------------------------------------------------------------------------
1 cm = ObjectsManager.getCapabilityMatrixInstance();
2 uam = ObjectsManager.getUAManagerInstance();
3 request = (HttpServletRequest) pageContext.getRequest();
4
5 //get the user agent
6 UA = TagUtil.getUA(this.request);
7
8 device_id = uam.getDeviceIDFromUALoose(UA);
9
10 capability_value = cm.getCapabilityForDevice(device_id, "preferred_markup");
11 capability_value = TagUtil.getWallMarkup(capability_value);
12
13 if ( capability_value.startsWith("xhtmlmp") ) {
14 out.print("
");
15 }
16
17 if ( capability_value.startsWith("wml") ) {
18 out.print("
");
19 }
20
21 //CHTML
without trailing slash
22 if ( capability_value.startsWith("chtml") ) {
23 out.print("
");
24 }
------------------------------------------------------------------------------

* lines 1 and 2 create our singletons.
* lines 3 and 6 extract the User-Agent string out of the request. TagUtil.getUA() simple gives the developer a chance to override the User-Agent HTTP header for debugging purposes.
* line 8 does whatever it can to retrieve the ID of the device definition that best models the requesting device out of the user-agent string.
* lines 10 and 11 query the 'preferred_markup' for the device. TagUtil.getWallMarkup() normalizes the retrieved value into one of the three that WALL expects ('wml','xhtmlmp' and 'chtml')
* lines 13 through 24 send the most appropriate break-line tag back according to the preferred markup.

It's simple stuff. No rocket science here.

All That We Have Left Behind

The main functionalities of the API are covered, but a bunch of other things are worth mentioning.

* CapabilitMatrix.isCapabilityIn(String capability_name)
In real apps, you may want to check that a given capabilities is defined in the WURFL before querying it. An error here and you may spend more time than you wish tracking out what went wrong where. This method does that.

* ListManager is also a singleton and it supports a bunch of methods to retrieve lists of devices and capabilities you can loop on. In practical applications, you don't need those methods, since you typically deal with one device at the time. The methods become necessary when you want to implement WURFL utilities to analyze the WURFL repository and build reports. For example, you may request a list of all actual devices (devices with 'actual_device_root==true').

* WurflDevice encapsulates in a Java class everything the WURFL knows about a given device. Also not very useful unless you need to build reports of some kind. This also includes the use of the WurflDevice.getActual_device_root(), which can be used to tell if a given device is marked as 'actual device' in the WURFL.

* WurflSource is an interface that lets you initialize the API using alternative sources from which to read wurfl.xml. Totally honestly, this functionality is not very tested. If it doesn't work, give the WURFL team a holler on the WMLProgramming mailing list.

Graphs

9.1 Introduction

A graph G consists of a set V, whose members are called vertices of G, together with a set E of pairs of distinct vertices from V. These pairs are called the edges of G. If the pairs are unordered then G is called undirected Graph and if they are in order they are called Directed or digraphs.

9.2 Computer Representation of Graphs

1. The set representation
2. Adjacency Table or Adjacency Matrix
3. Adjacency List
a. Linked Implementation
b. Contiguous List
c. Mixed Implementation

9.3 Operations on Graphs
1. Breadth First Traversal
2. Depth First traversal

Experiment 27

Aim –Write a program to execute a Breadth First search on a Graph G beginning at A

Algorithm -

1. Initialize all node to ready state (Status = 1)
2. Put the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until queue is empty
4. Remove the first node N of queue. Process N and change its status to processed state (status=3)
5. Add to the rear of queue all the neighbors of N that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 2 Loop]
6. Exit

Experiment 28


Aim –Write a program to execute a Depth First search on a Graph G beginning at A

Algorithm –

1. Initialize all nodes to ready state (Status = 1)
2. Push the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until stack is empty
4. Pop the Top node N of stack . Process N and change its status to processed state (status=3)
5. Push onto stack all the neighbors that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 3 Loop]
6. Exit


9.4 Viva Voice

1. Define graph, directed and undirected graph?
2. Define the following:
a. Adjacent vertices
b. Path
c. Cycle
d. Connected graph
e. Degree
f. Complete graph
g. Weighted graph
3. How the graph is represented in computers memory?
4. What do you mean by graph traversal? What are different traversal methods of graph?
5. Minimum spanning tree are designed on directed or undirected graph?
6. What must a graph look like if a row of its matrix consists only of zeros?

Trees

8.1 Introduction-
A binary tree is either empty or it consists of a node called the root together with two binary trees called the Left subtree and the right subtree of the root.

8.2 Operations on Binary trees.
1. Insertion in Binary Tree
2. Deletion in Binary Tree
3. Traversal of Trees
a. Pre-order Traversal ( Root-Left-Right )
b. In-order Traversal ( Left-Root-Right )
c. Post-order Traversal ( Left-Right-Root )

Applications

1. Comparison Trees
2. Expression Trees


Experiment 24

Aim –Write a program to create a binary tree

Algorithm -

Let create_tree (info,node) be a procedure where info is the information for which we have to create node and node is a structure type variable with pointers to point to both left and right child.

1. [check whether the tree is empty]
If node = NULL
Node=create a node
Left[node]=NULL
Right[node]=NULL
2. [Test for the left child]
If info[node] >= info
Left[node]=Call create_tree(info,left[node])
else
Right[node]=Call create_tree(info,right[node])
3. return (Node)

8.3 Viva Voice

1. What is a Tree
2. Define the following terms
a. Degree
b. Depth
c. Path
d. Forest
3. Differentiate between Terminal nodes and non-terminal nodes
4. What is Binary tree.
5. Mention the properties of binary tree
6. What is Strictly & completely binary Tree
7. How binary tree is represented in computers memory?
8. What is thearded binary tree? It’s advantages and disadvantages
9. Draw the binary tree using the given traversals?
10. What is AVL tree?
11. Whait if forest?

Searching

7.1 Introduction
Searching is used to find the location where element is available or not. There are two types of searching techniques as given below :
1. Linear or sequential searching
2. Binary searching


Experiment 22

Aim –Write a program to search the given element using linear search.

Theory
In linear search, we access each element of an array one by one sequentially and see whether it is desired element or not. A search will be unsuccessful if all the elements are accessed and the desired element is not found. In the worst case the number of average case we may have to scan half of the size of the array. Therefore, linear search can be defined as a technique which traverses the array sequentially to locate the given item.
The time taken or the number of comparisons made in searching a record in search table determines the efficiency of the technique. If the desired record is present in the first position then only one comparison is made. If the desired record is last one then n comparisons have to made.


Algorithms
Let A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in A, or sets LOC=0 if the search is unsuccessful.

1. [Initialize counter]
set LOC = 1
2. [Serach for item]
repeat while A[LOC] != ITEM
set LOC=LOC+1
3.[Successful]
if LOC = N+1, then
set LOC=0
4. Exit.



Experiment 23

Aim –Write a program to search the given element using binary search.

Theory- The search technique searches the given item in minimum possible comparisons. To do the Binary search, first the array is sorted. The logic behind the technique is
1. First find the middle element of the array.
2. Compare the mid element with the item
3. There are three cases:
a. If it is the desired element search is successful.
b. If it is less than desired item, then search the first half of the array
c. If it is greater than desired item, then search the second half of the array
Repeat the same steps until the search is exhausted.


Algorithms
Let A is sorted array with lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG, END and MID denoted, respectively, the beginning, end and middle location of a segment of element of A. This algorithm finds the location LOC of ITEM in A or sets LOC = NULL.

1. [Initialize segment variables]
Set BEG = LB ,END = UB and MID = int (( BEG + End)) / 2
2. Repeat steps 3 and 4 while BEG <= END and A[MID] != ITEM
3. if ITEM < A [MID] , then
Set END = MID – 1
Else
Set BEG = MID +1
[end of if structure]
4. set mid = int ((BEG + END))/2
[End of step 2 loop]
5. if A[MID] = ITEM then
set LOC = MID
else
set LOC = NULL
[end of if structure]
6.exit


7.2 Viva voice

1.What is sorting? List different types of sorting techniques.
2. What are the factors to be considered during the selection of sorting technique.
3.Which of the following sorts will take longest time to execute and which will take the shortest time?
a) Merge sort
b) Heap sort
c) Selection sort
d) Shell sort
e) Quick sort
f) Insertion sort

4. How many comparisons are required to sort an array of 10 elements using selection sort , if the original array values already sorted?
5. What do you mean by efficiency of the algorithm?
6. What is the best case , average case and worst case complexity of following:
a) merge sort
b) heap sort
c) selection sort
d) shell sort
e) quick sort
f) insertion sort
7.What are the factors on which complexity of algorithm depends? Which factor is taken into consideration while determining the complexity of algorithm for searching and sorting?
8.Suppose name consist of following list of names with n= 5
Amit, jaswinder , chander, gagan, seema
Find the number of comparisons to sort name using radix sort.
9.What is searching?
10.Distinguish between the following
a) Internal search and external search
b) Primary key and secondary key
c) Internal key and external key
10. Which is efficient search technique?
11. What is hashing? What is the need for a hashing?
12. What is the need for an ordered table searching?
13. What are the techniques to resolve hash clashes?

Sorting

6.1 Introduction
Sorting of an array is the technique of arranging the array elements in a specified order i.e either in ascending or descending order. Sorting is one of the operation which make the job of retrieval of data from the storage devices, easier, speedier and efficient.

There are several sorting techniques available. They are :

1. Bubble sort
2. Selection sort
3. Shell sort
4. Heap sort
5. Insertion sort
6. Quick sort
7. Merge sort


6.2 Efficiency of Sorting Algorithms


Performance analysis & measurement
The time and space the algorithm uses are the two major measures of the efficiency of the algorithm. The complexity of the algorithm is the function which gives the running time and/or space in terms of the input size.
Space complexity
The space complexity of a program is the amount of memory it needed to fun to completion.
Time Complexity:
It is the amount of computer time needs to run to completion.

Big OH Notation
Big OH is a characterization scheme that allows to measure properties of algorithm complexity performance and/or memory requirements in a general fashion.

LINKED LIST

5.1 INTRODUCTION
Linked lists are special list of some data element pointing to one another.The logical ordering is represented by having each element pointing to the next element.Each element is called a node, which has two parts.INFO part which stores the information and POINTER which points to the next element.

5.2 OPERATIONS ON LINKED LIST
The basic operation to be performed on linked list are as follows :
1. Creation 2. Insertion
3. Deletion 4. Traversing
5. searching 6.Concatenation
7.Display

5.3 TYPES OF LINKED LIST
1. Singly linked list 2. Doubly linked list
3. Circular linked list 4. Circular Doubly linked list

SINGLY LINKED LIST
singly linked list are known as one way list. In this one pointer is maintained , which points to the next node called the NEXT pointer. One can traverse the list in forward direction.

DOUBLY LINKED LIST
Doubly linked list are known as two way list. In this two pointers are maintained :One which points to the next node called the NEXT pointer and other which points to previous node called the PREV pointer. One can traverse the list both in forward as well as backward direction.

CIRCULAR LINKED LIST
A Circular Linked List is one which has no beginning and no end. In this two pointers are maintained: One which points to the next node called the NEXT pointer and other which points to previous node called the PREV pointer. One can traverse the list both in forward as well as backward direction. It is very similar to doubly linked list except that in doubly linked list the prev pointer of the first node and the next pointer of the last node points to NULL where as in circular linked list the last node contains the address of the first node and the last node contains the address of the first node. All operation are similar to doubly linked list

Queues

4.1 INTRODUCTION

A queue is a non-primitive linear data structure .It is an homogeneous collection of elements in which new elements are added at one end called the Rear end , and the existing elements are deleted from other end called the Front end.

4.2 OPERATION ON QUEUES

The basic operations that can be performed on queue are:
To insert an element in the queue.
To delete an element from the queue.

4.3 DEQUEUES

It is homogeneous list of elements in which insertion and deletion operations are performed from both the ends.

4.4 Operations on Dequeue

1. Insertion of an element at the REAR end of the queue.
2. Deletion of an element from the FRONT end of the queue.
3. Insertion of an element at the FRONT end of the queue.
4. Deletion of an element from the REAR end of the queue

For an input-restricted deque only the operations specified in 1, 2, 3 and 4 are valid. And for out- restricted deque only the operations specified in 1, 2, 3 are valid.


4.5Application of arrays

1. Round robin technique for processor scheduling is implemented using queues.
2. All types of customer service (like railway ticket reservation) center software’s are designed using queues to store customers information.
3. Printer server routines are designed using queues.


Experiment 7

Aim- Write a program to perform add and delete operations in the linear queue

Algorithm (Insertion)
Let QUEUE be the array of some specified size say MAXSIZE, then the insertion algorithm will be as given below.While implementing a queue using arrays we must check underflow and overflow conditions for queue.

1. Initialize Front =0 and Rear = -1
2. If Rear b>= MAXSIZE [Check overflow condition]
Write Queue Overflow and return
Else
Set Rear = Rear + 1
3. QUEUE[Rear] = Item
4. If Front = -1 [Set the front pointer]
5. Return.

Algorithm (Deletion)

1. [Check underflow condition]
If Front < 0
Print : Queue is Empty and return
Else :
Item = QUEUE[Front] [Remove Element from front]
3. [Find new value of front.]
If (Front= = Rear) [Checking for empty queue]
Set front=0 , Rear = -1 [Re- initialize the pointers]
Else:
Front = Front +1
4. Return

4.7VIVA VOICE

1.What is a queue?
2.What does ‘front’ and ‘rear’ of the queue?
3. What is the full form of DEQUEUE?
4. How is queue different from stack?
5. Distinguish between LIFO and FIFO.
6. What is full queue and empty queue condition
7. What is circular queue and how do you represent it?
8. What is Dequeue?
9. What is meant by priority queues?