Welcome, guest | Sign In | My Account | Store | Cart

A dictionary with case insensitive keys - that retains the case of the keyword. Only permits strings as keys. An alternative implementation of http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66315

Python, 257 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#  27-05-04
# v2.0.2
#

# caseless
# Featuring :

# caselessDict
# A case insensitive dictionary that only permits strings as keys.

# Implemented for ConfigObj
# Requires Python 2.2 or above

# Copyright Michael Foord
# Not for use in commercial projects without permission. (Although permission will probably be given).
# If you use in a non-commercial project then please credit me and include a link back.
# If you release the project non-commercially then let me know (and include this message with my code !)

# No warranty express or implied for the accuracy, fitness to purpose or otherwise for this code....
# Use at your own risk !!!

# E-mail fuzzyman AT atlantibots DOT org DOT uk (or michael AT foord DOT me DOT uk )
# Maintained at www.voidspace.org.uk/atlantibots/pythonutils.html


class caselessDict(dict):
    """A case insensitive dictionary that only permits strings as keys."""
    def __init__(self, indict={}):
        dict.__init__(self)
        self._keydict = {}                      # not self.__keydict because I want it to be easily accessible by subclasses
        for entry in indict:
            self[entry] = indict[entry]         # not dict.__setitem__(self, entry, indict[entry]) becasue this causes errors (phantom entries) where indict has overlapping keys... 

    def findkey(self, item):
        """A caseless way of checking if a key exists or not.
        It returns None or the correct key."""
        if not isinstance(item, str): raise TypeError('Keywords for this object must be strings. You supplied %s' % type(item))
        key = item.lower()
        try:
            return self._keydict[key]
        except:
            return None
    
    def changekey(self, item):
        """For changing the casing of a key.
        If a key exists that is a caseless match for 'item' it will be changed to 'item'.
        This is useful when initially setting up default keys - but later might want to preserve an alternative casing.
        (e.g. if later read from a config file - and you might want to write back out with the user's casing preserved).
        """
        key = self.findkey(item)           # does the key exist
        if key == None: raise KeyError(item)
        temp = self[key]
        del self[key]
        self[item] = temp
        self._keydict[item.lower()] = item
            
    def lowerkeys(self):
        """Returns a lowercase list of all member keywords."""
        return self._keydict.keys()

    def __setitem__(self, item, value):             # setting a keyword
        """To implement lowercase keys."""
        key = self.findkey(item)           # if the key already exists
        if key != None:
            dict.__delitem__(self,key)
        self._keydict[item.lower()] = item
        dict.__setitem__(self, item, value)

    def __getitem__(self, item):
        """To implement lowercase keys."""
        key = self.findkey(item)           # does the key exist
        if key == None: raise KeyError(item)
        return dict.__getitem__(self, key) 

    def __delitem__(self, item):                # deleting a keyword
        key = self.findkey(item)           # does the key exist
        if key == None: raise KeyError(item)
        dict.__delitem__(self, key)
        del self._keydict[item.lower()]

    def pop(self, item, default=None):
        """Correctly emulates the pop method."""
        key = self.findkey(item)           # does the key exist
        if key == None:
            if default == None:
                raise KeyError(item)
            else:
                return default
        del self._keydict[item.lower()]
        return dict.pop(self, key)
    
    def popitem(self):
        """Correctly emulates the popitem method."""
        popped = dict.popitem(self)
        del self._keydict[popped[0].lower()]
        return popped
    
    def has_key(self, item):
        """A case insensitive test for keys."""
        if not isinstance(item, str): return False               # should never have a non-string key
        return self._keydict.has_key(item.lower())           # does the key exist
        
    def __contains__(self, item):
        """A case insensitive __contains__."""
        if not isinstance(item, str): return False               # should never have a non-string key
        return self._keydict.has_key(item.lower())           # does the key exist

    def setdefault(self, item, default=None):
        """A case insensitive setdefault.
        If no default is supplied it sets the item to None"""
        key = self.findkey(item)           # does the key exist
        if key != None: return self[key]
        self.__setitem__(item, default)
        self._keydict[item.lower()] = item
        return default
    
    def get(self, item, default=None):
        """A case insensitive get."""
        key = self.findkey(item)           # does the key exist
        if key != None: return self[key]
        return default

    def update(self, indict):
        """A case insensitive update.
        If your dictionary has overlapping keys (e.g. 'FISH' and 'fish') then one will overwrite the other.
        The one that is kept is arbitrary."""
        for entry in indict:
            self[entry] = indict[entry]         # this uses the new __setitem__ method            

    def copy(self):
        """Create a new caselessDict object that is a copy of this one."""
        return caselessDict(self)

    def dict(self):
        """Create a dictionary version of this caselessDict."""
        return dict.copy(self)
    
    def clear(self):
        """Clear this caselessDict."""
        self._keydict = {}
        dict.clear(self)

    def __repr__(self):
        """A caselessDict version of __repr__ """
        return 'caselessDict(' + dict.__repr__(self) + ')'
    
    

    
