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
27from __future__ import print_function
| 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
27from __future__ import print_function
|
28
29from bisect import bisect_left, bisect_right
30
31class SortedDict(dict):
32 def _get_sorted(self):
33 return getattr(self, '_sorted', sorted)
34 def _set_sorted(self, val):
35 self._sorted = val
36 self._del_keys()
37 sorted = property(_get_sorted, _set_sorted)
38
39 @property
40 def _keys(self):
41 try:
42 return self._sorted_keys
43 except AttributeError:
44 _sorted_keys = self.sorted(dict.keys(self))
45 self._sorted_keys = _sorted_keys
46 return _sorted_keys
47
48 def _left_eq(self, key):
49 index = self._left_ge(self, key)
50 if self._keys[index] != key:
51 raise KeyError(key)
52 return index
53
54 def _right_eq(self, key):
55 index = self._right_le(self, key)
56 if self._keys[index] != key:
57 raise KeyError(key)
58 return index
59
60 def _right_lt(self, key):
61 index = bisect_left(self._keys, key)
62 if index:
63 return index - 1
64 raise KeyError(key)
65
66 def _right_le(self, key):
67 index = bisect_right(self._keys, key)
68 if index:
69 return index - 1
70 raise KeyError(key)
71
72 def _left_gt(self, key):
73 index = bisect_right(self._keys, key)
74 if index != len(self._keys):
75 return index
76 raise KeyError(key)
77
78 def _left_ge(self, key):
79 index = bisect_left(self._keys, key)
80 if index != len(self._keys):
81 return index
82 raise KeyError(key)
83
84 def _del_keys(self):
85 try:
86 del self._sorted_keys
87 except AttributeError:
88 pass
89
90 def __repr__(self):
91 return 'SortedDict({%s})' % ', '.join('%r: %r' % item
92 for item in self.items())
93 def __setitem__(self, key, item):
94 dict.__setitem__(self, key, item)
95 self._del_keys()
96
97 def __delitem__(self, key):
98 dict.__delitem__(self, key)
99 self._del_keys()
100
101 def clear(self):
102 self.data.clear()
103 self._del_keys()
104
105 def copy(self):
106 t = type(self)
107 return t(self)
108
109 def keys(self):
110 return self._keys
111
112 def values(self):
113 for k in self._keys:
114 yield self[k]
115
116 def items(self):
117 for k in self._keys:
118 yield k, self[k]
119
120 def keyrange(self, start=None, end=None, inclusive=False):
121 if start is not None:
122 start = self._left_ge(start)
123
124 if end is not None:
125 if inclusive:
126 end = self._right_le(end)
127 else:
128 end = self._right_lt(end)
129
130 return iter(self._keys[start:end+1])
131
132 def valuerange(self, *args, **kwargs):
133 for k in self.keyrange(*args, **kwargs):
134 yield self[k]
135
136 def itemrange(self, *args, **kwargs):
137 for k in self.keyrange(*args, **kwargs):
138 yield k, self[k]
139
140 def update(self, *args, **kwargs):
141 dict.update(self, *args, **kwargs)
142 self._del_keys()
143
144 def setdefault(self, key, _failobj=None):
145 try:
146 return self[key]
147 except KeyError:
148 self[key] = _failobj
149
150 def pop(self, key, *args):
151 try:
152 dict.pop(self, key)
153 self._del_keys()
154 except KeyError:
155 if not args:
156 raise
157 return args[0]
158
159 def popitem(self):
160 try:
161 key = self._keys[0]
162 self._del_keys()
163 except IndexError:
164 raise KeyError('popitem(): dictionary is empty')
165 else:
166 return key, dict.pop(self, key)
167
168 @classmethod
169 def fromkeys(cls, seq, value=None):
170 d = cls()
171 for key in seq:
172 d[key] = value
173 return d
174
175if __name__ == '__main__':
176 def display(d):
177 print(d)
178 print(list(d.keys()))
179 print(list(d.keys()))
180 print(list(d.values()))
181 print(list(d.values()))
182 print(list(d.items()))
183 print(list(d.items()))
184
185 d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4)
186 display(d)
187
188 print('popitem', d.popitem())
189 display(d)
190
191 print('pop j')
192 d.pop('j')
193 display(d)
194
195 d.setdefault('a', 1)
196 d.setdefault('g', 7)
197 d.setdefault('_')
198 display(d)
199
200 d.update({'b' : 2, 'h' : 8})
201 display(d)
202
203 del d['x']
204 display(d)
205 d['y'] = 26
206 display(d)
207
208 print(repr(d))
209
210 print(d.copy())
211
212 for k,v in d.itemrange('d', 'z', inclusive=True):
213 print(k, v)
| 29
30from bisect import bisect_left, bisect_right
31
32class SortedDict(dict):
33 def _get_sorted(self):
34 return getattr(self, '_sorted', sorted)
35 def _set_sorted(self, val):
36 self._sorted = val
37 self._del_keys()
38 sorted = property(_get_sorted, _set_sorted)
39
40 @property
41 def _keys(self):
42 try:
43 return self._sorted_keys
44 except AttributeError:
45 _sorted_keys = self.sorted(dict.keys(self))
46 self._sorted_keys = _sorted_keys
47 return _sorted_keys
48
49 def _left_eq(self, key):
50 index = self._left_ge(self, key)
51 if self._keys[index] != key:
52 raise KeyError(key)
53 return index
54
55 def _right_eq(self, key):
56 index = self._right_le(self, key)
57 if self._keys[index] != key:
58 raise KeyError(key)
59 return index
60
61 def _right_lt(self, key):
62 index = bisect_left(self._keys, key)
63 if index:
64 return index - 1
65 raise KeyError(key)
66
67 def _right_le(self, key):
68 index = bisect_right(self._keys, key)
69 if index:
70 return index - 1
71 raise KeyError(key)
72
73 def _left_gt(self, key):
74 index = bisect_right(self._keys, key)
75 if index != len(self._keys):
76 return index
77 raise KeyError(key)
78
79 def _left_ge(self, key):
80 index = bisect_left(self._keys, key)
81 if index != len(self._keys):
82 return index
83 raise KeyError(key)
84
85 def _del_keys(self):
86 try:
87 del self._sorted_keys
88 except AttributeError:
89 pass
90
91 def __repr__(self):
92 return 'SortedDict({%s})' % ', '.join('%r: %r' % item
93 for item in self.items())
94 def __setitem__(self, key, item):
95 dict.__setitem__(self, key, item)
96 self._del_keys()
97
98 def __delitem__(self, key):
99 dict.__delitem__(self, key)
100 self._del_keys()
101
102 def clear(self):
103 self.data.clear()
104 self._del_keys()
105
106 def copy(self):
107 t = type(self)
108 return t(self)
109
110 def keys(self):
111 return self._keys
112
113 def values(self):
114 for k in self._keys:
115 yield self[k]
116
117 def items(self):
118 for k in self._keys:
119 yield k, self[k]
120
121 def keyrange(self, start=None, end=None, inclusive=False):
122 if start is not None:
123 start = self._left_ge(start)
124
125 if end is not None:
126 if inclusive:
127 end = self._right_le(end)
128 else:
129 end = self._right_lt(end)
130
131 return iter(self._keys[start:end+1])
132
133 def valuerange(self, *args, **kwargs):
134 for k in self.keyrange(*args, **kwargs):
135 yield self[k]
136
137 def itemrange(self, *args, **kwargs):
138 for k in self.keyrange(*args, **kwargs):
139 yield k, self[k]
140
141 def update(self, *args, **kwargs):
142 dict.update(self, *args, **kwargs)
143 self._del_keys()
144
145 def setdefault(self, key, _failobj=None):
146 try:
147 return self[key]
148 except KeyError:
149 self[key] = _failobj
150
151 def pop(self, key, *args):
152 try:
153 dict.pop(self, key)
154 self._del_keys()
155 except KeyError:
156 if not args:
157 raise
158 return args[0]
159
160 def popitem(self):
161 try:
162 key = self._keys[0]
163 self._del_keys()
164 except IndexError:
165 raise KeyError('popitem(): dictionary is empty')
166 else:
167 return key, dict.pop(self, key)
168
169 @classmethod
170 def fromkeys(cls, seq, value=None):
171 d = cls()
172 for key in seq:
173 d[key] = value
174 return d
175
176if __name__ == '__main__':
177 def display(d):
178 print(d)
179 print(list(d.keys()))
180 print(list(d.keys()))
181 print(list(d.values()))
182 print(list(d.values()))
183 print(list(d.items()))
184 print(list(d.items()))
185
186 d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4)
187 display(d)
188
189 print('popitem', d.popitem())
190 display(d)
191
192 print('pop j')
193 d.pop('j')
194 display(d)
195
196 d.setdefault('a', 1)
197 d.setdefault('g', 7)
198 d.setdefault('_')
199 display(d)
200
201 d.update({'b' : 2, 'h' : 8})
202 display(d)
203
204 del d['x']
205 display(d)
206 d['y'] = 26
207 display(d)
208
209 print(repr(d))
210
211 print(d.copy())
212
213 for k,v in d.itemrange('d', 'z', inclusive=True):
214 print(k, v)
|