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