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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
# vim: set fileencoding=utf-8 :
#
# (C) 2012 Intel Corporation <markus.lehtonen@linux.intel.com>
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
"""Simple implementation of a doubly linked list"""
import collections
import gbp.log
class LinkedListNode(object):
"""Node of the linked list"""
def __init__(self, data="", prev_node=None, next_node=None):
self.prev = prev_node
self.next = next_node
self._data = data
def __str__(self):
return str(self.data)
@property
def data(self):
"""Get data stored into node"""
if self._data is None:
gbp.log.err("BUG: referencing a deleted node!")
return("")
return self._data
def set_data(self, data):
"""
Set data stored into node
>>> node = LinkedListNode('foo')
>>> node.data
'foo'
>>> node.set_data('bar')
>>> node.data
'bar'
>>> node.set_data(None)
>>> node.data
''
"""
if data is None:
gbp.log.err("BUG: trying to store 'None', not allowed")
data = ""
self._data = data
def delete(self):
"""Delete node"""
if self.prev:
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
self._data = None
class LinkedListIterator(collections.Iterator):
"""Iterator for the linked list"""
def __init__(self, obj):
self._next = obj.first
def next(self):
ret = self._next
if ret:
self._next = ret.next
else:
raise StopIteration
return ret
class LinkedList(collections.Iterable):
"""Doubly linked list"""
def __init__(self):
self._first = None
self._last = None
def __iter__(self):
return LinkedListIterator(self)
def __len__(self):
for num, data in enumerate(self):
pass
return num + 1
@property
def first(self):
"""Get the first node of the list"""
return self._first
def prepend(self, data):
"""
Insert to the beginning of list
>>> list = LinkedList()
>>> [str(data) for data in list]
[]
>>> node = list.prepend("foo")
>>> len(list)
1
>>> node = list.prepend("bar")
>>> [str(data) for data in list]
['bar', 'foo']
"""
if self._first is None:
new = self._first = self._last = LinkedListNode(data)
else:
new = self.insert_before(self._first, data)
return new
def append(self, data):
"""
Insert to the end of list
>>> list = LinkedList()
>>> node = list.append('foo')
>>> len(list)
1
>>> node = list.append('bar')
>>> [str(data) for data in list]
['foo', 'bar']
"""
if self._last is None:
return self.prepend(data)
else:
return self.insert_after(self._last, data)
def insert_before(self, node, data=""):
"""
Insert before a node
>>> list = LinkedList()
>>> node1 = list.append('foo')
>>> node2 = list.insert_before(node1, 'bar')
>>> node3 = list.insert_before(node1, 'baz')
>>> [str(data) for data in list]
['bar', 'baz', 'foo']
"""
new = LinkedListNode(data, prev_node=node.prev, next_node=node)
if node.prev:
node.prev.next = new
else:
self._first = new
node.prev = new
return new
def insert_after(self, node, data=""):
"""
Insert after a node
>>> list = LinkedList()
>>> node1 = list.prepend('foo')
>>> node2 = list.insert_after(node1, 'bar')
>>> node3 = list.insert_after(node1, 'baz')
>>> [str(data) for data in list]
['foo', 'baz', 'bar']
"""
new = LinkedListNode(data, prev_node=node, next_node=node.next)
if node.next:
node.next.prev = new
else:
self._last = new
node.next = new
return new
def delete(self, node):
"""
Delete node
>>> list = LinkedList()
>>> node1 = list.prepend('foo')
>>> node2 = list.insert_after(node1, 'bar')
>>> node3 = list.insert_before(node2, 'baz')
>>> [str(data) for data in list]
['foo', 'baz', 'bar']
>>> str(list.delete(node3))
'foo'
>>> [str(data) for data in list]
['foo', 'bar']
>>> print "%s" % node3
<BLANKLINE>
>>> str(list.delete(node1))
'bar'
>>> [str(data) for data in list]
['bar']
>>> list.delete(node2)
>>> [str(data) for data in list]
[]
"""
ret = node.prev
if node is self._first:
ret = self._first = self._first.next
if node is self._last:
self._last = self._last.prev
node.delete()
return ret
# vim:et:ts=4:sw=4:et:sts=4:ai:set list listchars=tab\:»·,trail\:·:
|
