Sleeping Threads: May 2013

Monday 27 May 2013

Expandable Treeview in HTML (without images).

A treeview presents a hierarchical view of information. Each item can have a number of subitems. An item can be expanded to reveal the subitems, and collapsed to hide them. The following figure gives an idea of what it actually looks like :

This kind of a treeview can be used in HTML reports to hierarchically categorize information in the way shown above. Most solutions for this, however, use external images for the plus/minus icons. This may not acceptable if the report has to be portable (as it would require that the icon file also be sent with the HTML report). So here we generate the above tree-view without using any extra image files, with the help of plain HTML elements, JavaScript and CSS.

The source code of the HTML document containing the treeview is shown below. An explanation of how this was achieved follows.


<html>
 <head>
  <style>
   .invisible
   {
    background-color: #E6E6E6;
    border: none;
    padding-bottom: 5;
   }
   li,ul
   {
    list-style-type: none;
   }
  </style>
  <script type="text/javascript">
   function toggle(id,v){
    if(v.value=="+")
     v.value="-";
    else
     v.value="+";
    var e=document.getElementById(id);
    if(e.style.display=='')
     e.style.display='none';
    else
     e.style.display='';
   }
  </script>
 </head>
 <body>
  <ul>
   <li><!- (+ item)->
    <input id="item1" class="invisible" type="button" onclick="toggle('content1',this)" value="+" style="width:20px;height:20px;"/>
    <label for"item1"> item 1 (nested item)</label>
    <div id="content1" style="display:none">
    <ul>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.1</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.2</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.3</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.4</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.5</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.6</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.7</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 1.8</li>
    </ul>
    </div>
   </li>
   <li><!- (normal item) ->
         
    item 2 (nomal item)
    
   </li>
   <li><!- (+ item)->
    <input id="item3" class="invisible" type="button" onclick="toggle('content3',this)" value="+" style="width:20px;height:20px;"/>
    <label for"item3"> item 3</label>
    <div id="content3" style="display:none">
    <ul>
     <li>     item 3.1</li>
     <li>
      <input id="item3.2" class="invisible" type="button" onclick="toggle('content3.2',this)" value="+" style="width:20px;height:20px;"/>
      <label for"item3.2">item 3.2</label>
      <div id="content3.2" style="display:none">
      <ul>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.1</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.2</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.3</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.4</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.5</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.2.6</li> 
      </ul>
     </li>
     <li>
      <input id="item3.3" class="invisible" type="button" onclick="toggle('content3.3',this)" value="+" style="width:20px;height:20px;"/>
      <label for"item3.3">item 3.3</label>
      <div id="content3.3" style="display:none">
      <ul>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.1</li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.2</li>
       <li>
        <input id="item3.3.3" class="invisible" type="button" onclick="toggle('content3.3.3',this)" value="+" style="width:20px;height:20px;"/>
        <label for"item3.3.3">item 3.3.3</label>
        <div id="content3.3.3" style="display:none">
        <ul>
         <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.3.1</li>
         <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.3.2</li>
         <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.3.3</li> 
        </ul>
       </li>
       <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3.6</li> 
      </ul>
     </li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 3.3</li>
    </div>
   </li>
   <li><!- (+ item)->
    <input id="item4" class="invisible" type="button" onclick="toggle('content4',this)" value="+" style="width:20px;height:20px;"/>
    <label for"item4"> item 4</label>
    <div id="content4" style="display:none">
    <ul>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 4.1</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 4.2</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 4.3</li>
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item 4.4</li>
    </ul>
    </div>
   </li>
  </ul>
 </body>
</html>

Explanation :

The List :
We can visualize each subtree as a separate list. We can thus use the HTML list <ul> to display the subtree. This <ul> will contain all the items in this subtree as list iems <li>. If any of the list items itself is a subtree we can include another <ul> inside the <li> elements. To hide the bullets that accompany the list we use the CSS property "list-style-type: none".

The Icons :
For the expandable icon, since we cannot use external image file for the icons, we shall make use of HTML elements. We use a Button in this case. For making it look less like a button and more like an expandable icon, we remove the border and change the background color of the button. We also set the text of the button to a '+' to make it look like an expandable icon. On clicking the button the text will change to '-' and the subtree will become visible.

The hidden <div> tags :
To display/hide the subtree we can use div tags with their style set to "display:none". On clicking the '+' icon we shall change this style attribute to the default(i.e. empty), which will make it visible once again.

The Javascript :
We shall use Javascript to hide/display the subtree. The following javascript function will take care of this. The function takes two arguments, the contained div tag and the button itself. In the function we check the text of the button from a '+' to a '-' for expanding and vice-versa for hiding the contents. Also we change the style attribute of the div tags from 'none' to empty (i.e. ' ') and for making it visible or vice-versa for hiding it.

function toggle(id,v){
    if(v.value=="+")
        v.value="-";
    else
        v.value="+";
    var e=document.getElementById(id);
    if(e.style.display=='')
        e.style.display='none';
    else
 e.style.display='';
}

Friday 3 May 2013

The Power of Recursion

“To iterate is human, to recurse divine”. Recursion is indeed a powerful technique capable of simplifying various complex programming tasks. Perhaps one of the best known examples of this is the Towers of Hanoi Problem. In short the problem consists of three towers and disks of various sizes. These disks are stacked on one tower (smallest on top) and are to be moved to another tower using the third tower as auxiliary. Two rules that must be observed are a) only the top disk can be moved from any tower at a time and b) a larger disk cannot be placed on top of a smaller one. The task of writing an algorithm that will get us the set of moves that must be performed for moving n disks in the way defined above is not an easy one. However using recursion it can be hugely simplified. But before writing a recursive solution to the problem lets delve further into what recursion is and how it can be used to solve simpler problems.

