// Copyright (c) 2007 Ric Hardacre 
//
// Permission to use, copy, modify, and distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

// filename    : cyclomedia_arrays.js
// description : 2d array manipulation functions
// namespace   : all functions and variables are prefixxed "array_"
// www         : http://www.cyclomedia.co.uk/ajax/
// author      : Ric Hardacre
// email       : ric.hardacre at above domain

// some of these rely on standard javascript v1.5 1d array prototype functions, which some
// legacy JS implimentations do not have, to support these legacy apps (such as IE 5)
// you may need the array.js extenstions from http://4umi.com/web/javascript/array.htm
// or similar, ideally your script should check for these (array.concat and array.copy)
// and degrade gracefully otherwise

//TODO
//functions to swap two rows/cols in place

var array_release_version = "1.0.0";
var array_release_date    = "2007-01-12";

// array_new
//
// create 2d array, will have at least one cell
//
// irm    = num rows, overload with 1d array to define contents of each cell across the row
// icm    = num cols, overload with 1d array to define contents of each cell down the column
// sNull  = default cell contents
//
function array_new( irm , icm , sNull )
{
	var a = new Array();
	var aIn = null;
	var ir,ic;
	
	//overload irm with 1D array to convert that into a 1-col 2d array
	if( array_isArray( irm ) )
	{
		aIn = irm;
		if( icm < 1 )	//you can still pass a col count, which will then repeat the array down each col
			icm = 1;
		irm = aIn.length;
		
		for( ir = 0 ; ir < irm ; ir++ )
		{
			a[ir] = new Array();
			for( ic = 0 ; ic < icm ; ic++ )
				a[ir][ic] = aIn[ir];
		}
	}
	else
	//overload icm with 1D array to convert that into a 1-row 2d array
	if( array_isArray( icm ) )
	{
		aIn = icm;
		icm = aIn.length;
		if( irm < 1 )	//pass a row count to repeat the array across each col
			irm = 1;
		
		for( ir = 0 ; ir < irm ; ir++ )
		{
			a[ir] = new Array();
			for( ic = 0 ; ic < icm ; ic++ )
				a[ir][ic] = aIn[ic];
		}

	}
	else
	//no overload, irm and irc are numeric
	{
		if( !irm || irm < 0 || !icm || icm < 0 )	//no dimensions, return empty array
			return new Array();
		
		for( ir = 0 ; ir < irm ; ir++ )
		{
			a[ir] = new Array();
			
			for( ic = 0 ; ic < icm ; ic++ )
			{
				a[ir][ic] = sNull;
			}
		}
	}
	
	//a may end up being returned as an empty 1d array (no rows, and therefore no cols)
	//this is ok, provided the functions that operate it (e.g. append a row)
	//are aware of this possible condition. which also makes it possible
	//to create a 2d array by calling array_append with two 1d arrays
	return a;
}

//
// array_cols
//
// return number of cols in array, only measures first row so calling
// array_pad and recieving the col count back that way might be more
// useful depending on your data
//
function array_cols( aRef )
{
	if( !array_is2dArray( aRef ) )
		return 0;
		
	return aRef[0].length;
}

//
// array_rows
//
// returns number of rows in array
//
function array_rows( aRef )
{
	if( !array_is2dArray( aRef ) )
		return 0;
		
	return aRef.length;
}

// array_copy
//
// duplicate a 2d array
//
function array_copy( aRef )
{
	if( !array_is2dArray( aRef ) )
	{
		if( !array_isArray( aRef ) )
			return null;
		else
			return aRef.copy();	//here aRef may be an empty 1d array, which is ok
	}

	var aNew = new Array();
	
	var ir,irm;

	irm = aRef.length;
	for( ir = 0 ; ir < irm ; ir++ )
		aNew[ aNew.length ] = aRef[ir].copy();
	
	return aNew;
}

//
// array_concat
//
// vertically join two 2d arrays, if they are of variable width a jagged array will result
// returns new row count
//
// aRef   - pointer to array to be joined to
// aIns   - pointer to array to append
//
function array_concat( aRef , aIns )
{
	if( !array_is2dArray( aRef ) )
		return 0;
		
	if( !array_is2dArray( aIns ) )
		return aRef.length;

	var ir,irm;

	irm = aIns.length;
	for( ir = 0 ; ir < irm ; ir++ )
		aRef[ aRef.length ] = aIns[ir].copy();
	
	return aRef.length;
}

//
// array_cojoin
//
// horizontally join two 2d arrays
// returns new col count
//
// aRef   - pointer to array to be joined to
// aIns   - pointer to array to append
//
function array_cojoin( aRef , aIns )
{
	if( !array_is2dArray( aRef ) )
		return 0;
		
	if( !array_is2dArray( aIns ) )
		return aRef[0].length;
	
	var ir,irm;

	//get min row count incase they are not equally tall
	irm = aIns.length;
	ir = aRef.length;
	if( ir < irm )
		irm = ir;

	for( ir = 0 ; ir < irm ; ir++ )
		aRef[ir] = aRef[ir].concat( aIns[ir] );
	
	return aRef[0].length;
}


