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