gbp/rpm/linkedlist.py

   1 # vim: set fileencoding=utf-8 :
   2 #
   3 # (C) 2012 Intel Corporation <markus.lehtonen@linux.intel.com>
   4 #    This program is free software; you can redistribute it and/or modify
   5 #    it under the terms of the GNU General Public License as published by
   6 #    the Free Software Foundation; either version 2 of the License, or
   7 #    (at your option) any later version.
   8 #
   9 #    This program is distributed in the hope that it will be useful,
  10 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 #    GNU General Public License for more details.
  13 #
  14 #    You should have received a copy of the GNU General Public License
  15 #    along with this program; if not, write to the Free Software
  16 #    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17 """Simple implementation of a doubly linked list"""
  18
  19 import collections
  20
  21 import gbp.log
  22
  23
  24 class LinkedListNode(object):
  25     """Node of the linked list"""
  26
  27     def __init__(self, data="", prev_node=None, next_node=None):
  28         self.prev = prev_node
  29         self.next = next_node
  30         self._data = data
  31
  32     def __str__(self):
  33         return str(self.data)
  34
  35     @property
  36     def data(self):
  37         """Get data stored into node"""
  38         if self._data is None:
  39             gbp.log.debug("BUG: referencing a deleted node!")
  40             return("")
  41         return self._data
  42
  43     def set_data(self, data):
  44         """
  45         Set data stored into node
  46
  47         >>> node = LinkedListNode('foo')
  48         >>> node.data
  49         'foo'
  50         >>> node.set_data('bar')
  51         >>> node.data
  52         'bar'
  53         >>> node.set_data(None)
  54         >>> node.data
  55         ''
  56         """
  57         if data is None:
  58             gbp.log.debug("BUG: trying to store 'None', not allowed")
  59             data = ""
  60         self._data = data
  61
  62
  63     def delete(self):
  64         """Delete node"""
  65         if self.prev:
  66             self.prev.next = self.__next__
  67         if self.__next__:
  68             self.next.prev = self.prev
  69         self._data = None
  70
  71
  72 class LinkedListIterator(collections.abc.Iterator):
  73     """Iterator for the linked list"""
  74
  75     def __init__(self, obj):
  76         self._next = obj.first
  77
  78     def __next__(self):
  79         ret = self._next
  80         if ret:
  81             self._next = ret.__next__
  82         else:
  83             raise StopIteration
  84         return ret
  85
  86
  87 class LinkedList(collections.abc.Iterable):
  88     """Doubly linked list"""
  89
  90     def __init__(self):
  91         self._first = None
  92         self._last = None
  93
  94     def __iter__(self):
  95         return LinkedListIterator(self)
  96
  97     def __len__(self):
  98         for num, data in enumerate(self):
  99             pass
 100         return num + 1
 101
 102     @property
 103     def first(self):
 104         """Get the first node of the list"""
 105         return self._first
 106
 107     def prepend(self, data):
 108         """
 109         Insert to the beginning of list
 110
 111         >>> list = LinkedList()
 112         >>> [str(data) for data in list]
 113         []
 114         >>> node = list.prepend("foo")
 115         >>> len(list)
 116         1
 117         >>> node = list.prepend("bar")
 118         >>> [str(data) for data in list]
 119         ['bar', 'foo']
 120         """
 121         if self._first is None:
 122             new = self._first = self._last = LinkedListNode(data)
 123         else:
 124             new = self.insert_before(self._first, data)
 125         return new
 126
 127     def append(self, data):
 128         """
 129         Insert to the end of list
 130
 131         >>> list = LinkedList()
 132         >>> node = list.append('foo')
 133         >>> len(list)
 134         1
 135         >>> node = list.append('bar')
 136         >>> [str(data) for data in list]
 137         ['foo', 'bar']
 138         """
 139         if self._last is None:
 140             return self.prepend(data)
 141         else:
 142             return self.insert_after(self._last, data)
 143
 144     def insert_before(self, node, data=""):
 145         """
 146         Insert before a node
 147
 148         >>> list = LinkedList()
 149         >>> node1 = list.append('foo')
 150         >>> node2 = list.insert_before(node1, 'bar')
 151         >>> node3 = list.insert_before(node1, 'baz')
 152         >>> [str(data) for data in list]
 153         ['bar', 'baz', 'foo']
 154         """
 155         new = LinkedListNode(data, prev_node=node.prev, next_node=node)
 156         if node.prev:
 157             node.prev.next = new
 158         else:
 159             self._first = new
 160         node.prev = new
 161         return new
 162
 163     def insert_after(self, node, data=""):
 164         """
 165         Insert after a node
 166
 167         >>> list = LinkedList()
 168         >>> node1 = list.prepend('foo')
 169         >>> node2 = list.insert_after(node1, 'bar')
 170         >>> node3 = list.insert_after(node1, 'baz')
 171         >>> [str(data) for data in list]
 172         ['foo', 'baz', 'bar']
 173         """
 174         new = LinkedListNode(data, prev_node=node, next_node=node.__next__)
 175         if node.__next__:
 176             node.next.prev = new
 177         else:
 178             self._last = new
 179         node.next = new
 180         return new
 181
 182     def delete(self, node):
 183         """
 184         Delete node
 185
 186         >>> list = LinkedList()
 187         >>> node1 = list.prepend('foo')
 188         >>> node2 = list.insert_after(node1, 'bar')
 189         >>> node3 = list.insert_before(node2, 'baz')
 190         >>> [str(data) for data in list]
 191         ['foo', 'baz', 'bar']
 192         >>> str(list.delete(node3))
 193         'foo'
 194         >>> [str(data) for data in list]
 195         ['foo', 'bar']
 196         >>> print "%s" % node3
 197         <BLANKLINE>
 198         >>> str(list.delete(node1))
 199         'bar'
 200         >>> [str(data) for data in list]
 201         ['bar']
 202         >>> list.delete(node2)
 203         >>> [str(data) for data in list]
 204         []
 205         """
 206         ret = node.prev
 207         if node is self._first:
 208             ret = self._first = self._first.__next__
 209         if node is self._last:
 210             self._last = self._last.prev
 211         node.delete()
 212         return ret
 213
 214 # vim:et:ts=4:sw=4:et:sts=4:ai:set list listchars=tab\:»·,trail\:·: