/*

Please send corrections, questions and suggestions to:
    Alexander Kasiukov <kasiuka@sunysuffolk.edu>

These functions are mostly concerned with combinatorics of combinations, permutations and 
    the statistics of the Mann-Whitney U test.
Probably should be broken apart.

Uses: "common.js", "dynamic.js", "distributions.js", "storage.js"

*/

//--------------------------- U Test Basic Utilities -------------------------------------------

function WilcoxonMannWhitneyTest( givenFirstSample, givenSecondSample )
{
    this.A = givenFirstSample;
    this.B = givenSecondSample;
    this.nA = givenFirstSample.length;
    this.nB = givenSecondSample.length;
    this.ties = 0;
    this.A_below_B = 0;
    this.A_above_B = 0;
    this.computeUStatistic = function()
        {
            for( var i = 0; i < this.nA; i++ )
            {
                for( var j = 0; j < this.nB; j++ )
                {
                    if( this.A[ i ] < this.B[ j ] ) this.A_below_B++;
                    else if( this.A[ i ] > this.B[ j ] ) this.A_above_B++;
                    else this.ties++;
                }
            }
        }
    this.computeNormalApproximation = function()
        {
            var product = this.nA * this.nB;
            var sum = this.nA + this.nB;

            this.mean = product / 2;
            this.deviation = Math.sqrt( product * ( sum + 1 ) / 12 );

            this.zA = Math.abs( standardize( this.A_below_B , this.mean, this.deviation ) );
            this.pzA = twoTailStandardNormal( this.zA );

            this.zB = Math.abs( standardize( this.A_above_B , this.mean, this.deviation ) );
            this.pzB = twoTailStandardNormal( this.zB );
        };
    this.computeNoTiesP = function()
        {
            var myExtremeCount = 0;
            var mySplicings = generateUntiedSplicings( this.nA, this.nB );
            var myProduct = this.nA * this.nB;
            function countOrderedPairs( n ){ return n * ( n - 1 ) / 2; };

            for( var i = 0; i < mySplicings.length; i++ )
            {
                var myWilcoxonRankA = 0;
                var myWilcoxonRankB = 0;
                for( var j = 0; j < mySplicings[ i ].length; j++ )
                {
                    if( mySplicings[ i ][ j ] == 0 ) myWilcoxonRankA += j + 1;
                    else if( mySplicings[ i ][ j ] == 1 ) myWilcoxonRankB += j + 1;
                    else alert( "Something is wrong: ranks are tied" );
                }
                var myResult = 
                    {
                        'A_below_B': myProduct + countOrderedPairs( this.nA + 1 ) - myWilcoxonRankA,
                        'A_above_B': myProduct + countOrderedPairs( this.nB + 1 ) - myWilcoxonRankB
                    };
                if( firstMoreExtreme( myResult, this ) ) myExtremeCount++;
            }
            this.p = myExtremeCount / mySplicings.length;
        }
    this.computeExactP = function()
        {
            var myStorage = makeWilcoxonMannWhitneyStorage( this );
            enumeratePossibleRankings( this.nA, this.nB, myStorage );
            this.p = myStorage.content();
        }
    this.computeUStatistic();
}
function enumeratePossibleRankings( givenSizeA, givenSizeB, givenStorage )
{
    var myResult = [];
    var myTotalSize = givenSizeA + givenSizeB;
    var myArray = constructArray( myTotalSize, function ( x ) { return x; } );   
    var myPartitions = generateSetPartitions( myArray.slice() );              
    
    for( var i = 0; i < myPartitions.length; i++ )
    {
        var myPartition = myPartitions[ i ];
        generatePermutations( myPartition, givenStorage );
        var myPermutations = givenStorage.content();
    }
}
function createTestFromRankings( givenOrderedPartition, givenAsize )
{
    var mySampleA = [];
    var mySampleB = [];
    for( var i = 0; i < givenOrderedPartition.length; i++ )
    {   
        var myTiedRanks = givenOrderedPartition[ i ];
        for( var j = 0; j < myTiedRanks.length; j++ )
        {
            if( myTiedRanks[ j ] < givenAsize ) mySampleA[ myTiedRanks[ j ] ] = i;
            else mySampleB[ myTiedRanks[ j ] ] = i;
        }
    }
    return new WilcoxonMannWhitneyTest( mySampleA, mySampleB );
}
function firstMoreExtreme( firstTest, secondTest )
{
    function myMin( a, b ){ return ( a < b )? a : b; };
    function myMax( a, b ){ return ( a > b )? a : b; };
    var firstMin = myMin( firstTest.A_below_B, firstTest.A_above_B );
    var secondMin = myMin( secondTest.A_below_B, secondTest.A_above_B ); 
    var firstMax = myMax( firstTest.A_below_B, firstTest.A_above_B );
    var secondMax = myMax( secondTest.A_below_B, secondTest.A_above_B ); 
    return ( firstMin < secondMin || firstMax > secondMax );
}
function makeWilcoxonMannWhitneyStorage( givenTest )
{
    return new function ()
    {
        var myTotalCount = 0;
        var myExtremeCount = 0;
        this.content = function ()
            {
                return ( myTotalCount == 0 )? 0 : myExtremeCount / myTotalCount;
            }
        this.store = function ( givenArray )
            {
                myTotalCount++;   
                var myTest = createTestFromRankings( givenArray, givenTest.nA );
                var myMessage = listRecursiveArray( givenArray );
                if( firstMoreExtreme( myTest, givenTest ) )
                {
                    myExtremeCount++;
                    myMessage += ", more extreme";
                }
                //alert( myMessage );
            }
        this.count = function()
            {
                return myTotalCount;
            }
    }
}


