lib/standard/collection/list.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # This file is free software, which comes along with NIT.  This software is
   6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9 # is kept unaltered, and a notification of the changes is added.
  10 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11 # another product.
  12
  13 # This module handle double linked lists
  14 module list
  15
  16 import abstract_collection
  17
  18 # Double linked lists.
  19 class List[E]
  20         super Sequence[E]
  21
  22 # Access
  23
  24         redef fun [](index) do return get_node(index).item
  25
  26         redef fun []=(index, item) do get_node(index).item = item
  27
  28         # O(1)
  29         redef fun first do return _head.item
  30
  31         # O(1)
  32         redef fun first=(e) do _head.item = e
  33
  34         # O(1)
  35         redef fun last do return _tail.item
  36
  37         # O(1)
  38         redef fun last=(e) do _tail.item = e
  39
  40 # Queries
  41
  42         # O(1)
  43         redef fun is_empty do return _head == null
  44
  45         # O(n)
  46         redef fun length
  47         do
  48                 var l = 0
  49                 var t = _head
  50                 while t != null do
  51                         l += 1
  52                         t = t.next
  53                 end
  54                 return l
  55         end
  56
  57         # O(n)
  58         redef fun has(e) do return search_node_after(e, _head) != null
  59
  60         redef fun has_only(e)
  61         do
  62                 var node = _head
  63                 while node != null do
  64                         if node.item != e then return false
  65                         node = node.next
  66                 end
  67                 return true
  68         end
  69
  70         redef fun count(e)
  71         do
  72                 var nb = 0
  73                 var node = _head
  74                 while node != null do
  75                         if node.item != e then nb += 1
  76                         node = node.next
  77                 end
  78                 return nb
  79         end
  80
  81         # Return a list of elements between 'from' and 'to'.
  82         fun slice(from: Int, to: Int): List[E] do
  83                 assert from >= 0 and from < length
  84                 assert to >= 0 and to < length and from <= to
  85                 var list = new List[E]
  86                 while from <= to do
  87                         list.add(self[from])
  88                         from += 1
  89                 end
  90                 return list
  91         end
  92
  93 # Add elements
  94
  95         # O(1)
  96         redef fun push(e)
  97         do
  98                 var node = new ListNode[E](e)
  99                 if _tail == null then
 100                         _head = node
 101                 else
 102                         _tail.next = node
 103                         node.prev = _tail
 104                 end
 105                 _tail = node
 106         end
 107
 108         # O(1)
 109         redef fun unshift(e)
 110         do
 111                 var node = new ListNode[E](e)
 112                 if _head == null then
 113                         _tail = node
 114                 else
 115                         node.next = _head
 116                         _head.prev = node
 117                 end
 118                 _head = node
 119         end
 120
 121         # O(n)
 122         redef fun insert(e, i)
 123         do
 124                 var node = get_node(i)
 125                 if node == null then
 126                         push(e)
 127                         return
 128                 end
 129                 var nnode = new ListNode[E](e)
 130                 var next = node.next
 131                 if next == null then
 132                         _tail = nnode
 133                 else
 134                         next.prev = nnode
 135                 end
 136                 nnode.prev = node
 137                 nnode.next = next
 138                 node.next = nnode
 139         end
 140
 141         # Append `l` to `self` but clear `l`.
 142         ##
 143         # O(1)
 144         fun link(l: List[E])
 145         do
 146                 if _tail == null then
 147                         _head = l._head
 148                 else if l._head != null then
 149                         _tail.next = l._head
 150                         _tail.next.prev = _tail
 151                 end
 152                 _tail = l._tail
 153                 l.clear
 154         end
 155
 156 # Remove elements
 157
 158         # O(1)
 159         redef fun pop
 160         do
 161                 var node = _tail
 162                 _tail = node.prev
 163                 node.prev = null
 164                 if _tail == null then
 165                         _head = null
 166                 else
 167                         _tail.next = null
 168                 end
 169                 return node.item
 170         end
 171
 172         # O(1)
 173         redef fun shift
 174         do
 175                 var node = _head
 176                 _head = node.next
 177                 node.next = null
 178                 if _head == null then
 179                         _tail = null
 180                 else
 181                         _head.prev = null
 182                 end
 183                 return node.item
 184         end
 185
 186         redef fun remove(e)
 187         do
 188                 var node = search_node_after(e, _head)
 189                 if node != null then remove_node(node)
 190         end
 191
 192         redef fun remove_at(i)
 193         do
 194                 var node = get_node(i)
 195                 if node != null then remove_node(node)
 196         end
 197
 198         redef fun clear
 199         do
 200                 _head = null
 201                 _tail = null
 202         end
 203
 204
 205         redef fun iterator: ListIterator[E] do return new ListIterator[E](self)
 206         redef fun reverse_iterator: ListIterator[E] do return new ListReverseIterator[E](self)
 207
 208         # Build an empty list.
 209         init do end
 210
 211         # Build a list filled with the items of `coll`.
 212         init from(coll: Collection[E]) do append(coll)
 213
 214         # The first node of the list
 215         private var head: nullable ListNode[E] = null
 216
 217         # The last node of the list
 218         private var tail: nullable ListNode[E] = null
 219
 220         # Get the `i`th node. get `null` otherwise.
 221         private fun get_node(i: Int): nullable ListNode[E]
 222         do
 223                 var n = _head
 224                 if i < 0 then
 225                         return null
 226                 end
 227                 while n != null and i > 0 do
 228                         n = n.next
 229                         i -= 1
 230                 end
 231                 return n
 232         end
 233
 234         # get the first node that contains `e` after 'after', null otherwise
 235         private fun search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
 236         do
 237                 var n = after
 238                 while n != null and n.item != e do n = n.next
 239                 return n
 240         end
 241
 242         # Remove the node (ie. atach prev and next)
 243         private fun remove_node(node: ListNode[E])
 244         do
 245                 if node.prev == null then
 246                         _head = node.next
 247                         if node.next == null then
 248                                 _tail = null
 249                         else
 250                                 node.next.prev = null
 251                         end
 252                 else if node.next == null then
 253                         _tail = node.prev
 254                         node.prev.next = null
 255                 else
 256                         node.prev.next = node.next
 257                         node.next.prev = node.prev
 258                 end
 259         end
 260
 261         private fun insert_before(element: E, node: ListNode[E])
 262         do
 263                 var nnode = new ListNode[E](element)
 264                 var prev = node.prev
 265                 if prev == null then
 266                         _head = nnode
 267                 else
 268                         prev.next = nnode
 269                 end
 270                 nnode.prev = prev
 271                 nnode.next = node
 272                 node.prev = nnode
 273         end
 274 end
 275
 276 # This is the iterator class of List
 277 class ListIterator[E]
 278         super IndexedIterator[E]
 279         redef fun item do return _node.item
 280
 281         fun item=(e: E) do _node.item = e
 282
 283         redef fun is_ok do return not _node == null
 284
 285         redef fun next
 286         do
 287                 _node = _node.next
 288                 _index += 1
 289         end
 290
 291         # Build a new iterator for `list`.
 292         private init(list: List[E])
 293         do
 294                 _list = list
 295                 _node = list._head
 296                 _index = 0
 297         end
 298
 299         # The current list
 300         private var list: List[E]
 301
 302         # The current node of the list
 303         private var node: nullable ListNode[E]
 304
 305         # The index of the current node
 306         redef var index
 307
 308         # Remove the current item
 309         fun delete
 310         do
 311                 _list.remove_node(_node.as(not null))
 312         end
 313
 314         # Insert before the current item
 315         fun insert_before(element: E)
 316         do
 317                 _list.insert_before(element, _node.as(not null))
 318         end
 319 end
 320
 321 private class ListReverseIterator[E]
 322         super ListIterator[E]
 323
 324         redef fun next
 325         do
 326                 _node = _node.prev
 327                 _index -= 1
 328         end
 329
 330         private init(list: List[E])
 331         do
 332                 _list = list
 333                 _node = list._tail
 334                 _index = list.length
 335         end
 336 end
 337
 338 # Linked nodes that constitute a linked list.
 339 private class ListNode[E]
 340         super Container[E]
 341         init(i: E)
 342         do
 343                 item = i
 344         end
 345
 346         # The next node.
 347         var next: nullable ListNode[E]
 348
 349         # The previous node.
 350         var prev: nullable ListNode[E]
 351 end