trash of a luring machine

Implementation of undirected graph in java

2011-06-21T22:23:00.000-07:00

A minimal implementation of undirected graph in Java :


import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * @author Narendra Yadala
 * Implementation of undirected graph represented using adjacency list.
 */
public final class UndirectedGraph<T> implements Iterable<T>{
 private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

 public boolean addNode(T node) {
  if (graph.containsKey(node))
   return false;

  graph.put(node, new HashSet<T>());
  return true;
 }

 public void addEdge(T start, T dest) {
  if (!graph.containsKey(start) || !graph.containsKey(dest))
   throw new NoSuchElementException("Nodes must be in the graph.");
  
  graph.get(start).add(dest);
  graph.get(dest).add(start);
 }

 public void removeEdge(T start, T dest) {
  if (!graph.containsKey(start) || !graph.containsKey(dest))
   throw new NoSuchElementException("Nodes must be in the graph.");

  graph.get(start).remove(dest);
  graph.get(dest).remove(start);
 }

 public boolean isEdgeExists(T start, T end) {
  if (!graph.containsKey(start) || !graph.containsKey(end))
   throw new NoSuchElementException("Nodes must be in the graph.");

  return graph.get(start).contains(end);
 }

 public Set<T> getNeighbors(T node) {
  Set<T> neighbors = graph.get(node);
  if (neighbors == null)
   throw new NoSuchElementException("Node does not exist.");

  return Collections.unmodifiableSet(neighbors);
 }

 public Iterator<T> iterator() {
  return graph.keySet().iterator();
 }
 public Iterable<T> getNodes() {
  return graph.keySet();
 }
 public int size() {
  return graph.size();
 }
 public boolean isEmpty() {
  return graph.isEmpty();
 }
}

Inheritance in Javascript

2011-04-26T04:43:00.000-07:00

Javascript does not provide inheritance as a built-in feature like Java/C++ but it can be easily programmed by using the prototype property of an object.

Every Javascript object has two internal properties 'constructor' and '__proto__'. For this post I will just confine to '__proto__' property as it is more instrumental in understanding the prototypal inheritance provided by Javascript. Also, the constructor property is quite confusing and demands an entire post for itself.

Let us see what happens when we create an object invoking new operator on a function.


var Animal = function() { this.eat = function(){console.log('EATING')} }
Animal.prototype = { sleep : function(){console.log('SLEEPING')} }

animal = new Animal();

The __proto__ property of animal object is set from the prototype property of Animal constructor function. That is why the statement animal.__proto__ == Animal.prototype returns true. When we call animal.sleep function the interpreter checks if the animal object has its own property 'sleep' and if it does not, then it searches for 'sleep' property in animal.__proto__ object.

Similarly when we call animal.toString() method, then it checks for toString property inside animal object and finds nothing there. Then it goes ahead and checks in animal.__proto__ object and finds nothing there. It does not stop there and checks for toString property in animal.__proto__.__proto__ object which points to Object.prototype object. It finally finds the toString property there and then executes it. And, since the Animal object did not override the toString method of Object object we get the raw output "[object Object]".

This form of chaining of prototypes forms the basis of inheritance in Javascript. Let us create a Dog object to see how we can create a inheritance hierarchy :


var Dog = function(){this.bark = function(){console.log('BARKING')}}

Dog is an animal so it needs to inherit from Animal. All we need for this is to set the prototype of the Dog object to point to an Animal object :

 Dog.prototype = new Animal();

Above statement sets Dog.prototype.__proto__ to Animal.prototype which is what we wanted. We now instantiate dog objects using the Dog function we created.

dog = new Dog();

We can now call dog.bark() , dog.sleep(), dog.eat() and dog.toString() seamlessly.

Functions in Javascript

2011-03-31T04:04:00.000-07:00

In Javascript functions are first-class objects.

In computing, a first-class object (also value, entity, and citizen), in the context of a particular programming language, is an entity that can be passed as a parameter, returned from a subroutine, or assigned into a variable.

This means that Javascript can support functional programming constructs such as anonymous functions, higher order functions, nested functions, closures, currying etc.

