Thursday, May 26, 2011

An attempt towards Code Optimization


Often I read many code optimization techniques, but when it comes to applying them practically, it requires practice and strict adherence to a set of coding standards and making it a habit.
In order to see the difference myself before and after applying optimizations, i tried a simple example of merging two sorted arrays into one sorted array

The initial algorithm that pictured in my mind is as follows:

void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
            int k = 0, j = 0;
            for(int i = 0; i < array_ALength; )
            {
                        for(; j < array_BLength;)
                        {
                                    if(i < array_ALength && array_A[i] <= array_B[j])
                                    {
                                                resultArray[k] = array_A[i];
                                                k++; i++;
                                    }
                                    else
                                    {
                                                resultArray[k] = array_B[j];
                                                k++; j++;
                                    }
                        }
                        if(i < array_ALength)
                        {
                                    resultArray[k] = array_A[i];
                                k++; i++;
                        }
            }          
}

Since there were two arrays, I used two ‘for’ loops. Then compare the corresponding value of each array and add the smallest to the result array and increment the pointer of result array and the array from which it is copied. The above algorithm is tested and seems to work as expected.


Lets compute the complexity of the algorithm. Looking at the two ‘for’ loops, one within another, will give an impression of time complexity of O(n*n), but a detailed observation says otherwise. The inner for loop is executed until all the elements in array_B is copied to result array (‘array_BLength’ number of elements). At the same time some of the elements in array_A may also be copied. Lets say ‘x’ elements copied (where x <= array_ALength, and array_ALength being the total number of elements). The outer ‘for loop’ copies any of the left over elements from array_A to the resultArray (array_ALength – x elements are copied). 

Total complexity = array_BLength + x + array_ALength – x = array_ALength + array_BLength (sum of the number of elements in both arrays) = O(n)


Observing the above complexity,

1)    we can eliminate the need for two ‘for loops’ and can merge all into one loop.
2)    The code looks messy because of the presence of loop index incrementing code. This can be eliminated by post-incrementing the loop counter, while coping the elements to the result array.

The resulting algorithm after applying the above two optimizations is as follows.

void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
            int k = 0;
            for(int i = 0, j = 0; i < array_ALength, j < array_BLength; )
            {

                        if(i < array_ALength && array_A[i] <= array_B[j])
                        {
                                    resultArray[k++] = array_A[i++];
                        }
                        else
                        {
                                    resultArray[k++] = array_B[j++];
                        }

                        if(i < array_ALength && j >= array_BLength)
                        {
                                    resultArray[k++] = array_A[i++];
                        }
            }          
}

A further review shows the above algorithm can still be optimized.
3)    The two ‘if’ conditions are essentially doing the same job and they can be merged into one.


The final algorithm:

void MergeArrays(int* array_A, int* array_B, int* resultArray, int array_ALength, int array_BLength)
{
       int resPtr = 0;
       for(int i = 0, j = 0; (i < array_ALength || j < array_BLength); )
       {

              if(i < array_ALength && (array_A[i] <= array_B[j] || j >= array_BLength))
              {
                     resultArray[resPtr++] = array_A[i++];
              }
              else
              {
                     if(j < array_BLength)
                           resultArray[resPtr++] = array_B[j++];
              }
       }   
}

With the above examples, I am with the opinion that, along with standard methods of optimizations, understanding and estimating the complexity of the algorithm help us write better code, making small tweaks helps to reduce the length of code and reviewing code will help us get rid of redundant code either by merging or making it a function.

In the beginning stages as a programmer it’s important to review as much code as possible and making it a habit. Obviously the final product will be more reliable and reduces the support and maintenance cost.

Saturday, April 9, 2011

Determine if HTML5 Canvas is Empty or has Data

Over the past week I have been working on the problem of identifying if an HTML5 canvas is empty or not. That is to determine if something is written or not on the canvas.

To begin with, I searched if there are any existing solutions and found one which suggests to check every pixel with in the canvas area. Of course this could be a solution, but I was looking for some thing that suits my case better. I am working on a web application having several forms where canvas is used to take signatures either using a stylus/ mouse (as in touch screen laptops) or with finger touch (Iphone/ IPad) events. Also each web page may have up to four canvas boxes. So the method of checking each pixel could increase the processing time for each web page.

