Ticket #4546: datastructures.py

File datastructures.py, 8.8 KB (added by glin@…, 8 years ago)
Line 
1class MergeDict(object):
2    """
3    A simple class for creating new "virtual" dictionaries that actualy look
4    up values in more than one dictionary, passed in the constructor.
5    """
6    def __init__(self, *dicts):
7        self.dicts = dicts
8
9    def __getitem__(self, key):
10        for dict in self.dicts:
11            try:
12                return dict[key]
13            except KeyError:
14                pass
15        raise KeyError
16
17    def __contains__(self, key):
18        return self.has_key(key)
19
20    def __copy__(self):
21        return self.__class__(*self.dicts)
22
23    def get(self, key, default=None):
24        try:
25            return self[key]
26        except KeyError:
27            return default
28
29    def getlist(self, key):
30        for dict in self.dicts:
31            try:
32                return dict.getlist(key)
33            except KeyError:
34                pass
35        raise KeyError
36
37    def items(self):
38        item_list = []
39        for dict in self.dicts:
40            item_list.extend(dict.items())
41        return item_list
42
43    def has_key(self, key):
44        for dict in self.dicts:
45            if key in dict:
46                return True
47        return False
48
49    def copy(self):
50        """ returns a copy of this object"""
51        return self.__copy__()
52
53class SortedDict(dict):
54    "A dictionary that keeps its keys in the order in which they're inserted."
55    def __init__(self, data=None):
56        if data is None: data = {}
57        dict.__init__(self, data)
58        self.keyOrder = data.keys()
59
60    def __setitem__(self, key, value):
61        dict.__setitem__(self, key, value)
62        if key not in self.keyOrder:
63            self.keyOrder.append(key)
64
65    def __delitem__(self, key):
66        dict.__delitem__(self, key)
67        self.keyOrder.remove(key)
68
69    def __iter__(self):
70        for k in self.keyOrder:
71            yield k
72
73    def items(self):
74        return zip(self.keyOrder, self.values())
75
76    def keys(self):
77        return self.keyOrder[:]
78
79    def values(self):
80        return [dict.__getitem__(self, k) for k in self.keyOrder]
81
82    def update(self, dict):
83        for k, v in dict.items():
84            self.__setitem__(k, v)
85
86    def setdefault(self, key, default):
87        if key not in self.keyOrder:
88            self.keyOrder.append(key)
89        return dict.setdefault(self, key, default)
90
91    def value_for_index(self, index):
92        "Returns the value of the item at the given zero-based index."
93        return self[self.keyOrder[index]]
94
95    def copy(self):
96        "Returns a copy of this object."
97        # This way of initializing the copy means it works for subclasses, too.
98        obj = self.__class__(self)
99        obj.keyOrder = self.keyOrder
100        return obj
101   
102    def popitem(self):
103        "Return first inserted (key, value) pair"
104        if len(self.keyOrder) == 0:
105            raise KeyError, 'popitem(): dictionary is empty'
106        key = self.keyOrder[0]
107        value = self[key]
108        self.__delitem__(key)
109        return (key, value)
110   
111    def pop(self, key, default=None):
112        if default is None:
113            value = self[key]
114        else:
115            value = self.get(key, default)
116        if self.has_key(key):
117            self.__delitem__(key)
118        return value
119       
120
121    def __repr__(self):
122        """
123        Replaces the normal dict.__repr__ with a version that returns the keys
124        in their sorted order.
125        """
126        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
127
128class MultiValueDictKeyError(KeyError):
129    pass
130
131class MultiValueDict(dict):
132    """
133    A subclass of dictionary customized to handle multiple values for the same key.
134
135    >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer']})
136    >>> d['name']
137    'Simon'
138    >>> d.getlist('name')
139    ['Adrian', 'Simon']
140    >>> d.get('lastname', 'nonexistent')
141    'nonexistent'
142    >>> d.setlist('lastname', ['Holovaty', 'Willison'])
143
144    This class exists to solve the irritating problem raised by cgi.parse_qs,
145    which returns a list for every key, even though most Web forms submit
146    single name-value pairs.
147    """
148    def __init__(self, key_to_list_mapping=()):
149        dict.__init__(self, key_to_list_mapping)
150
151    def __repr__(self):
152        return "<MultiValueDict: %s>" % dict.__repr__(self)
153
154    def __getitem__(self, key):
155        """
156        Returns the last data value for this key, or [] if it's an empty list;
157        raises KeyError if not found.
158        """
159        try:
160            list_ = dict.__getitem__(self, key)
161        except KeyError:
162            raise MultiValueDictKeyError, "Key %r not found in %r" % (key, self)
163        try:
164            return list_[-1]
165        except IndexError:
166            return []
167
168    def __setitem__(self, key, value):
169        dict.__setitem__(self, key, [value])
170
171    def __copy__(self):
172        return self.__class__(dict.items(self))
173
174    def __deepcopy__(self, memo=None):
175        import copy
176        if memo is None: memo = {}
177        result = self.__class__()
178        memo[id(self)] = result
179        for key, value in dict.items(self):
180            dict.__setitem__(result, copy.deepcopy(key, memo), copy.deepcopy(value, memo))
181        return result
182
183    def get(self, key, default=None):
184        "Returns the default value if the requested data doesn't exist"
185        try:
186            val = self[key]
187        except KeyError:
188            return default
189        if val == []:
190            return default
191        return val
192
193    def getlist(self, key):
194        "Returns an empty list if the requested data doesn't exist"
195        try:
196            return dict.__getitem__(self, key)
197        except KeyError:
198            return []
199
200    def setlist(self, key, list_):
201        dict.__setitem__(self, key, list_)
202
203    def setdefault(self, key, default=None):
204        if key not in self:
205            self[key] = default
206        return self[key]
207
208    def setlistdefault(self, key, default_list=()):
209        if key not in self:
210            self.setlist(key, default_list)
211        return self.getlist(key)
212
213    def appendlist(self, key, value):
214        "Appends an item to the internal list associated with key"
215        self.setlistdefault(key, [])
216        dict.__setitem__(self, key, self.getlist(key) + [value])
217
218    def items(self):
219        """
220        Returns a list of (key, value) pairs, where value is the last item in
221        the list associated with the key.
222        """
223        return [(key, self[key]) for key in self.keys()]
224
225    def lists(self):
226        "Returns a list of (key, list) pairs."
227        return dict.items(self)
228
229    def values(self):
230        "Returns a list of the last value on every key list."
231        return [self[key] for key in self.keys()]
232
233    def copy(self):
234        "Returns a copy of this object."
235        return self.__deepcopy__()
236
237    def update(self, *args, **kwargs):
238        "update() extends rather than replaces existing key lists. Also accepts keyword args."
239        if len(args) > 1:
240            raise TypeError, "update expected at most 1 arguments, got %d" % len(args)
241        if args:
242            other_dict = args[0]
243            if isinstance(other_dict, MultiValueDict):
244                for key, value_list in other_dict.lists():
245                    self.setlistdefault(key, []).extend(value_list)
246            else:
247                try:
248                    for key, value in other_dict.items():
249                        self.setlistdefault(key, []).append(value)
250                except TypeError:
251                    raise ValueError, "MultiValueDict.update() takes either a MultiValueDict or dictionary"
252        for key, value in kwargs.iteritems():
253            self.setlistdefault(key, []).append(value)
254
255class DotExpandedDict(dict):
256    """
257    A special dictionary constructor that takes a dictionary in which the keys
258    may contain dots to specify inner dictionaries. It's confusing, but this
259    example should make sense.
260
261    >>> d = DotExpandedDict({'person.1.firstname': ['Simon'],
262            'person.1.lastname': ['Willison'],
263            'person.2.firstname': ['Adrian'],
264            'person.2.lastname': ['Holovaty']})
265    >>> d
266    {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']},
267    '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}}
268    >>> d['person']
269    {'1': {'firstname': ['Simon'], 'lastname': ['Willison'],
270    '2': {'firstname': ['Adrian'], 'lastname': ['Holovaty']}
271    >>> d['person']['1']
272    {'firstname': ['Simon'], 'lastname': ['Willison']}
273
274    # Gotcha: Results are unpredictable if the dots are "uneven":
275    >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})
276    >>> {'c': 1}
277    """
278    def __init__(self, key_to_list_mapping):
279        for k, v in key_to_list_mapping.items():
280            current = self
281            bits = k.split('.')
282            for bit in bits[:-1]:
283                current = current.setdefault(bit, {})
284            # Now assign value to current position
285            try:
286                current[bits[-1]] = v
287            except TypeError: # Special-case if current isn't a dict.
288                current = {bits[-1] : v}
Back to Top