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 # NaiveCollection contains working (but inefficient) implementation of
25 # the methods of Collection.
26 super NaiveCollection[E
]
28 # The first node of the list if any
29 # The special case of an empty list is handled by a null node
30 private var node
: nullable CLNode[E
] = null
32 redef fun iterator
do return new CircularListIterator[E
](self)
34 redef fun first
do return self.node
.item
38 var new_node
= new CLNode[E
](e
)
44 # not the first one, so attach nodes correctly.
45 var old_last_node
= n
.prev
47 new_node
.prev
= old_last_node
48 old_last_node
.next
= new_node
63 # not the only one do detach nodes correctly.
64 var prev_prev
= prev
.prev
72 # Circularity has benefits.
74 self.node
= self.node
.prev
79 # Circularity has benefits.
80 self.node
= self.node
.next
84 # Move the first at the last position, the second at the first, etc.
88 if n
== null then return
92 # Sort the list using the Josephus algorithm.
93 fun josephus
(step
: Int)
95 var res
= new CircularList[E
]
96 while not self.is_empty
do
98 for i
in [1..step
[ do self.rotate
107 # Nodes of a CircularList
108 private class CLNode[E
]
112 # The next item in the circular list.
113 # Because of circularity, there is always a next;
114 # so by default let it be self
115 var next
: CLNode[E
] = self
117 # The previous item in the circular list.
118 # Coherence between next and previous nodes has to be maintained by the
120 var prev
: CLNode[E
] = self
123 # An iterator of a CircularList.
124 private class CircularListIterator[E
]
125 super IndexedIterator[E
]
129 # The current node pointed.
130 # Is null if the list is empty.
131 var node
: nullable CLNode[E
]
134 var list
: CircularList[E
]
138 # Empty lists are not OK.
139 # Pointing again the first node is not OK.
140 return self.node
!= null and (self.index
== 0 or self.node
!= self.list
.node
)
145 self.node
= self.node
.next
149 redef fun item
do return self.node
.item
151 init(list
: CircularList[E
])
153 self.node
= list
.node
159 var i
= new CircularList[Int]
160 i
.add_all
([1, 2, 3, 4, 5, 6, 7])