This is best understood through an example :
function sum(a,b) {return a+b}
function incrementer(a) {
  return function(b) { //here we are returning a function and also
    //creating an anonymous function
    return sum(a,b); //here we are using closure by
    //referring to local variable a of the incrementer function
  }
}
var incrementBy1 = incrementer(1);
incrementBy1(10); //returns 11
var incrementBy2 = incrementer(2);
incrementBy2(10); //returns 12

Tweetify Plain Text

2011-02-25T01:09:00.000-08:00

When we use twitter API to retrieve the tweets, it gives us the plain text that has to be converted into proper html so that they are rendered to web user in a more usable fashion. For this we need to do three tasks :
1. Replace plain text urls to anchor tags pointing to those urls.
2. Replace @username with proper anchor tags pointing to their twitter accounts.
3. Replace #topic with anchor tags pointing to twitter search api.

This is the javascript needed to convert a tweet in plain text to that containing proper links, hashtags and @ operators.


function tweetify(text) {
    text = text.replace(/\b((?:[a-z][\w-]+:(?:\/{1,3}|[a-z0-9%])|www\d{0,3}[.]|[a-z0- 9.\-]+[.][a-z]{2,4}\/)(?:(?:[^\s()<>.]+[.]?)+|\((?:[^\s()<>]+|(?:\([^\s()<>]+\)))*\))+(?:\((?:[^\s()<>]+|(?:\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/gi, "<a target=_blank href=$1>$1</a>");
    text = text.replace(/[\@]+([A-Za-z0-9-_]+)/gi, "<a target=_blank href=http://twitter.com/$1>@$1</a>");
    return text.replace(/(?:^| )[\#]+([A-Za-z0-9-_]+)/gi, "<a target=_blank href=http://search.twitter.com/search?q=&tag=$1&lang=all>#$1</a>");
}

Regular Expressions

2011-02-24T03:25:00.000-08:00

In programming languages one generally comes across a situation where one needs to match input text against a pattern. I will quickly summarize the basic terminology involving the use of regular expressions.
1. Input text
2. Regular expression - this is also called the search pattern, there is a whole lot of syntax on how to construct this pattern which can be found here ( Regular Expression Reference)
3. Regular expression engine - this is the program that basically matches the regular expression occurring in the input text, and then it can do several operations on the matches that are found such as replacing it with some other text. So this can be thought of as consisting of two main components : a matcher and a replacer
4. Match - the text in the input text that complies exactly to the specification of the regular expression.

I will take a regex I recently modified (Original regex) to explain the concepts involved. This regex basically matches the url inside input text. I was working on showing tweets on a page and I needed to replace the plain URL text inside the tweet with html anchor tag pointing to the the plain URL text.

Here I am using javascript regex syntax to show how one can use this regex to convert text 'This is the URL of current webpage http://wearmyhat.blogspot.com' to 'This is the URL of current webpage < a href="http://wearmyhat.blogspot.com">http://wearmyhat.blogspot.com< / a>'
I marked the modification I did in bold..this is a slight modification to avoid matching the ellipsis that occurs after the actual URL text. For example original regex was matching the ellipsis occuring after the following URL http://wearmyhat.blogspot.com... This was not really acceptable to my application.
Modified Regex:

text = text.replace(/\b((?:[a-z][\w-]+:(?:\/{1,3}|[a-z0-9%])|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:(?:[^\s()<>.]+[.]?)+|$(?:[^\s()<>]+|(?:\([^\s()<>]+$))*\))+(?:$(?:[^\s()<>]+|(?:\([^\s()<>]+$))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/gi, "<a target=_blank href=$1>$1</a>");

What I am going to do is take the main constructs that are used in this regex in order and explain them one by one.
1. \b Matches character between word and non-word character..in other words matches starting or ending character of a word.
2. () Capturing group [whatever is inside is captured by the matcher in entirety]. The above regex has only one outer capturing group with multiple non-capturing groups placed inside. These groups are the only groups that can be backreferenced.
3. (?:) Non-capturing group [whatever is inside is not captured by the matcher in entirety]. This also means that these groups are not available for backreferencing purpose. Any number of capturing groups inside a non-capturing group are treated as capturing groups by the Regex engine (which is actually non-intuitive).
4. [\w] matches a word character.
5. [^\s] matches a non-space character, [a-z] matches any character between a to z.
6. /{1,3} forward slash 1-3 times, \d{0,3} a digit 0-3 times, [a-z]{2-4} any character between a to z can occur 2-4 times.
7. My change : ([^\s()<>.]+[.]?)+ and the corresponding group in original regex is [^\s()<>]+
Here I force '.' to occur only once at a time in the input text.
8. $1 This is needed to backreference a captured group which is needed to construct the anchor tag properly.
9. + means preceding expression can once or more, ? means preceding expression can occur 0 or 1 times, * means preceding expression can occur 0 or more times. These are called the quantifiers.
10. g and i in the end indicate the javascript syntax to match globally and in a case insensitive manner.
11. The second parameter of the replace function is the string that will replace the match found by the regex engine. We replace every url with an anchor tag pointing to that url.

On the nature of things (By Lucretius 94-55BC)

2008-07-01T11:57:00.000-07:00

Lovely it is, when the winds are churning up the waves on the great sea, to gaze out from the land on the great efforts of someone else; not because it's an enjoyable pleasure that somebody is in difficulties, but it's lovely to realize what troubles you are yourself spared..

A nice haiku from FightClub

2008-06-18T21:37:00.000-07:00

worker bees can leave
even drones can fly away
the queen is their slave
- Fight Club

Completeness in Incompleteness

2008-06-18T21:14:00.001-07:00

Everyday reminds me of my Incompleteness.
The more I try to complete it, the more incomplete it gets.
But I try and try and try,
Only to realize that the Incompleteness is just a part of my Completeness.

Forward Referencing

2008-06-10T09:23:00.000-07:00

The following notes are taken from Java Language Specification in reference to forward referencing of variables.

The declaration of a member needs to appear before it is used only if the member is an instance (respectively static) field of a class or interface C and all of the following conditions hold:
1. The usage occurs in an instance (respectively static) variable initializer of C
or in an instance (respectively static) initializer of C.
2. The usage is not on the left hand side of an assignment.
3. C is the innermost class or interface enclosing the usage.
Example where it needs to be taken care of

public class ForwardReference
{
int j = i;
int i = 10;
}
Here in this example all the above three conditions are met because i is used in the instance variable initializer, i is not on the left hand side of the assignment and the usage of i belongs to the ForwardRef which is the innermost class holding the variable i.

Examples where it need not be taken care of:

Example1:
public class ForwardRef
{
int j;

ForwardReference()
{
j = i;
}

int i = 5;
}

Here the usage is in the constructor and not in instance varialble initializer or instance initializer so the first rule is violated.

Example2:
public class ForwardReference
{
{
i = 9;
}
int i = 8;
}
Here second rule specified in JLS is violated, so we need not worry about it appearing before it is defined. We should be worried if i is used on the right hand side of the assignment.

Example3:
public class ForwardReference
{
class InnerForwardRef
{
int j = i;
}

int i = 5;
}
Here the usage of i is in a inner class so the third rule is violated, so the compiler will not create a problem for this.

Now we come to a very strange example where forward referencing is allowed..
public class X
{
private static int x = getValue();
private static int y = 5;

private static int getValue()
{
return y;
}
public static void main(String args [])
{
System.out.print(x);
}
}

The code above prints..zero which is quite weird in fact. Here the compiler is tricked making it think that it is a valid forward reference.

Daemon threads in Java

2008-05-26T10:36:00.000-07:00

Threads that work in the background to support the runtime environment are called daemon threads. For example, the clock handler thread, the idle thread, the screen updater thread, and the garbage collector thread are all daemon threads. The virtual machine exits whenever all non-daemon threads have completed.

public final void setDaemon(boolean isDaemon)
public final boolean isDaemon()

By default a thread you create is not a daemon thread. All the user applications are generally started off as non-daemon threads. However you can use the setDaemon(true) method to turn it into one.

Covariant return type

2008-05-22T09:05:00.000-07:00

A covariant return type means changing a method's return type when overriding it in a subclass. Covariant return types were allowed in the Java language since the release of JDK5.0. I will try to illustrate the use of covariant return type using the following example.

class A
{
public List test()
{
return null;
}
}
class B extends A
{
public ArrayList test()
{
return new ArrayList();
}
}
Here we can see that the return type of the method test() in subclass B is the subclass of the return type of method test() in the superclass A.

Contract between the subclass and superclass

2008-05-21T22:00:00.000-07:00

The following is an excerpt from the book 'The Java FAQ' .. "An API (application programming interface) establishes a contract of intent, not just of form or interpretation. To borrow terminology from linguistics and philosophy, an API contract involves both extension and intension: the boundaries of the current state of the world (extension) as well as the intended boundaries for other possible states of the world (intension: possible future implementations). In object-oriented programming, a common source of "possible future implementations" is subclassing from an existing class in an API.
A method defines a contract for any subclass method that would override it; it constrains possible implementations that a subclass could provide. In Java, the bare minimum contract for a method's inputs and outputs is the following:

* A method's parameter list is fixed; an overriding method in a subclass must declare precisely the same number and types of arguments.
* A method's return type is fixed; an overriding method in a subclass must declare precisely the same return type.
* The set of checked exceptions a method can throw (the method's declared exception classes and all their subclasses) establishes an upper bound. An overriding method in a subclass cannot throw any checked exceptions outside of that; it can, however, throw fewer exception types, or even none at all.

Note that the contract on exceptions concerns only checked exceptions; errors and runtime exceptions (that is, Error, RuntimeException, and their subclasses) are always permitted.
If a method, such as Object's toString method, is declared as throwing no checked exceptions, any overriding method you define must live within those bounds. You cannot define your own subclass of Exception and have your toString method throw that. In such a case, if you really need some exception to be thrown, you can resort to a subclass of RuntimeException, which is not checked or constrained by the compiler."

This description basically covers all the rules that a subclass must follow when overriding a method from superclass.

What does a constructor do?

2008-05-20T11:40:00.000-07:00

The constructor helps initializing the state of the object. So initially the implicit or the defined no-argument constructor of the super class is called so that the parent gets initialized in a proper manner.

One more restriction that is being imposed when a constructor is being defined is that call to any explicit super class constructor must be the first statement of all the constructors. So this might sound like a weird restriction at first but this rule guarantees the parent object to be in a valid state before the child object gets operational. This would help in avoiding the situations like this :

class Date{
public Date(){ date = setDate... }
String date;
}

// what if?
class DateViewer extends Date{
public DateViewer(){
System.out.println("The Date: " + date);
super();
}
}

Another thing that must be kept in mind while dealing with the constructors is that once you define a non-default constructor with non-zero arguments then and there the implicit constructor's definition inserted is removed from the code. So now if you have two classes X and Y such that
class Y
{
Y(int x,int y)
{

}
}

class X extends Y
{

}

Now this will result in a compilation error in the class X..Because the JVM tries to call the super() method while initializing the child object but since there is not implicit constructor for the parent class, this results in a error. Also see this amusing thread on sun forum:

http://forum.java.sun.com/thread.jspa?threadID=731805&start=0&tstart=0

About null in Java

2008-05-13T19:05:00.000-07:00

In Java(tm), "null" is not a keyword, but a special literal of the null type. It can be cast to any reference type, but not to any primitive type such as int or boolean. The null literal doesn't necessarily have value zero. And it is impossible to cast to the null type or declare a variable of this type.

Implementation of a multithreaded singleton in Java

2008-05-09T23:25:00.000-07:00


package yn.graph;

/**
 * @author ny
 * 
 */
public class MultithreadedSingleton {
 private static final MultithreadedSingleton singleton = new MultithreadedSingleton();
 
 private MultithreadedSingleton() {
  synchronized (MultithreadedSingleton.class) {
   //initialize the variables   
  }
 }

 public static MultithreadedSingleton getSingleton() {
  return singleton;
 }

 private static class TestMultithreadedSingleton implements Runnable {
  @Override
  public void run() {
   MultithreadedSingleton sgt = getSingleton();
   System.out.println(sgt);
  }
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  new Thread(new TestMultithreadedSingleton()).start();
  new Thread(new TestMultithreadedSingleton()).start();
  new Thread(new TestMultithreadedSingleton()).start();
  new Thread(new TestMultithreadedSingleton()).start();
  new Thread(new TestMultithreadedSingleton()).start();
 }
}

Does Java pass by reference or pass by value?

2008-04-21T13:22:00.000-07:00

A compact answer to this question will be

"Java passes the reference of the object by value".
So what does it mean to pass the reference of the object by value.
It means that if an object is passed to a method, then the object itself can be altered but not its reference. Because the reference of the object is passed by value. For example consider a object O and let the reference of the object O be x. Now when you pass the object O to a method, the VM internally makes a copy of x, that means there is another reference y which points to the same location as x does.
But x >< y. Now this means whenever you pass a object to a method, the object has atleast two references. Thus objects in java can be altered by passing to a method but they cannot be swapped with another object or assigned to some other object or something like that.

Useful Firefox Addons

2008-04-03T16:13:00.000-07:00

Here I would like to mention some of the Addons to Firefox that I find very useful.
1. Many of the people would like to restore their browser session once they boot their personal computer. So that they need not open each and every tab once they start their browser. There are session restoring features in Firefox but they are not upto the mark. So the best session restoring addon according to me is Tab Mix Plus and it can be found at the Tab Mix Plus
2. For those who are into web development there are two addons that I wud like to suggest. The first and the most notable addon being firebug. This addon is available at the Firebug
This addon has a long list of features. But I would like to point out my favorite features. First being the inspect element feature that will enable you to see the html source of any element that you want to locate. For this you need to right click on the element and select the Inspect Element option. Now many people want to look at the contents of the response that has come back and also check whether the request made is proper or not. For this you need to select the Net tab of firebug and then inspect the contents of request and response. One can also view the contents of the XHRs that are being made. Viewing the contents of XHR is a pretty nifty feature of Firebug.
The second addon that is not very popular being Web Developer. This is at the Web Developer. The feature of this addon which is not present as it is in Fire Bug being the View Layout option. This option enables one to view the layout of the page properly. Fire Bug also has this option but not as sophisticated as Web Developer.
3. The third addon being the stumble upon addon which is my favorite addon. Now this addon not only allows you to stumble but also record any pages that you want to record. This is much more useful for me because I visit certain pages and I dont want to loose their pointer at any cost. So as soon as I find any page that needs to be stored I wud mark it as thumbs up. Then later in time I can retrieve the list of pages that I liked and I can easily search for the wanted pages. This addon however is present in the stumble upon home page from where one can obtain and install stumble upon add on.

I will be adding to this list as soon as I find any new and useful addons..

Precision Vs Recall

2008-04-01T22:07:00.000-07:00

In all the applications involving Information Retrieval one of the main concerns would be to balance Precision and Recall parameters. The general application involves a scenario where a query is submitted by the user and the documents that match the query in the corpus are retrieved using some information retrieval model. Well known information retrieval models include Vector Space model, Latent Semantic Indexing and several other Probabilistic models.

Precision refers to the ratio --> Number of relevant documents retrieved / Total number of retrieved documents.
Recall refers to the ratio --> Number of relevant documents retrieved / Total number of relevant documents.

Now one can observe that Recall will be 1 if one returns all the documents in the corpus but the whole application's performance will be in jeopardy if one returns all the documents in the corpus thus rendering the application useless. On the other extreme is when we return no documents, then the Precision is infinity. But even then the application is unusable because no documents are rendered to the user.
So the balance between precision and recall has to be established in the applications involving the Information Retrieval. Due to the ambiguities in the natural language many irrelevant documents are returned resulting in a text search applications with low precision. One of the main reasons that Google has established its ground as a giant is due to its Page rank algorithm which increases the precision a lot. So while developing the applications one can improve the performance by giving the proper weights to precision and recall as required by the specifications of a particular application.
For example there might be some applications where all the relevant documents need to be displayed irrespective of the total number of the retrieved documents. In this case one needs to give a high weight to the recall parameter while designing the search query. Commercial search engines require a high degree of precision because the number of web pages (each web page can be viewed as a document and the set of all web pages is the corpus) is in zillions. There are several measures like F1 measure in which precision and recall are evenly weighted.