Ordered Doubly Linked List

Question

Ok A question from assignment says to create an ordered doubly linked list...such that each object with lexicographically smaller name comes "Before" the other One...Like names in a Dictionary...also objects with same name can be arranged in any order...

To link two objects I have setBefore() and setAfter() method... and I have done this much...but still don't know where I'm doing wrong..may be a little guidance from you guys can help me...

atMe is an object that is already present in the doubly linked list and newFrob is an object to be inserted...

def insert(atMe, newFrob):
    if newFrob.myName() < atMe.myName():
        if atMe.getBefore() == None:
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        elif atMe.getBefore().myName()<newFrob.myName():
            atMe.getBefore().setAfter(newFrob)
            newFrob.setBefore(atMe.getBefore)
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        else:
            insert(atMe.getBefore(),newFrob)

    elif newFrob.myName() > atMe.myName():
        if atMe.getAfter() == None:
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        elif atMe.getAfter().myName()>newFrob.myName():
            atMe.getAfter().setBefore(newFrob)
            newFrob.setAfter(atMe.getAfter)
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        else:
            insert(atMe.getAfter(),newFrob)

    elif newFrob.myName()==atMe.myName():
        if atMe.getAfter() != None:
            newFrob.setAfter(atMe.getAfter())
        newFrob.setBefore(atMe)
        if atMe.getAfter() != None:
            atMe.getAfter().setBefore(newFrob)
        atMe.setAfter(newFrob)

And this is the Frob Class to be used...

class Frob(object):
    def __init__(self, name):
        self.name = name
        self.before = None
        self.after = None
    def setBefore(self, before):
        self.before = before
    def setAfter(self, after):
        self.after = after
    def getBefore(self):
        return self.before
    def getAfter(self):
        return self.after
    def myName(self):
        return self.name

where Before and After are links to left and right objects in double linked list... objects from this class are to be inserted to double linked list...

Example:

a=Frob('foo')
b=Frob('bar')
c=Frob('frob')
d=Frob('code')

code                             output
insert(a,b)                   bar->foo
insert(a,c)                   bar->foo->frob
insert(b,d)                   bar->code->foo->frob

now suppose

code                             output
insert(b,Frob('code'))        bar->code->code->foo->frob

Answer 1

The issue is in this line (and an equivalent one when you're moving the other direction):

newFrob.setBefore(atMe.getBefore)

You're missing a set of parentheses after atMe.getBefore, so you end up passing the bound method itself to newFrob.setBefore rather than the value that would be returned by that method. This is an easy typo to make, so I wouldn't feel too bad about missing it on your assignment.

I found the error by trying the following sequence of inserts and inspecting the values (I've summarized the ones that worked OK with comments):

>>> a = Frob("a")
>>> b = Frob("b")
>>> c = Frob("c")
>>> d = Frob("d")
>>> insert(a, b) # list is a<->b
>>> insert(a, d) # list is a<->b<->d
>>> insert(a, c) # list is a<->b<->c->?
>>> c.getAfter()
<bound method Frob.getAfter of <__main__.Frob object at 0x000000000318EBA8>>

That object mentioned at the end is b, which lead me to find the error in the code.