Some Bits in Few Pieces
Dictionary for WP - Approaches to String Lookup
Couple of months back I wrote a simple dictionary app for Windows Phone. The idea of the app was to make the list of words available offline so that we do not need a data connection to look up a definition.

There are few aspects that this app was designed around:
1) Words available locally
2) Show a list of matching words while typing
3) Show the definition instantly

Of these 1 and 3 was achieved easily using a hashtable of words, the value indexed to an offset in a huge file containing all the definitions. So as soon as we have a word, we look up the offset and seek to the definition in the large file. This happens almost instantly when the app is loaded on the phone.

The big problem was to solve 2. There was a list of over 87k words and to show a list of matching words, we have to search the list again after every keypress. Initially the app used a list of string for searching which worked well while running on the Phone Emulator but was extremely slow - up to 4 seconds for each keypress - while running on the phone. Below is the sequence of investigations that followed to improve the lookup performance.

1) Simple List - Lookup through direct sequential search
As mentioned the lookup is slow. But this has a benefit of having the least startup time as we can directly read all the strings into a list which was the fastest way to create the initial data structure.

The lookup took almost 3-4 seconds to get the list of matching words. As this was a sequential search, the matching words if present in the beginning of the list took comparativefly less time than the words towards end (so ab* loaded much faster than zy*).

Though this was the simplest way to store and had faster load times, the lookup responsiveness was simply unacceptable.

2) Trie - Lookup through DFS
Trie is a specialized tree data structure used specially for this kind of scenario with very quick string prefix matches, in constant time. List of all matching words with a given prefix can be generated by doing a depth first iteration over the node matching the prefix.

This was a great structure for prefix matches and perfect fit for the app scenario. The string searches were almost instant for words with 3 or more character but for less than 3 characters the number of words was so large that the depth first search took very very long, surprisingly even longer than the sequential searches.

The longer time spent for shorter words needed some improvement.

3) Trie & Sorted List - Search in Trie with Indexed Lookup in List
The original Trie was modified to store now two integers. One represented an index into the Sorted List with first matching substring, the second represented the count of words that actually matched that prefix. So to list all strings matching a prefix, we go to the location in the list using the index and iterate using the count.

This has great performance for lookup for all strings of any length and works amazingly well on the phone too. But this structure takes time to create, as we are doing a count of all matching substrings, the structure was created offline and exported to a file and read into the app.

The act of storing the structure in the file was the great drawback. The exported trie itself was almost 7MB in size (compared to rest of the app which was just 6MB) and the time taken to read and recreate the structure in the app was very long. The app startup took almost 12 seconds and in many cases it didn't start at all as WP throttles any app which takes near to 15 seconds to start.

I also did an iteration to load the structure in the background so that the ui thread doesn't get blocked and the app loads correctly. The structure was ready to use a few seconds after load and searches after that worked well without glitch. But the limited usability studies that I did (with my wife) clearly gave an indication that waiting for a few seconds after the app was loaded was not possible, as the primary intent of users is to quickly lookup a word instead of looking around the app then try to lookup.

I did couple more iteration by trying to store the structure differently - using BinaryWriter for serialized objects, XML output, custom string serialization - but each of them had the same result, loading the structure into the app took very long.

4) Character Indexed Array of Arrays
Though this sounds like a super specialized data structure, this was a collection of 26 arrays each representing a character from the alphabet. The arrays were created while loading the list of strings using first character of the string as index and the strings were stored in their respective array. For lookup the correct array was picked by the first character entered and a sequential search was done to generate the list of strings matching the prefixes.

The creation of the structure took almost same time as a single list. The look up was way faster than that of a single list. Though it was not almost instant as the case was with trie, it was near to half a second. Compared to a single list, this was a great improvement.

I came down to this structure taking the cue from the first single list, that the searches for strings early in the list were faster than those which were towards the end. So by reducing the number of strings to match, we decreased the surface area for search and thereby searches are now way faster than a single list.


For a full fledged computer system I'd have chosen option 3 but limited processing power and space for an app on a phone made it a non-ideal choice. Eventually the app was shipped with option 4, which given the circumstances, was the perfect solution that can work with acceptable User Experience.


Trie: http://en.wikipedia.org/wiki/Trie
Radix Tree: http://en.wikipedia.org/wiki/Radix_tree

The App: http://www.windowsphone.com/apps/8f4c22ee-a3bb-4236-9e12-3cb2c2637f42
 
Print "Hello World" in Java
public class HelloWorld
{
public static void main(String args[])
{
System.out.println("Hello World");
}
}


Pretty Simple. Rite!! Well.. yeah. So whats the catch?

Can we do it without the main function??

How could we? Thats not possible. The execution begins from the main function only, how can anything be executed before that?

If you think this way, you are absolutely correct. Till 5 minutes ago i too was correct in the same way. But then came Static Blocks. Check this out -

public class HelloWorldNoMain
{
static
{
System.out.println("Hello World!!!");
System.exit(0);
}
}