//
// array_flip
//
// - swaps [row][col] array into [col][row] and vis versa
//
function array_flip( aRef )
{
	if( !array_is2dArray( aRef ) )
		return;

	var ir,ic;
	var irm = aRef.length;
	var icm = array_pad( aRef , null );
	var imm = irm;	//max dimension, assume geometrically square for starters
	
	//because the array may not be geometrically square we
	//may need to add rows or columns before flipping
	if( irm < icm )
	{
		imm = icm;
		for( ir = irm ; ir < icm ; ir++ )
			array_row_ins( aRef , null , -1 );
	}
	else
	if( irm > icm )
	{
		imm = irm;
		for( ic = icm ; ic < irm ; ic++ )
			array_col_ins( aRef , null , -1 );
	}
	
	//the array is now geometrically square but icm and irm remain unchanged
	//imm now holds the row/col max
	
	//to flip the array we simply swap the cell at [a][b] with [b][a]
	var s;
	
	for( ir = 0 ; ir < imm ; ir++ )
		for( ic = 0 ; ic < ir ; ic++ )
		{
			s = aRef[ir][ic];
			aRef[ir][ic] = aRef[ic][ir];
			aRef[ic][ir] = s;
		}
	
	//now it's flipped we need to trim off the extra rows or cols, check
	//imm against the original dimensions and strip the OPPOSITE dimension
	//as now the array is flipped
	if( irm < imm )
		for( ir = irm ; ir < imm ; ir++ )
			array_col_del( aRef , -1 );
	else
	if( icm < imm )
		for( ic = icm ; ic < imm ; ic++ )
			array_row_del( aRef , -1 );

}

//
// array_pad
//
// make a jagged array square by filling in any blank entries
// returns column count
//
// aRef   - pointer to array to pad
// sNull  - string to insert into any new cells that are created
//
function array_pad( aRef , sNull )
{
	if( !array_is2dArray( aRef ) )
		return 0;

	var ic,icm,ir,irm,icc;
	var bNotSquare = false;
	
	//get num of rows
	irm = aRef.length;

	if( irm == 0 )
		return 0;
	
	//find widest row
	icc = aRef[0].length
	for( ir = 1 ; ir < irm ; ir ++ )
	{
		icm = aRef[ir].length;
		if( icm != icc )
		{
			bNotSquare = true;
			if( icm > icc )
				icc = icm;
		}
	}

	//now pad, but only if we need to
	if( bNotSquare )
	for( ir = 0 ; ir < irm ; ir ++ )
	{
		icm = aRef[ir].length;
		for( ic = icm ; ic < icc ; ic++ )	//note how if icm == icc this loop is skipped
			aRef[ir][ic] = sNull;
	}

	return icc;
}

// 
// array_resize
//
// aRef    - array to resize
// irOfs   - index of top row of array relative to current top row, a negative value prepends rows
// icOfs
// irCount - new num rows, if < 1 then row count will not change
// icCount
// sNull   - custom null char
//
function array_resize( aRef , irOfs , icOfs , irCount , icCount , sNull )
{
	var irm = 0;
	var icm = 0;
	var ir,ic;
	
	//aRef is not a valid array at all, quit out
	if( !array_isArray( aRef ) )
		return;

	//aRef is not a valid 2d array, or an empty 2d array, so fill it out
	if( !array_is2dArray( aRef ) )
	{
		//reset the length, though this will clear a 1d array
		//if the user wants to convert a 1d array into a 2d 
		//array they should create an empty 2d array by calling array_new
		//and then use array_row_push to add the row
		aRef.length = 0;
		
		//compensate for negative offsets
		irm = irCount - irOfs;
		icm = icCount - icOfs;
		
		for( ir = 0 ; ir < irm ; ir++ )
		{
			aRef[ir] = new Array();
			
			for( ic = 0 ; ic < icm ; ic++ )
			{
				aRef[ir][ic] = sNull;
			}
		}
		return;
	}

	//some of the functionality here is very similar to what goes on in the
	//array region paste function, but rather than create overhead by copying
	//out and repasting an array back onto itself we're going to work on the
	//original array directly
	
	//first add rows or cols depending on negative offsets, or delete them in the case of positive ones
	if( irOfs < 0 )
	{
		do
			array_row_ins( aRef , sNull , 0 );
		while( ++irOfs < 0 )
	}
	else
	if( irOfs > 0 )
	{
		while( irOfs-- > 0 )
			array_row_del( aRef , 0 );
	}
	
	if( icOfs < 0 )
	{
		do
			array_col_ins( aRef , sNull , 0 );
		while( ++icOfs < 0 )
	}
	else
	if( icOfs > 0 )
	{
		do
			array_col_del( aRef , 0 );
		while( --icOfs > 0 )
	}
	
	//both offsets will now be zero
	//get any dimensions that remain in the array
	if( aRef )
	{
		irm = aRef.length;
		if( aRef[0] )
			icm = aRef[0].length;
	}
	
	//now add or remove any length that's needed
	if( irm < irCount )
	{
		do
			array_row_ins( aRef , sNull , -1 );
		while( ++irm < irCount )
	}
	else
	if( irCount > -1 && irm > irCount )	//overload: pass -1 to leave row count unaffected
	{
		do
			array_row_del( aRef , -1 );
		while( --irm > irCount )
	}
	
	if( icm < icCount )
	{
		do
			array_col_ins( aRef , sNull , -1 );
		while( ++icm < icCount )
	}
	else
	if( icCount > -1 && icm > icCount )	//overload: pass -1 to leave col count unaffected
	{
		do
			array_col_del( aRef , -1 );
		while( --icm > icCount )
	}
	
}

