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