It does work. It prints Hello World!!!. The exclamation marks do signify the amusement that i felt. :)

Static blocks are a facility provided in java language for executing some statements before our application starts executing from the main.

Ideally these blocks are used for initializing static variables. We can do the bulk initialisation in here, to reduce the code size and complexity. But in addition to this sort of simple initialisation, the code can attain any complexity.

To Quote from http://www.developer.com -

"A static initializer block resembles a method with no name, no arguments, and no return type. It doesn't need a name, because there is no need to refer to it from outside the class definition. The code in a static initializer block is executed by the virtual machine when the class is loaded.

Like a constructor, a static initializer block cannot contain a return statement. Therefore, it doesn't need to specify a return type.

Because it is executed automatically when the class is loaded, parameters don't make any sense, so a static initializer block doesn't have an argument list."

Syntax -

Simple as ABC, jus include whatever code you want inside a static block.

static {
...
}


And all the code would be executed as such before the main is called.

Cheers :)
Dynamic JavaScript
Ever wonderd, how can you hide the JavaScript from the user?? Or is there a way that you can run dynamic JS code on the client. Well, there is a way, where you can hide the script from getting viewed in the source and getting saved in the cache files on the client.

What we need to do is, append a new script, dynamically generated, to the document. And set its content to what we recieve from the server by making a server call. Here is how we do. Though for demo, i am not making any AJAX call, you can easily replace the string with the response from server.

Step 1: Get the script text, and initialize it to a variable.
var ScriptText = "function ExecuteDynamicScript() { alert('This is Dynamic Script'); }"

Step 2: Create a new script element.
var ScriptObj = document.createElement('script');
ScriptObj.type = 'text/javascript';


Step 3: Append the script code to script object and attach it to DOM.
ScriptObj.text = ScriptText;
document.getElementsByTagName('head')[0].appendChild(scriptObj);


Here is an example. Try clicking "Execute Dynamic Script" before "Load Script" it should give a script error. Now try it after clicking "Load Script" it should work :)







Here is the Full Code to make this work -
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<script type="text/javascript">
function loadScript()
{
var ScriptText = "function ExecuteDynamicScript() { alert('This is Dynamic Script'); }";
var scriptObj = document.createElement('script');
scriptObj.type = 'text/javascript';
scriptObj.text = ScriptText;
document.getElementsByTagName('head')[0].appendChild(scriptObj);
}
</script>
</head>
<body>
<center>
<input type="button" onclick="loadScript();" value="Load Script"/>
<input type="button" onclick="ExecuteDynamicScript();" value="Execute Dynamic Script" />
</center>
</body>
</html>


PS: You see, this can only help you not show in the browser, as in, when the user does the view source or checks for browser cache it wont show up. But still there are ways to get the dynamic text, by reading the DOM currently present in the browser, and say by snooping in on whatever is coming from the browser.

PPS: But then a normal user is not so inclined to do that, so you can rest assured that it remains safe from more than 60% of the users.

PPS II: Cheers :)
In Place Text Editing
With the advent of Ajax we have seen use of quite a few editing of text in-place. This in-place thing is leveraged to a great extent by Flickr (http://www.flickr.com/).

I give an example of how we can do the same thing with little of coding. It just requires a few CSS Style attributes used along with Javascript.
This in place is a Client only without any server postback with Ajax. For including the Ajax functionality, we can jus make an extra function call to send the edited text to the server, in the onclick event of the Save button.
Here is the example:


Here is the code that makes this live:

<div id="inplace">
<input type="text" value="In place edit"
oldvalue="" id="inplacetext"
style="border: none;
font-family: Tahoma; font-size: 10pt;
font-weight: bold;
background-color: #FAFAFA;
color: #336699;"
onmouseover="this.style.backgroundColor='#EEEEEE';" onmouseout="this.style.backgroundColor='#FAFAFA';"
onfocus="document.getElementById('ipbuttons').style.display='block'; this.oldvalue=this.value; this.style.border='solid #333333 1px';" />

<div id="ipbuttons" style="display: none; margin-top: 10px;">
<input type="button" value="Save"
onclick="
document.getElementById('inplacetext').oldvalue=document.getElementById('inplacetext').value;
document.getElementById('inplacetext').blur();
document.getElementById('inplacetext').style.border='none';
document.getElementById('ipbuttons').style.display='none';" />

<input type="button" value="Cancel"
onclick="
document.getElementById('inplacetext').value=document.getElementById('inplacetext').oldvalue;
document.getElementById('inplacetext').blur();
document.getElementById('inplacetext').style.border='none';
document.getElementById('ipbuttons').style.display='none';" />

</div>
</div>

Have Fun :)
Uniform Web Layout & Sizes
Well, one of my friends today wanted to keep the layout and the appearance of his webpage uniform over different screen resolutions. Since the apparent size of the font and the images changes with the screen resolution he wanted to keep them constant.

The obvious solution was to somehow zoom in or out the content. IE provides a zooming javascript call that can be used to zoom in/out any webpage. If you are using IE, try the links below:

Zoom In | Zoom Out | Original

