1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Implementation of circular lists
16 # This example shows the usage of generics and somewhat a specialisation of collections.
19 # Sequences of elements implemented with a double-linked circular list
21 # Like standard Array or LinkedList, CircularList is a Sequence.
24 # The first node of the list if any
25 # The special case of an empty list is handled by a null node
26 private var node
: nullable CLNode[E
] = null
28 redef fun iterator
do return new CircularListIterator[E
](self)
30 redef fun first
do return self.node
.item
34 var new_node
= new CLNode[E
](e
)
40 # not the first one, so attach nodes correctly.
41 var old_last_node
= n
.prev
43 new_node
.prev
= old_last_node
44 old_last_node
.next
= new_node
59 # not the only one do detach nodes correctly.
60 var prev_prev
= prev
.prev
68 # Circularity has benefits.
70 self.node
= self.node
.prev
75 # Circularity has benefits.
76 self.node
= self.node
.next
80 # Move the first at the last position, the second at the first, etc.
84 if n
== null then return
88 # Sort the list using the Josephus algorithm.
89 fun josephus
(step
: Int)
91 var res
= new CircularList[E
]
92 while not self.is_empty
do
94 for i
in [1..step
[ do self.rotate
103 # Nodes of a CircularList
104 private class CLNode[E
]
108 # The next item in the circular list.
109 # Because of circularity, there is always a next;
110 # so by default let it be self
111 var next
: CLNode[E
] = self
113 # The previous item in the circular list.
114 # Coherence between next and previous nodes has to be maintained by the
116 var prev
: CLNode[E
] = self
119 # An iterator of a CircularList.
120 private class CircularListIterator[E
]
121 super IndexedIterator[E
]
125 # The current node pointed.
126 # Is null if the list is empty.
127 var node
: nullable CLNode[E
]
130 var list
: CircularList[E
]
134 # Empty lists are not OK.
135 # Pointing again the first node is not OK.
136 return self.node
!= null and (self.index
== 0 or self.node
!= self.list
.node
)
141 self.node
= self.node
.next
145 redef fun item
do return self.node
.item
147 init(list
: CircularList[E
])
149 self.node
= list
.node
155 var i
= new CircularList[Int]
156 i
.add_all
([1, 2, 3, 4, 5, 6, 7])