CODEWITHSUNDEEP
javascriptcomparison
abl
abl

Reputation: 5968

Is there a total order on JavaScript objects?

The title pretty much says it all. Does JavaScript guarantee a total order on objects when using the <, >, <= and >= operators?

I wrote some code just to check total ordering on some objects. The result is consistent with total ordering, but that doesn't prove anything:

function thereIsTotalOrder(items){

    var one, other, theThird;

    // warning: n^3 complexity follows

    // If a <= b and b <= a then a = b (antisymmetry);
    for(var i=0; i<items.length; i++){
        for(var j=0; j<items.length; j++){
            one = items[i];
            other = items[j];
            if((one <= other) && (other <= one) && (one != other)){
                return false;
            }
        }
    }

    // If a <= b and b <= c then a <= c (transitivity)
    for(var i=0; i<items.length; i++){
        for(var j=0; j<items.length; j++){
            for(var k=0; k<items.length; k++){
                one = items[i];
                other = items[j];
                theThird = items[k];
                if((one <= other) && (other <= theThird) && !(one <= theThird)) {
                    return false;
                }
            }
        }
    }

    // a <= b or b <= a (totality). 
    for(var i=0; i<items.length; i++){
        for(var j=0; j<items.length; j++){
            one = items[i];
            other = items[j];
            if(!((one <= other) || (other <= one))) {
                return false;
            }
        }
    }

    return true;
}

function a(){};
function b(){};
var c = "foo";
var d = "bar";
var e = "bar";
var f = function(){};
var g = {name : "bananas"};

console.log(thereIsTotalOrder([a, b, c, d, e, f, g])); // prints "true"

Upvotes: 3

Views: 362

Answers (1)

Hunan Rostomyan
Hunan Rostomyan

Reputation: 2176

Depends on what objects we're considering. If we confine our attention to the class of numbers, then yes, the order will be total. As your example demonstrates, the same can be said of (at least some) strings. But totality doesn't seem to hold generally.

For instance, if you add var h = 5; to your declarations and then add h to your thereIsTotalOrder call, you will get a false. That's because in a state where h = 5 and c = 'foo', (h ≤ c ∨ c ≤ h) is false (which means that totality is not satisfied).

As you rightly noted, while the absence of a false value returned by thereIsTotalOrder doesn't prove that all objects are totally ordered, the presence of a false value does prove that the order (if defined) between all objects is not total.

Upvotes: 3

Related Questions