<commit_before><!DOCTYPE html>
<html>
	<head>
		<title>Huffman Coding Tree</title>
		<meta charset="utf-8" />
		<link href="opendsaAV.css" title="CSS" rel="stylesheet" type="text/css" />
		<link href="../JSAV/css/JSAV.css" rel="stylesheet" type="text/css" />
		<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
		<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
		<script src="https://ajax.googleapis.com/ajax/libs/jqueryui/1.8.16/jquery-ui.min.js"></script>
		<script src="../JSAV/lib/jquery.transform.light.js"></script>
		<script src="../JSAV/lib/raphael.js"></script>
		<script src="../JSAV/build/JSAV.js"></script>

		<style>
			#container {
				width: 800px;
				height: 760px;
				background-color: #efe;
				border:1px solid #A5B6C8;
				padding: 10px;
				overflow-x: hidden;
				overflow-y: visible;
			}

			#av{
				overflow: visible;	
			}
			.jsavtree { position: absolute; } /* position trees absolutely */
			.jsavtree:nth-of-type(1) { left:50px;} /* move 2nd tree to the right */
			.jsavtree:nth-of-type(2) { left:150px;} /* move 3rd tree to the right */
			.jsavtree:nth-of-type(3) { left:250px;} /* move 4th tree to the right */
			.jsavtree:nth-of-type(4) { left:350px;} /* move 5th tree to the right */
			.jsavtree:nth-of-type(5) { left:450px;} /* move 6th tree to the right */
			.jsavtree:nth-of-type(6) { left:550px;} /* move 7th tree to the right */
			.jsavtree:nth-of-type(7) { left:650px;} /* move 8th tree to the right */
			.jsavtree:nth-of-type(8) { left:750px;} /* move 9th tree to the right */
			.jsavtree:nth-of-type(9) { left:350px;} /* move 9th tree to the right */
			.jsavcanvas { height: 500px;} /* set the height of the container */

			div h1 {
				background-color: #efe;
				margin: 5px;
			}
			.jsavcontainer {
				background-color: #efe;
				border: none;
				padding 0px;
			}
			.jsavcounter {
				float: left;
				width: 100px;
			}
			.jsavarray {
				padding-left:0;
				position: absolute;
			}
			p.jsavoutput.jsavline {
				height: 30px;
				margin: 0;
			}
			#about {
				float: right;
			}
			a.jsavsettings {
				display: block;
				margin-top: 10px;
				margin-left: 10px;
			}
			form {
				clear: both;
			}
			#hfTable {
				font-family:"Trebuchet MS", Arial, Helvetica, sans-serif;
				width: 550px;
				margin-left: 100px;
				margin-top: -450px;
				text-align: center;
				border-collapse:collapse;
			}

			#hfTable td, #hfTable th 
			{
				font-size:1.2em;
				border:1px solid #98bf21;
				padding:3px 7px 2px 7px;
			}
			#hfTable th 
			{
				font-size: 1.4em;
				text-align: center;
				padding-top: 5px;
				padding-bottom: 4px;
				background-color: #A7C942;
				color: #fff;
			}
			#hfTable tr.alt td 
			{
				color:#000;
				background-color:#EAF2D3;
			}
		</style>
	</head>

	<body>
		<div id="container">
			<input type="button" id="about" name="about" value="about" style="margin-top:10px; height:24px"/>
			<a class="jsavsettings" href="#">Settings</a>
			<h1 style="">Huffman Coding Tree Visualization</h1>
			<div id="av">
				<span class="jsavcounter"></span>
				<div class="jsavcontrols"></div>
				<p class="jsavoutput jsavline" readonly="readonly"></p>
			</div> <!--av-->
		</div> <!--container-->

		<script>	
			// sorting the elements of an array with Insertation Sort
			var sortArray = function (anArray, hfArray) {
				for (var i = 1; i < anArray.length; i++) {
					var key = anArray[i];
					var tmpTree = hfArray[i];
					var j = i - 1;
					while(j >= 0 && key < anArray[j]) {
						anArray[j + 1] = anArray[j];
						hfArray[j + 1] = hfArray[j];
						j--;
					}
					anArray[j + 1] = key;
					hfArray[j + 1] = tmpTree;
				}
			}

			// Shuffle the array by moving left
			var shuffle = function (anArray, hfArray) {
				for (var i = 0; i < anArray.length - 2; i++) {
					anArray[i] = anArray[i + 2];
					hfArray[i] = hfArray[i + 2];
				}
				anArray.length -= 2;
				hfArray.length -= 2;
			}

			// shift the merged tree to the 1st place
			var shift = function (anArray, hfArray) {
				var key = anArray[anArray.length - 1];
				var tmp = hfArray[hfArray.length -1];
				for (var i = anArray.length - 1; i > 0; i--) {
					anArray[i] = anArray[i - 1];
					hfArray[i] = hfArray[i - 1];
				}
				anArray[0] = key;
				hfArray[0] = tmp;
			}

			// traverse one tree and copy all its nodes to another tree
			var traverse_copy = function(startNode, treeOne, treeTwoRoot) {
				var val = treeTwoRoot.value();

				// the node is an empty node	
				if (!val || val === "jsavnull") {	
					return;
				} 
				else {		
					startNode.value(treeTwoRoot.value());
					// Traverse the left subtree
					if (treeTwoRoot.left()) {
						var lchild = treeOne.newNode();
						lchild.value(treeTwoRoot.left().value());
						startNode.left(lchild);
						traverse_copy(lchild, treeOne, treeTwoRoot.left());
					}
					// Traverse the right subtree
					if (treeTwoRoot.right()) {
						var rchild = treeOne.newNode();
						rchild.value(treeTwoRoot.right().value());
						startNode.right(rchild);
						traverse_copy(rchild, treeOne, treeTwoRoot.right());
					}
				}
			}

			// traverse to reset background color of the entire tree
			var traverse_color = function(node, col) {
				var val = node.value();

				// the node is an empty node	
				if (!val || val === "jsavnull") {	
					return;
				} 
				else {
					// if the node is an internal node, then display an circle
					if (node.left()) {
						node.css("background-color", col);
						traverse_color(node.left(),col);
					}
					if (node.right()) {
						node.css("background-color", col);
						traverse_color(node.right(),col);
					}
					// if the node is a leaf node, then display an rectangle
					else {  
						node.css({"height": "46px", "width": "36px", "border-radius":1, "background-color":"orange", "line-height":"22px"});
					}
				}
			}

			// adding "0" or "1" to the label of edges in Huffman Coding tree without animation
			var traverse_code = function(node) {
				if (node.left()) {
					node.left().edgeToParent().label(0); 
					traverse_code(node.left());
				}	
				if (node.right()) {
					node.right().edgeToParent().label(1);
					traverse_code(node.right());
				}
				else
				return;
			}

			// adding "0" or "1" to the label of edges in Huffman Coding tree with animation
			var traverse_code_animation = function(node) {
				if (node.left()) {
					jsav.umsg("\"0\" is set to the edge connecting the left child of the node " + "\"" + node.value() + "\".");
					node.left().edgeToParent().label(0); 
					jsav.step();
					traverse_code_animation(node.left());
				}	
				if (node.right()) {
					jsav.umsg("\"1\" is set to the edge connecting the right child of the node " + "\"" + node.value() + "\".");
					node.right().edgeToParent().label(1);
					jsav.step();
					traverse_code_animation(node.right());
				}
				else
				return;
			}

			// find a leaf node in Huffman Tree with a specific value
			var findNode = function(node, anValue) {
				var val = node.value();
				if (!val || val === "jasvnull")
				return
				else {
					if (node.left()) {
						if (node.left().value() == anValue)
						anLeaf = node.left();
						else
						findNode(node.left(), anValue);
					}   
					if (node.right()) {
						if (node.right().value() == anValue)
						anLeaf = node.right();
						else
						findNode(node.right(), anValue);
					}
				}
			}

			// find the Huffman Code for a specific leaf node without animation
			var leafCode = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						code += aLeafNode.edgeToParent().label();
						leafCode(aLeafNode.parent());
					}
					else {
						var tmpCode = "";
						for (var i = code.length - 1; i >= 0; i--) {
							tmpCode += code.substr(i, 1); 
						}
						code = tmpCode;
						return;	
					}
				}
			}

			// find the Huffman Code for a specific leaf node with animation
			var leafCode_animation = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						code += aLeafNode.edgeToParent().label();
						aLeafNode.parent().highlight();
						leafCode_animation(aLeafNode.parent());
					}
					else {
						var tmpCode = "";
						for (var i = code.length - 1; i >= 0; i--) {
							tmpCode += code.substr(i, 1); 
						}
						code = tmpCode;
						return;	
					}
				}
			}

			// Clear the highlight node from a specific leaf node to the root
			var path_clear = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						aLeafNode.parent().css("background-color", "white");
						path_clear(aLeafNode.parent());
					}
					else
					return;	
				}
			}

			// find the Huffman codes for all leaf nodes without animation
			var hfCode = function(valArr, codeArr, aTree) {
				for (var i = 0; i < valArr.length; i++) {
					findNode(aTree.root(), valArr[i]);
					leafCode(anLeaf);
					codeArr[i] = code;
					code = "";
				}	
			}

			// find the Huffman codes for all leaf nodes with animation
			var hfCode_animation = function(valArr, codeArr, aTree) {
				for (var i = 0; i < valArr.length; i++) {
					findNode(aTree.root(), valArr[i]);
					var tmpArray = new Array();
					tmpArray = valArr[i].split("<br>");
					jsav.umsg("Next we will show the path from the leaf node \"" + tmpArray[1] + "\" to the root \"" + aTree.root().value() + "\", and get the Huffman code of \"" + tmpArray[1]+ "\".");
					aTree.root().highlight();
					anLeaf.highlight();
					jsav.step();
					leafCode_animation(anLeaf);
					codeArr[i] = code;
					code = "";
					jsav.umsg("Huffman code for character \"" + tmpArray[1] + "\" is: \"" + codeArr[i] + "\", which is the value along the path from the root \"" + aTree.root().value() + "\" to \"" + tmpArray[1] + "\"");
					jsav.step();
					path_clear(anLeaf);
					anLeaf.css("background-color", "orange");
				}	
			}

			// Layout all the trees
			var layAll = function(trees) {
				var leftSoFar = 30;
				for (var i = 0; i < trees.length; i++) {
					trees[i].css({"left": leftSoFar, "top":"-40px"});
					traverse_color(trees[i].root(), "white");
					trees[i].layout();
					leftSoFar += trees[i].element.width() + 50;
				}
			}

			// Hide all the trees
			var hideAll = function(trees) {
				for (var i = 0; i < trees.length; i++) {
					trees[i].hide();
				}
			}

			// Show all the trees
			var showAll = function(trees) {
				for (var i = 0; i < trees.length; i++) {
					trees[i].show();
				}
			}

			// Constructing the huffmanCodingTree
			var huffTree = function (anArray, hfArray) {
				while (anArray.length > 1) {
					sortArray(anArray, hfArray);	
					var key = anArray[0] + anArray[1];

					// Extend the numArray
					var newIndex = anArray.length;
					anArray[1] = key;

					// construct a new tree
					hfArray.length += 1;
					hfArray[newIndex] = jsav.ds.bintree({visible: false, center: false});
					hfArray[newIndex].root(key);

					// Construct the left subtree by copying the 1st tree
					var lsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().left(lsub);
					traverse_copy(lsub, hfArray[newIndex], hfArray[0].root());

					// Construct the right subtree by copying the 2nd tree
					var rsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().right(rsub);
					traverse_copy(rsub, hfArray[newIndex], hfArray[1].root());

					// Restruct the tree array
					shuffle(anArray, hfArray);
				}	
			}

			// Constructing the huffmanCodingTree with animation
			var huffTree_animation = function (anArray, hfArray) {
				while (anArray.length > 1) {
					sortArray(anArray, hfArray);
					jsav.umsg("Sorting the data by their frequency, and the results are as follows: ");
					layAll(hfArray);
					jsav.step();

					jsav.umsg("Choose the two samllest number: " + anArray[0] + " and " + anArray[1] + ".");
					// Hightlight two elements that will be chosen
					hfArray[0].root().highlight();
					hfArray[1].root().highlight();
					jsav.step();

					hideAll(hfArray);

					var key = anArray[0] + anArray[1];						
					// Extend the numArray
					var newIndex = anArray.length;
					anArray.length += 1;
					anArray[newIndex] = key;

					// construct a new tree
					hfArray.length += 1;
					hfArray[newIndex] = jsav.ds.bintree({visible: false, center: false});
					hfArray[newIndex].root(key);

					// Construct the left subtree by copying the 1st tree
					var lsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().left(lsub);
					traverse_copy(lsub, hfArray[newIndex], hfArray[0].root());

					// Construct the right subtree by copying the 2nd tree
					var rsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().right(rsub);
					traverse_copy(rsub, hfArray[newIndex], hfArray[1].root());

					hfArray[newIndex].hide();
					jsav.umsg("Merge them together with the sum of them " + "\"" + key + "\"" +", and update the data as follows: ");
					// Restruct the tree array
					shuffle(anArray, hfArray);
					// Shif the merged tree to the 1st place
					shift(anArray, hfArray);

					showAll(hfArray);
					layAll(hfArray);
					jsav.step();
				}	
			}	

			// Create a table with all information about the character	
			var createTable = function(valArr, codeArr) {
				var table = document.createElement("table");
				table.id = "hfTable";
				table.setAttribute("border","1");
				var line = valArr.length;
				var list = 3;

				// create the table head
				var tr = document.createElement("tr");
				for(var i = 0; i <= list; i++) {
					var th = document.createElement("th");
					switch(i) {
						case 0:
						th.innerHTML = "<b>Character</b>";
						break;
						case 1:
						th.innerHTML = "<b>Frequency</b>";
						break;
						case 2:
						th.innerHTML = "<b>Huffman Code</b>";
						break;
						default:
						th.innerHTML = "<b>Bit</b>";
					}
					tr.appendChild(th);
				}
				table.appendChild(tr);

				// create the table content
				for(var i = 0; i < line; i++) {
					var tr = document.createElement("tr");
					for(var j = 0; j <= list; j++) {
						var td = document.createElement("td");
						switch(j) {
							case 0: 
							td.innerHTML = valArr[i].split("<br>")[1];
							break;
							case 1:
							td.innerHTML = valArr[i].split("<br>")[0];
							break;
							case 2:
							td.innerHTML = codeArr[i];
							break;
							default:
							td.innerHTML = codeArr[i].length;
						}
						tr.appendChild(td);
					}
					table.appendChild(tr);
				}
				document.getElementsByTagName("div")[0].appendChild(table);
			}

			var jsav = new JSAV("av");

			// numArray: used for logic control
			var numArray = new Array();

			// chaArray: used for storing characters
			var chaArray = new Array();

			// hfArray: used for holding the root of several binary trees
			var hfArray = new Array();

			// valArray: used for finding the Huffman Codes, which store the value with both the character and its frequency
			var valArray = new Array();

			// codeArray: used for storing the Huffman codes
			var codeArray = new Array();

			// userArry: an array to store the number and character
			var userArray = new Array();
			userArray[0] = 32;
			userArray[1] = "C";
			userArray[2] = 42;
			userArray[3] = "D";
			userArray[4] = 120;
			userArray[5] = "E";
			userArray[6] = 7;
			userArray[7] = "K"
			userArray[8] = 42;
			userArray[9] = "L"
			userArray[10] = 24;
			userArray[11] = "M";
			userArray[12] = 37;
			userArray[13] = "U";
			userArray[14] = 2;
			userArray[15] = "Z";

			// initialization for all the arrays
			for (var i = 0, j = 0; i < userArray.length - 1; i += 2, j++) {
				value = userArray[i] + "<br>" + userArray[i + 1];
				valArray[j] = value;
				// hfArray[j] = jsav.ds.bintree({visible: false, center: false});
				hfArray[j] = jsav.ds.bintree({center: false});	
				hfArray[j].root(value);
				numArray[j] = userArray[i];
				chaArray[j] = userArray[i+1];
			}

			jsav.umsg("The initial data are as follows (the first line is frequency and the second line is the chracter): ");
			layAll(hfArray);	
			jsav.step();

			// Constructing Huffman Coding Tree with animation.
			huffTree_animation(numArray, hfArray);
			jsav.umsg("The Huffman Coding Tree is as follows: ");
			layAll(hfArray);
			jsav.step();

			jsav.umsg("The codes for each node are as follows: ");
			traverse_code_animation(hfArray[0].root());

			var anLeaf;	     
			var code = "";  // used for record Huffman code
			hfCode_animation(valArray, codeArray, hfArray[0]);
			jsav.umsg("Huffman codes for all characters are as follows:"); 
			hfArray[0].hide();
			createTable(valArray, codeArray);
			jsav.recorded(); // done recording changes, will rewind

			$(".jsavtreenode").live("hover", function() {
				//console.log($(this).text(), $(this).offset().left, $(this).offset().top);
			});
			$("path").live("hover", function() {
				//console.log($(this).attr("d"));
			});

			(function($) {
				var context = $("#ssperform");

				// create a new settings panel and specify the link to show it
				var settings = new JSAV.utils.Settings($(".jsavsettings"));
				// Connect action callbacks to the HTML entities
				$('input[name="about"]').click(about);

				// Process About button: Pop up a message with an Alert
				function about() {
					var mystring = "HuffmanCoding Tree Visualization\nWritten by <NAME>\nCreated as part of the OpenDSA hypertextbook project.\nFor more information, see http://algoviz.org/eBook\nWritten during June, 2012\nLast update: June 4, 2012\nJSAV library version " + JSAV.version();
					alert(mystring);
				}
			})(jQuery);  
		</script>
	</body>
