JavaScript N-Dimentional sort





14
Date Submitted Sun. Jan. 28th, 2007 1:18 PM
Revision 1 of 1
Scripter Fordiman
Tags JavaScript | json | sort
Comments 0 comments
Flexible sorting algorithm based on Quicksort with extra functionality, such as:
- Direction (ie: ascending or descending)
- Sort-by-path (eg: item.name, item.name.firstName or item[5])
- Sorting function (returns true if two items are already sorted)
- Type checking
- All constants and support functions are members of the Sort() function
- Testsuite with hooks for cscript and in-browser javascript, so you can tweak and optimize, and make sure it still works
- Environment agnostic (can use with, say, SpiderMonkey or .Net's jsc)

function Sort(data,att,asc,fnc) {
        try {
                switch (typeof data) {
                        case 'undefined':
                                throw new Error(false,'First argument (data) is NEVER optional.');
                        case 'string':
                                var tod=1;
                                if (typeof att!='undefined'&&att!=null)
                                        throw new Error(false,'To sort a string, second argument (attribute) MUST be null or undefined.  I was passed a '+(typeof att)+'!');
                                var tmp=Array();
                                for (i=0; i<data.length; i++) tmp[i]=data.charAt(i);
                                data=tmp;
                                break;
                        case 'object':
                                if (typeof data.length == 'number') break;
                        default:
                                throw new Error(false,'First argument (data) should be of type Array or String.  I was passed a '+(typeof data)+'!');
                }
                switch (typeof att) {
                        case 'undefined': att=[]; break;
                        case 'number': case 'string': att=[att]; break;
                        case 'object':
                                if (att==null) { att=[]; break; }
                                if (typeof att.length == 'undefined')
                                        throw new Error(false, 'Second argument (attribute) must be a scalar value or array; objects are not allowed');
                                break;
                        case 'boolean':
                                att=att?1:0;
                                break;
                        default:
                                throw new Error(false, 'Second argument (attribute) must be a scalar value or array; '+(typeof att)+'s are not allowed');
                }
                switch (typeof asc) {
                        case 'boolean': break;
                        case 'undefined': asc=true; break;
                        case 'number': asc=(asc==0?false:true); break;
                        case 'string':
                                if (!isNaN(parseInt(asc))) asc=(parseInt(asc)==0?false:true);
                                else asc=(asc.indexOf('asc')==-1?false:true);
                                break;
                        case 'object':
                                if (fnc==null) { fnc=Sort.scalar; break; }
                        default:
                                throw new Error(false, 'Third argument (order) must be a scalar value; I was passed a '+(typeof att)+'!');
                }              
                switch (typeof fnc) {
                        case 'undefined': fnc=Sort.scalar;
                        case 'function': break;
                        case 'object':
                                if (fnc==null) { fnc=Sort.scalar; break; }
                        default:
                                throw new Error(false, 'Fourth argument (sort function) must be undefined, null, or a function, preferably taking two arguments.  I was passed a '+(typeof fnc)+'!');
                }
        } catch (e) {
                Sort.lastError=e.message;
                return e.number;
        }
        return Sort.process(data,att,asc,fnc,0,data.length-1,tod);
}
Sort.process = function (data,att,asc,fnc,min,max,tod) {
        if (isNaN(min)||isNaN(max))            
                throw new Error(false, 'Ok, this function will only pass itself numbers in args five and six, so you\'re the one trying to pass something else.  Bad coder!');
        var len=max-min+1;
        if (len>1) {
                var mid=min+Math.ceil(len/2)-1;
                var b1=Sort.process(data,att,asc,fnc,min,mid);
                var b2=Sort.process(data,att,asc,fnc,mid+1,max);
                var b1c, b2c;
                var ret=Array();
                var v1,v2;
                for (b1c=b2c=0; b1c<b1.length || b2c<b2.length;) {
                        if (b2c>=b2.length) ret.push(b1[b1c++]);
                        else if (b1c>=b1.length) ret.push(b2[b2c++]);
                        else if (!asc^fnc(Sort.descend(b1[b1c],att),Sort.descend(b2[b2c],att)))
                                ret.push(b1[b1c++]);
                        else ret.push(b2[b2c++]);
                }
                if (typeof tod!='undefined')
                        return ret.join('');
                return ret;
        }else{
                return [data[min]];
        }
}
//NOT FOR YOU!
Sort.descend = function (item,path) {
        if (typeof path!='object'||typeof path.length!='number')
                throw new Error(false,'Sort.descend only takes an Array as its second parameter.  Also, YOU shouldn\'t be using it.');
        for (var i=0; i<path.length; i++) {
                key=path[i];
                item=item[key];
        }
        return item;
}

//Quick testcases
Sort.testSuite = function () {
        Sort.testSuite.check('String, Normal Sorting','string','BDFHaceg',Sort('eFBcaDgH'),[]);
        Sort.testSuite.check('String, Reverse Sorting','string','gecaHFDB',Sort('eFBcaDgH',null,false),[]);
        Sort.testSuite.check('String, Insensitive Sorting','string','aBcDeFgH',Sort('eFBcaDgH',null,'asc',Sort.insensitive),[]);
        Sort.testSuite.check('Array, Normal Sorting','object','2,3,4,5,5,6,7,8',Sort([5,3,6,4,5,7,8,2]),[]);
        Sort.testSuite.check('Multidimentional Array, Normal Sorting by index 0','object','2,3,4,5,5,6,7,8',Sort([[5],[3],[6],[4],[5],[7],[8],[2]],0),[0]);
        var objTest = [
                {'test':{'one':5}},
                {'test':{'one':3}},
                {'test':{'one':6}},
                {'test':{'one':4}},
                {'test':{'one':7}},
                {'test':{'one':8}},
                {'test':{'one':2}}
        ];
        Sort.testSuite.check('Array of Objects, Normal Sorting by path test|one','object','2,3,4,5,6,7,8',Sort(objTest,['test','one']),['test','one']);
        Sort.testSuite.check(
                'Array of Objects, reverse custom Sorting by path test|one',
                'object',
                '5,3,6,4,7,8,2',
                Sort(
                        objTest,
                        ['test','one'],
                        false,
                        function (a,b) { return a^170 < b^170; }
                ),
                ['test','one']);
}              
Sort.testSuite.check = function(testName,exptype, expres, data,att) {
        var txt='';
        if (typeof data == 'string') txt+=data;
        else for (i=0; i<data.length; i++)
                txt+=(i!=0?',':'')+Sort.descend(data[i],att);
        if ((exptype==typeof data)&&(txt==expres))
                Sort.testSuite.echo(testName+' OK!');
        else {
                Sort.testSuite.echo(testName+' failed!');
                Sort.testSuite.echo('  Expected: ('+exptype+'): '+expres);
                Sort.testSuite.echo('    Actual: ('+(typeof data)+'): '+txt);
        }
}
Sort.testSuite.echo = function (txt) {
        if (WScript) return WScript.Echo(txt);
        if (window.document) {
                var X = document.getElementById('debug');
                if (X==null) {
                        X = document.createElement('div');
                        X.id='debug';
                        document.body.appendChild(X);
                }
                X.innerHTML+=txt+'<br />';
                return true;
        }
        return false;
}

//'Constants' for the user
//Use in arg 2 (path to sorted value)
Sort.noPath = null;

//Use in arg 3 (ascending/descending switch)
Sort.ascending=true;
Sort.descending=false;

//Use in arg 4 (sort function)
Sort.scalar = function (a,b) {
        return a<b;
}
Sort.insensitive = function (a,b) {
        return (a+'').toLowerCase()<(b+'').toLowerCase();
}
//If Sort() returns false, read this.
Sort.lastError='All OK';

 

Bryan Elliott

Comments

There are currently no comments for this snippet.

Voting