#!/usr/local/bin/node
var assert = require('assert');

// utils

Array.prototype.swap = function(a, b) {
    if (a == b) {
        return;
    }
    var tmp = this[a];
    this[a] = this[b];
    this[b] = tmp;
};


var produceRamdomArray = function(n, d) {
    d = d || 18;
    d = Math.pow(10, d);
    var a = [];
    while (n--) {
        var b = Math.random();
        a.push(Math.round(b*d));
    }
    return a;
};


var produceRamdomStrArray = function(n, d) {
    var set = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    var a = [];
    while (n--) {
        var dd = d;
        var s = '';
        while (dd--) {
            s += set.charAt(Math.floor(Math.random() * set.length));
        }
        a.push(s);
    }
    return a;
};


var checkSort = function(a) {
    for (var i = 0; i != a.length-1; ++i) {
        assert.ok(a[i] <= a[i+1], 'sort fail!');
    }
};


// algorithms

var findSameElements = function(a, b) {
    var ret = [];
    var i = 0;
    var j = 0;

    while (i < a.length && j < b.length) {
        if (a[i] < b[j]) {
            ++i;
        } else if (a[i] > b[j]) {
            ++j;
        } else { // a[i] == b[j]
            ret.push(a[i]);
            ++i;
            ++j;
        }
    }

    return ret;
};


var fibonacci = function(n) {
    return (n == 0 || n == 1) ? n : fibonacci(n-1) + fibonacci(n-2);
};


var find2ndMax = function(a) {
    var max = a[0];
    var secMax = Number.NEGATIVE_INFINITY;

    for (var i = 0; i != a.length; ++i) {
        if (a[i] > max) {
            secMax = max;
            max = a[i];
        } else if (a[i] < max && a[i] > secMax) {
            secMax = a[i];
        }
    }
    return secMax;
};


var maxSubseqSum = function(a) {
    var thisSum = 0;
    var maxSum = 0;
    for (var i = 0; i != a.length; ++i) {
        thisSum += a[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) { // reset to 0
            thisSum = 0;
        }
    }

    return maxSum;
};


var allRanges = function(a) {
    var exchange = function(l, r) {
        if (l == r) {
            console.log(a);
            return;
        }
        // exchange every elem to first position once
        for (var i = l; i <= r; ++i) {
            a.swap(l, i);
            exchange(l+1, r);
            a.swap(l, i);
        }
    };

    exchange(0, a.length-1);
};


var gcdAndLcm = function(a, b) {
    var c = a * b;
    while (b) {
        var temp = b;
        b = a % b;
        a = temp;
    }
    console.log('GCD:', a);
    console.log('LCM:', c/a);
};


var matrixRadio = function(n) {
    for (var i = 0; i < 2*n-1; ++i) {
        for (var j = 0; j < 2*n-1; ++j) {
            var x = Math.abs(n-1-i);
            var y = Math.abs(n-1-j);
            process.stdout.write((n-(x>=y?x:y)).toString());
        }
        process.stdout.write('\n');
    }
};


var matrixRound = function(n) {
    // init arrays
    a = [];
    for (var i = 0; i != n; ++i) {
        a[i] = [];
    }

    var round = 0;
    var m=1;

    while(m <= n*n) {
        for (var i=round; i<=n-round-1; ++i) {
            a[round][i] = m++;
        }
        for (var i=round+1; i<=n-round-1; ++i) {
            a[i][n-round-1] = m++;
        }
        for (var i=n-round-2; i>=round; --i) {
            a[n-round-1][i] = m++;
        }
        for (var i=n-round-2; i>=round+1; --i) {
            a[i][round] = m++;
        }
        round++;
    }

    return a;
};


var isPrimer = function(n) {
    var ret = false;
    if (n%2 != 0) {
        ret = true;
        for (var i = 3; i*i <= n; i += 2) {
            if (n%i == 0) {
                ret = false;
                console.log('can be dived by', i);
                break;
            }
        }
    }
};


var starDot = function(n) {
    for (var i = 0; i != n; ++i) {
        for (var j = 0; j != i; ++j) {
            process.stdout.write('*');
            for (var k = 0; k != i; ++k) {
                process.stdout.write('.');
            }
        }
        process.stdout.write('\n');
    }
};


var josephus = function(interval) {
    var a = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
    var index = -1;
    for (var i = 0; i != a.length; ++i) {
        for (var j = 0; j != interval;) { // count interval
            index = (index+1)%a.length; // move forward
            if (a[index] != 0) { // skip the outed
                ++j;
            }
        }
        a[index] = 0; // kick out
        console.log(a);
    }
};


var findMiddle = function(a, b, c) {
    var ret = c;
    if ((a-b)*(a-c) < 0) {
        ret = a;
    } else if ((b-a)*(b-c) < 0) {
        ret = b;
    }
    return ret;
};


var dec2bin = function(n) {
    var ret = 0;
    var deci = 1;
    while (n) {
        var t = n%2;
        t *= deci;
        deci *= 10;
        ret += t;
        n = Math.floor(n/2);
    }
    return ret;
};