##############################################################



# brief test stuff
if __name__ == '__main__':
    print 'caselessDict Tests'
    b = { 'FISH' : 'fish' }
    a = caselessDict(b)
    print "An apparently standard dict."
    print a
    print "a['FisH'] = ", a['FisH']
    b = {1 : 'fail'}
    print "We will now check that creating a caselessDict with an integer key fails."
    try:
        print caselessDict(b)
        print "oops - that shouldn't have worked"
    except Exception, e:
        print 'Exception : '
        print e
        print 'Good'
    print 'Testing deleting a key'
    del a['Fish']
    print "del a['Fish']\na = ", a
    a['FISH'] = 'fish'
    print 'Reset a[\'FISH\'] again and then pop the value : ', a.pop('fish')
    print 'Reset a[\'FISH\'] again and then test if it has the key : '
    a['FISH'] = 'fish'
    print 'a.has_key(\'fish\') : ', a.has_key('fish')
    print 'Let\'s test the __contains__ method by doing an if \'FiSH\' in a test :', 'FiSH' in a
    print 'setdefault, first with the keyword \'FISh\' and default of None. Then with keyword \'FROG\' and default None.'
    print a.setdefault('FISh', None)
    print a.setdefault('FROG', None)
    print a
    print 'Next get - but with keys \'FIsH\' and \'PIANO\' and default of False.'
    print a.get('FIsH', False)
    print a.get('PIANO', False)
    print 'An update - we\'ll add the key \'PIANO\'.'
    a.update({'PIANO' : ' A Piano'})
    print a
    print 'Popitem :', 
    print a.popitem()
    print a
    b = a.copy()
    b.clear()
    b['FISH'] = 'fish'
    print 'The following is a copy, then cleared (clear method), a new key added.'
    print 'We then test the type of the new dictionary...'
    print b
    print type(b)
    print 'The keys :'
    print b.keys()
    
        

"""
TODO
fromkeys returns a dict - not a caselessDict
The findkey method could be inline wherever it's used - to improve speed. (Use psyco instead - this inlines small functions !)
Could methods of caselessDict that return lists return caselessLists ? (e.g. keys)
Only allow strings or lists as values ? (This would be useful for me - but less useful for others)
If I knew how to implement iterators I could increase the speed further !!


ISSUES
If you initialise or update with a dictionary that has overlapping keys (e.g. 'FISH' and 'fish') then one entry will overwrite the other..
The one that is kept is arbitrary !



CHANGELOG

27-05-02       Version 2.0.2
Added the clear and __repr__ methods.

25-05-04       Version 2.0.1
Changed the findkey method to using a try/except test.. quicker for lookups.
*Slightly* optimised __init__ (removed duplicate type check)...

24-05-04       Version 2.0.0
Changed the way caselessDict work - it now uses an internal dict to keep track of keys
This should be *much* quicker (although still twice as slow as a standard dict !)
Added the popitems method - needed for new implementation.
Changed pop and setdefault to properly mimic dict, with the optional argument.
Added the dict method.


17-05-04       Version 1.1.1
Added the changekey method to caselessDict. Don't ask !! 

15-05-04       Version 1.1.0
Added caselessList a caseless List implementation.
Lot more work than dict actually - more methods to implement for a sequence object.
Changed module name from caselessDict to caseless.

13-05-04       Version 1.0.2
Added lowerkeys method.
Renamed _caselessfind method to 'findkey'

10-05-04       Version 1.0.1
Slight change to allow '' as a valid key.

09-05-04       Version 1.0.0
First version. Seems to work.
I don't understand __new__ but all the other keys seem to work.
popitem, keys, fromkeys etc seem to work without being explicitly defined.

"""

Now uses a second dictionary of keys _keydict This obviously increases memory use but gets rid of the 'linear' key lookup. It is now only twice as slow as an ordinary dictionary - for every lookuyp you have two, one lookup to fetch the right key and then another to do the access. A lot quicker than it was though.

Uses a try: except in the findkey function which also helps improve the speed.

