/*************************
 * Matrix class          *
 * --------------------- *
 * by Greg Landweber     *
 * last updated: 7/06/02 *
 *************************

new Matrix();
matrix = Matrix.identity(size);

value = [Matrix].get(row,column);
[Matrix].set(row,column,value);

rows    = [Matrix].getRows();
columns = [Matrix].getColumns();

[Matrix].setRows(rows);
[Matrix].setColumns(columns);

[Matrix].transpose();

rowOp = [Matrix].rowReduce(reduced);
[Matrix].rowOperation(rowOp);

[Matrix].toString();

*/

function Matrix() {
    this.transposed = false;
    this.setRows(0);
    this.setColumns(0);
}

Matrix.prototype.fromString = function(string) {
    var rowStrings = string.split('\\\\');
    var row, column;
    
    this.setRows ( rowStrings.length ) ;
    
    for ( row = 0; row < rowStrings.length; row++ ) {
	var colStrings = rowStrings[row].split('&');
	if ( colStrings.length > this.getColumns() ) {
	    this.setColumns ( colStrings.length );
	}
	for ( column = 0; column < colStrings.length; column++ ) {
	    this.set(row+1,column+1,colStrings[column].toRational());
	}
    }
    return this;
}

Matrix.identity = function(size) {
    var m = new Matrix();
    
    m.setRows(size);
    m.setColumns(size);
    
    for ( row = 1; row <= size; row++ ) {
        for ( column = 1; column <= size; column++ ) {
            if ( row == column ) {
		m.set ( row, column, new Rational(1,1) );
            } else {
		m.set ( row, column, new Rational(0,1) );
            }
        }
    }
    return m;
}

Matrix.prototype.getRows = function() {
    if ( this.transposed ) {
        return this.columns;
    } else {
	return this.rows;
    }
}

Matrix.prototype.getColumns = function() {
    if ( this.transposed ) {
        return this.rows;
    } else {
	return this.columns;
    }
}

Matrix.prototype.setRows = function(value) {
    if ( this.transposed ) {
        this.columns = value;
    } else {
	this.rows = value;
    }
}

Matrix.prototype.setColumns = function(value) {
    if ( this.transposed ) {
        this.rows = value;
    } else {
	this.columns = value;
    }
}

Matrix.prototype.transpose = function() {
    this.transposed = !this.transposed;
    return this;
}

Matrix.prototype.get = function(row,column) {
    if ( this.transposed ) {
	return this[column][row];
    } else {
	return this[row][column];
    }
}

Matrix.prototype.set = function(row,column,value) {
    if ( this.transposed ) {
	if ( !this[column] ) {
	    this[column] = [];
	}
	this[column][row] = value;
    } else {
	if ( !this[row] ) {
	    this[row] = [];
	}
	this[row][column] = value;
    }
}

Matrix.prototype.setPivot = function(row,column) {
}

Matrix.prototype.setZero = function(row,column) {
}

Matrix.prototype.rowOperation = function(rowOp) {
    switch ( rowOp.type ) {
      case "scale" :
	this.scale(rowOp.row,rowOp.factor);
	break;
      case "exchange" :
	this.exchange(rowOp.row1,rowOp.row2);
	break;
      case "add" :
	this.replace(rowOp.factor,rowOp.pivotRow,rowOp.row);
	break;
    }
    return this;
}

Matrix.prototype.scale = function(row,factor) {
    for ( var column = 1; column <= this.getColumns(); column++ ) {
	this.set(row,column,Rational.multiply(factor,this.get(row,column)));
    }
}

Matrix.prototype.exchange = function(row1,row2) {
    for ( var column = 1; column <= this.getColumns(); column++ ) {
	temp=this.get(row1,column);
	this.set(row1,column,this.get(row2,column));
	this.set(row2,column,temp);
    }
}

Matrix.prototype.replace = function(factor,pivotRow,row) {
    for ( column = 1; column <= this.getColumns(); column++ ) {
	this.set(row,column,Rational.add(this.get(row,column),
	Rational.multiply(factor,this.get(pivotRow,column))));
    }
}

Matrix.prototype.toString = function(type,td) {
    var rows    = this.getRows();
    var columns = this.getColumns();
    var row, column;
    var result = "";
    
    if ( type == "TeX" ) {
	result = "";
	for ( row = 1; row <= rows; row++ ) {
	    if ( row > 1 ) {
	        result += "\\\\";
	    }
	    for ( column = 1; column <= columns; column++ ) {
		if ( column > 1 ) {
		    result += "&";
		}
		result += this.get(row,column).toString();
	    }
	}
    } else {	
	for ( row = 1; row <= rows; row++ ) {
	    result += "<tr>";
	    for ( column = 1; column <= columns; column++ ) {
		if ( td ) {
		    result += "<td " + td + ">";
		} else {
		    result += "<td>";
		}
		result += this.get(row,column).toString();
		result += "</td>";
	    }
	    result += "</tr>";
	}
    }
    
    return result;
}

Matrix.prototype.rowReduce = function(reduced) {
    var pivotRow;
    var pivotColumn;
    var pivotEntry, entry;
    
  forwardPhase:
    for ( pivotRow = 1, pivotColumn = 1; 
          pivotRow <= this.getRows() && pivotColumn <= this.getColumns();
	  ++pivotRow, ++pivotColumn ) {
	while ( (pivotEntry=this.get(pivotRow,pivotColumn)) == 0 ) {
	    for ( row = pivotRow + 1; row <= this.getRows(); row++ ) {
		if ( this.get(row,pivotColumn) != 0 ) {
		    return new RowOperation ( "exchange", pivotRow, row, pivotColumn );
		}		
	    }
	    if ( ++pivotColumn > this.getColumns() ) {
		break forwardPhase;
	    }
	}
	
	this.setPivot ( pivotRow, pivotColumn );
	
	for ( row = pivotRow + 1; row <= this.getRows(); row++ ) {
	    if ( (entry=this.get(row,pivotColumn)) != 0 ) {
		return new RowOperation ( "add", Rational.divide(entry,pivotEntry).minus(), pivotRow, row, pivotColumn );
	    } else {
		this.setZero ( row, pivotColumn );
	    }
	}
    }
    
    if ( !reduced ) {
	return false;
    }
    
  backwardPhase:
    for ( pivotRow = this.getRows(); pivotRow > 0; pivotRow-- ) {
	
	pivotColumn = 1;
	while ( (pivotEntry=this.get(pivotRow,pivotColumn)) == 0 ) {
	    if ( ++pivotColumn > this.getColumns() ) {
		if ( --pivotRow < 1 ) {
		    return false;
		}
		pivotColumn = 1;
	    }
	}
	
	if ( pivotEntry != 1 ) {
	    return new RowOperation ( "scale", pivotRow, pivotEntry.inverse(), pivotColumn );
	}
	
	for ( row = pivotRow - 1; row > 0; row-- ) {
	    if ( (entry=this.get(row,pivotColumn)) != 0 ) {
				
		return new RowOperation ( "add", Rational.divide(entry,pivotEntry).minus(), pivotRow, row, pivotColumn );
	    } else {
		this.setZero ( row, pivotColumn );
	    }
	}
    }
    return false;
}