//
// array_split
//
// - takes a simply delimited input string and returns a 2d array
// - the input string should be delimited in the order cccrcccrcccr
//
// parameters:
// s        - the string to split
// r        - the row delimiter
// c        - the col delimiter
//
// returns
// a        - new 2d array
// null     - on error
//

function array_split( sIn , sRow , sCol )
{
	if( !array_isString( sIn ) )
		return null;
		
	var aTMP = sIn.split( sRow );
	
	if( !aTMP )
		return null;
	
	var ir,irm;
	irm = aTMP.length;
	
	var aOut = new Array( irm );
	for( ir = 0 ; ir < irm ; ir++ )
	{
		aOut[ir] = aTMP[ir].split( sCol );
	}

	return aOut;
}

//
// array_join
//
// takes an array and simply delimits it down to a string
//
// parameters:
// aRef      - the 2d array to join
// sRow      - row delimiter
// sCol      - col delimiter
//
// returns:
// sOut      - delimited string in row col order : "cccrcccrcccr"
function array_join( aRef , sRow , sCol )
{
	if( !array_is2dArray( aRef ) )
		return "";
	
	var ir,irm;
	irm = aRef.length;
	
	var sOut = "";
	for( ir = 0 ; ir < irm ; ir++ )
	{
		if( ir > 0 )
			sOut += sRow;
			
		sOut += aRef[ir].join( sCol );
	}
	
	return sOut;
}


//
// array_join_clear
//
// takes an array and returns a delimited string, strips the
// input array of any delimiter chars found
//
// parameters:
// aRef         - the 2d array to join
// sRow         - row delimiter
// sCol         - col delimiter
//
// returns:
// sOut         - delimited string in row col order : "cccrcccrcccr"
function array_join_clear( aRef , sRow , sCol )
{
	if( !array_is2dArray( aRef ) )
		return "";
	
	var ir,irm;
	var ic,icm;
	irm = aRef.length;
	
	var sOut = "";
	var sTMP = "";	//regexp cleaned entry
	var re = new RegExp( array_EscapeRE(sRow) + "|" + array_EscapeRE(sCol) , "g" );
	
	for( ir = 0 ; ir < irm ; ir++ )
	{
		if( ir > 0 )
			sOut += sRow;
		
		icm = aRef[ir].length;
		for( ic = 0 ; ic < icm ; ic++ )
		{
			if( ic > 0 )
				sOut += sCol;
		
			sTMP = aRef[ir][ic].replace( re , "" );
			sOut += sTMP;
		}	
	}
	
	return s;
}


//csv rules:
//
//row delimiter is \n, \r or \r\n
//col delimiter is comma (or tab?)
//entries may be qualified by enclosing in double quotes
//non-qualified leading and trailing spaces are truncated
//a literal quote must be qualified and escaped with another quote char
//a literal row or col seperator must be qualified
//
function array_split_csv( sIn )
{
	return array_split_params( sIn , "\n" , "," , "\"" , "\"" );
}