//-------------- How to compute the exact statistic in the absence of ties ------------------

/*

Suppose we have two samples with nA and nB data points in each. Assume further that there are no two 
equal data points (i.e. there are no two ties, between the samples and within the samples).

If the null hypothesis is true, then every permutation of (nA + nB) is equally likely. 
There are (nA + nB)! permutations of these data points. Since a permutation within each sample does not
affect the U statistic, we can assume that the order of the ranking within each sample is fixed and
the problem becomes enumerating all the splicings of two linearly ordered sets. 
There are (nA + nB)! /( nA! * nB! ) of such splicings. We can compute the U statistic for each one of them

Is it true that U statistic in this case determines the splicing?
*/






// ----------- experimental computation of exact statistic, probably wrong and definitely inefficient --------

// Not used anymore


function MannWhitneyOld( sizeA, sizeB )
{
    var myPartitionsA = generateNumberPartitions( sizeA );
    var myPartitionsB = generateNumberPartitions( sizeB );
        
    var myMessage = '';
    for( var i = 0; i < myPartitionsA.length; i++ )
    {
        for( var j = 0; j < myPartitionsB.length; j++ )
        {
            var myStorageA = new ArrayOfArraysStorage(); 
            var myStorageB = new ArrayOfArraysStorage();
            
            myMessage += "Need to permute [" 
                        + myPartitionsA[ i ].join(", ") + "] and ["  
                            + myPartitionsB[ j ].join(", ") + "]<br/>";
                            
            generatePermutations( myPartitionsA[ i ], myStorageA );
            generatePermutations( myPartitionsB[ j ], myStorageB );
            
            var myA = myStorageA.content();
            var myB = myStorageB.content();
            
            for( var k = 0; k < myStorageA.count(); k++ )
            {
                for( var l = 0; l < myStorageB.count(); l ++ )
                {
                    myMessage += "<dd />Need to splice [" 
                        + ( myA[ k ]).join("+") + "] and ["  
                            + ( myB[ l ]).join("+") + "]<br/>";
                    myMessage += listTiedSplicings( generateTiedSplicings( ( myA[ k ]).length, ( myB[ l ]).length ) );
                }
            }
            
        }
    }
    return myMessage;
}
////document.write( MannWhitneyOld( 3, 4 ) );