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