lib/core/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                 insert_before(e, node)
 130         end
 131
 132         # Append `l` to `self` but clear `l`.
 133         #
 134         # O(1)
 135         fun link(l: List[E])
 136         do
 137                 if _tail == null then
 138                         _head = l._head
 139                 else if l._head != null then
 140                         _tail.next = l._head
 141                         _tail.next.prev = _tail
 142                 end
 143                 _tail = l._tail
 144                 l.clear
 145         end
 146
 147 # Remove elements
 148
 149         # O(1)
 150         redef fun pop
 151         do
 152                 var node = _tail
 153                 _tail = node.prev
 154                 node.prev = null
 155                 if _tail == null then
 156                         _head = null
 157                 else
 158                         _tail.next = null
 159                 end
 160                 return node.item
 161         end
 162
 163         # O(1)
 164         redef fun shift
 165         do
 166                 var node = _head
 167                 _head = node.next
 168                 node.next = null
 169                 if _head == null then
 170                         _tail = null
 171                 else
 172                         _head.prev = null
 173                 end
 174                 return node.item
 175         end
 176
 177         redef fun remove(e)
 178         do
 179                 var node = search_node_after(e, _head)
 180                 if node != null then remove_node(node)
 181         end
 182
 183         redef fun remove_at(i)
 184         do
 185                 var node = get_node(i)
 186                 if node != null then remove_node(node)
 187         end
 188
 189         redef fun clear
 190         do
 191                 _head = null
 192                 _tail = null
 193         end
 194
 195
 196         redef fun iterator: ListIterator[E] do return new ListIterator[E](self)
 197         redef fun reverse_iterator: ListIterator[E] do return new ListReverseIterator[E](self)
 198
 199         # Build an empty list.
 200         init do end
 201
 202         # Build a list filled with the items of `coll`.
 203         init from(coll: Collection[E]) do append(coll)
 204
 205         # The first node of the list
 206         private var head: nullable ListNode[E] = null
 207
 208         # The last node of the list
 209         private var tail: nullable ListNode[E] = null
 210
 211         # Get the `i`th node. get `null` otherwise.
 212         private fun get_node(i: Int): nullable ListNode[E]
 213         do
 214                 var n = _head
 215                 if i < 0 then
 216                         return null
 217                 end
 218                 while n != null and i > 0 do
 219                         n = n.next
 220                         i -= 1
 221                 end
 222                 return n
 223         end
 224
 225         # get the first node that contains `e` after 'after', null otherwise
 226         private fun search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
 227         do
 228                 var n = after
 229                 while n != null and n.item != e do n = n.next
 230                 return n
 231         end
 232
 233         # Remove the node (ie. atach prev and next)
 234         private fun remove_node(node: ListNode[E])
 235         do
 236                 if node.prev == null then
 237                         _head = node.next
 238                         if node.next == null then
 239                                 _tail = null
 240                         else
 241                                 node.next.prev = null
 242                         end
 243                 else if node.next == null then
 244                         _tail = node.prev
 245                         node.prev.next = null
 246                 else
 247                         node.prev.next = node.next
 248                         node.next.prev = node.prev
 249                 end
 250         end
 251
 252         private fun insert_before(element: E, node: ListNode[E])
 253         do
 254                 var nnode = new ListNode[E](element)
 255                 var prev = node.prev
 256                 if prev == null then
 257                         _head = nnode
 258                 else
 259                         prev.next = nnode
 260                 end
 261                 nnode.prev = prev
 262                 nnode.next = node
 263                 node.prev = nnode
 264         end
 265 end
 266
 267 # This is the iterator class of List
 268 class ListIterator[E]
 269         super IndexedIterator[E]
 270         redef fun item do return _node.item
 271
 272         # Set item `e` at self `index`.
 273         fun item=(e: E) do _node.item = e
 274
 275         redef fun is_ok do return not _node == null
 276
 277         redef fun next
 278         do
 279                 _node = _node.next
 280                 _index += 1
 281         end
 282
 283         # Build a new iterator for `list`.
 284         init
 285         do
 286                 _node = _list._head
 287         end
 288
 289         # The current list
 290         private var list: List[E]
 291
 292         # The current node of the list
 293         private var node: nullable ListNode[E] = null
 294
 295         # The index of the current node
 296         redef var index = 0
 297
 298         # Remove the current item
 299         fun delete
 300         do
 301                 _list.remove_node(_node.as(not null))
 302         end
 303
 304         # Insert before the current item
 305         fun insert_before(element: E)
 306         do
 307                 _list.insert_before(element, _node.as(not null))
 308         end
 309 end
 310
 311 private class ListReverseIterator[E]
 312         super ListIterator[E]
 313
 314         redef fun next
 315         do
 316                 _node = _node.prev
 317                 _index -= 1
 318         end
 319
 320         init
 321         do
 322                 var list = _list
 323                 _node = list._tail
 324                 _index = list.length
 325         end
 326 end
 327
 328 # Linked nodes that constitute a linked list.
 329 private class ListNode[E]
 330         super Ref[E]
 331
 332         # The next node.
 333         var next: nullable ListNode[E] = null
 334
 335         # The previous node.
 336         var prev: nullable ListNode[E] = null
 337 end