Added the clear and __repr__ methods.

See also caselessList.

I'm implementing a very simple config file parser. The keywords in the config file shouldn't be case sensitive (to make it easier for the user).

I used to subclass dict and convert all keywords to lowercase - but this didn't preserve the original casing - so when writing out an updated file it lost the casing.

I now subclass caselessDict instead of dict. It also raises a TypeError if you try to use anything other than a string as a key.....

Resulting parser is very easy to use<BR>

configobj = ConfigObj(filename) # read in and parse a config file value1 = configobj['value1'] # check the values value2 = configobj['value2'] . . configobj['value3'] = value3 # change or add values configobj.write() # writing out the updated file # lot's of extra options of course See ConfigObj at http://www.voidspace.org.uk/atlantibots/pythonutils.html

This dictionary is an alternative implementation of http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66315 Missing dictionary methods are available because it subclasses dict. This means it only works with Python 2.2+ of course.

5 comments

Phillip J. Eby 19 years, 10 months ago  # | flag

This recipe is going to be incredibly slow... ...because you've obliterated the whole point of dictionaries by using a linear search in the "caseless find" operation. You might as well have used a list of (key,value) pairs, for all the value the dictionary is giving you.

If I needed a case-insensitive dictionary, but needed to preserve key case, I'd simply do something like:

aDictionary[key.lower()] = key,value

and then use aDictionary.values() (or itervalues) wherever I needed the dictionary's items. While this approach isn't a drop-in replacement for a dictionary, it's trivial to implement if you know from the beginning you need case insensitivity. And if you really need to abstract the data structure, then you can always subclass dict and still use the structure above for implementation.

Michael Foord (author) 19 years, 10 months ago  # | flag

Now only twice as slow as a dictionary. I got rid of the 'linear lookup' and replaced it with a dictionary of keys. This means it is now only twice as slow as an ordinary dictionary ! But much quicker than the previous version.

For every access it is basically two lookups, one to look up the 'real key' and one to do the access. I could implement your method in a 'drop-in' way if I explicitly defined all the iter methods (every method that did access as well - with my method I (basically) only have to implement methods that set items).

For what I need it for speed isn't a big issue anyway....

B T 19 years, 10 months ago  # | flag

right, see the other case-insensitive dictionary recipe instead. Right, that's how the other case-insensitive dictionary recipe works: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66315

Other than that, the only functional difference is that the recipe here only allows strings for keys. I.E., you can have mydict["abc"] but not mydict[3].

So right now my preference is for the other recipe, although one might update it to directly subclass dict like this recipe (although that means you cannot use it with python versions before 2.2).

Michael Foord (author) 19 years, 10 months ago  # | flag

Not the only difference....

"""the only functional difference is that the recipe here only allows strings for keys"""

In actual fact I've defined lot's of methods in my version that are simply missing in the alternative. Just subclassing dict for the alernative won't help; because of the details of the implementation - you'll need to define those methods to use the properties of dict. Mine is a drop in replacement for dictionaries.

For what I'm using it for it's *far* more useful to have an object that behaves like a dictionary than to have the slight speed improvement.

*However* I've been working on iterators and think I understand enough to implement a dictionary with my own iterator. I'll use that first to do an ordered dictionary, then I'll reimplment the caseless dictionary. I can do a version that uses the faster method but is still a drop in replacement. As I will have to redefine *almost* all the dictionary methods I might as well do all of them and then I odn't *have* to subclass dict... although in practise Python 2.2 is pretty ubiquitous - I'm using a free-host with Python on (Xennos) and thatr has Python 2.2 (and subclassing dict is useful for the isinstance test...)
Michael Foord (author) 19 years, 9 months ago  # | flag

Alternative Implementation. As I've now done a dictionary replacement with a custom iterator, http://www.voidspace.org.uk/atlantibots/pythonutils.html#odict , I could implement the suggested alternative.

In order to implement the suggested technique you need to overload all the methods that fetch values as well as set them - which is what I've done in my 'ordered dictionary'.

However - that would make doing the keys method very expensive, you would need to look up every entry and fetch the real key.

Which is faster a dictionary lookup or an index operation ? I thought there wasn't much in it ! In which case my recipe here, which does two lookups for each access will actually be about as fast as a method that does one lookup and an index for each lookup.

I think I'll leave it as it is !

Created by Michael Foord on Mon, 10 May 2004 (PSF)
Python recipes (4591)
Michael Foord's recipes (20)

Required Modules

  • (none specified)

Other Information and Tasks