diff options
Diffstat (limited to 'gbp/rpm/linkedlist.py')
| -rw-r--r-- | gbp/rpm/linkedlist.py | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/gbp/rpm/linkedlist.py b/gbp/rpm/linkedlist.py new file mode 100644 index 00000000..ca000453 --- /dev/null +++ b/gbp/rpm/linkedlist.py @@ -0,0 +1,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\:·: |