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