Also i was more inclined towards a solution using the properties of canvas or the programming language (in this case ASP .Net) and with less inclination towards the old school method of checking each pixel. One such property is the 'toDataURL', which retrieves the canvas data in string format. This string data can be converted as a byte array and there by we can get the size of the image. But the size of the byte array is not zero, even when the canvas is empty. When the canvas is empty, the default header information adds up to some size. Adding to this problem is the size of this default header is different in different browsers like safari, chrome, opera and firefox.

Initially i thought of checking the default size for each browser and use it to determine if the canvas is empty, but later found that this header size changes for different sizes of canvas and it may change in the later versions of the browsers. Still as of today, all the browsers are yet to comply to all the set standards of HTML5.

Finally, i came up with a solution where the emptiness of the canvas is determined dynamically, by comparing the size of the canvas before writing (during the page-load event) and after writing (when form 'submit' button is pressed). The data-URL of the canvas is retrieved and stored when the canvas is empty (during the page load event) and the data-URL of the canvas is retrieved again when the page is submitted. By checking the difference between the two data-URLs we can determine the status of the canvas.

The sample code below, explains the implementation.


HTML Part:
<canvas id=”canvasLayout” width=”400” height=”200” />
<asp:HiddenField ID=”emptyCanvas” runat=”server” />       // to store the value of the empty canvas
<asp:HiddenField ID=”dataCanvas” runat=”server” />        // to store the value of canvas at page submit along with any data.

JavaScript Part:
During the page-load event the java-script’s ‘window.onload’ is executed by default. In the 'onload' event the size of the empty canvas data is captured. The function 'SaveImage' is triggered when the form/page is submitted. 

<script type="text/javascript">

function getImageURL(element) {
    var canvasElement = document.getElementById(element);
    var imageDataUrl = canvasElement.toDataURL("image/png");
    return imageDataUrl;
}

window.onload = function(){
var tempEmptyCanvas = document.getElementById(‘’);
                  tempEmptyCanvas.value = getImageURL(“canvasLayout”);
}


function SaveImage(){
       var tempDataCanvas = document.getElementById(‘’);
       tempDataCanvas.value = getImageURL(“canvasLayout”);
}

script>

Server Side:

On the server side, the values in the two hidden fields are retrieved and their sizes are computed. If the difference between their sizes is 0, then the canvas is empty, else there is some data on canvas.
        protected void Page_Load(object sender, EventArgs e)
        {
            if (!IsPostBack)
            {
            }
            String emptyCanvasValue = emptyCanvas.Value;
            String dataCanvasValue = dataCanvas.Value;

            byte[] whenEmpty = Convert.FromBase64String(emptyCanvasValue);
            byte[] whenNotEmpty = Convert.FromBase64String(dataCanvasValue);

            int checkCanvasDataSize = whenNotEmpty.Length – whenEmpty.Length;

            if(checkCanvasDataSize == 0)
            {
            //Canvas empty
            }
            else
            {
            //Canvas Not empty
            }
        }


Thus by using the canvas 'toDataURL' property and the page_load events, we could determine if the canvas is empty.

// to store the value of the empty canvas
// to store the value of canvas at page submit along with any data.

JavaScript Part:

During the page-load event the java-script’s ‘window.onload’ is executed by default. In the 'onload' event the size of the empty canvas data is captured. The function 'SaveImage' is triggered when the form/page is submitted.



Server Side:

On the server side, the values in the two hidden fields are retrieved and their sizes are computed. If the difference between their sizes is 0, then the canvas is empty, else there is some data on canvas.

protected void Page_Load(object sender, EventArgs e)
{
if (!IsPostBack)
{
}

String emptyCanvasValue = emptyCanvas.Value;
String dataCanvasValue = dataCanvas.Value;

byte[] whenEmpty = Convert.FromBase64String(emptyCanvasValue);
byte[] whenNotEmpty = Convert.FromBase64String(dataCanvasValue);

int checkCanvasDataSize = whenNotEmpty.Length – whenEmpty.Length;

if(checkCanvasDataSize == 0)
{
//Canvas empty
}
else
{
//Canvas Not empty
}
}

