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                 length = 0
 190         end
 191
 192
 193         redef fun iterator: ListIterator[E] do return new ListIterator[E](self)
 194         redef fun reverse_iterator: ListIterator[E] do return new ListReverseIterator[E](self)
 195
 196         # Build an empty list.
 197         init do end
 198
 199         # Build a list filled with the items of `coll`.
 200         init from(coll: Collection[E]) do append(coll)
 201
 202         # The first node of the list
 203         private var head: nullable ListNode[E] = null
 204
 205         # The last node of the list
 206         private var tail: nullable ListNode[E] = null
 207
 208         # Get the `i`th node. get `null` otherwise.
 209         private fun get_node(i: Int): nullable ListNode[E]
 210         do
 211                 var n = _head
 212                 if i < 0 then
 213                         return null
 214                 end
 215                 while n != null and i > 0 do
 216                         n = n.next
 217                         i -= 1
 218                 end
 219                 return n
 220         end
 221
 222         # get the first node that contains `e` after 'after', null otherwise
 223         private fun search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
 224         do
 225                 var n = after
 226                 while n != null and n.item != e do n = n.next
 227                 return n
 228         end
 229
 230         # Remove the node (ie. atach prev and next)
 231         private fun remove_node(node: ListNode[E])
 232         do
 233                 length -= 1
 234                 if node.prev == null then
 235                         _head = node.next
 236                         if node.next == null then
 237                                 _tail = null
 238                         else
 239                                 node.next.prev = null
 240                         end
 241                 else if node.next == null then
 242                         _tail = node.prev
 243                         node.prev.next = null
 244                 else
 245                         node.prev.next = node.next
 246                         node.next.prev = node.prev
 247                 end
 248         end
 249
 250         private fun insert_before(element: E, node: ListNode[E])
 251         do
 252                 length += 1
 253                 var nnode = new ListNode[E](element)
 254                 var prev = node.prev
 255                 if prev == null then
 256                         _head = nnode
 257                 else
 258                         prev.next = nnode
 259                 end
 260                 nnode.prev = prev
 261                 nnode.next = node
 262                 node.prev = nnode
 263         end
 264 end
 265
 266 # This is the iterator class of List
 267 class ListIterator[E]
 268         super IndexedIterator[E]
 269         redef fun item do return _node.item
 270
 271         # Set item `e` at self `index`.
 272         fun item=(e: E) do _node.item = e
 273
 274         redef fun is_ok do return not _node == null
 275
 276         redef fun next
 277         do
 278                 _node = _node.next
 279                 _index += 1
 280         end
 281
 282         # Build a new iterator for `list`.
 283         init
 284         do
 285                 _node = _list._head
 286         end
 287
 288         # The current list
 289         private var list: List[E]
 290
 291         # The current node of the list
 292         private var node: nullable ListNode[E] = null
 293
 294         # The index of the current node
 295         redef var index = 0
 296
 297         # Remove the current item
 298         fun delete
 299         do
 300                 _list.remove_node(_node.as(not null))
 301         end
 302
 303         # Insert before the current item
 304         fun insert_before(element: E)
 305         do
 306                 _list.insert_before(element, _node.as(not null))
 307         end
 308 end
 309
 310 private class ListReverseIterator[E]
 311         super ListIterator[E]
 312
 313         redef fun next
 314         do
 315                 _node = _node.prev
 316                 _index -= 1
 317         end
 318
 319         init
 320         do
 321                 var list = _list
 322                 _node = list._tail
 323                 _index = list.length
 324         end
 325 end
 326
 327 # Linked nodes that constitute a linked list.
 328 private class ListNode[E]
 329         super Ref[E]
 330
 331         # The next node.
 332         var next: nullable ListNode[E] = null
 333
 334         # The previous node.
 335         var prev: nullable ListNode[E] = null
 336 end