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).as(not null).item
  25
  26         redef fun []=(index, item) do get_node(index).as(not null).item = item
  27
  28         # O(1)
  29         redef fun first do return _head.as(not null).item
  30
  31         # O(1)
  32         redef fun first=(e) do _head.as(not null).item = e
  33
  34         # O(1)
  35         redef fun last do return _tail.as(not null).item
  36
  37         # O(1)
  38         redef fun last=(e) do _tail.as(not null).item = e
  39
  40 # Queries
  41
  42         # O(1)
  43         redef fun is_empty do return _head == null
  44
  45         # O(1)
  46         redef var length = 0
  47
  48         # O(n)
  49         redef fun has(e) do return search_node_after(e, _head) != null
  50
  51         redef fun has_only(e)
  52         do
  53                 var node = _head
  54                 while node != null do
  55                         if node.item != e then return false
  56                         node = node.next
  57                 end
  58                 return true
  59         end
  60
  61         redef fun count(e)
  62         do
  63                 var nb = 0
  64                 var node = _head
  65                 while node != null do
  66                         if node.item != e then nb += 1
  67                         node = node.next
  68                 end
  69                 return nb
  70         end
  71
  72         # Return a list of elements between 'from' and 'to'.
  73         fun slice(from: Int, to: Int): List[E] do
  74                 assert from >= 0 and from < length
  75                 assert to >= 0 and to < length and from <= to
  76                 var list = new List[E]
  77                 while from <= to do
  78                         list.add(self[from])
  79                         from += 1
  80                 end
  81                 return list
  82         end
  83
  84 # Add elements
  85
  86         # O(1)
  87         redef fun push(e)
  88         do
  89                 var node = new ListNode[E](e)
  90                 var tail = _tail
  91                 if tail == null then
  92                         _head = node
  93                 else
  94                         tail.next = node
  95                         node.prev = tail
  96                 end
  97                 _tail = node
  98                 length += 1
  99         end
 100
 101         # O(1)
 102         redef fun unshift(e)
 103         do
 104                 var node = new ListNode[E](e)
 105                 var head = _head
 106                 if head == null then
 107                         _tail = node
 108                 else
 109                         node.next = head
 110                         head.prev = node
 111                 end
 112                 _head = node
 113                 length += 1
 114         end
 115
 116         # O(n)
 117         redef fun insert(e, i)
 118         do
 119                 var node = get_node(i)
 120                 if node == null then
 121                         push(e)
 122                         return
 123                 end
 124                 insert_before(e, node)
 125         end
 126
 127         # Append `l` to `self` but clear `l`.
 128         #
 129         # O(1)
 130         fun link(l: List[E])
 131         do
 132                 var tail = _tail
 133                 if tail == null then
 134                         _head = l._head
 135                 else if l._head != null then
 136                         tail.next = l._head
 137                         tail.next.as(not null).prev = tail
 138                 end
 139                 _tail = l._tail
 140                 length += l.length
 141                 l.clear
 142         end
 143
 144 # Remove elements
 145
 146         # O(1)
 147         redef fun pop
 148         do
 149                 var node = _tail.as(not null)
 150                 _tail = node.prev
 151                 node.prev = null
 152                 if _tail == null then
 153                         _head = null
 154                 else
 155                         _tail.as(not null).next = null
 156                 end
 157                 length -= 1
 158                 return node.item
 159         end
 160
 161         # O(1)
 162         redef fun shift
 163         do
 164                 var node = _head.as(not null)
 165                 _head = node.next
 166                 node.next = null
 167                 if _head == null then
 168                         _tail = null
 169                 else
 170                         _head.as(not null).prev = null
 171                 end
 172                 length -= 1
 173                 return node.item
 174         end
 175
 176         redef fun remove(e)
 177         do
 178                 var node = search_node_after(e, _head)
 179                 if node != null then remove_node(node)
 180         end
 181
 182         redef fun remove_at(i)
 183         do
 184                 var node = get_node(i)
 185                 if node != null then remove_node(node)
 186         end
 187
 188         redef fun clear
 189         do
 190                 _head = null
 191                 _tail = null
 192                 length = 0
 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                 length -= 1
 237                 if node.prev == null then
 238                         _head = node.next
 239                         if node.next == null then
 240                                 _tail = null
 241                         else
 242                                 node.next.as(not null).prev = null
 243                         end
 244                 else if node.next == null then
 245                         _tail = node.prev
 246                         node.prev.as(not null).next = null
 247                 else
 248                         node.prev.as(not null).next = node.next
 249                         node.next.as(not null).prev = node.prev
 250                 end
 251         end
 252
 253         private fun insert_before(element: E, node: ListNode[E])
 254         do
 255                 length += 1
 256                 var nnode = new ListNode[E](element)
 257                 var prev = node.prev
 258                 if prev == null then
 259                         _head = nnode
 260                 else
 261                         prev.next = nnode
 262                 end
 263                 nnode.prev = prev
 264                 nnode.next = node
 265                 node.prev = nnode
 266         end
 267 end
 268
 269 # This is the iterator class of List
 270 class ListIterator[E]
 271         super IndexedIterator[E]
 272         redef fun item do return _node.as(not null).item
 273
 274         # Set item `e` at self `index`.
 275         fun item=(e: E) do _node.as(not null).item = e
 276
 277         redef fun is_ok do return not _node == null
 278
 279         redef fun next
 280         do
 281                 _node = _node.as(not null).next
 282                 _index += 1
 283         end
 284
 285         # Build a new iterator for `list`.
 286         init
 287         do
 288                 _node = _list._head
 289         end
 290
 291         # The current list
 292         private var list: List[E]
 293
 294         # The current node of the list
 295         private var node: nullable ListNode[E] = null
 296
 297         # The index of the current node
 298         redef var index = 0
 299
 300         # Remove the current item
 301         fun delete
 302         do
 303                 _list.remove_node(_node.as(not null))
 304         end
 305
 306         # Insert before the current item
 307         fun insert_before(element: E)
 308         do
 309                 _list.insert_before(element, _node.as(not null))
 310         end
 311 end
 312
 313 private class ListReverseIterator[E]
 314         super ListIterator[E]
 315
 316         redef fun next
 317         do
 318                 _node = _node.as(not null).prev
 319                 _index -= 1
 320         end
 321
 322         init
 323         do
 324                 var list = _list
 325                 _node = list._tail
 326                 _index = list.length
 327         end
 328 end
 329
 330 # Linked nodes that constitute a linked list.
 331 private class ListNode[E]
 332         super Ref[E]
 333
 334         # The next node.
 335         var next: nullable ListNode[E] = null
 336
 337         # The previous node.
 338         var prev: nullable ListNode[E] = null
 339 end