How to assert two list with dicts without order?

everyone. I recently switch from python 2 to 3.5.1 and there was an assert function, which I cannot rewrite.

def assertEqualUnordered(self, data1, data2):
    """
    compare that data are similar
    i.e.:
    [d1, d2] == [d2, d1]
    or
    {'a': [d1, d2]} == {'a': [d2, d1]}
    or
    [{'a': [d1, d2]}, {'b': [d3, d4]}] == [{'b': [d4, d3]}, {'a': [d2, d1]}]
    """
    if isinstance(data1, list) or isinstance(data1, tuple):
        self.assertEqual(len(data1), len(data2))
        for d1, d2 in zip(sorted(data1), sorted(data2)):
            self.assertEqualUnordered(d1, d2)
    elif isinstance(data1, dict):
        data1_keys = sorted(data1.keys())
        data2_keys = sorted(data2.keys())
        self.assertListEqual(data1_keys, data2_keys)
        for key in data1_keys:
            self.assertEqualUnordered(data1[key], data2[key])
    else:
        self.assertEqual(data1, data2)

In general this code works normal, but if d1 and d2 are dicts, than I've got:

TypeError: unorderable types: dict() < dict()

How can I rewrite it to work in py3k?

EDIT 1: Simplify code example:

def assertEqualUnordered(data1, data2):
    assert len(data1) == len(data2)
    for d1, d2 in zip(sorted(data1), sorted(data2)):
        assert d1 == d2

data1 = [{'a': 'a'}, {'b': 'b'}]
data2 = [{'b': 'b'}, {'a': 'a'}]
assertEqualUnordered(data1, data2)

Solution

I'm not sure whether this is the easiest way to do it, but you could make the sort work by resurrecting the cmp function that Python 3 removed. Something along these lines:

def cmp(lhs, rhs):
    try:
        if lhs == rhs:
            return 0
        elif lhs < rhs:
            return -1
        else:
            return 1
    except TypeError:
        if isinstance(lhs, dict) and isinstance(rhs, dict):
            return dict_cmp(lhs, rhs)
        raise

For the implementation of dict_cmp see Is there a description of how __cmp__ works for dict objects in Python 2?

Once you have your cmp function, you can do sorted(data1, key = functools.cmp_to_key(cmp)).

This still isn't complete, because I haven't tried to cover mixed-type comparisons, which would come up for example if you passed in [{'a' : 'b'}, ['a']] as one of the objects. But hopefully I've provided a direction to go in.

An alternative is to fall back to an O(n^2) algorithm, which would be in effect agreeing with Python3's opinion that dictionaries do not have an order. Instead of sorting the lists and then comparing them for equality, take each item on the left in turn and search for an item on the right that is equal to it (with removal to ensure that the count is the same on both sides, since you don't want to falsely claim that [x, x, y] is equal to [x, y, y]).

Btw, not really necessary to the answer but I noticed that your current code would say that ['a', 'b'] is equal unordered to {'a' : 'foo', 'b' : 'bar'}, but only if the list is on the left and the dictionary on the right. If you passed them in the other way around you'd get an exception when the code tries to call keys() on the list. This might need addressing, depending what you're planning to pass in ;-)