sorteddict.py revision 7503
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 277503Snate@binkert.orgclass SortedDict(dict): 287503Snate@binkert.org def _get_sorted(self): 297503Snate@binkert.org return getattr(self, '_sorted', sorted) 307503Snate@binkert.org def _set_sorted(self, val): 317503Snate@binkert.org self._sorted = val 327503Snate@binkert.org self._del_keys() 337503Snate@binkert.org sorted = property(_get_sorted, _set_sorted) 347503Snate@binkert.org 357503Snate@binkert.org @property 367503Snate@binkert.org def _keys(self): 377503Snate@binkert.org try: 387503Snate@binkert.org return self._sorted_keys 397503Snate@binkert.org except AttributeError: 407503Snate@binkert.org _sorted_keys = self.sorted(dict.iterkeys(self)) 417503Snate@binkert.org self._sorted_keys = _sorted_keys 427503Snate@binkert.org return _sorted_keys 437503Snate@binkert.org 447503Snate@binkert.org def _del_keys(self): 457503Snate@binkert.org try: 467503Snate@binkert.org del self._sorted_keys 477503Snate@binkert.org except AttributeError: 487503Snate@binkert.org pass 497503Snate@binkert.org 507503Snate@binkert.org def __repr__(self): 517503Snate@binkert.org return 'SortedDict({%s})' % ', '.join('%r: %r' % item 527503Snate@binkert.org for item in self.iteritems()) 537503Snate@binkert.org def __setitem__(self, key, item): 547503Snate@binkert.org dict.__setitem__(self, key, item) 557503Snate@binkert.org self._del_keys() 567503Snate@binkert.org 577503Snate@binkert.org def __delitem__(self, key): 587503Snate@binkert.org dict.__delitem__(self, key) 597503Snate@binkert.org self._del_keys() 607503Snate@binkert.org 617503Snate@binkert.org def clear(self): 627503Snate@binkert.org self.data.clear() 637503Snate@binkert.org self._del_keys() 647503Snate@binkert.org 657503Snate@binkert.org def copy(self): 667503Snate@binkert.org t = type(self) 677503Snate@binkert.org return t(self) 687503Snate@binkert.org 697503Snate@binkert.org def keys(self): 707503Snate@binkert.org return self._keys[:] 717503Snate@binkert.org 727503Snate@binkert.org def values(self): 737503Snate@binkert.org return list(self.itervalues()) 747503Snate@binkert.org 757503Snate@binkert.org def items(self): 767503Snate@binkert.org return list(self.iteritems()) 777503Snate@binkert.org 787503Snate@binkert.org def iterkeys(self): 797503Snate@binkert.org return iter(self._keys) 807503Snate@binkert.org 817503Snate@binkert.org def itervalues(self): 827503Snate@binkert.org for k in self._keys: 837503Snate@binkert.org yield self[k] 847503Snate@binkert.org 857503Snate@binkert.org def iteritems(self): 867503Snate@binkert.org for k in self._keys: 877503Snate@binkert.org yield k, self[k] 887503Snate@binkert.org 897503Snate@binkert.org def update(self, *args, **kwargs): 907503Snate@binkert.org dict.update(self, *args, **kwargs) 917503Snate@binkert.org self._del_keys() 927503Snate@binkert.org 937503Snate@binkert.org def setdefault(self, key, _failobj=None): 947503Snate@binkert.org try: 957503Snate@binkert.org return self[key] 967503Snate@binkert.org except KeyError: 977503Snate@binkert.org self[key] = _failobj 987503Snate@binkert.org 997503Snate@binkert.org def pop(self, key, *args): 1007503Snate@binkert.org try: 1017503Snate@binkert.org dict.pop(self, key) 1027503Snate@binkert.org self._del_keys() 1037503Snate@binkert.org except KeyError: 1047503Snate@binkert.org if not args: 1057503Snate@binkert.org raise 1067503Snate@binkert.org return args[0] 1077503Snate@binkert.org 1087503Snate@binkert.org def popitem(self): 1097503Snate@binkert.org try: 1107503Snate@binkert.org key = self._keys[0] 1117503Snate@binkert.org self._del_keys() 1127503Snate@binkert.org except IndexError: 1137503Snate@binkert.org raise KeyError('popitem(): dictionary is empty') 1147503Snate@binkert.org else: 1157503Snate@binkert.org return key, dict.pop(self, key) 1167503Snate@binkert.org 1177503Snate@binkert.org @classmethod 1187503Snate@binkert.org def fromkeys(cls, seq, value=None): 1197503Snate@binkert.org d = cls() 1207503Snate@binkert.org for key in seq: 1217503Snate@binkert.org d[key] = value 1227503Snate@binkert.org return d 1237503Snate@binkert.org 1247503Snate@binkert.orgif __name__ == '__main__': 1257503Snate@binkert.org def display(d): 1267503Snate@binkert.org print d 1277503Snate@binkert.org print d.keys() 1287503Snate@binkert.org print list(d.iterkeys()) 1297503Snate@binkert.org print d.values() 1307503Snate@binkert.org print list(d.itervalues()) 1317503Snate@binkert.org print d.items() 1327503Snate@binkert.org print list(d.iteritems()) 1337503Snate@binkert.org 1347503Snate@binkert.org d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4) 1357503Snate@binkert.org display(d) 1367503Snate@binkert.org 1377503Snate@binkert.org print 'popitem', d.popitem() 1387503Snate@binkert.org display(d) 1397503Snate@binkert.org 1407503Snate@binkert.org print 'pop j' 1417503Snate@binkert.org d.pop('j') 1427503Snate@binkert.org display(d) 1437503Snate@binkert.org 1447503Snate@binkert.org d.setdefault('a', 1) 1457503Snate@binkert.org d.setdefault('g', 7) 1467503Snate@binkert.org d.setdefault('_') 1477503Snate@binkert.org display(d) 1487503Snate@binkert.org 1497503Snate@binkert.org d.update({'b' : 2, 'h' : 8}) 1507503Snate@binkert.org display(d) 1517503Snate@binkert.org 1527503Snate@binkert.org del d['x'] 1537503Snate@binkert.org display(d) 1547503Snate@binkert.org d['y'] = 26 1557503Snate@binkert.org display(d) 1567503Snate@binkert.org 1577503Snate@binkert.org print `d` 1587503Snate@binkert.org 1597503Snate@binkert.org print d.copy() 160