comparing lists

[jepler at unpythonic.net]

def compare_with_dict(l, m):
    d = {}
    if len(l) != len(m): return 0 # Cannot be equal (?)
    for i in l: d[i.lower()] = 0
    for i in m:
	if i.lower() not in d: return 0 # Proven unequal
    return 1

Setting a key in a dict and checking for a key in dict ('d.has_key(k)' in
older versions of Python) are supposed to be constant-time operations, so
this is O(len(l) + len(m)) to run.

Your versions either use sort (O(n lg n)) or 'in' with lists (O(n^2)),
so this one should perform better than the original.

However, you might want to use the dict-representation all the time.  It'd
save you the cost of the copy.  If the original case is sometimes
important, you might store the key as the lowercase version with the value
as the original case (eg l['studlycaps'] == 'StUdLyCaPs')

>>> t = CaseInsensitiveSet()
>>> u = CaseInsensitiveSet()
>>> print t == u
1
>>> t.add('a')
>>> u.add('B')
>>> print t == u
0
>>> t.add('b')
>>> u.add('a')
>>> print t, `u`, u['b'], u['B']
<Set a b> <Set 'a' 'b'> B B
>>> print t == u
1
>>> u.remove('b')
>>> print t == u
0
>>> t.remove('b')
>>> print t == u
1

Here's an implementation for 2.2 (tested against 2.3a0 CVS):

class CaseInsensitiveSet(dict):
    def __setitem__(self, item, value):
        item = item.lower()
        super(CaseInsensitiveSet, self).__setitem__(item, value)

    def __getitem__(self, item):
        item = item.lower()
        return super(CaseInsensitiveSet, self).__getitem__(item)

    def add(self, item):
        self[item] = item

    def remove(self, item):
        del self[item]

    def __eq__(self, other):
        for k in self:
            if not k in other: return 0
        return 1
	# for sk, ok in zip(self, other): 
	#     if sk != ok: return 0
	# return 

    def __str__(self):
        return "<Set %s>" % " ".join(self)

    def __repr__(self):
        return "<Set %s>" % " ".join(map(repr, self))