</html><commit_msg>Fix the problem that the table displays in each slide. Now the table only displays in the last slide.<commit_after><!DOCTYPE html>
<html>
	<head>
		<title>Huffman Coding Tree</title>
		<meta charset="utf-8" />
		<link href="opendsaAV.css" title="CSS" rel="stylesheet" type="text/css" />
		<link href="../JSAV/css/JSAV.css" rel="stylesheet" type="text/css" />
		<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
		<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
		<script src="https://ajax.googleapis.com/ajax/libs/jqueryui/1.8.16/jquery-ui.min.js"></script>
		<script src="../JSAV/lib/jquery.transform.light.js"></script>
		<script src="../JSAV/lib/raphael.js"></script>
		<script src="../JSAV/build/JSAV.js"></script>

		<style>
			#container {
				width: 800px;
				height: 760px;
				background-color: #efe;
				border:1px solid #A5B6C8;
				padding: 10px;
				overflow-x: hidden;
				overflow-y: visible;
			}

			#av{
				overflow: visible;	
			}
			.jsavtree { position: absolute; } /* position trees absolutely */
			.jsavtree:nth-of-type(1) { left:50px;} /* move 2nd tree to the right */
			.jsavtree:nth-of-type(2) { left:150px;} /* move 3rd tree to the right */
			.jsavtree:nth-of-type(3) { left:250px;} /* move 4th tree to the right */
			.jsavtree:nth-of-type(4) { left:350px;} /* move 5th tree to the right */
			.jsavtree:nth-of-type(5) { left:450px;} /* move 6th tree to the right */
			.jsavtree:nth-of-type(6) { left:550px;} /* move 7th tree to the right */
			.jsavtree:nth-of-type(7) { left:650px;} /* move 8th tree to the right */
			.jsavtree:nth-of-type(8) { left:750px;} /* move 9th tree to the right */
			.jsavtree:nth-of-type(9) { left:350px;} /* move 9th tree to the right */
			.jsavcanvas { height: 500px;} /* set the height of the container */			

			// change size and margins of arrays
			.jsavarray { margin: 0; height: 40px; min-height: 40px; position: absolute}
			.jsavarray li { border-radius: 0 !important; height: 35px; width: 145px; font-size: 15px; line-height: 40px;}
			.jsavarray:nth-of-type(1) {top: 0px;}
			.jsavarray:nth-of-type(2) {top: 35px;}
			.jsavarray:nth-of-type(3) {top: 70px;}
			.jsavarray:nth-of-type(4) {top: 105px;}
			.jsavarray:nth-of-type(5) {top: 140px;}
			.jsavarray:nth-of-type(6) {top: 175px;}
			.jsavarray:nth-of-type(7) {top: 210px;}
			.jsavarray:nth-of-type(8) {top: 245px;}
			.jsavarray:nth-of-type(9) {top: 280px;}
			
  			div h1 {
				background-color: #efe;
				margin: 5px;
			}
			.jsavcontainer {
				background-color: #efe;
				border: none;
				padding 0px;
			}
			.jsavcounter {
				float: left;
				width: 100px;
			}
			.jsavarray {
				padding-left:0;
				position: absolute;
			}
			p.jsavoutput.jsavline {
				height: 30px;
				margin: 0;
			}
			#about {
				float: right;
			}
			a.jsavsettings {
				display: block;
				margin-top: 10px;
				margin-left: 10px;
			}
			form {
				clear: both;
			}

		</style>
	</head>

	<body>
		<div id="container">
			<input type="button" id="about" name="about" value="about" style="margin-top:10px; height:24px"/>
			<a class="jsavsettings" href="#">Settings</a>
			<h1 style="">Huffman Coding Tree Visualization</h1>
			<div id="av">
				<span class="jsavcounter"></span>
				<div class="jsavcontrols"></div>
				<p class="jsavoutput jsavline" readonly="readonly"></p>
			</div> <!--av-->
		</div> <!--container-->

		<script>	
			// sorting the elements of an array with Insertation Sort
			var sortArray = function (anArray, hfArray) {
				for (var i = 1; i < anArray.length; i++) {
					var key = anArray[i];
					var tmpTree = hfArray[i];
					var j = i - 1;
					while(j >= 0 && key < anArray[j]) {
						anArray[j + 1] = anArray[j];
						hfArray[j + 1] = hfArray[j];
						j--;
					}
					anArray[j + 1] = key;
					hfArray[j + 1] = tmpTree;
				}
			}

			// Shuffle the array by moving left
			var shuffle = function (anArray, hfArray) {
				for (var i = 0; i < anArray.length - 2; i++) {
					anArray[i] = anArray[i + 2];
					hfArray[i] = hfArray[i + 2];
				}
				anArray.length -= 2;
				hfArray.length -= 2;
			}

			// shift the merged tree to the 1st place
			var shift = function (anArray, hfArray) {
				var key = anArray[anArray.length - 1];
				var tmp = hfArray[hfArray.length -1];
				for (var i = anArray.length - 1; i > 0; i--) {
					anArray[i] = anArray[i - 1];
					hfArray[i] = hfArray[i - 1];
				}
				anArray[0] = key;
				hfArray[0] = tmp;
			}

			// traverse one tree and copy all its nodes to another tree
			var traverse_copy = function(startNode, treeOne, treeTwoRoot) {
				var val = treeTwoRoot.value();

				// the node is an empty node	
				if (!val || val === "jsavnull") {	
					return;
				} 
				else {		
					startNode.value(treeTwoRoot.value());
					// Traverse the left subtree
					if (treeTwoRoot.left()) {
						var lchild = treeOne.newNode();
						lchild.value(treeTwoRoot.left().value());
						startNode.left(lchild);
						traverse_copy(lchild, treeOne, treeTwoRoot.left());
					}
					// Traverse the right subtree
					if (treeTwoRoot.right()) {
						var rchild = treeOne.newNode();
						rchild.value(treeTwoRoot.right().value());
						startNode.right(rchild);
						traverse_copy(rchild, treeOne, treeTwoRoot.right());
					}
				}
			}

			// traverse to reset background color of the entire tree
			var traverse_color = function(node, col) {
				var val = node.value();

				// the node is an empty node	
				if (!val || val === "jsavnull") {	
					return;
				} 
				else {
					// if the node is an internal node, then display an circle
					if (node.left()) {
						node.css("background-color", col);
						traverse_color(node.left(),col);
					}
					if (node.right()) {
						node.css("background-color", col);
						traverse_color(node.right(),col);
					}
					// if the node is a leaf node, then display an rectangle
					else {  
						node.css({"height": "46px", "width": "36px", "border-radius":1, "background-color":"orange", "line-height":"22px"});
					}
				}
			}

			// adding "0" or "1" to the label of edges in Huffman Coding tree without animation
			var traverse_code = function(node) {
				if (node.left()) {
					node.left().edgeToParent().label(0); 
					traverse_code(node.left());
				}	
				if (node.right()) {
					node.right().edgeToParent().label(1);
					traverse_code(node.right());
				}
				else
				return;
			}

			// adding "0" or "1" to the label of edges in Huffman Coding tree with animation
			var traverse_code_animation = function(node) {
				if (node.left()) {
					jsav.umsg("\"0\" is set to the edge connecting the left child of the node " + "\"" + node.value() + "\".");
					node.left().edgeToParent().label(0); 
					jsav.step();
					traverse_code_animation(node.left());
				}	
				if (node.right()) {
					jsav.umsg("\"1\" is set to the edge connecting the right child of the node " + "\"" + node.value() + "\".");
					node.right().edgeToParent().label(1);
					jsav.step();
					traverse_code_animation(node.right());
				}
				else
				return;
			}

			// find a leaf node in Huffman Tree with a specific value
			var findNode = function(node, anValue) {
				var val = node.value();
				if (!val || val === "jasvnull")
				return
				else {
					if (node.left()) {
						if (node.left().value() == anValue)
						anLeaf = node.left();
						else
						findNode(node.left(), anValue);
					}   
					if (node.right()) {
						if (node.right().value() == anValue)
						anLeaf = node.right();
						else
						findNode(node.right(), anValue);
					}
				}
			}

			// find the Huffman Code for a specific leaf node without animation
			var leafCode = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						code += aLeafNode.edgeToParent().label();
						leafCode(aLeafNode.parent());
					}
					else {
						var tmpCode = "";
						for (var i = code.length - 1; i >= 0; i--) {
							tmpCode += code.substr(i, 1); 
						}
						code = tmpCode;
						return;	
					}
				}
			}

			// find the Huffman Code for a specific leaf node with animation
			var leafCode_animation = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						code += aLeafNode.edgeToParent().label();
						aLeafNode.parent().highlight();
						leafCode_animation(aLeafNode.parent());
					}
					else {
						var tmpCode = "";
						for (var i = code.length - 1; i >= 0; i--) {
							tmpCode += code.substr(i, 1); 
						}
						code = tmpCode;
						return;	
					}
				}
			}

			// Clear the highlight node from a specific leaf node to the root
			var path_clear = function(aLeafNode) {
				var leafVal = aLeafNode.value();
				if (!leafVal || leafVal === "jsavnull")
				return;
				else {
					if (aLeafNode.parent()) {
						aLeafNode.parent().css("background-color", "white");
						path_clear(aLeafNode.parent());
					}
					else
					return;	
				}
			}

			// find the Huffman codes for all leaf nodes without animation
			var hfCode = function(valArr, codeArr, aTree) {
				for (var i = 0; i < valArr.length; i++) {
					findNode(aTree.root(), valArr[i]);
					leafCode(anLeaf);
					codeArr[i] = code;
					code = "";
				}	
			}

			// find the Huffman codes for all leaf nodes with animation
			var hfCode_animation = function(valArr, codeArr, aTree) {
				for (var i = 0; i < valArr.length; i++) {
					findNode(aTree.root(), valArr[i]);
					var tmpArray = new Array();
					tmpArray = valArr[i].split("<br>");
					jsav.umsg("Next we will show the path from the leaf node \"" + tmpArray[1] + "\" to the root \"" + aTree.root().value() + "\", and get the Huffman code of \"" + tmpArray[1]+ "\".");
					aTree.root().highlight();
					anLeaf.highlight();
					jsav.step();
					leafCode_animation(anLeaf);
					codeArr[i] = code;
					code = "";
					jsav.umsg("Huffman code for character \"" + tmpArray[1] + "\" is: \"" + codeArr[i] + "\", which is the value along the path from the root \"" + aTree.root().value() + "\" to \"" + tmpArray[1] + "\"");
					jsav.step();
					path_clear(anLeaf);
					anLeaf.css("background-color", "orange");
				}	
			}

			// Layout all the trees
			var layAll = function(trees) {
				var leftSoFar = 30;
				for (var i = 0; i < trees.length; i++) {
					trees[i].css({"left": leftSoFar, "top":"-40px"});
					traverse_color(trees[i].root(), "white");
					trees[i].layout();
					leftSoFar += trees[i].element.width() + 50;
				}
			}

			// Hide all the trees
			var hideAll = function(trees) {
				for (var i = 0; i < trees.length; i++) {
					trees[i].hide();
				}
			}

			// Show all the trees
			var showAll = function(trees) {
				for (var i = 0; i < trees.length; i++) {
					trees[i].show();
				}
			}

			// Constructing the huffmanCodingTree
			var huffTree = function (anArray, hfArray) {
				while (anArray.length > 1) {
					sortArray(anArray, hfArray);	
					var key = anArray[0] + anArray[1];

					// Extend the numArray
					var newIndex = anArray.length;
					anArray[1] = key;

					// construct a new tree
					hfArray.length += 1;
					hfArray[newIndex] = jsav.ds.bintree({visible: false, center: false});
					hfArray[newIndex].root(key);

					// Construct the left subtree by copying the 1st tree
					var lsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().left(lsub);
					traverse_copy(lsub, hfArray[newIndex], hfArray[0].root());

					// Construct the right subtree by copying the 2nd tree
					var rsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().right(rsub);
					traverse_copy(rsub, hfArray[newIndex], hfArray[1].root());

					// Restruct the tree array
					shuffle(anArray, hfArray);
				}	
			}

			// Constructing the huffmanCodingTree with animation
			var huffTree_animation = function (anArray, hfArray) {
				while (anArray.length > 1) {
					sortArray(anArray, hfArray);
					jsav.umsg("Sorting the data by their frequency, and the results are as follows: ");
					layAll(hfArray);
					jsav.step();

					jsav.umsg("Choose the two samllest number: " + anArray[0] + " and " + anArray[1] + ".");
					// Hightlight two elements that will be chosen
					hfArray[0].root().highlight();
					hfArray[1].root().highlight();
					jsav.step();

					hideAll(hfArray);

					var key = anArray[0] + anArray[1];						
					// Extend the numArray
					var newIndex = anArray.length;
					anArray.length += 1;
					anArray[newIndex] = key;

					// construct a new tree
					hfArray.length += 1;
					hfArray[newIndex] = jsav.ds.bintree({visible: false, center: false});
					hfArray[newIndex].root(key);

					// Construct the left subtree by copying the 1st tree
					var lsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().left(lsub);
					traverse_copy(lsub, hfArray[newIndex], hfArray[0].root());

					// Construct the right subtree by copying the 2nd tree
					var rsub = hfArray[newIndex].newNode();
					hfArray[newIndex].root().right(rsub);
					traverse_copy(rsub, hfArray[newIndex], hfArray[1].root());

					hfArray[newIndex].hide();
					jsav.umsg("Merge them together with the sum of them " + "\"" + key + "\"" +", and update the data as follows: ");
					// Restruct the tree array
					shuffle(anArray, hfArray);
					// Shif the merged tree to the 1st place
					shift(anArray, hfArray);

					showAll(hfArray);
					layAll(hfArray);
					jsav.step();
				}	
			}	
			
			// Create a table with all information about the character	
			var createTable = function(valArr, codeArr) {
		
				// Create the title of the table by using jsav array
				var tableArray = new Array("<b>Character</b>", "<b>Frequency</b>", "<b>Huffman Code</b>", "<b>Bit</b>");
				var index = 4; // used to add value in jsav array.
				var line = valArr.length;
				var list = 3;
				for(var i = 1; i <= line; i++) {
					for(var j = 0; j <= list; j++) {
						switch(j) {
							case 0: 
							tableArray[index] = valArr[i - 1].split("<br>")[1];
							index++;
							break;
							case 1:
							tableArray[index] = valArr[i - 1].split("<br>")[0];
							index++;
							break;
							case 2:
							tableArray[index] = codeArr[i - 1];
							index++;
							break;
							default:
							tableArray[index] = codeArr[i - 1].length;
							index++;
						}
					}
				}			

				// Create 9 jsav array to construct a table
				var tableDisplay = new Array();	// an array used for display the table
				for(var i = 0, j = 0; i < tableArray.length; i += 4, j++) {
					var tmpArr = new Array();

					if (i % 4 == 0) {
						tmpArr[j] = new Array(tableArray[i], tableArray[i + 1], tableArray[i + 2], tableArray[i + 3]);
					}
					tableDisplay[j] = jsav.ds.array(tmpArr[j]);
				}
				
				// Set css properties for the table
				tableDisplay[0].css([0, 1, 2, 3], {"font-family":"Trebuchet MS, Arial, Helvetica, sans-serif", "font-size":"1.2em", "border":"1px #98bf21", "background-color":"#9ACD32", "color":"#fff"});
				for (var i = 1; i < tableDisplay.length; i++) {
					tableDisplay[i].css([0, 1, 2, 3], {"font-family":"Trebuchet MS, Arial, Helvetica, sans-serif", "font-size":"1.1em", "border":"1px #98bf21", "color":"#000"});
				}
			}

			var jsav = new JSAV("av");

			// numArray: used for logic control
			var numArray = new Array();

			// chaArray: used for storing characters
			var chaArray = new Array();

			// hfArray: used for holding the root of several binary trees
			var hfArray = new Array();

			// valArray: used for finding the Huffman Codes, which store the value with both the character and its frequency
			var valArray = new Array();

			// codeArray: used for storing the Huffman codes
			var codeArray = new Array();

			// userArry: an array to store the number and character
			var userArray = new Array();
			userArray[0] = 32;
			userArray[1] = "C";
			userArray[2] = 42;
			userArray[3] = "D";
			userArray[4] = 120;
			userArray[5] = "E";
			userArray[6] = 7;
			userArray[7] = "K"
			userArray[8] = 42;
			userArray[9] = "L"
			userArray[10] = 24;
			userArray[11] = "M";
			userArray[12] = 37;
			userArray[13] = "U";
			userArray[14] = 2;
			userArray[15] = "Z";

			// initialization for all the arrays
			for (var i = 0, j = 0; i < userArray.length - 1; i += 2, j++) {
				value = userArray[i] + "<br>" + userArray[i + 1];
				valArray[j] = value;
				hfArray[j] = jsav.ds.bintree({center: false});	
				hfArray[j].root(value);
				numArray[j] = userArray[i];
				chaArray[j] = userArray[i+1];
			}

			jsav.umsg("The initial data are as follows (the first line is frequency and the second line is the chracter): ");
			layAll(hfArray);	
			jsav.step();

			// Constructing Huffman Coding Tree with animation.
			huffTree_animation(numArray, hfArray);
			jsav.umsg("The Huffman Coding Tree is as follows: ");
			layAll(hfArray);
			jsav.step();

			jsav.umsg("The codes for each node are as follows: ");
			traverse_code_animation(hfArray[0].root());

			var anLeaf;	     
			var code = "";  // used for record Huffman code
			hfCode_animation(valArray, codeArray, hfArray[0]);
			jsav.umsg("Huffman codes for all characters are as follows:"); 
			hfArray[0].hide();
			createTable(valArray, codeArray);		
			jsav.recorded(); // done recording changes, will rewind

			$(".jsavtreenode").live("hover", function() {
				//console.log($(this).text(), $(this).offset().left, $(this).offset().top);
			});
			$("path").live("hover", function() {
				//console.log($(this).attr("d"));
			});

			(function($) {
				var context = $("#ssperform");

				// create a new settings panel and specify the link to show it
				var settings = new JSAV.utils.Settings($(".jsavsettings"));
				// Connect action callbacks to the HTML entities
				$('input[name="about"]').click(about);

				// Process About button: Pop up a message with an Alert
				function about() {
					var mystring = "HuffmanCoding Tree Visualization\nWritten by <NAME>\nCreated as part of the OpenDSA hypertextbook project.\nFor more information, see http://algoviz.org/eBook\nWritten during June, 2012\nLast update: June 19, 2012\nJSAV library version " + JSAV.version();
					alert(mystring);
				}
			})(jQuery);  
		</script>
	</body>
</html>
{'fraction_non_alphanumeric': 0.16014460757257976, 'fraction_numerical': 0.016475328402693452, 'mean_word_length': 2.6164670658682634, 'pattern_counts': {'":': 23, '<': 144, '<?xml version=': 0, '>': 131, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3353888', 'n_tokens_mistral': 16372, 'n_tokens_neox': 12467, 'n_words': 3192}