Hash map with multiple keys per value ?

Tom Anderson twic at urchin.earth.li
Sun Nov 13 05:10:09 CET 2005


On Fri, 11 Nov 2005, Chris Stiles wrote:

> Is there an easier and cleaner way of doing this ?  Is there example 
> code floating around that I might have a look at ?

I'm not aware of a way which can honestly be called better.

However, i do feel your pain about representing the alias relationships 
twice - it feels wrong. Therefore, i offer you an alternative 
implementation - represent each set as a linked list, threaded through a 
dict by making the value the dict holds under each key point to the next 
key in the alias set. Confused? No? You will be ...

class Aliases(object):
 	def __init__(self, aliases=None):
 		self.nexts = {}
 		if (aliases != None):
 			for key, value in aliases:
 				self[key] = value
 	def __setitem__(self, key, value):
 		if ((value != None) and (value != key)):
 			self.nexts[key] = self.nexts[value]
 			self.nexts[value] = key
 		else:
 			self.nexts[key] = key
 	def __getitem__(self, key):
 		return list(follow(key, self.nexts))
 	def __delitem__(self, key):
 		cur = key
 		while (self.nexts[cur] != key):
 			cur = self.nexts[cur]
 		if (cur != key):
 			self.nexts[cur] = self.nexts[key]
 		del self.nexts[key]
 	def canonical(self, key):
 		canon = key
 		for cur in follow(key, self.nexts):
 			if (cur < canon):
 				canon = cur
 		return canon
 	def iscanonical(self, key):
 		for cur in follow(key, self.nexts):
 			if (cur < key):
 				False
 		return True
 	def iteraliases(self, key):
 		cur = self.nexts[key]
 		while (cur != key):
 			yield cur
 			cur = self.nexts[cur]
 	def __iter__(self):
 		return iter(self.nexts)
 	def itersets(self):
 		for key in self.nexts:
 			if (not isprimary(key, self.nexts)):
 				continue
 			yield [key] + self[key]
 	def __len__(self):
 		return len(self.nexts)
 	def __contains__(self, key):
 		return key in self.nexts
 	def __str__(self):
 		return "<Aliases " + str(list(self.itersets())) + ">"
 	def __repr__(self):
 		return "Aliases([" + ", ".join(str((key, self.canonical(key))) for key in sorted(self.nexts.keys())) + "])"

As i'm sure you'll agree, code that combines a complete absence of clarity 
with abject lack of runtime efficiency. Oh, and i haven't tested it 
properly.

tom

-- 
if you can't beat them, build them



More information about the Python-list mailing list