//
//array_split_params
//
//splits a qualified text input string into an array to allow the literal inclusion
//of the row or col delimiters in the data
//
// s   - string to parse
// sdr - row seperator
// sdc - col seperator
// sdq - data qualifier
// sqq - data qualifier escape char (self escaping by doubling up e.g. '\\')
//
function array_split_params( s , sdr , sdc , sdq , sqq )
{
	var sCol,sRow,sEOF,sQua;
	var i;
	
	//find ascii codes not used in the string for each delimiter
	//these are 99% likely to be 1,2 and 3, non alphanumeric control
	//characters
	//col
	for( i = 1 ; i < 256 ; i++ )
	{
		sCol = String.fromCharCode(i);
		if( s.indexOf( sCol ) < 0 )
			break;
	}
	//row
	for( i++ ; i < 256 ; i++ )
	{
		sRow = String.fromCharCode(i);
		if( s.indexOf( sRow ) < 0 )
			break;
	}
	//EOF
	for( i++ ; i < 256 ; i++ )
	{
		sEOF = String.fromCharCode(i);
		if( s.indexOf( sEOF ) < 0 )
			break;
	}
	//Qualifier
	for( i++ ; i < 256 ; i++ )
	{
		sQua = String.fromCharCode(i);
		if( s.indexOf( sQua ) < 0 )
			break;
	}

	//now we can replace certain chars, and groups of chars in the input string
	//with these control characters to delimit the string
	
	//method: step through the string one char at a time, forking the control path on the
	//character we are on, so a row or col seperator will fork into the "this is an entry"
	//path and within that a qualifier char will fork into the "this is qualified text" 
	//path.
	
	var ie = true;		//we're in an entry, assume first char of input string is first char of first entry
	var iq = false;		//we're in a qualified string
	var im = s.length;	//length of string
	var c,n;			//cur char, next char
	var sOut = "";
	
	//convert all line breaks to \n
	s = s.replace( /\r\n/g , "\n" );
	//s = s.replace( /\n\r/g , "\n" );
	s = s.replace( /\r/g , "\n" );

	for( i = 0 ; i < im ; i++ )
	{
		c = s.charAt(i);		//cur char
			
		//not in an entry, look for delimiters
		if( !ie )
		{
			if( c == sdc )
			{
				sOut += sCol;	//append our internal col delimiter to the output
				ie = true;		//new entry
				iq = false;		//... so far unqualified
			}					
			else
			if( c == sdr )
			{
				sOut += sRow;	//append our internal row delimiter to the output
				ie = true;		//new entry
				iq = false;		//... so far unqualified
			}
		}
		//in an entry
		else
		{	
			//not in a qualified string			
			if( !iq )
			{
				//found a qualifier char? switch to qualified parse mode
				if( c == sdq )
				{
					iq = true;
					sOut += sQua;	//this allows the regExp at the end of the func to preserve qualified leading/trailing spaces
				}
				else
				//capture col and row delimiters
				if( c == sdr || c == sdc )
				{	
					ie = false;		//end InEntry status
					i--;			//hack i back one step so the next iteration picks it back up
				}
				else
					sOut += c;
			}
			//inside qualified string, preserve literal occurences of delimiters
			else
			{
				n = s.charAt(i+1);		//next char
				
				//escaped qualifier e.g. '\"' or '""'
				if( c == sqq && n == sdq )		
				{
					sOut += sdq;	//append it and skip the escaped char
					i++;
				}
				else
				//escaped escape char e.g. '\\'
				if( c == sqq && n == sqq )
				{
					sOut += sqq;	//append it and skip the escaped char
					i++;
				}
				else
				//non escaped qualifier char, exit qualified string
				if( c == sdq )
				{
					iq = false;
					sOut += sQua;
				}
				else
					sOut += c;
			}
		}
	}
	
	//strip leading and trailing spaces, let regexp do the work here
	sOut = (sOut + " " + sEOF).replace( new RegExp( " +" + sEOF ) , "" );	//trailing entire string
	sOut = (sEOF + " " + sOut).replace( new RegExp( sEOF + " +" ) , "" );	//leading entire string
	sOut.replace( new RegExp( " +" + sCol , "g" ) , sCol );	//trailing cell
	sOut.replace( new RegExp( " +" + sRow , "g" ) , sRow );	//trailing row
	sOut.replace( new RegExp( sCol + " +" , "g" ) , sCol );	//leading cell
	sOut.replace( new RegExp( sRow + " +" , "g" ) , sRow );	//leading row
	sOut.replace( new RegExp( sQua , "g" ) , "");			//strip qualifier placeholders
	

	//finally we can use the vanilla split function to produce the array
	return array_split( sOut , sRow , sCol );
}

function array_join_csv( aRef )
{
	return array_join_params( aRef , "\n" , "," , "\"" , "\"" );
}

