KeyedList

[pataphor]

The ordered dictionary discussion made me think of another data type
which seems to be somewhat related, a kind of ordered dictionary where
the order of the items is arbitrary. One can insert items in the middle
and still have O(1) access (I think). I have provided a very basic
implementation, it could be extended to also remove items with O(1)
access. I am wondering if the idea makes sense at all and what would be
the best name for the type itself and for its methods.

Could it be that the ordered dictionary is a result of a way of
thinking which slowly extends what we currently have, while a
KeyedList or whatever we ultimately choose to name it is the kind of
data type we are really looking for? If accepted, I think this type
could be used for Knuth's dancing links style algorithms.

P.

#warning, embryonic, probably very buggy implementation

class Node:

def __init__(self, left = None, right = None, key = None, item =
None): self.left = left
self.right = right
self.key = key
self.item = item

class KeyedList:

def __init__(self):
self.first = Node()
self.last = Node()
self.last.left = self.first
self.first.right = self.last
self.D = {}

def append(self, key, item):
last = self.last
prev = last.left
x = Node(prev,last,key,item)
prev.right = x
last.left = x
self.D[key] = x

def insertafter(self,key1,key2,item):
left = self.D[key1]
right = left.right
x = Node(left,right,key2,item)
left.right =x
right.left =x
self.D[key2] = x

def iteritems(self):
x = self.first.right
while x.right:
key = x.key
yield key, self.D[key].item
x = x.right

def test():
K = KeyedList()
K.append('one','hello')
K.append('two','hello')
K.append('four','hello')
K.insertafter('two','three','hello')
for x in K.iteritems():
print x

if __name__ == '__main__':
test()