August 13, 2017

HTML5 - Display Arrows for Array Items on Canvas

I see this question titled as How to Display Data on Canvas? on StackOverFlow site. I found this interesting and dedicated some time to work on this requirement. In this post I will explain how did I achieve to draw arrows among array items' positions before and after sorting. Lets start with the same example as posted in this question.

We have the following array along-with the sorting function, this is the original code posted in that question:

	var selectionSort = function(arr) {
		var j,i;
		var smallest;
		for(j = 0; j < arr.length ; j++)
		{
			smallest = j;
			for(i = j + 1; i < arr.length ; i++)
			{
				if(arr[i] < arr[smallest])
			{
				smallest = i;
			}
			}
		var temp;
		arr[temp] = arr[smallest];
		arr[smallest] = arr[j];
		arr[j] = arr[temp];
	}
	return arr;
	};

	var array = [6,5,4,3,2,1];
	
	array2 = selectionSort(array.slice()).slice();

At this point, we have two arrays, array is the original unsorted array and array2 is the final sorted one. And we want to display both arrays on screen with drawing arrows to show the possible movement of items in positions inside the array.

Let first setup our UI to have canvas containers where we want to display array, here is the HTML I used for this example:

	<body>

		<div id="myocontainer" style="width:70%;margin-left:100px;">
			<div style="width:300px;float: left;">
				<h2>Origianl Array</h2>
				<hr/>
				<h4 style="float:left; margin-left:50px;margin-top:5px;"><u>Index</u></h4>
				<h4 style="float:left; margin-left:40px;margin-top:5px;"><u>Value</u></h4>
				<canvas id="cnvTable1" width="100%" height="100%"></canvas>
			</div>
			<div style="width:300px;float:left; margin-left:300px;">
				<h2>Sorted Array</h2>
				<hr/>
				<h4 style="float:left; margin-left:50px;margin-top:5px;"><u>Index</u></h4>
				<h4 style="float:left; margin-left:40px;margin-top:5px;"><u>Value</u></h4>
				<canvas id="cnvTable2"></canvas>
			</div>
		</div>
		
	</body>

To make things simpler I created a class ArrayItem to represent array items by maintaining their index, value and with two helper functions getPosX, getPosY. getPosX, getPosY respectively describes the postion of items being drawn on canvas for that particular item. Here is the code for this class:

	function ArrayItem(indx, val) {
	  this.index = indx;
	  this.value = val;
	  
	  this.getPosX = function() {
		return 50;
	  };
	  
	  this.getPosY = function() {
		return this.index * 50;
	  };
	}

Since we are drawing objects on screen, in order to have better dispaly on screen I have hardcoded values for postionX and relative value for positionY.

Next part is to create temp array of ArrayItem objects for both array and array2.

	var array1Items = [];
	$.each(array, function( index, value ) {
		array1Items.push(new ArrayItem(index, value));
	});
	
	var array2Items = [];
	$.each(array2, function( index, value ) {
		array2Items.push(new ArrayItem(index, value));
	});

Now comes the tricky part how to display array items on canvas. I write this printArray() function to display items on canvas.

	function printArray(arr1, canvasID, offsetX, offsetY)
	{
		var c = document.getElementById(canvasID);
		var ctx = c.getContext("2d");
		c.width  = 800;
		c.height = 1000;

		ctx.font="30px Georgia";
		var tempX = 50;
		var tempY = 50;
		
		$.each(arr1, function( index, value ) {
			tempX = value.getPosX() + offsetX;
			tempY = value.getPosY() + offsetY;
			
			ctx.fillText(index, tempX, tempY);
			ctx.fillText(value.value, tempX + 70, tempY);
		});
	}

It takes following parameters:

  • arr1: the array we need to print
  • canvasID: container, where we have to print array items
  • offsetX: offset of X position, or left margin from the container.
  • offsetY: offset of Y position, or top margin from the container.

Using this function we can print our arrays:

	printArray(array1Items, "cnvTable1", 10, 50);
	printArray(array2Items, "cnvTable2", 10, 50);

Now comes the final part how to draw arrows showing possible movement among array items before and after sorting process. I have used this jQuery plugin Curved Arrow to draw arrows, you can download this js file and add reference to this along-with jQuery.

	$.each(array1Items, function( index, value ) {
		offsetX = 140;
		offsetY = 170;
		
		var newArrayItem = getArrayItemAfterSort(value.value);
		if(newArrayItem != undefined)
		{
			console.log(index  + " - " + value.value + " - " + newArrayItem.index);
			
			$("#myocontainer").curvedArrow({
				p0x: value.getPosX() + offsetX,
				p0y: value.getPosY() + offsetY,
				p1x: value.getPosX() + offsetX,
				p1y: value.getPosY() + offsetY,
				p2x: newArrayItem.getPosX() + 570 + offsetX,
				p2y: newArrayItem.getPosY() + offsetY,
				lineWidth: 3,
				size:10
			});
			
		}
	});	
	
	function getArrayItemAfterSort(valueToFind)
	{
		var arrayItem = undefined;
		
		for (i = 0; i < array2Items.length; i++) {
			if(array2Items[i].value == valueToFind)
			{
				arrayItem = array2Items[i];
				break;
			}
		}
		
		return arrayItem;
	}

We are done with drawing arrows for array items. Lets try running this code and with the array items used in this example, you will see output similar to this:

Slightly changing the sequence of array items, i.e. var array = [6,4,1,5,2,3]; , you will see output like this:

August 6, 2017

MS SQL Server - Calculate Running Total

In this post we will see different ways to calculate running total using T-SQL. I am using Microsoft SQL SERVER 2008 R2. Let first setup a target table we want to calculate running values. Create a new table (say @tblItems) with the following script.

 declare @tblItems table(
  ID int identity(1, 1),
  Amount decimal(12, 3),
  RunningTotal decimal(12, 3) default(0)
 )

Populate @tblItems table with some dummy records.

 insert into @tblItems(Amount)
 values
  (50),
  (20),
  (100),
  (430),
  (80)
 ;

SELF JOIN

This is the first way we are calculating running total using INNER JOIN.

 SELECT t1.ID, t1.Amount, RunningTotal = SUM(t2.Amount)
 FROM @tblItems AS t1
 INNER JOIN @tblItems AS t2
   ON t1.ID >= t2.ID
 GROUP BY t1.ID, t1.Amount
 ORDER BY t1.ID;

But this technique is not recommended for large tables, because as the table gets larger, each incremental row requires reading n-1 rows in the table. This may lead to failures, timeouts, or low performance.

Update with Local Variable:

 DECLARE @RunningTotal decimal(12, 3) = 0;

 UPDATE @tblItems
 SET @RunningTotal = RunningTotal = @RunningTotal + Amount
 FROM @tblItems;

 SELECT ID, Amount, RunningTotal
 FROM @tblItems
 ORDER BY ID;

This method is more efficient than the above, but since the behavior is not properly documented, there are no guarantees about order.

Nested / Sub-Query

 SELECT ID, Amount,
  (SELECT SUM(amount) 
   FROM @tblItems t2 WHERE t2.ID <= t1.ID
          ) 
  as RunningTotal 
    
 FROM @tblItems as t1

This method performs similar to self join technique, as the table gets larger, this may lead to failures, timeouts, or low performance.

OVER Clause (For SQL Server 2012 or above)

New window functions introduced in SQL Server 2012 make this task a lot easier.

 SELECT ID, Amount, 
   SUM(Amount) OVER (ORDER BY ID) as RunningTotal 
 FROM @tblItems 

It performs better than all of the above techniques.