From 76c92c3e308c13b031dfa739d51f9f1f6917bd4b Mon Sep 17 00:00:00 2001 From: Nathan Binkert Date: Wed, 21 Jul 2010 15:53:53 -0700 Subject: python: add a sorted dictionary class It would be nice if python had a tree class that would do this for real, but since we don't, we'll just keep a sorted list of keys and update it on demand. --- src/python/SConscript | 1 + src/python/m5/util/__init__.py | 1 + src/python/m5/util/sorteddict.py | 159 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 161 insertions(+) create mode 100644 src/python/m5/util/sorteddict.py diff --git a/src/python/SConscript b/src/python/SConscript index 935986a12..24a4e4d8a 100644 --- a/src/python/SConscript +++ b/src/python/SConscript @@ -58,6 +58,7 @@ PySource('m5.util', 'm5/util/jobfile.py') PySource('m5.util', 'm5/util/multidict.py') PySource('m5.util', 'm5/util/orderdict.py') PySource('m5.util', 'm5/util/smartdict.py') +PySource('m5.util', 'm5/util/sorteddict.py') SwigSource('m5.internal', 'swig/core.i') SwigSource('m5.internal', 'swig/debug.i') diff --git a/src/python/m5/util/__init__.py b/src/python/m5/util/__init__.py index e87096841..9154e73c4 100644 --- a/src/python/m5/util/__init__.py +++ b/src/python/m5/util/__init__.py @@ -39,6 +39,7 @@ from code_formatter import code_formatter from multidict import multidict from orderdict import orderdict from smartdict import SmartDict +from sorteddict import SortedDict # define this here so we can use it right away if necessary def errorURL(prefix, s): diff --git a/src/python/m5/util/sorteddict.py b/src/python/m5/util/sorteddict.py new file mode 100644 index 000000000..c91bd943d --- /dev/null +++ b/src/python/m5/util/sorteddict.py @@ -0,0 +1,159 @@ +# Copyright (c) 2006-2009 Nathan Binkert +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are +# met: redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer; +# redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution; +# neither the name of the copyright holders nor the names of its +# contributors may be used to endorse or promote products derived from +# this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +class SortedDict(dict): + def _get_sorted(self): + return getattr(self, '_sorted', sorted) + def _set_sorted(self, val): + self._sorted = val + self._del_keys() + sorted = property(_get_sorted, _set_sorted) + + @property + def _keys(self): + try: + return self._sorted_keys + except AttributeError: + _sorted_keys = self.sorted(dict.iterkeys(self)) + self._sorted_keys = _sorted_keys + return _sorted_keys + + def _del_keys(self): + try: + del self._sorted_keys + except AttributeError: + pass + + def __repr__(self): + return 'SortedDict({%s})' % ', '.join('%r: %r' % item + for item in self.iteritems()) + def __setitem__(self, key, item): + dict.__setitem__(self, key, item) + self._del_keys() + + def __delitem__(self, key): + dict.__delitem__(self, key) + self._del_keys() + + def clear(self): + self.data.clear() + self._del_keys() + + def copy(self): + t = type(self) + return t(self) + + def keys(self): + return self._keys[:] + + def values(self): + return list(self.itervalues()) + + def items(self): + return list(self.iteritems()) + + def iterkeys(self): + return iter(self._keys) + + def itervalues(self): + for k in self._keys: + yield self[k] + + def iteritems(self): + for k in self._keys: + yield k, self[k] + + def update(self, *args, **kwargs): + dict.update(self, *args, **kwargs) + self._del_keys() + + def setdefault(self, key, _failobj=None): + try: + return self[key] + except KeyError: + self[key] = _failobj + + def pop(self, key, *args): + try: + dict.pop(self, key) + self._del_keys() + except KeyError: + if not args: + raise + return args[0] + + def popitem(self): + try: + key = self._keys[0] + self._del_keys() + except IndexError: + raise KeyError('popitem(): dictionary is empty') + else: + return key, dict.pop(self, key) + + @classmethod + def fromkeys(cls, seq, value=None): + d = cls() + for key in seq: + d[key] = value + return d + +if __name__ == '__main__': + def display(d): + print d + print d.keys() + print list(d.iterkeys()) + print d.values() + print list(d.itervalues()) + print d.items() + print list(d.iteritems()) + + d = SortedDict(x=24,e=5,j=4,b=2,z=26,d=4) + display(d) + + print 'popitem', d.popitem() + display(d) + + print 'pop j' + d.pop('j') + display(d) + + d.setdefault('a', 1) + d.setdefault('g', 7) + d.setdefault('_') + display(d) + + d.update({'b' : 2, 'h' : 8}) + display(d) + + del d['x'] + display(d) + d['y'] = 26 + display(d) + + print `d` + + print d.copy() -- cgit v1.2.3