1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
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
13 # This module handle double linked lists
16 import abstract_collection
18 # Double linked lists.
22 redef fun [](index
) do return get_node
(index
).item
24 redef fun []=(index
, item
) do get_node
(index
).item
= item
27 redef fun first
do return _head
.item
30 redef fun first
=(e
) do _head
.item
= e
33 redef fun last
do return _tail
.item
36 redef fun last
=(e
) do _tail
.item
= e
41 redef fun is_empty
do return _head
== null
56 redef fun has
(e
) do return search_node_after
(e
, _head
) != null
62 if node
.item
!= e
then return false
73 if node
.item
!= e
then nb
+= 1
79 redef fun has_key
(index
) do return get_node
(index
) != null
86 var node
= new ListNode[E
](e
)
99 var node
= new ListNode[E
](e
)
100 if _head
== null then
109 # Append `l' to `self' but clear `l'.
114 if _tail
== null then
116 else if l
._head
!= null then
118 _tail
.next
.prev
= _tail
132 if _tail
== null then
146 if _head
== null then
156 var node
= search_node_after
(e
, _head
)
157 if node
!= null then remove_node
(node
)
160 redef fun remove_at
(i
)
162 var node
= get_node
(i
)
163 if node
!= null then remove_node
(node
)
173 redef fun iterator
: ListIterator[E
] do return new ListIterator[E
](self)
175 # Build an empty list.
178 # Build a list filled with the items of `coll'.
179 init from
(coll
: Collection[E
]) do append
(coll
)
181 # The first node of the list
182 var _head
: nullable ListNode[E
]
184 # The last node of the list
185 var _tail
: nullable ListNode[E
]
187 # Get the `i'th node. get `null' otherwise.
188 private fun get_node
(i
: Int): nullable ListNode[E
]
194 while n
!= null and i
> 0 do
201 # get the first node that contains e after 'after', null otherwise
202 private fun search_node_after
(e
: E
, after
: nullable ListNode[E
]): nullable ListNode[E
]
205 while n
!= null and n
.item
!= e
do n
= n
.next
209 # Remove the node (ie. atach prev and next)
210 private fun remove_node
(node
: ListNode[E
])
212 if node
.prev
== null then
214 if node
.next
== null then
217 node
.next
.prev
= null
219 else if node
.next
== null then
221 node
.prev
.next
= null
223 node
.prev
.next
= node
.next
224 node
.next
.prev
= node
.prev
228 private fun insert_before
(element
: E
, node
: ListNode[E
])
230 var nnode
= new ListNode[E
](element
)
243 # This is the iterator class of List
244 class ListIterator[E
]
245 super IndexedIterator[E
]
246 redef fun item
do return _node
.item
248 fun item
=(e
: E
) do _node
.item
= e
250 redef fun is_ok
do return not _node
== null
258 # Build a new iterator from `node'.
259 private init(list
: List[E
])
269 # The current node of the list
270 var _node
: nullable ListNode[E
]
272 # The index of the current node
273 redef readable var _index
: Int
275 # Remove the current item
278 _list
.remove_node
(_node
.as(not null))
281 # Insert before the current item
282 fun insert_before
(element
: E
)
284 _list
.insert_before
(element
, _node
.as(not null))
288 # Linked nodes that constitute a linked list.
289 private class ListNode[E
]
297 readable writable var _next
: nullable ListNode[E
]
300 readable writable var _prev
: nullable ListNode[E
]