//array_join_params
//
// a   - array to join
// sdr - row seperator
// sdc - col seperator
// sdq - data qualifier
// sqq - data qualifier escape char
//
function array_join_params( a , sdr , sdc , sdq , sqq )
{
	if( !array_is2dArray( a ) )
		return "";
	
	var s = ""
	
	//this is quite simple, check each element in the array to see if it contains a "forbidden"
	//char, if it does then enclose it in qualifier chars and add it to the output string, the 
	//only caveat is that you need to escape the qualifier char and escape the escape char
	
	var ir,irm,ic,icm;
	
	irm = a.length;
	icm = a[0].length;
	
	for( ir = 0 ; ir < irm ; ir++ )
	{
		//append row delimiter between rows
		if( ir > 0 )
			s += sdr;
			
		for( ic = 0 ; ic < icm ; ic++ )
		{
			//append col delimiter between cols
			if( ic > 0 )
				s += sdc;
			
			//sanity check
			if( !a[ir][ic] )
				s += ""
			else
			//if any of the following occur then the string needs qualifying
			if( a[ir][ic].indexOf( sdc ) > -1		//contains col delimiter
				|| a[ir][ic].indexOf( sdr ) > -1	//contains row delimiter
				|| a[ir][ic].indexOf( sdq ) > -1	//contains qualifier char
				|| a[ir][ic].indexOf( sqq ) > -1	//contains qualifier escape char
				|| a[ir][ic].charAt(0) == " "		//leading space
				|| a[ir][ic].charAt(a[ir][ic].length-1) == " "		//trailing space
				)				
			{
				//if the escape char is a special regexp char it needs escaping into the regexp, yay!
				if( "[\\^$.|?*+()".indexOf( sqq ) > -1 )
					s += sdq + a[ir][ic].replace( new RegExp( "\\"+sqq , "g") , sqq+sqq ).replace( new RegExp( sdq , "g") , sqq+sdq ) + sdq;
				else
				//normal CSV escapes " with "", simple
				if( sqq == sdq )
					s += sdq + a[ir][ic].replace( new RegExp( sdq , "g") , sdq+sdq ) + sdq;
				//some other hair-brained scheme
				else
					s += sdq + a[ir][ic].replace( new RegExp( sqq , "g") , sqq+sqq ).replace( new RegExp( sdq , "g") , sqq+sdq ) + sdq;
			}
			//no escaping neccesary
			else
				s += a[ir][ic];
		}
	}
	
	return s;
}

//
// row manipulation
//

//insert a row into the array before the row with index idx
//
// returns new row count
//
// aRef    - Pointer to Array to manipulate
// aIns    - 1d array of row data to insert, if NULL a blank row is inserted, if Str then that is inserted in every cell
// idx     - row index to insert at, existing row at this index will be bumped along
//         - if idx == 0 then row is prepended
//         - if idx == [width] or idx == -1 then row is appended
//
function array_row_ins( aRef , aIns , idx )
{	
	//no sign of an array at all, quit
	if( !array_isArray( aRef ) )
		return 0;
	
	//not a 2d array, this is ok, assume it's an empty 2d array and insert the row as the zeroth row
	if( !array_is2dArray( aRef ) )
	{
		if( !array_isArray( aIns ) )	//for this to work aIns needs to be a 1d array
			return 0;
			
		aRef.length = 0;		//clear any existing 1d array
		aRef[0] = aIns.copy();	//easy, just copy the 1d array in as a new row
		return 1;
	}
	
	//make the original array square by padding any jagged rows we find
	var icm = array_pad( aRef , null );	
	var ir,ic;
	var irm = aRef.length;
	var inc = ( aIns && !array_isString( aIns ) ) ? aIns.length : 0;
	
	//null char to pad cells that the input array doesnt cover
	var sNull = "";
	if( array_isString( aIns ) )
		sNull = aIns;
	
	//bound, don't error
	if( idx < 0 || idx >= irm )
		idx = irm;	//allow idx to be equal to length, for appending a row
	
	//inserting a row? bump the rest along
	if( idx < irm )
	for( ir = irm ; ir > idx ; ir-- )
		aRef[ir] = aRef[ir-1];
		
	aRef[idx] = new Array();
	
	//now populate each cell in the target row
	for( ic = 0 ; ic < icm ; ic ++ )
	{
		//if aIns == NULL then insert all blank cells,
		
		//also check if the aIns array is shorter than the Original array is tall
		if( aIns && ic < inc )
			aRef[idx][ic] = aIns[ic];
		else
			aRef[idx][ic] = sNull;
	}
	
	return aRef.length;
}

// array_row_del
//
// delete a row at given index
// returns detatched row as 1d array
//
// aRef  - array to manipulate
// idx   - index of row to delete
//
function array_row_del( aRef , idx )
{	
	if( !array_is2dArray( aRef ) )
		return null;
		
	var ir,ic;
	var irm = aRef.length;
	
	//bound, don't error
	if( idx < 0 || idx >= irm )
		idx = irm - 1;			//last row
	
	//copy reference to row 1d array
	var aNew = aRef[idx];
	
	//bump the rest down
	for( ir = idx+1 ; ir < irm ; ir++ )
		aRef[ir-1] = aRef[ir];
		
	aRef.length -= 1;

	return aNew;
}

//adds a row to the end of the array
//
//returns new row count
function array_row_push( aRef , aIns )
{
	return array_row_ins( aRef , aIns , -1 )
}

//remove last row from the array
//
//returns the detached row
function array_row_pop( aRef )
{
	return array_row_del( aRef , -1 )
}

//add a row to the start of the array
//
//returns the new row count
function array_row_unshift( aRef , aIns )
{
	return array_row_ins( aRef , aIns , 0 )
}

//remove a row from the front of the array
//
//returns the shifted row
function array_row_shift( aRef )
{
	return array_row_del( aRef , 0 )
}

//
// col manipulation
//

