-
Notifications
You must be signed in to change notification settings - Fork 1
/
#frobs.py#
51 lines (48 loc) · 1.6 KB
/
#frobs.py#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
def insert(atMe, newFrob):
"""
atMe: a Frob that is part of a doubly linked list
newFrob: a Frob with no links
This procedure appropriately inserts newFrob into the linked list that atMe
is a part of.
"""
def forwardInsert(atMe, newFrob):
if atMe.getAfter() == None:
atMe.setAfter(newFrob)
newFrob.setBefore(atMe)
elif atMe.getAfter().myName() >= newFrob.myName():
newFrob.setBefore(atMe)
newFrob.setAfter(atMe.getAfter())
atMe.getAfter().setBefore(newFrob)
atMe.setAfter(newFrob)
else:
forwardInsert(atMe.getAfter(), newFrob)
def backwardInsert(atMe, newFrob):
if atMe.getBefore() == None:
atMe.setBefore(newFrob)
newFrob.setAfter(atMe)
elif atMe.getBefore().myName() <= newFrob.myName():
newFrob.setAfter(atMe)
newFrob.setBefore(atMe.getBefore())
atMe.getBefore().setAfter(newFrob)
atMe.setBefore(newFrob)
else:
backwardInsert(atMe.getBefore(), newFrob)
if atMe.myName() < newFrob.myName():
forwardInsert(atMe, newFrob)
else:
backwardInsert(atMe, newFrob)