// Square Matrix handling functions for Javascript
// by David Turover, 9 October 2008. 
// Used by the hermite spline examples.

function sqMatrix(size) {
	this.data = new Array(size * size); 
	this.size = size; 

	// Initializer functions. Run by caller. 
	this.initIdentity = function(){
		var j=0; 
		var end=this.size * this.size; 
		for(var i = 0; i<end; i++){
			if(i == j){
				this.data[i] = 1;
				j += this.size + 1;
			} else {
				this.data[i] = 0;
			}
                }
	}

	this.initZero = function(){
		var end = this.size * this.size; 
		for(var i = 0; i < end; i++){
			this.data[i] = 0;
		}
	}

	// String functions. For debugging. 
	this.toStr = function(){
		var str = "<table class=\"matrix\">";
		for(var row = 0; row < this.size; row++){
			str += "<tr>";
			for(var col = 0; col < this.size; col++){
				str += "<td>" + this.data[row * this.size + col] +  "</td>";
			}
			str += "</tr>";
		}
		str += "</table>";
		return str;
	}
	this.printTo = function(divTgt){
		divTgt.innerHTML += this.toStr(); 
	}


	// Arithmetic Operations  
	this.rowAdd = function(rowDst, rowSrc){
		var i = rowDst * this.size; 
		var j = rowSrc * this.size; 
		var end = i + this.size; 
		while(i < end){
			this.data[i++] += this.data[j++];
		}
	}
	this.rowSub = function(rowDst, rowSrc){
		var i = rowDst * this.size; 
		var j = rowSrc * this.size; 
		var end = i + this.size; 
		while(i < end){
			this.data[i++] -= this.data[j++];
		}
	}
	this.rowMultStatic = function(rowNum, amt){
		var i = rowNum * this.size; 
		var end = i + this.size; 
		while(i<end){
			this.data[i++] *= amt; 
		}
	}

	this.rowArithOp = function(rowDst, rowSrc, amt){
		this.rowMultStatic(rowSrc, amt);	// BUG: race condition if multithreaded 
		this.rowAdd(rowDst, rowSrc);
		this.rowMultStatic(rowSrc, 1/amt);  
	}

	// Other row operations
	this.rowReduce = function(rowNum){
		// Cut leftmost nonzero element to 1, others by same ratio
		var i = rowNum * this.size; 
		var end = i + this.size;
		var amt = 0;
		while(i<end){
			if(amt == 0){ amt = this.data[i]; }
			if(this.data[i] != 0){
				this.data /= amt; // amt known to be nonzero
			}
			i++;
		}
	}

	this.rowSwap = function(rowA, rowB){
		if(rowA != rowB){ // logic unsafe if running on one row
			this.rowAdd(rowA, rowB); // rows are a+b, b
			this.rowMultStatic(rowB, -1); // rows are a+b, -b
			this.rowAdd(rowB, rowA); // rows are a+b, a
			this.rowSub(rowA, rowB); // rows are b, a
		}
	}

	// Run math on row as if it were a polynomial.
	this.rowCalc = function(rowNum, amt){
		var result = 0.0;
		for(var i=0; i<this.size; i++){
			result *= amt;
			result += this.data[rowNum * size + i]
		}
		return result;
	}

	// Other stuff 
	this.hasZeroRowOrCol = function(){
		var hZero = 0; // Row: only zeros seen so far.
		var vZero = 0; // Column: only zeros seen so far. 
		for(var i = 0; i < this.size; i++){
			hZero = 1;
			vZero = 1; 
			for(var j = 0; j < this.size; j++){
				if(this.data[i + j*this.size] != 0){ hZero = 0; }
				if(this.data[j + i*this.size] != 0){ vZero = 0; }
			}
			if(hZero || vZero){
				alert("DEBUG: Zero row or col found.");
				return 1; }
		}
		return 0;
	}
	this.hasEqRows = function(){
		var firstRelation = 0;
		var thisRelation = 0;
		var relsEq = 0 
		
		for(var i = 0; i < this.size-1; i++){
			for (var j = i+1; j < this.size; j++){
				relsEq = 1; 
				firstRelation = undefined;
				for(var k = 0; relsEq == 1 && k<this.size; k++){
					var x = this.data[i*this.size + k];
					var y = this.data[j*this.size + k];
					if(y == 0){ // avoid div-by-zero
						if(x != 0){ relsEq = 0; }  
						// else continue 
					} else { // General case
						if(firstRelation == undefined){
							firstRelation = x/y; 
						} else {
							thisRelation = x/y;
							if(firstRelation != thisRelation){
								relsEq = 0;
							}
						}
					}
				}
				if(relsEq){ return 1;  }
			}
		}
		return 0; // No equal rows found. 
	}

	this.hasInverse = function(){
		return ! (this.hasZeroRowOrCol() || this.hasEqRows());
	}

	this.calcInverse = function(){
		if(! this.hasInverse()){ return null;  }

		// Create a copy of this matrix; do not operate on this one. 
		var copy = new sqMatrix(this.size);
		for(var i = 0; i < this.size* this.size; i++){
			copy.data[i] = this.data[i]; }
		// TODO: Replace all instances of "this" with "copy" here to end. 
		var dstMatrix = new sqMatrix(copy.size);
		dstMatrix.initIdentity(); 

		for(var skip = 0; skip< size; skip++){
			// Look for a nonzero at the leftmost position
			var nonZeroAtLeft = 0 
			for(var i = skip; nonZeroAtLeft == 0 &&  i < size; i++){
				if(copy.data[i * copy.size + skip]){
					nonZeroAtLeft = 1; 
					if(i != skip){
						copy.rowSwap(skip, i);
						dstMatrix.rowSwap(skip, i);
					}
				}
			}

			if(nonZeroAtLeft == 0){ return null; } // FAIL
			// TODO: Do we need any garcol on above line? Does JS have a delete? 

			// Reduce the current row's value to 1.
			var divFactor = 1.0 / copy.data[skip* copy.size + skip] // Factor to divide by. 
			copy.rowMultStatic(skip, divFactor);
			dstMatrix.rowMultStatic(skip, divFactor);

			// Subtract from all other rows to zero out their left sides.
			for(var i=0; i<size; i++){
				if(i == skip){ continue; } // Skip the current working row
				// Get negative of relationship between rows for the working column.
				// First take the targeted column's leftmost...
				var tgtAmt =  - copy.data[i*copy.size + skip] ;
				if(tgtAmt){ // ...  and only work if target is nonzero.
					copy.rowArithOp(i, skip, tgtAmt);
					dstMatrix.rowArithOp(i, skip, tgtAmt);
				}
			}
		}
		delete copy;
		return dstMatrix;
	}

	this.transpose = function(){
		// Requiring square matrixes makes this easy
		var tmp = 0;
		for(var skip = 0; skip < this.size; skip++){
			for(var i = skip; i < this.size; i++){
				tmp = this.data[skip * this.size+i];
				this.data[skip * this.size+i] = this.data[skip + i * this.size]; 
				this.data[skip + this.size*i] = tmp; 
			}
		}
	}

	this.multVsPtRow = function(someArray){
		// Multiply against a single set of Points,
		// the set having equal size to the height of the square matrix.  
		var X = 0; // Index of X in Point implementation as 2-unit array
		var Y = 1; // Index of Y

		// The result will also be a row of Points. 
		var result = Array(Array());
		for(var i = 0 ; i < this.size; i++){ // Initialize 
			//result[i] = Array(someArray[i][X], someArray[i][Y]); // Point is array of 2 values.
			result[i] = Array(0.0, 0.0); // Point is array of 2 values.
		}

		// Algorithm A-47 from page 800 of Hearn and Baker's Computer Graphics 
		for(var i = 0; i < this.size; i++ ){
			var offsetX = 0.0;
			var offsetY = 0.0;
			for(var k = 0; k < this.size; k++ ){
				var factor = this.data[i*this.size + k]; 
				offsetX += factor * someArray[k][X];
				offsetY += factor * someArray[k][Y];
			}
			result[i][X] = offsetX;
			result[i][Y] = offsetY;
		}
		return result;
	}
}