Recursion is the process of defining a problem in terms of itself. To understand this, consider the following situation. Suppose we need to find the factorial of a number say 3. Now 3! can be written as 3! = 3 X 2!. In general we can write n! as n! = n X (n-1)!. So we have represented the problem in terms of itself. Thus if we can compute (n-1)! then we can also find n! with just a single multiplication. Also we must consider a base case. This base case is where the problem must terminate. For the factorial example the base case would be 0! which is equal to 1. 0! factorial is chosen as the base case because this is the least number whose factorial can be calculated. Now, for the implementation part, we can make use of a function which calls itself (recursion). Note that since here we have a function that solves a problem by calling itself, we have in fact represented the problem in terms of itself i.e. we have represented the problem as:

factorial(n)=n * factorial(n-1) .

A recursive function (function that calls itself) to accomplish the above task is shown below :

int factorial(int n){
     if(n==0) return 1;//The base case
     else return n*factorial(n-1);//The recursion
}

The following figure explains the working :

Each box represents a call to a function and the first line in each box shows the value with which it is called. Each call to the function will return a value indicated by the number beside the red arrow. The rest is self-explanatory.

So, we were able to write a recursive solution to the factorial problem once we had figured out two crucial things

1. The base case: the case where the recursion will terminate. (n = 0 in the above case).
2. How the function represented in terms of itself. (factorial ( n ) = n * factorial (n -1 ) ).

The above technique can be used to approach a recursive problem. Now consider another problem, finding the nth Fibonacci number. Fibonacci numbers start with 0 , 1 , . . . and each successive no is the sum of the previous two. The Fibonacci series thus goes like 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 . . . and so on. So for finding the nth Fibonacci number we can just sum the previous two. We can represent this as fib(n) = fib(n-1) + fib(n-2), where fib(int n) is a function that finds the nth Fibonacci number. Here the first two numbers remain constant so they constitute the base cases which are Fib(1)=0 & Fib(2)=1, representing the fact that the first Fibonacci number is 0 and the second Fibonacci number is 1. A recusive function for this can be written as :

int fib(int n){
     if(n==1) return 0 ; //Base case #1         
     else if(n==2) return 1 ; //Base case #2
     else return fib(n-1) + fib(n-2) ; // The recursion 
}

Note that in both of the above problems we were never concerned with the actual theme of the problem (finding factorial of a number or finding the nth Fibonacci number). We assumed that a function would do that for us and just represented the problem in terms of itself and wrote a straightforward algorithm for it. The rest recursion did for us automatically. Such is the power of recursion.

So to sum up, the idea behind recursion is that a problem can be solved by breaking it up into smaller pieces, solving each of those smaller pieces by breaking them up into even smaller pieces and so on till we reach a piece that can be solved non trivially(the base case).

For the above two cases simpler iterative solutions are possible and perhaps more efficeitn, but for certain complex problems it is easier to write a recursive solution than an iterative one. The Towers of Hanoi problem illustrates this fact.

Let us first state the Towers of Hanoi problem formally:

The problem consists of three pegs/towers and a number of disks of varying sizes which can be slid onto any peg/tower. Each disk is of a different size. Initially the disks are stacked on one of the towers (lets call it A) one atop another with the smallest one at the top. The goal is to move all disks from tower A to another tower (lets call this C), using the third tower (B) as auxiliary while obeying the following rules:

1. Only the top disk can be moved from a tower at any time.

2. No disk must be placed on top of a smaller disk.

Let us consider a recursive strategy for moving n disks.

Step 1 : Move n-1 disks from Tower A to Tower B

Step 2 : Move 1 disk from Tower A to Tower C

Step 3 : Move n-1 disks from Tower B to Tower C

This would solve the problem. (Note that here we are not concerned with how we would move the n-1 disks. The steps are shown visually in the figures below :

The base case here would be that of a single disk which we can move directly from Tower A to Tower C. The towers are named A, B, C where B is the auxiliary tower. The recursive solution is shown below :

public void move( int numberofdisks, char firstTower, char auxTower, char finalTower )
{
     if(numberofdisks == 1){
          System.out.println("Move disk from "+firstTower+" to "+finalTower);  //#0
     }
     else{
          move(numberofdisks-1,firstTower,finalTower,auxTower);   //#1
          System.out.println("Move disk from "+firstTower+" to "+finalTower);  //#2
          move(numberofdisks-1,auxTower,firstTower,finalTower);  //#3
     }
}

Explanation :

#0 : This illustrates the base case where a single disk can be moved from the first to the final tower directly.

#1 : This is Step 1 of the solution. Here we move n-1 disks from firstTower to auxTower using the finalTower as auxiliary. Note that in the function prototype auxiliary tower is denoted as the third parameter (first is the no. of disks), so here we had to use finalTower as auxiliary(third parameter) in the actual function call.

#2 : This is Step 2 of the solution.

#3 : This is Step 3 of the solution. Here we move n-1 disks from auxTower to finalTower using firstTower the as auxiliary. So here we had to use firstTower as auxiliary(third parameter) in the actual function call.

For 3 disks the above program the function call move(3, ‘A’, ’B’, ’C’) displays the following steps :

Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C

“Move disk” obviously means moving the top disk from the tower.

This above solution clearly demonstrates how easily recursion can be used to solve such complex problems. The use of recursion in an algorithm, however, has both advantages and disadvantages. The main advantage is usually simplicity. (for solving certain problems like the Towers of Hanoi, preorder/inorder/postorder traversal of binary trees etc.). Also some problems like displaying a list of all files of the system cannot be solved without recursion. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large.

Recursive techniques are also widely used to implement important algorithms based on the Divide & Conquer approach like quicksort and merge sort as well as graph based algorithms like Depth First Search.