Please answer in Python code. Augment the PositionalList class to support a meth
ID: 3830250 • Letter: P
Question
Please answer in Python code.
Augment the PositionalList class to support a method named merge with the following behavior. If A and B are PositionalList instances whose elements are sorted, the syntax A.merge(B) should merge all elements of B into A so that A remains sorted and B becomes empty. Your implementation must accomplish the merge by relinking existing nodes; you are not to create any new nodes.
PositionalList class:
1 class PositionalList( DoublyLinkedBase):
2 ”””A sequential container of elements allowing positional access.”””
3
4 #-------------------------- nested Position class --------------------------
5 class Position:
6 ”””An abstraction representing the location of a single element.”””
7
8 def init (self, container, node):
9 ”””Constructor should not be invoked by user.”””
10 self. container = container
11 self. node = node
12
13 def element(self):
14 ”””Return the element stored at this Position.”””
15 return self. node. element
16
17 def eq (self, other):
18 ”””Return True if other is a Position representing the same location.”””
19 return type(other) is type(self) and other. node is self. node
20
21 def ne (self, other):
22 ”””Return True if other does not represent the same location.”””
23 return not (self == other) # opposite of eq
24
25 #------------------------------- utility method -------------------------------
26 def validate(self, p):
27 ”””Return position s node, or raise appropriate error if invalid.”””
28 if not isinstance(p, self.Position):
29 raise TypeError( p must be proper Position type )
30 if p. container is not self:
31 raise ValueError( p does not belong to this container )
32 if p. node. next is None: # convention for deprecated nodes
33 raise ValueError( p is no longer valid )
34 return p. node
35 #------------------------------- utility method -------------------------------
36 def make position(self, node):
37 ”””Return Position instance for given node (or None if sentinel).”””
38 if node is self. header or node is self. trailer:
39 return None # boundary violation
40 else:
41 return self.Position(self, node) # legitimate position
42
43 #------------------------------- accessors -------------------------------
44 def first(self):
45 ”””Return the first Position in the list (or None if list is empty).”””
46 return self. make position(self. header. next)
47
48 def last(self):
49 ”””Return the last Position in the list (or None if list is empty).”””
50 return self. make position(self. trailer. prev)
51
52 def before(self, p):
53 ”””Return the Position just before Position p (or None if p is first).”””
54 node = self. validate(p)
55 return self. make position(node. prev)
56
57 def after(self, p):
58 ”””Return the Position just after Position p (or None if p is last).”””
59 node = self. validate(p)
60 return self. make position(node. next)
61
62 def iter (self):
63 ”””Generate a forward iteration of the elements of the list.”””
64 cursor = self.first( )
65 while cursor is not None:
66 yield cursor.element( )
67 cursor = self.after(cursor)
68 #------------------------------- mutators -------------------------------
69 # override inherited version to return Position, rather than Node
70 def insert between(self, e, predecessor, successor):
71 ”””Add element between existing nodes and return new Position.”””
72 node = super(). insert between(e, predecessor, successor)
73 return self. make position(node)
74
75 def add first(self, e):
76 ”””Insert element e at the front of the list and return new Position.”””
77 return self. insert between(e, self. header, self. header. next)
78
79 def add last(self, e):
80 ”””Insert element e at the back of the list and return new Position.”””
81 return self. insert between(e, self. trailer. prev, self. trailer)
82
83 def add before(self, p, e):
84 ”””Insert element e into list before Position p and return new Position.”””
85 original = self. validate(p)
86 return self. insert between(e, original. prev, original)
87
88 def add after(self, p, e):
89 ”””Insert element e into list after Position p and return new Position.”””
90 original = self. validate(p)
91 return self. insert between(e, original, original. next)
92
93 def delete(self, p):
94 ”””Remove and return the element at Position p.”””
95 original = self. validate(p)
96 return self. delete node(original) # inherited method returns element
97
98 def replace(self, p, e):
99 ”””Replace the element at Position p with e.
100
101 Return the element formerly at Position p.
102 ”””
103 original = self. validate(p)
104 old value = original. element # temporarily store old element
105 original. element = e # replace with new element
106 return old value # return the old element value
Explanation / Answer
class PositionalList(DoublyLinkedBase):
"""A sequential container of elements allowing positional access."""
# -----------------------Nested Position Class-------------------------------
class Position:
"""An abstraction representing the location of a single element."""
def __init__(self, container, node):
"""Constructor shouldn't be invoked by user."""
self._container = container
self._node = node
def element(self):
"""Return the element stored at this Position."""
return self._node._element
def __eq__(self, other):
return type(other) is type(self) and other._node == self._node
def __ne__(self, other):
return not(self == other)
# ------------------------------Utility method----------------------------------
def _validate(self, p):
"""Return Position's node, or raise appropriate error if invalid."""
if not isinstance(p, self.Position):
raise TypeError('p must be proper Position type !')
if p._container is not self:
raise ValueError('p does not belong to this container !')
if p._node._next is None:
raise ValueError('p is no longer valid !')
return p._node
def _make_position(self, node):
"""Return Position instance for given node ( or None if sentinel )."""
if node is self._header or node is self._trailer:
return None # boundary violation
else:
return self.Position(self, node) # legitimate position
# ---------------------------------Accessors---------------------------------------
def first(self):
return self._make_position(self._header._next)
def last(self):
return self._make_position(self._trailer._prev)
def before(self, p):
node = self._validate(p)
return self._make_position(node._prev)
def after(self, p):
node = self._validate(p)
return self._make_position(node._next)
def __iter__(self):
cursor = self.first()
while cursor is not None:
yield cursor.element()
cursor = self.after(cursor)
# -----------------------------------Mutators---------------------------------------
# override inherited version of return Position , rather than Node
def _insert_between(self, e, predecessor, successor):
node = super()._insert_between(e, predecessor, successor)
return self._make_position(node)
def add_first(self, e):
return self._insert_between(e, self._header, self._header._next)
def add_last(self, e):
return self._insert_between(e, self._trailer, self._trailer._prev)
def add_before(self, p, e):
original = self._validate(p)
return self._insert_between(e, original._prev, original)
def add_after(self, p, e):
original = self._validate(p)
return self._insert_between(e, original, original._next)
def delete(self, p):
original = self._validate(p)
return self._delete_node(original)
def replace(self, p, e):
original = self._validate(p)
old_value = original._element
original._element = e
return old_value
@staticmethod
def insertion_sort(alist):
"""Sort Positional List of comparable elements into nondecreasing order"""
if len(alist) > 1:
marker = alist.first()
while marker != alist.last():
pivot = alist.after(marker)
value = pivot.element()
if value > marker.element():
marker = pivot
else:
walk = marker
while walk != alist.first() and alist.before(walk).element() > value:
walk = alist.before(walk)
alist.delete(pivot)
alist.add_before(walk, value)