sorteddict.py revision 13682
17503Snate@binkert.org# Copyright (c) 2006-2009 Nathan Binkert <nate@binkert.org> 27503Snate@binkert.org# All rights reserved. 37503Snate@binkert.org# 47503Snate@binkert.org# Redistribution and use in source and binary forms, with or without 57503Snate@binkert.org# modification, are permitted provided that the following conditions are 67503Snate@binkert.org# met: redistributions of source code must retain the above copyright 77503Snate@binkert.org# notice, this list of conditions and the following disclaimer; 87503Snate@binkert.org# redistributions in binary form must reproduce the above copyright 97503Snate@binkert.org# notice, this list of conditions and the following disclaimer in the 107503Snate@binkert.org# documentation and/or other materials provided with the distribution; 117503Snate@binkert.org# neither the name of the copyright holders nor the names of its 127503Snate@binkert.org# contributors may be used to endorse or promote products derived from 137503Snate@binkert.org# this software without specific prior written permission. 147503Snate@binkert.org# 157503Snate@binkert.org# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 167503Snate@binkert.org# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 177503Snate@binkert.org# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 187503Snate@binkert.org# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 197503Snate@binkert.org# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 207503Snate@binkert.org# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 217503Snate@binkert.org# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 227503Snate@binkert.org# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 237503Snate@binkert.org# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 247503Snate@binkert.org# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 257503Snate@binkert.org# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 267503Snate@binkert.org 2712563Sgabeblack@google.comfrom __future__ import print_function 2812563Sgabeblack@google.com 298223Snate@binkert.orgfrom bisect import bisect_left, bisect_right 308223Snate@binkert.org 317503Snate@binkert.orgclass SortedDict(dict): 327503Snate@binkert.org def _get_sorted(self): 337503Snate@binkert.org return getattr(self, '_sorted', sorted) 347503Snate@binkert.org def _set_sorted(self, val): 357503Snate@binkert.org self._sorted = val 367503Snate@binkert.org self._del_keys() 377503Snate@binkert.org sorted = property(_get_sorted, _set_sorted) 387503Snate@binkert.org 397503Snate@binkert.org @property 407503Snate@binkert.org def _keys(self): 417503Snate@binkert.org try: 427503Snate@binkert.org return self._sorted_keys 437503Snate@binkert.org except AttributeError: 447503Snate@binkert.org _sorted_keys = self.sorted(dict.iterkeys(self)) 457503Snate@binkert.org self._sorted_keys = _sorted_keys 467503Snate@binkert.org return _sorted_keys 477503Snate@binkert.org 488223Snate@binkert.org def _left_eq(self, key): 498223Snate@binkert.org index = self._left_ge(self, key) 508223Snate@binkert.org if self._keys[index] != key: 518223Snate@binkert.org raise KeyError(key) 528223Snate@binkert.org return index 538223Snate@binkert.org 548223Snate@binkert.org def _right_eq(self, key): 558223Snate@binkert.org index = self._right_le(self, key) 568223Snate@binkert.org if self._keys[index] != key: 578223Snate@binkert.org raise KeyError(key) 588223Snate@binkert.org return index 598223Snate@binkert.org 608223Snate@binkert.org def _right_lt(self, key): 618223Snate@binkert.org index = bisect_left(self._keys, key) 628223Snate@binkert.org if index: 638223Snate@binkert.org return index - 1 648223Snate@binkert.org raise KeyError(key) 658223Snate@binkert.org 668223Snate@binkert.org def _right_le(self, key): 678223Snate@binkert.org index = bisect_right(self._keys, key) 688223Snate@binkert.org if index: 698223Snate@binkert.org return index - 1 708223Snate@binkert.org raise KeyError(key) 718223Snate@binkert.org 728223Snate@binkert.org def _left_gt(self, key): 738223Snate@binkert.org index = bisect_right(self._keys, key) 748223Snate@binkert.org if index != len(self._keys): 758223Snate@binkert.org return index 768223Snate@binkert.org raise KeyError(key) 778223Snate@binkert.org 788223Snate@binkert.org def _left_ge(self, key): 798223Snate@binkert.org index = bisect_left(self._keys, key) 808223Snate@binkert.org if index != len(self._keys): 818223Snate@binkert.org return index 828223Snate@binkert.org raise KeyError(key) 838223Snate@binkert.org 847503Snate@binkert.org def _del_keys(self): 857503Snate@binkert.org try: 867503Snate@binkert.org del self._sorted_keys 877503Snate@binkert.org except AttributeError: 887503Snate@binkert.org pass 897503Snate@binkert.org 907503Snate@binkert.org def __repr__(self): 917503Snate@binkert.org return 'SortedDict({%s})' % ', '.join('%r: %r' % item 927503Snate@binkert.org for item in self.iteritems()) 937503Snate@binkert.org def __setitem__(self, key, item): 947503Snate@binkert.org dict.__setitem__(self, key, item) 957503Snate@binkert.org self._del_keys() 967503Snate@binkert.org 977503Snate@binkert.org def __delitem__(self, key): 987503Snate@binkert.org dict.__delitem__(self, key) 997503Snate@binkert.org self._del_keys() 1007503Snate@binkert.org 1017503Snate@binkert.org def clear(self): 1027503Snate@binkert.org self.data.clear() 1037503Snate@binkert.org self._del_keys() 1047503Snate@binkert.org 1057503Snate@binkert.org def copy(self): 1067503Snate@binkert.org t = type(self) 1077503Snate@binkert.org return t(self) 1087503Snate@binkert.org 1097503Snate@binkert.org def keys(self): 1107503Snate@binkert.org return self._keys[:] 1117503Snate@binkert.org 1127503Snate@binkert.org def values(self): 1137503Snate@binkert.org return list(self.itervalues()) 1147503Snate@binkert.org 1157503Snate@binkert.org def items(self): 1167503Snate@binkert.org return list(self.iteritems()) 1177503Snate@binkert.org 1187503Snate@binkert.org def iterkeys(self): 1197503Snate@binkert.org return iter(self._keys) 1207503Snate@binkert.org 1217503Snate@binkert.org def itervalues(self): 1227503Snate@binkert.org for k in self._keys: 1237503Snate@binkert.org yield self[k] 1247503Snate@binkert.org 1257503Snate@binkert.org def iteritems(self): 1267503Snate@binkert.org for k in self._keys: 1277503Snate@binkert.org yield k, self[k] 1287503Snate@binkert.org 1298223Snate@binkert.org def keyrange(self, start=None, end=None, inclusive=False): 1308223Snate@binkert.org if start is not None: 1318223Snate@binkert.org start = self._left_ge(start) 1328223Snate@binkert.org 1338223Snate@binkert.org if end is not None: 1348223Snate@binkert.org if inclusive: 1358223Snate@binkert.org end = self._right_le(end) 1368223Snate@binkert.org else: 1378223Snate@binkert.org end = self._right_lt(end) 1388223Snate@binkert.org 1398223Snate@binkert.org return iter(self._keys[start:end+1]) 1408223Snate@binkert.org 1418223Snate@binkert.org def valuerange(self, *args, **kwargs): 1428223Snate@binkert.org for k in self.keyrange(*args, **kwargs): 1438223Snate@binkert.org yield self[k] 1448223Snate@binkert.org 1458223Snate@binkert.org def itemrange(self, *args, **kwargs): 1468223Snate@binkert.org for k in self.keyrange(*args, **kwargs): 1478223Snate@binkert.org yield k, self[k] 1488223Snate@binkert.org 1497503Snate@binkert.org def update(self, *args, **kwargs): 1507503Snate@binkert.org dict.update(self, *args, **kwargs) 1517503Snate@binkert.org self._del_keys() 1527503Snate@binkert.org 1537503Snate@binkert.org def setdefault(self, key, _failobj=None): 1547503Snate@binkert.org try: 1557503Snate@binkert.org return self[key] 1567503Snate@binkert.org except KeyError: 1577503Snate@binkert.org self[key] = _failobj 1587503Snate@binkert.org 1597503Snate@binkert.org def pop(self, key, *args): 1607503Snate@binkert.org try: 1617503Snate@binkert.org dict.pop(self, key) 1627503Snate@binkert.org self._del_keys() 1637503Snate@binkert.org except KeyError: 1647503Snate@binkert.org if not args: 1657503Snate@binkert.org raise 1667503Snate@binkert.org return args[0] 1677503Snate@binkert.org 1687503Snate@binkert.org def popitem(self): 1697503Snate@binkert.org try: 1707503Snate@binkert.org key = self._keys[0] 1717503Snate@binkert.org self._del_keys() 1727503Snate@binkert.org except IndexError: 1737503Snate@binkert.org raise KeyError('popitem(): dictionary is empty') 1747503Snate@binkert.org else: 1757503Snate@binkert.org return key, dict.pop(self, key) 1767503Snate@binkert.org 1777503Snate@binkert.org @classmethod 1787503Snate@binkert.org def fromkeys(cls, seq, value=None): 1797503Snate@binkert.org d = cls() 1807503Snate@binkert.org for key in seq: 1817503Snate@binkert.org d[key] = value 1827503Snate@binkert.org return d 1837503Snate@binkert.org 1847503Snate@binkert.orgif __name__ == '__main__': 1857503Snate@binkert.org def display(d): 18612563Sgabeblack@google.com print(d) 18712563Sgabeblack@google.com print(d.keys()) 18812563Sgabeblack@google.com print(list(d.iterkeys())) 18912563Sgabeblack@google.com print(d.values()) 19012563Sgabeblack@google.com print(list(d.itervalues())) 19112563Sgabeblack@google.com print(d.items()) 19212563Sgabeblack@google.com print(list(d.iteritems())) 1937503Snate@binkert.org 1947503Snate@binkert.org d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4) 1957503Snate@binkert.org display(d) 1967503Snate@binkert.org 19712563Sgabeblack@google.com print('popitem', d.popitem()) 1987503Snate@binkert.org display(d) 1997503Snate@binkert.org 20012563Sgabeblack@google.com print('pop j') 2017503Snate@binkert.org d.pop('j') 2027503Snate@binkert.org display(d) 2037503Snate@binkert.org 2047503Snate@binkert.org d.setdefault('a', 1) 2057503Snate@binkert.org d.setdefault('g', 7) 2067503Snate@binkert.org d.setdefault('_') 2077503Snate@binkert.org display(d) 2087503Snate@binkert.org 2097503Snate@binkert.org d.update({'b' : 2, 'h' : 8}) 2107503Snate@binkert.org display(d) 2117503Snate@binkert.org 2127503Snate@binkert.org del d['x'] 2137503Snate@binkert.org display(d) 2147503Snate@binkert.org d['y'] = 26 2157503Snate@binkert.org display(d) 2167503Snate@binkert.org 21713682Sandreas.sandberg@arm.com print(repr(d)) 2187503Snate@binkert.org 21912563Sgabeblack@google.com print(d.copy()) 2208223Snate@binkert.org 2218223Snate@binkert.org for k,v in d.itemrange('d', 'z', inclusive=True): 22212563Sgabeblack@google.com print(k, v) 223