rpm: implement a simple doubly linked list

This class is intended to store the spec file content, needed for
modifying the spec file.

Signed-off-by: Markus Lehtonen <markus.lehtonen@linux.intel.com>

1 files changed, 211 insertions, 0 deletions

diff --git a/gbp/rpm/linkedlist.py b/gbp/rpm/linkedlist.py
new file mode 100644
index 00000000..f1321776
--- /dev/null
+++ b/gbp/rpm/linkedlist.py
@@ -0,0 +1,211 @@
+# 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']
+        >>> list.delete(node3)
+        >>> [str(data) for data in list]
+        ['foo', 'bar']
+        >>> print "%s" % node3
+        <BLANKLINE>
+        >>> list.delete(node1)
+        >>> [str(data) for data in list]
+        ['bar']
+        >>> list.delete(node2)
+        >>> [str(data) for data in list]
+        []
+        """
+        if node is self._first:
+            self._first = self._first.next
+        if node is self._last:
+            self._last = self._last.prev
+        node.delete()
+
+
+# vim:et:ts=4:sw=4:et:sts=4:ai:set list listchars=tab\:»·,trail\:·: