sorteddict.py revision 7503:37da2c208f5f 
1# Copyright (c) 2006-2009 Nathan Binkert <nate@binkert.org>
2# All rights reserved.
3#
4# Redistribution and use in source and binary forms, with or without
5# modification, are permitted provided that the following conditions are
6# met: redistributions of source code must retain the above copyright
7# notice, this list of conditions and the following disclaimer;
8# redistributions in binary form must reproduce the above copyright
9# notice, this list of conditions and the following disclaimer in the
10# documentation and/or other materials provided with the distribution;
11# neither the name of the copyright holders nor the names of its
12# contributors may be used to endorse or promote products derived from
13# this software without specific prior written permission.
14#
15# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27class SortedDict(dict):
28    def _get_sorted(self):
29        return getattr(self, '_sorted', sorted)
30    def _set_sorted(self, val):
31        self._sorted = val
32        self._del_keys()
33    sorted = property(_get_sorted, _set_sorted)
34
35    @property
36    def _keys(self):
37        try:
38            return self._sorted_keys
39        except AttributeError:
40            _sorted_keys = self.sorted(dict.iterkeys(self))
41            self._sorted_keys = _sorted_keys
42            return _sorted_keys
43
44    def _del_keys(self):
45        try:
46            del self._sorted_keys
47        except AttributeError:
48            pass
49
50    def __repr__(self):
51        return 'SortedDict({%s})' % ', '.join('%r: %r' % item
52                                              for item in self.iteritems())
53    def __setitem__(self, key, item):
54        dict.__setitem__(self, key, item)
55        self._del_keys()
56
57    def __delitem__(self, key):
58        dict.__delitem__(self, key)
59        self._del_keys()
60
61    def clear(self):
62        self.data.clear()
63        self._del_keys()
64
65    def copy(self):
66        t = type(self)
67        return t(self)
68
69    def keys(self):
70        return self._keys[:]
71
72    def values(self):
73        return list(self.itervalues())
74
75    def items(self):
76        return list(self.iteritems())
77
78    def iterkeys(self):
79        return iter(self._keys)
80
81    def itervalues(self):
82        for k in self._keys:
83            yield self[k]
84
85    def iteritems(self):
86        for k in self._keys:
87            yield k, self[k]
88
89    def update(self, *args, **kwargs):
90        dict.update(self, *args, **kwargs)
91        self._del_keys()
92
93    def setdefault(self, key, _failobj=None):
94        try:
95            return self[key]
96        except KeyError:
97            self[key] = _failobj
98
99    def pop(self, key, *args):
100        try:
101            dict.pop(self, key)
102            self._del_keys()
103        except KeyError:
104            if not args:
105                raise
106            return args[0]
107
108    def popitem(self):
109        try:
110            key = self._keys[0]
111            self._del_keys()
112        except IndexError:
113            raise KeyError('popitem(): dictionary is empty')
114        else:
115            return key, dict.pop(self, key)
116
117    @classmethod
118    def fromkeys(cls, seq, value=None):
119        d = cls()
120        for key in seq:
121            d[key] = value
122        return d
123
124if __name__ == '__main__':
125    def display(d):
126        print d
127        print d.keys()
128        print list(d.iterkeys())
129        print d.values()
130        print list(d.itervalues())
131        print d.items()
132        print list(d.iteritems())
133
134    d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4)
135    display(d)
136
137    print 'popitem', d.popitem()
138    display(d)
139
140    print 'pop j'
141    d.pop('j')
142    display(d)
143
144    d.setdefault('a', 1)
145    d.setdefault('g', 7)
146    d.setdefault('_')
147    display(d)
148
149    d.update({'b' : 2, 'h' : 8})
150    display(d)
151
152    del d['x']
153    display(d)
154    d['y'] = 26
155    display(d)
156
157    print `d`
158
159    print d.copy()
160