var binarySearch = function(x) {
    var ret;
    var a = [0,1,2,3,4,5,6,7,8,9,10];
    var l = 0;
    var r = a.length-1;
    while (l <= r) {
        var t = Math.floor((l+r)/2);
        if (x > a[t]) {
            l = t + 1;
        } else if (x < a[t]) {
            r = t - 1;
        } else {
            ret = t;
            break;
        }
    }
    return ret;
};


// aka. swap sort
var bubbleSort = function(a) {
    var fin = false;
    for (var i = a.length-1; i > 0; --i) { // n-1 round
        fin = true;
        for (var j = 0; j != i; ++j) {
            if (a[j] > a[j+1]) {
                a.swap(j, j+1);
                fin = false;
            }
        }
        if (fin) { // already all sorted
            break;
        }
    }
};


var selectionSort = function(a) {
    for (var i = 0; i != a.length-1; ++i) {
        var t = i; // min pos
        // select minium to front
        for (var j = i+1; j != a.length; ++j) {
            if (a[j] < a[t]) {
                t = j;
            }
        }
        a.swap(i, t);
    }
};


var insertionSort = function(a) {
    for (var i = 1; i != a.length; ++i) {
        var t = a[i];
        // insert current a[i] to front proper pos
        for (var j = i; j > 0; --j) {
            if (a[j-1] > t) {
                a[j] = a[j-1];
            } else {
                break;
            }
        }
        a[j] = t;
    }
};


// aka. grouped insertion sort
var shellSort = function(a) {
    var d = Math.floor(a.length/2);
    while (d) {
        // insertion sort by d
        for (var i = d; i != a.length; ++i) {
            var t = a[i];
            // insert current to proper pos
            for (var j = i; j >= d; j -= d) {
                if (a[j-d] > t) {
                    a[j] = a[j-d];
                } else {
                    break;
                }
            }
            a[j] = t;
        }

        d = Math.floor(d/2);
    }
};


var mergeSort = function(a) {
    var merge = function(l, m, r) {
        var ret = [];
        var x = l;
        var y = m + 1;
        while (x <= m && y <= r) {
            if (a[x] <= a[y]) {
                ret.push(a[x]);
                ++x;
            } else {
                ret.push(a[y]);
                ++y;
            }
        }

        // concat left
        if (x > m) {
            ret = ret.concat(a.slice(y, r+1));
        } else { // y > r
            ret = ret.concat(a.slice(x, m+1));
        }

        // copy the result back
        var j = 0;
        for (var i = l; i <= r; ++i) {
            a[i] = ret[j++];
        }

        if (j != ret.length) {
            console.log('Error', ret);
        }
    }

    var sort = function(l, r) {
        if (l < r) {
            var m = Math.floor((l+r)/2);
            sort(l, m);
            sort(m+1, r);
            merge(l, m, r);
        }
    }

    sort(0, a.length-1);
};


var quickSortFirst = function(a) {
    var qs = function(l, r) {
        if (l < r) {
            var m = l; // m is the last smaller element pos (swapable)
            for (var i = l+1; i <= r; ++i) {
                if (a[i] < a[l]) { // take first a[l] as the middle value to divide
                    ++m;
                    a.swap(i, m);
                }
            }
            a.swap(l ,m); // put to middle
            qs(l, m-1); // sort left
            qs(m+1, r); // sort right
        }
    };

    qs(0, a.length-1);
};


var quickSortLast = function(a) {
    var qs = function(l, r) {
        if (l < r) {
            var m = l; // m is the first bigger element pos (swapable)
            for (var i = l; i <= r-1; ++i) {
                if (a[i] < a[r]) { // take last a[r] as the middle value to divide
                    a.swap(i, m);
                    ++m;
                }
            }
            a.swap(r ,m); // put to middle
            qs(l, m-1); // sort left
            qs(m+1, r); // sort right
        }
    };

    qs(0, a.length-1);
};


var heapSort = function(a) {
    var shiftup = function(l, r) {
        var j = r;
        while (true) {
            if (j <= l) {
                break;
            }

            // the larger the upper
            var p = Math.floor((j-1)/2); // father
            if (a[p] >= a[j]) {
                break;
            }
            a.swap(p, j);
            j = p;
        }
    };

    // build the max heap
    for (var i = 1; i < a.length; ++i) {
        // shift the last up
        shiftup(0, i);
    }

    var shiftdown = function(l, r) {
        var j = l;
        while (true) {
            var p = 2*j+1; // left child
            if (p > r) {
                break;
            }

            // find the bigger child
            if (p+1 <= r && a[p+1] > a[p]) {
                ++p;
            }
            if (a[j] >= a[p]) { // j is already the biggest among the three
                break;
            }
            a.swap(p, j);
            j = p;
        }
    };

    // find max every time and rebuild heap
    for (var i = a.length-1; i > 0; --i) {
        a.swap(0, i); // swap the max to last
        // shift first(top) down
        shiftdown(0, i-1);
    }
};