To use this, we need to determine specific amount for the zoom for each resolution and then, when the page loads, we do the trick and zoom the page appropriately.

<script>
var z_1024_768 = 0.8;
var z_1280_1024 = 0.0;

var zoom_value = 0.0;
function CheckResolution()
{
var width = window.screen.width;
var height = window.screen.height;
if(width == 1024 && height == 768)
zoom_value = z_1024_768;
else if(width == 1280 && height == 1024)
zoom_value = z_1280_1024;

zoomDoc();
}

function zoomDoc()
{
window.parent.document.body.style.zoom = zoom_value;
}
</script>


Add the above script in the head of the html document and add this onload handler to the body.

<body onload="CheckResolution();">

This would take care of the screen resolution and zoom in or out the document to give a uniform width. (The zoom values are randomly chosen, you would like to check the exact value that gives the similar layout to the document).

But this approach has a drawback, since the zooming is done based on the bitmap output displayed in the web-browser, it introduces some distortion.

So is there a way out of this?
Yes there is :) Using styles.

We define 2 style sheets with the same CSS classes and appropriate widths/heights/font sizes of various elements, and in the CheckResolution() function we attach the appropriate style sheet to the document. This is how we do it:

Step 1: Link a stylesheet to the current document and leave the href empty.

<link rel="stylesheet" href="" />

Step 2: Include the javascript in the head.

<script>
var css_1024_768 = "style_1024_768.css";
var css_1280_1024 = "style_1280_1024.css";

var stylesheet = "";
function CheckResolution()
{
var width = window.screen.width;
var height = window.screen.height;
if(width == 1024 && height == 768)
stylesheet = css_1024_768;
else if(width == 1280 && height == 1024)
stylesheet = css_1280_1024;

setDocStyle();
}

function setDocStyle()
{
document.styleSheets[0].href = stylesheet;
}
<script>


Step 3: Add onload handler in body

<body onload="CheckResolution();">

And its all done. :)
Transluscent Images
Well, we have an IE specific way of doing this. Those pro FF can skip this. But when used with nice effects it works wonders and gets us rid of multiple images to make a fading menu by use of only a few lines of Javascript code.




How to get this:

1. Add the image as you do and specify the filter property in the styles.
2. Set the onmouseover and onmouseout event to alter the filter


<img src="some-image.gif" style="filter: alpha(opacity=20);"
onmouseover="this.filters.alpha.opacity = 100;" onmouseout="this.filters.alpha.opacity = 20;" />


And all's done. :)

We can add some javascript call instead of setting the opacity directly which would reduce the opacity gradually making a fading effect. Clean and Simple.
Javascript Show/Hide
There have been lots of posts about this thing, still i felt like i should add one to it, so here it is :)

With the improvements in CSS styles, the Javascript programmers have found ways to do wonders to the webpages and make the content more intuitive to the end user.

One of them is to show a one line heading for some content, and display the content only when the user is further interested into it. This helps in removing the clutter from the webpage, keeps the layout clean, and increases readability. Moreover it makes the user to be more interactive with the web app.

Moreover with the advent of Ajax, the content has not to be loaded into the webpage, it can be dynamically loaded into the website and hence reducing the overall load time of the webpage and improving responsiveness.

The key lies in the display property of any html object. This property denotes if the content be displayed on the webpage or not. We specify the property as:

style="display: none;"

Code Listing

PS: The show hide effect in this webpage is not achieved in the same way, since Blogger didn't allow me to include <script> tags in the blog text.
Blog.Init(Work.Bits);
So here finally, I am with my new blog where in i plan to put the bits from the other half of my life ;)

To cut the story short, I am kicking off this with a simple yet amusing problem that i gave to my friends.

Question:

Given a class:

class ClassWithPrivateConstructor
{
private ClassWithPrivateConstructor() {}

public string toString() { return "Class With Private Constructor"; }
}

Give a method to create the object of the above class. Write the code for the class 'PrivateAccessor' that would create the object of this class, and then call the 'toString' method to print the name of the class.

Solution:

import java.lang.reflect.*;

class ClassWithPrivateConstructor
{
private ClassWithPrivateConstructor() { }

public String toString() { return "Class with Private Constructor"; }
}


class PrivateAccessor
{
public PrivateAccessor()
{
try
{
Class cls = Class.forName("ClassWithPrivateConstructor");
Constructor constructor = cls.getDeclaredConstructors()[0];
constructor.setAccessible(true);

ClassWithPrivateConstructor pc = (ClassWithPrivateConstructor)constructor.newInstance(new Object[0]);
System.out.println(pc);
}
catch (Throwable e)
{
System.err.println(e);
}
}

public static void main(String args[])
{
new PrivateAccessor();
}
}


Explanation:

The key here is the "setAccessible()" method defined in the Constructor Class. We can use Reflection and call this method on the constructor that has private access specifier to make it accessible from code outside the class. And hence allows us to create the object of the class.

The same functionality is also available with C#, in the same way we can use Reflection there to set the access and create the objects.