// array_col_ins
//
// insert a col before col at index idx
//
// returns new col count
//
// aRef    - Pointer to Array to manipulate
// aIns    - 1d array of col data to insert, if NULL a blank column is inserted
// idx     - col index to insert at, existing col at this index will be bumped along
//         - if idx <= 0 then col is prepended
//         - if idx >= [width] or idx == -1 then col is appended
//
function array_col_ins( aRef , aIns , idx )
{
	//no sign of an array at all, quit
	if( !array_isArray( aRef ) )
		return 0;
	
	//not a 2d array, this is ok, assume it's an empty 2d array and insert the row as the zeroth row
	if( !array_is2dArray( aRef ) )
	{
		if( !array_isArray( aIns ) )	//for this to work aIns needs to be a 1d array
			return 0;
			
		aRef.length = 0;		//clear any existing 1d array entries
		var i;
		var im = aIns.length;
		for( i = 0 ; i < im ; i++ )
		{
			aRef[i] = new Array();
			aRef[i][0] = aIns[i];	//for a 2d array containng one column each row has one entry
		}
			
		return 1;
	}
	
	//make the array square by padding any jagged rows we find
	var icm = array_pad( aRef , null );	
	var ir,ic;
	var irm = aRef.length;
	var inr = ( aIns && !array_isString( aIns ) ) ? aIns.length : 0;
	
	//null char to pad cells that the input array doesnt cover
	var sNull = null;
	
	//overload: pass a string (or object!) to insert into every cell
	if( !array_isArray( aIns ) )
	{
		sNull = aIns;
		aIns = null;
	}
	
	//bound, don't error
	if( idx < 0 || idx > icm )
		idx = icm;	//allow idx to be equal to length, for appending a col
	
	for( ir=0 ; ir < irm ; ir++ )
	{
		//inserting a col? we need to make space by bumping the rest along
		if( idx < icm )
		for( ic = icm ; ic > idx ; ic-- )
			aRef[ir][ic] = aRef[ir][ic-1];
	
		//if aIns == NULL then insert all blank cells,
		//also check if the aIns array is shorter than the Original array is tall
		if( aIns && ir < inr )
			aRef[ir][idx] = aIns[ir];
		else
			aRef[ir][idx] = sNull;
	}
	
	return aRef[0].length;
}

//remove col at given index
//
//returns detatched col
function array_col_del( aRef , idx )
{
	if( !array_is2dArray( aRef ) )
		return null;
		
	var aOut = new Array();

	//make the array square by padding any jagged rows we find
	var icm = array_pad( aRef , null );	
	
	//bound, don't error
	if( idx < 0 || idx >= icm )
		idx = icm - 1;		//idx can only be one less than length
	
	var ir,irm;
	irm = aRef.length;
	icm = aRef.length;
	
	for( ir=0 ; ir < irm ; ir++ )
		aOut[ aOut.length ] = aRef[ir].splice( idx , 1 );

	return aOut;
}

//add a col to the end of the array
//
//returns new col count
function array_col_push( aRef , aIns )
{
	return array_col_ins( aRef , aIns , -1 );
}

//remove last col from array
//
//returns detached col
function array_col_pop( aRef )
{
	return array_col_del( aRef , -1 );
}

//add a col to the start of the array
//
//returns new col count
function array_col_unshift( aRef , aIns )
{
	return array_col_ins( aRef , aIns , 0 );
}

//remove first col from array
//
//returns detached col
function array_col_shift( aRef )
{
	return array_col_del( aRef , 0 );
}

//
// region functions
//