// aka. bucket sort
var radixSort = function(a) {
    // use LSD
    var d = 1;
    // get Nth digit
    var dig = function(n, i) {
        var ret = 0;
        while (i--) {
            ret = n%10;
            n = Math.floor(n/10);
        }
        return ret;
    };

    while (true) {
        var b = [];
        var go = 0;

        for (var i = 0; i != a.length; ++i) {
            var j = dig(a[i], d);
            if (b[j] == undefined) {
                b[j] = [];
            }
            b[j].push(a[i]);
            go = go || j;
        }

        if (!go) {
            break;
        }

        // collect
        a = [];
        for (var k = 0; k != b.length; ++k) {
            if (b[k] != undefined) {
                a = a.concat(b[k]);
            }
        }
        ++d;
    }

    return a;
};


var radixStrSort = function(a) {
    // use MSD, recursive forward
    var d = 0;
    var rss = function(arr, dd) {
        var b = [];
        for (var i = 0; i != arr.length; ++i) {
            // get d-th char
            var j = 0;
            if (dd < arr[i].length) {
                j = arr[i][dd].charCodeAt();
            }

            if (b[j] == undefined) {
                b[j] = [];
            }
            b[j].push(arr[i]);
        }

        //console.log(dd, b);

        arr = [];
        for (var k = 0; k != b.length; ++k) {
            // collect
            if (b[k] != undefined) {
                // recursive sort if more than 1
                if (b[k].length > 1) {
                    b[k] = rss(b[k], dd+1);
                }

                arr = arr.concat(b[k]);
            }
        }
        return arr;
    }
    a = rss(a, d);
    return a;
};


// test main
(function() {
    var ret, a;

    console.log('=== find same elements ===');
    ret = findSameElements([1,2,3,4,5,7,9,10], [3,4,7,10,12,13]);
    console.log('Result:', ret);

    console.log('=== fibonacci recursive ===');
    for (var i = 0; i <= 10; ++i) {
        console.log(fibonacci(i));
    }

    console.log('=== find 2nd max ===');
    ret = find2ndMax([7,-6,7,7,7]);
    console.log('Result:', ret);

    console.log('=== max subsequence sum ===');
    ret = maxSubseqSum([-2,11,-4,13,-5,-2,8]);
    console.log('Result:', ret);

    console.log('=== all arranges ===');
    allRanges([1,2,3,4]);

    console.log('=== Greatest Common Divisor & Least Common Multiple ===');
    gcdAndLcm(6, 9);

    console.log('=== matrix radio ===');
    matrixRadio(9);

    console.log('=== matrix round ===');
    ret = matrixRound(9);
    for (var i = 0; i != 9; ++i) {
        console.log(ret[i]);
    }

    console.log('=== star & dot ===');
    starDot(9);

    console.log('=== is primer ===');
    ret = isPrimer(437);
    console.log('Result:', ret);

    console.log('=== josephus ===');
    josephus(3);

    console.log('=== find the middle value ===');
    ret = findMiddle(1,-2,3);
    console.log('Result:', ret);

    console.log('=== decimal to binary ===');
    ret = dec2bin(9);
    console.log('Result:', ret);

    console.log('=== binary search ===');
    ret = binarySearch(8);
    console.log('Result:', ret);

    // Sorting Ref: http://en.wikipedia.org/wiki/Sorting_algorithm
    a = produceRamdomArray(10000, 6);
    console.time('=== internal sort ===');
    a.sort(function(a, b) { return a - b;}); // internal sort as number
    console.timeEnd('=== internal sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== bubble sort ===');
    bubbleSort(a);
    console.timeEnd('=== bubble sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== selection sort ===');
    selectionSort(a);
    console.timeEnd('=== selection sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== insertion sort ===');
    insertionSort(a);
    console.timeEnd('=== insertion sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== shell sort ===');
    shellSort(a);
    console.timeEnd('=== shell sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== merge sort ===');
    mergeSort(a);
    console.timeEnd('=== merge sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== quick sort first ===');
    quickSortFirst(a);
    console.timeEnd('=== quick sort first ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== quick sort last ===');
    quickSortLast(a);
    console.timeEnd('=== quick sort last ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== heap sort ===');
    heapSort(a);
    console.timeEnd('=== heap sort ===');
    checkSort(a);

    a = produceRamdomArray(10000, 6);
    console.time('=== radix sort ===');
    a = radixSort(a);
    console.timeEnd('=== radix sort ===');
    checkSort(a);

    a = produceRamdomStrArray(10000, 6);
    console.time('=== internal string sort ===');
    a.sort(); // internal sort as string
    console.timeEnd('=== internal string sort ===');
    checkSort(a);

    a = produceRamdomStrArray(10000, 6);
    //a = ['cbda','cbad','cbbb','cb','cbb','cba','abc','bac']; // special case
    console.time('=== radix string sort ===');
    a = radixStrSort(a);
    console.timeEnd('=== radix string sort ===');
    checkSort(a);
})();