Discussion in 'Python' started by pataphor, Feb 28, 2009.

  1. pataphor

    pataphor Guest

    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.


    #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()
    for x in K.iteritems():
    print x

    if __name__ == '__main__':
    pataphor, Feb 28, 2009
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page