Implementation of undirected graph in java

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

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

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

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

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)

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

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