// 
// array_reg_copy
//
// copy a 2-d sub-array out of a master-array.
//
// the specified region need not be restricted to the bounds of the master-array,
// as if it were laid on an infinite grid. the behaviour in the out-of-bounds
// case can be switched using the bPad boolean parameter:
//
//  true : sub-array is fixed in width and height, if no cells overlap an empty array is returned.
//         e.g. copying a 3x3 sub-array from coords -2,-2 will return a 3x3 sub-array
//         with data in the bottom-right cell from the top-left of the master-array
//
// false : sub-array only contains overlapping cells, if no cells overlap NULL is returned.
//         in the above example a 1x1 array would be returned containing the single
//         overlapping cell
// 
// final note; the sub-array CAN be larger than the master-array, though this is obviously
// only useful in the bPad == true use case.
//
// returns new sub-array
//
// aRef  - master array to copy region from
// isr   - idx start row - index of row to form top left of sub-array
// isc   - idx start col - index of col to form top left of sub-array
// nsr   - num sub rows - num rows to copy (min of 1)(not zero based!)
// nsc   - num sub cols - num cols to copy (min of 1)(not zero based!)
// bPad  - out-of bounds behaviour switch, true=returned array is always nsr by ncr 
//
function array_reg_copy( aRef , isr , isc , nsr , nsc , bPad , sNull )
{
	if( !array_isArray( aRef ) )
		return 0;
		
	//empty 2d array behaviour: just return a new
	if( !array_is2dArray( aRef ) )
	{
		//padding, return a new fully empty 2d array of the desired size
		if( bPad )
			return array_new( nsr - isr , nsc - isc , sNull );
		//not padding, return a new ,but empty 2d array
		else
			return new Array();
	}
		
	
	//sanity check : has the user tried to get a zero width/height sub-array?	
	//if( nsr < 1 || nsc < 1 )
	//	return null;
	
	//get original array bounds
	var irm = aRef.length;
	var icm = array_pad( aRef , sNull );
	
	//overload NumSubRows with -1 to copy all rows up to final row
	if( nsr < 1 )
		nsr = irm - isr;
	
	//same behaviour for nsc = -1
	if( nsc < 1 )
		nsc = icm - isc;
	
	//sanity check: is our desired region inside the master-array?
	if( (isr+nsr) < 1 || (isc+nsc) < 1 || isr >= irm || isc >= icm )
	{
		//if we're padding then we're technically copying an empty region so return succesfully
		if( bPad )
			return array_new( nsr , nsc , sNull );
		else
			return null;
	}

	//if bPad is true the output array will be nr tall and nc wide
	//if false it will be however much space we have available in each direction up to that
	if( !bPad )
	{
		//region spills out bottom of array, reduce height
		if((isr + nsr) >= (irm+1))
		{
			nsr = (irm - isr);
		}
		
		//region spills out right of array, reduce width
		if((isc + nsc) >= (icm+1))
		{
			nsc = (icm - isc);
		}
		
		//region spills out top of array, only copy cells that the bottom of the "window" overlap
		if( isr < 0 )
		{
			nsr = (isr + nsr);
			isr = 0;
		}
		
		//region spills out left of array
		if( isc < 0 )
		{
			nsc = (isc + nsc);
			isc = 0;
		}
		
		//sanity check : if we aren't padding these could get adjusted to zero rows or columns
		if( nsc < 1 || nsr < 1 )
			return null;
		
	}
	
	//create output array
	var aOut = array_new( nsr , nsc , sNull );
	
	
	//populate
	
	//about 8 things happen here, first the ir and ic iterators are indexes
	//of the output array, and there's no need to iterate over cells in the
	//master-array that don't exist, so first they start off at the first
	//sub-array index that overlaps the master-array, or zero. and iterate
	//up to the last index that overlaps the master-array, or the end of the sub-array
	
	var ic,ir;	
	for( ir = (isr<0)?-isr:0 ; ir<nsr && (ir+isr)<irm ; ir++ )
		for( ic = (isc<0)?-isc:0 ; ic<nsc && (ic+isc)<icm ; ic++ )
			aOut[ir][ic] = aRef[ ir+isr ][ ic+isc ];

	return aOut;
	
}

//
// array_reg_paste
//
// paste a sub-array over an area within a master-array
//
// aRef - master-array
// aIns - sub-array to paste, or NULL to simply clear
// isr  - target top-left row index in master array
// isc  - target top-left col index in master-array
// nsr  - num sub rows to paste , can be less or more than the sub-array holds, pass -1 to do "all"
// nsc  - num sub cols to paste 
// bPad - if nsr/nsc are less than height of sub-array then paste blank cells to extend area to desired size
// bExt - if isr+nsr/isc+nsc are greater than the bounds of the master-array then extend the master array to accomodate
//