Saturday, March 12, 2011

Drawing board/Scribbling Pad for Tablet PC’s and smart phones

My previous post on developing Drawing Board/ Scribbling pad with HTML5 Canvas, works only on browsers supporting HTML5 canvas and drawn with a mouse or a stylus. But with a growth in usage of the touch screen devices like the tablet PC’s and smart phones, it makes more sense when we are able to scribble with our hand.

The example in my previous post can be extended to support touch-screen devices by adding the touch events, similar to the existing mouse events. In this post we look into touch events.

The touch events are ‘ontouchstart’, ‘ontouchmove’ and ‘ontouchend’.

‘OnTouchStart’ Event:-

sigCanvas.ontouchstart = function (event) {
event.preventDefault(); // to get rid of the default touch screen scroll action
var sigContext = this.getContext('2d');
var pos = getTouchPositionInElement(this, event); //get touch position on to canvas
sigContext.beginPath();
sigContext.moveTo(pos.x, pos.y);
sigContext.lineTo(pos.x + 0.5, pos.y + 0.5); //puts a dot on screen
sigContext.stroke();
this.down = true;
}

‘OnTouchMove’ Event:-

sigCanvas.ontouchmove = function (event) {
event.preventDefault(); //to get rid of the default touch screen scroll action
if (this.down) {
var sigContext = sigCanvas.getContext('2d');
var pos = getTouchPositionInElement(this, event);
sigContext.lineTo(pos.x, pos.y);
sigContext.closePath();
sigContext.stroke();
sigContext.beginPath();
sigContext.moveTo(pos.x, pos.y)
}
}

‘OnTouchEnd’ Event:-

sigCanvas.onTouchEnd = function (event) {
event.preventDefault(); //to get rid of the default touch screen scroll action
if (this.down) {
var sigContext = sigCanvas.getContext('2d');
var pos = getTouchPositionInElement(this, event);
sigContext.lineTo(pos.x, pos.y);
sigContext.closePath();
sigContext.stroke();
this.down = false;
}
}

Determine the Touch position on the canvas:-

var getTouchPositionInElement = function (element, e) {
var elementPosition = getElementPosition(element); //get canvas position on screen
var touchPosition= getTouchPosition(e); //get touch position on screen
var x = touchPosition.x - elementPosition.x;
var y = touchPosition.y - elementPosition.y;
var position = new Array();
position['x'] = x;
position['y'] = y;
return position; //touch position relative to canvas
}


Determine the canvas position on the screen:-

var getElementPosition = function (element) {
var posX = element.offsetLeft;
var posY = element.offsetTop;
try {
while (element.offsetParent) {
posX += element.offsetParent.offsetLeft;
posY += element.offsetParent.offsetTop;
if (element == document.getElementsByTagName('body')[0]) {
break
}
else {
element = element.offsetParent;
}
}
}
catch (e) {
}
var dims = new Array(0);
dims['x'] = posX;
dims['y'] = posY;
return dims; //return the top left position (co-ordinates) of canvas
}

Determine the touch position on the screen:-

var getTouchPosition = function (e) {
var touch = e.changedTouches[0]; //retrieves figure touch co-ordinates on screen
var touchPosition = new Array();
touchPosition['x'] = touch.pageX;
touchPosition['y'] = touch.pageY;
return touchPosition;
}



When the final application (with both mouse and touch events) is accessed through a mouse/ stylus the ‘mouse events’ are triggered and when accessed on a touch screen device triggers the ‘touch events’.

Saturday, February 19, 2011

Drawing Board/ Scribbling Pad with HTML5 Canvas

Recently, I was assigned with a problem of implementing the cross browser signature functionality. Since there was a need to support some of the major browsers (IE, Safari, FF, Chrome, Opera) and different platforms, there was a need to identify any one feature that works on all browsers. Based on a lead given, I started looking at the canvas feature of HTML5.

