-
Notifications
You must be signed in to change notification settings - Fork 0
/
poslist.py
153 lines (132 loc) · 4.63 KB
/
poslist.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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
from .doublylinkedlist import _DoublyLinkedBase
class PositionalList(_DoublyLinkedBase):
"""
A sequential container of elements allowing positional access.
"""
class Position:
"""
An abstraction representing the location of a single element.
"""
def __init__(self, container, node):
"""
Constructor should not 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 True if other is a Position representing the same location.
"""
return type(other) is type(self) and other._node is self._node
def __ne__(self, other):
"""
Return True if other does not represent the same location.
"""
return not (self == other)
def _validate(self, p):
"""
Return positional'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')
# convention for deprecated nodes
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:
# boundary violation
return None
else:
# legitimate position
return self.Position(self, node)
# accessors
def first(self):
"""
Return the first Position in the list (or None if list is empty).
"""
return self._make_position(self._header._next)
def last(self):
"""
Return the last Position in the list (or None if list is empty).
"""
return self._make_position(self._trailer._prev)
def before(self, p):
"""
Return the Position just before Position p (or None if p is first).
"""
node = self._validate(p)
return self._make_position(node._prev)
def after(self, p):
"""
Return the Position just after Position p (or None if p is last).
"""
node = self._validate(p)
return self._make_position(node._next)
def __iter__(self):
"""
Generate a forward iteration of the elements of the list.
"""
cursor = self.first()
while cursor is not None:
yield cursor.element()
cursor = self.after(cursor)
# mutators
# override inherited version to return Position, rather than node
def _insert_between(self, e, predecessor, successor):
"""
Add element between existing nodes and return new Position.
"""
node = super()._insert_between(e, predecessor, successor)
return self._make_position(node)
def add_first(self, e):
"""
Insert element e at the front of the list and return new Position.
"""
return self._insert_between(e, self._header, self._header._next)
def add_last(self, e):
"""
Insert element e at the back of the list and return new Position.
"""
return self._insert_between(e, self._trailer._prev, self._trailer)
def add_before(self, p, e):
"""
Insert element e into list before Position p and return new Position.
"""
original = self._validate(p)
return self._insert_between(e, original._prev, original)
def add_after(self, p, e):
"""
Insert element e into list after Position p and return new Position.
"""
original = self._validate(p)
return self._insert_between(e, original, original._next)
def delete(self, p):
"""
Remove and return the element at Position p.
"""
original = self._validate(p)
# inherited method returns element
return self._delete_node(original)
def replace(self, p, e):
"""
Replace the element at Position p with e.
Return the element formerly at Position p.
"""
original = self._validate(p)
# temporarily store old element
old_value = original._element
# replace with new element
original._element = e
# return the old element value
return old_value