function array_reg_paste( aRef , aIns , isr , isc , nsr , nsc , bPad , bExt , sNull )
{
	if( !array_isArray( aRef ) )
		return;
		
	var ic,ir,icm,irm;
		
	//input array is empty: create a new array of the requested size
	if( !array_is2dArray( aRef ) )
	{
		if( !bExt )
			return;
		
		aRef.length = 0;
		
		//compensate for negative offsets
		irm = nsr + isr;
		icm = nsc + isc;
		
		for( ir = 0 ; ir < irm ; ir++ )
		{
			aRef[ir] = new Array();
			
			for( ic = 0 ; ic < icm ; ic++ )
			{
				aRef[ir][ic] = sNull;
			}
		}
	}
	else
	{
		//get original array bounds
		irm = aRef.length;
		icm = array_pad( aRef , sNull );
	}
	
	
	//get sub-array bounds
	var sir = 0;	//start row
	var sic = 0;	//start col
	var srm = 0;	//end row
	var scm = 0;	//end col
	
	//overload: pass aIns as a string (or null) to fill every cell	
	if( array_isString(aIns) )
		sNull = aIns
	else
	//got a sub-array to paste? get it's bounds
	if( array_is2dArray(aIns) )	
	{
		srm = aIns.length;
		scm = array_pad( aIns , sNull );
	}
	
	
	
	
	//num rows/cols not given, use bounds of sub-array
	if( nsr < 1 )
		nsr = srm;
		
	if( nsc < 1 )
		nsc = scm;
	
	//sanity check: not padding and the sub-array has no bounds, quit
	if( !bPad && (srm < 1 || scm < 1) )
		return;
		
	//extending to accomodate, so add rows/cols to master-array
	if( bExt )
	{
		var i;
		
		//bottom/right is complicated by the bPad parameter
		//the bottom-right of the pasted sub-array depends on either
		//it's bounds or the num rows/cols the user wants to paste
		if( bPad )
		{
			if( isr+nsr>irm )
			{
				i = isr+nsr;
				while( i-- > irm )
					array_row_ins( aRef , null , -1 );
			}
					
			if( isc+nsc>icm )
			{
				i = isc+nsc;
				while( i-- > icm )
					array_col_ins( aRef , null , -1 );
			}		
		}
		else
		{
			if( isr+srm>irm )
			{
				i = isr+nsr;
				while( i-- > irm )
					array_row_ins( aRef , null , -1 );
			}
					
			if( isc+scm>icm )
			{
				i = isc+nsc;
				while( i-- > icm )
					array_col_ins( aRef , null , -1 );
			}		
		}
		
		//top left is easy, just append the rows/cols as we need them
		//but remember to increase the negative ofset too
		if( isr < 0 )
		{
			do
				array_row_ins( aRef , null , 0 );
			while( ++isr < 0 )
		}
		
		if( isc < 0 )
		{
			do
				array_col_ins( aRef , null , 0 );
			while( ++isc < 0 )
		}
		 
		
	}
	else
	//not extending force bounds
	{
		//sanity check: does any part of ourdesired region fall inside the master-array?
		if( (isr+nsr) < 1 || (isc+nsc) < 1 || isr >= irm || isc >= icm )
			return;
		
		//index-start-row of master-array is negative, so to only paste the
		//bottom area that overlap set the sub-index-row start index to
		//the first overlapping row	
		if( isr < 0 )
			sir = -isr;
		
		//same principle for col	
		if( isc < 0 )
			sic = -isc;
		
		//not padding, shrink the num-rows and num-cols to the max's found
		//in the sub-array
		if( !bPad )
		{
			if( nsr > srm )
				nsr = srm;

			if( nsc > scm )
				nsc = scm;
		}
			
		//num-sub-rows to paste fall below bottom row of master array, so
		//to only paste the overlapping top rows set the num-sub-rows to
		//a value that will stop at that last row by subtracting the
		//index-start-row from the index-row-max
		if( isr+nsr > irm )
			nsr = irm-isr;
			
		//same principle for col
		if( isc+nsc > icm )
			nsc = icm-isc;
	}
		
	//should just be able to loop now, which suddenly, due to all the above
	//effort, looks incredibly dumbly simple
	for( ir = sir ; ir < nsr ; ir++ )
		for( ic = sic ; ic < nsc ; ic++ )
		{
			if( ir >= srm || ic >= scm )		//this will happen if bPad is true and/or aIns is not an array
				aRef[isr+ir][isc+ic] = sNull;
			else
				aRef[isr+ir][isc+ic] = aIns[ir][ic];
		}
	

}

//
// array_reg_clear
//
// clear the contents of the cells in the given region
//
// aRef    - array to manipulate
// isr,isc - indexes of top left of region
// nsr,nsc - num rows and cols
// sNull   - null string to insert, e.g. "" or "-"
//
function array_reg_clear( aRef , isr , isc , nsr , nsc , sNull )
{
	array_reg_paste( aRef , sNull , isr , isc , nsr , nsc , true , true , sNull)
}

//
// TRANSFORMATION FUNCTIONS
//

//
// array_trans_horiz
//
// flip contents horizontally
// 
function array_trans_horiz( aRef )
{
	if( !array_is2dArray( aRef ) )
		return;
	
	//get original array bounds
	var irm = aRef.length;
	
	var ir;
	for( ir = 0 ; ir < irm ; ir++ )
		aRef[ir].reverse();	
	
}

//
// array_trans_vert
//
// flip contents vertically
//
function array_trans_vert( aRef )
{
	if( !array_is2dArray( aRef ) )
		return;

	aRef.reverse();	
}

//
// array_trans_180
//
// rotate contents 180 degrees
//
function array_trans_180( aRef )
{
	array_trans_horiz( aRef );
	array_trans_vert( aRef );
}

//
// array_trans_left
//
// rotate contents 90 degrees anti-clockwise
//
function array_trans_left( aRef )
{
	array_flip( aRef );
	array_trans_vert( aRef );
}

//
// array_trans_right
//
// rotate contents 90 degrees clockwise
//
function array_trans_right( aRef )
{
	array_flip( aRef );
	array_trans_horiz( aRef );
}




//utility functions

//
// array_EscapeRE
//
// escapes any special regexp chars within the given string
//
function array_EscapeRE(s)
{
	return s.replace( /([.*+?^${}[]()|[\]\/\\])/g, '\\$1');
}

function array_isString(a)
{
	return a && typeof a == 'string';
}

function array_isArray(a)
{
	return a && a.constructor == Array;
}

function array_is2dArray(a)
{
	return a && (a.constructor == Array) && (a.length>0) && (a[0].constructor == Array);
}