var BRANCH = 0;
var LEAF = 1;

/* Let us fashion something akin to an XML tree */
hNode = function () {}
hNode.prototype.id=-1; // 0 or 1 (left or right)
hNode.prototype.type; // BRANCH or LEAF
hNode.prototype.value; // Character value
hNode.prototype.weight; // # of instances of value
hNode.prototype.parent; // Parent node
hNode.prototype.children; // Child nodes
hNode.prototype.render = function (depth,prefix) {
	var out='';
	if (!depth) {
		depth = 0;
		prefix = '    ';
		out = 'Root';
	}
	if (this.children) {
		for (i in this.children) {
			if (i>0) {
				out+=prefix;
				out+=' '+i;
				pref = '  ';
			} else {
				out+='-'+i;
				pref = ' |';
			}
			out+=this.children[i].render(depth+1,prefix+pref);
		}
	} else {
		out+=':\''+this.value+'\' ('+this.weight+')<br>';
	}
	return out;
}

function createTree() {
	var hNodes = new Array();
	var i,j;
	var outBuf;
	inpBuf = document.forms['form1'].inpBuf.value;
	if (inpBuf.length<2) {
		document.getElementById('outBuf').innerHTML = 'Error: Huffman code requires at least 2 characters.  Root node cannot be a leaf.';
		return false;
	}
	for (i=0;i<inpBuf.length;i++) {
		ch = inpBuf.charAt(i);
		for (j=0;j<hNodes.length;j++) {
			if (ch==hNodes[j].value) {
				hNodes[j].weight++;
				break;
			}
		}
		if (j>=hNodes.length) {
			tempNode = new hNode();
			tempNode.type = LEAF;
			tempNode.value = ch;
			tempNode.weight = 1;
			hNodes.push (tempNode);
		}
	}
	outBuf = 'Initial pass:<br>';
	outBuf += 'Total characters: '+inpBuf.length+'<br>';
	outBuf += 'Unique characters: '+hNodes.length+'<br>';
	for (i=0;i<hNodes.length;i++) {
		outBuf += '['+hNodes[i].value+hNodes[i].weight+'] '
	}
	outBuf += '<br>';
	var count = hNodes.length-1;
	for (h=0;h<count;h++) {
		tempNode = new hNode();
		tempNode.type = BRANCH;
		tempNode.weight = 0;
		var lowNodes = new Array();
		for (i=0;i<2;i++) {
			lowNodes[i] = -1;
			for (j=0;j<hNodes.length;j++) {
				if (hNodes[j].id==-1 && (lowNodes[i]==-1 || hNodes[j].weight<hNodes[lowNodes[i]].weight)) {
					lowNodes[i] = j;
				}
			}
			hNodes[lowNodes[i]].id = i;
			//outBuf+='lownode '+i+': '+lowNodes[i]+' id='+hNodes[lowNodes[i]].id+'<br>';
		}
		newNode = hNodes.push(tempNode)-1;
		hNodes[newNode].children = new Array();
		for (i=0;i<2;i++) {
			hNodes[lowNodes[i]].parent = hNodes[newNode];
			hNodes[newNode].weight += hNodes[lowNodes[i]].weight;
			hNodes[newNode].children.push(hNodes[lowNodes[i]]);
		}
	}
	outBuf += 'Second pass:<br>';
	outBuf += 'Total nodes in tree: '+hNodes.length+'<br>';
	outBuf += 'Render tree:<br>';
	outBuf += hNodes[hNodes.length-1].render();

	document.getElementById('outBuf').innerHTML = outBuf;
}