sorteddict.py revision 13709
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: 4413709Sandreas.sandberg@arm.com _sorted_keys = self.sorted(dict.keys(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 9213709Sandreas.sandberg@arm.com for item in self.items()) 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): 11013709Sandreas.sandberg@arm.com return self._keys 1117503Snate@binkert.org 1127503Snate@binkert.org def values(self): 1137503Snate@binkert.org for k in self._keys: 1147503Snate@binkert.org yield self[k] 1157503Snate@binkert.org 11613709Sandreas.sandberg@arm.com def items(self): 1177503Snate@binkert.org for k in self._keys: 1187503Snate@binkert.org yield k, self[k] 1197503Snate@binkert.org 1208223Snate@binkert.org def keyrange(self, start=None, end=None, inclusive=False): 1218223Snate@binkert.org if start is not None: 1228223Snate@binkert.org start = self._left_ge(start) 1238223Snate@binkert.org 1248223Snate@binkert.org if end is not None: 1258223Snate@binkert.org if inclusive: 1268223Snate@binkert.org end = self._right_le(end) 1278223Snate@binkert.org else: 1288223Snate@binkert.org end = self._right_lt(end) 1298223Snate@binkert.org 1308223Snate@binkert.org return iter(self._keys[start:end+1]) 1318223Snate@binkert.org 1328223Snate@binkert.org def valuerange(self, *args, **kwargs): 1338223Snate@binkert.org for k in self.keyrange(*args, **kwargs): 1348223Snate@binkert.org yield self[k] 1358223Snate@binkert.org 1368223Snate@binkert.org def itemrange(self, *args, **kwargs): 1378223Snate@binkert.org for k in self.keyrange(*args, **kwargs): 1388223Snate@binkert.org yield k, self[k] 1398223Snate@binkert.org 1407503Snate@binkert.org def update(self, *args, **kwargs): 1417503Snate@binkert.org dict.update(self, *args, **kwargs) 1427503Snate@binkert.org self._del_keys() 1437503Snate@binkert.org 1447503Snate@binkert.org def setdefault(self, key, _failobj=None): 1457503Snate@binkert.org try: 1467503Snate@binkert.org return self[key] 1477503Snate@binkert.org except KeyError: 1487503Snate@binkert.org self[key] = _failobj 1497503Snate@binkert.org 1507503Snate@binkert.org def pop(self, key, *args): 1517503Snate@binkert.org try: 1527503Snate@binkert.org dict.pop(self, key) 1537503Snate@binkert.org self._del_keys() 1547503Snate@binkert.org except KeyError: 1557503Snate@binkert.org if not args: 1567503Snate@binkert.org raise 1577503Snate@binkert.org return args[0] 1587503Snate@binkert.org 1597503Snate@binkert.org def popitem(self): 1607503Snate@binkert.org try: 1617503Snate@binkert.org key = self._keys[0] 1627503Snate@binkert.org self._del_keys() 1637503Snate@binkert.org except IndexError: 1647503Snate@binkert.org raise KeyError('popitem(): dictionary is empty') 1657503Snate@binkert.org else: 1667503Snate@binkert.org return key, dict.pop(self, key) 1677503Snate@binkert.org 1687503Snate@binkert.org @classmethod 1697503Snate@binkert.org def fromkeys(cls, seq, value=None): 1707503Snate@binkert.org d = cls() 1717503Snate@binkert.org for key in seq: 1727503Snate@binkert.org d[key] = value 1737503Snate@binkert.org return d 1747503Snate@binkert.org 1757503Snate@binkert.orgif __name__ == '__main__': 1767503Snate@binkert.org def display(d): 17712563Sgabeblack@google.com print(d) 17813709Sandreas.sandberg@arm.com print(list(d.keys())) 17913709Sandreas.sandberg@arm.com print(list(d.keys())) 18013709Sandreas.sandberg@arm.com print(list(d.values())) 18113709Sandreas.sandberg@arm.com print(list(d.values())) 18213709Sandreas.sandberg@arm.com print(list(d.items())) 18313709Sandreas.sandberg@arm.com print(list(d.items())) 1847503Snate@binkert.org 1857503Snate@binkert.org d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4) 1867503Snate@binkert.org display(d) 1877503Snate@binkert.org 18812563Sgabeblack@google.com print('popitem', d.popitem()) 1897503Snate@binkert.org display(d) 1907503Snate@binkert.org 19112563Sgabeblack@google.com print('pop j') 1927503Snate@binkert.org d.pop('j') 1937503Snate@binkert.org display(d) 1947503Snate@binkert.org 1957503Snate@binkert.org d.setdefault('a', 1) 1967503Snate@binkert.org d.setdefault('g', 7) 1977503Snate@binkert.org d.setdefault('_') 1987503Snate@binkert.org display(d) 1997503Snate@binkert.org 2007503Snate@binkert.org d.update({'b' : 2, 'h' : 8}) 2017503Snate@binkert.org display(d) 2027503Snate@binkert.org 2037503Snate@binkert.org del d['x'] 2047503Snate@binkert.org display(d) 2057503Snate@binkert.org d['y'] = 26 2067503Snate@binkert.org display(d) 2077503Snate@binkert.org 20813682Sandreas.sandberg@arm.com print(repr(d)) 2097503Snate@binkert.org 21012563Sgabeblack@google.com print(d.copy()) 2118223Snate@binkert.org 2128223Snate@binkert.org for k,v in d.itemrange('d', 'z', inclusive=True): 21312563Sgabeblack@google.com print(k, v) 214