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