But very soon realized Canvas is not supported in IE (or until IE version 8), but soon learnt it will be supported from IE9. Also there are libraries available like “Excanvas” with which the Canvas feature can be supported in earlier versions of IE, except for few limitations.

The signature pad is similar to a drawing board where we can scribble; hence the example below is a drawing application. The languages used are html5 and JavaScript. For the most part the code is self-explanatory and commented at places.

<html xmlns="http://www.w3.org/1999/xhtml">

<head runat="server">

<title>Canvas Drawing Boardtitle>

<style type="text/css">

.canvasborder {border: 2px solid black;}

style>

<script type="text/javascript" src="Scripts/jquery-1.4.1.js">script>

<script type="text/javascript">

var DrawingBlock = function (element) {

var DrawCanvas = document.getElementById(element); //

var DrawContext = DrawCanvas.getContext('2d');

DrawCanvas.down = false;

//Event is triggered when mouse button is pressed down on canvas

DrawCanvas.onmousedown = function (event) {

var pos = getMousePositionInElement(this, event); //retrieve the mouse position on canvas

DrawContext.beginPath();

DrawContext.moveTo(pos.x, pos.y);

DrawContext.lineTo(pos.x + 0.5, pos.y + 0.5); //put a dot, at the point of mouse down.

DrawCanvas.down = true; // true until the mouse button is pressed down.

}

//Event is triggered when pressed mouse button is released when on canvas

DrawCanvas.onmouseup = function (event) {

if (this.down) {

var pos = getMousePositionInElement(this, event);

DrawContext.lineTo(pos.x, pos.y);

DrawContext.closePath();

DrawContext.stroke();

this.down = false;

}

}

//Event is triggered when mouse is moved over canvas.

DrawCanvas.onmousemove = function (event) {

if (this.down) { //only if mouse button is held down

var pos = getMousePositionInElement(this, event);

DrawContext.lineTo(pos.x, pos.y);

DrawContext.closePath();

DrawContext.stroke();

DrawContext.beginPath();

DrawContext.moveTo(pos.x, pos.y)

}

}

//Return the canvas position on the document.

var getCanvasElementPosition = function (element) {

//Top left corner of the canvas is used as the

//reference to calculate the mouse position

var posX = element.offsetLeft;

var posY = element.offsetTop;

var canvasPos = new Array(0);

canvasPos['x'] = posX;

canvasPos['y'] = posY;

return canvasPos;

}

//Retrieve the mouse position on canvas

var getMousePositionInElement = function (element, event) {

var elementPosition = getCanvasElementPosition(element); //canvas position on the page

var mousePosition = getMousePosition(event); //mouse cordinates on the page.

var x = mousePosition.x - elementPosition.x;

var y = mousePosition.y - elementPosition.y;

var position = new Array(); //mouse position w.r.t canvas

position['x'] = x;

position['y'] = y;

return position;

}

//Retrieve the mouse co-ordinates in the document (web page)

var getMousePosition = function (event) {

var x = event.pageX;

var y = event.pageY;

var mouseposition = new Array();

mouseposition['x'] = x;

mouseposition['y'] = y;

return mouseposition;

}

//tracking the mouse-up event outside canvas (drawing board).

this.setMouseUpButton = function () {

DrawCanvas.down = false;

}

DrawCanvas.onselectstart = function () {

return false;

}

}

var drawingImage;

window.onload = function init() {

drawingImage = new DrawingBlock("DrawingCanvas"); //initialize the canvas element

}

//Event is triggered with mouse button is released in the document (web page).

$(document).mouseup(function (e) {

drawingImage.setMouseUpButton();

});

script>

head>

<body>

<tr>

<canvas id="DrawingCanvas" width="500" height="500" class="canvasborder">canvas>

tr>

<tr>

<td class="bold text">Drawing Boardtd>

tr>

body>

html>

The above code is tested in browsers like, IE 9 (Release Candidate), Safari, Firefox, Chrome and Opera on Windows and Mac platforms.