On 09 March 2005, Delaney, Timothy C (Timothy) said:
> For those who don't know, LinkedHashSet and LinkedHashMap are simply
> hashed sets and maps that iterate in the order that the keys were added
> to the set/map. I almost invariably use them for the above scenario -
> removing duplicates without changing order.
>
> Does anyone else think it would be worthwhile adding these to
> collections, or should I just make a cookbook entry?
+1 on a cookbook entry. +0 on adding to stdlib.
I'll attach another approach to the same problem, an ordered dictionary
object. I believe the semantics of adding/readding/deleting keys is the
same as java.util.LinkedHashMap -- certainly it seems the most sensible
and easy-to-implement semantics.
Greg
--
Greg Ward <[EMAIL PROTECTED]> http://www.gerg.ca/
I brought my BOWLING BALL -- and some DRUGS!!
"""
Provides odict, a subclass of the standard dict type that preserves
insertion order.
"""
__revision__ = "$Id: odict.py,v 1.1 2004/03/09 02:32:08 gward Exp $"
class odict(dict):
"""
An order-preserving mapping: lookup works like a dictionary, but
keys(), values(), items(), etc. all return items in order of
insertion. (Resetting a key preserves order; deleting a key and
re-adding it moves it to the end.)
Don't use this for enormous dictionaries, since it increases the
memory use of the whole object, and the worst-case runtime for many
common operations is O(N) rather than O(1).
"""
def __init__(self, arg=None):
super(odict, self).__init__()
self.order = []
if isinstance(arg, dict):
self.update(arg)
def copy(self):
return self.__class__(self)
def __delitem__(self, key):
dict.__delitem__(self, key)
self.order.remove(key)
def __iter__(self):
return iter(self.order)
def __setitem__(self, key, value):
add = key not in self
dict.__setitem__(self, key, value)
if add:
self.order.append(key)
def items(self):
return [(key, self[key]) for key in self.order]
def keys(self):
return self.order
def values(self):
return [self[key] for key in self.order]
def iteritems(self):
for key in self.order:
yield (key, self[key])
iterkeys = __iter__
def itervalues(self):
for key in self.order:
yield self[key]
def clear(self):
dict.clear(self)
self.order.clear()
def popitem(self):
"""
Remove and return the most-recently-added item of the mapping.
"""
key = self.order.pop()
value = self[key]
dict.__delitem__(self, key)
return value
def setdefault(self, key, value=None):
if key in self:
return self[key]
else:
self[key] = value
return value
def update(self, other):
for key in other:
self[key] = other[key]
if __name__ == "__main__":
m = odict()
m['foo'] = 43
m['bar'] = 'barf'
m[42] = None
print m.items()
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
