--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Implementation of circular lists
+# This example shows the usage of generics and somewhat a specialisation of collections.
+module circular_list
+
+# Sequences of elements implemented with a double-linked circular list
+class CircularList[E]
+ # Like standard Array or LinkedList, CircularList is a Sequence.
+ super Sequence[E]
+
+ # NaiveCollection contains working (but inefficient) implementation of
+ # the methods of Collection.
+ super NaiveCollection[E]
+
+ # The first node of the list if any
+ # The special case of an empty list is handled by a null node
+ private var node: nullable CLNode[E] = null
+
+ redef fun iterator do return new CircularListIterator[E](self)
+
+ redef fun first do return self.node.item
+
+ redef fun push(e)
+ do
+ var new_node = new CLNode[E](e)
+ var n = self.node
+ if n == null then
+ # the first node
+ self.node = new_node
+ else
+ # not the first one, so attach nodes correctly.
+ var old_last_node = n.prev
+ new_node.next = n
+ new_node.prev = old_last_node
+ old_last_node.next = new_node
+ n.prev = new_node
+ end
+ end
+
+ redef fun pop
+ do
+ var n = self.node
+ assert n != null
+ var prev = n.prev
+ if prev == n then
+ # the only node
+ self.node = null
+ return n.item
+ end
+ # not the only one do detach nodes correctly.
+ var prev_prev = prev.prev
+ n.prev = prev_prev
+ prev_prev.next = n
+ return prev.item
+ end
+
+ redef fun unshift(e)
+ do
+ # Circularity has benefits.
+ push(e)
+ self.node = self.node.prev
+ end
+
+ redef fun shift
+ do
+ # Circularity has benefits.
+ self.node = self.node.next
+ return self.pop
+ end
+
+ # Move the first at the last position, the second at the first, etc.
+ fun rotate
+ do
+ var n = self.node
+ if n == null then return
+ self.node = n.next
+ end
+
+ # Sort the list using the Josephus algorithm.
+ fun josephus(step: Int)
+ do
+ var res = new CircularList[E]
+ while not self.is_empty do
+ # count 'step'
+ for i in [1..step[ do self.rotate
+ # kill
+ var x = self.shift
+ res.add(x)
+ end
+ self.node = res.node
+ end
+end
+
+# Nodes of a CircularList
+private class CLNode[E]
+ # The current item
+ var item: E
+
+ # The next item in the circular list.
+ # Because of circularity, there is always a next;
+ # so by default let it be self
+ var next: CLNode[E] = self
+
+ # The previous item in the circular list.
+ # Coherence between next and previous nodes has to be maintained by the
+ # circular list.
+ var prev: CLNode[E] = self
+end
+
+# An iterator of a CircularList.
+private class CircularListIterator[E]
+ super IndexedIterator[E]
+
+ redef var key: Int
+
+ # The current node pointed.
+ # Is null if the list is empty.
+ var node: nullable CLNode[E]
+
+ # The list iterated.
+ var list: CircularList[E]
+
+ redef fun is_ok
+ do
+ # Empty lists are not OK.
+ # Pointing again the first node is not OK.
+ return self.node != null and (self.key == 0 or self.node != self.list.node)
+ end
+
+ redef fun next
+ do
+ self.node = self.node.next
+ self.key += 1
+ end
+
+ redef fun item do return self.node.item
+
+ init(list: CircularList[E])
+ do
+ self.node = list.node
+ self.list = list
+ self.key = 0
+ end
+end
+
+var i = new CircularList[Int]
+i.add_all([1, 2, 3, 4, 5, 6, 7])
+print i.first
+print i.join(":")
+
+i.push(8)
+print i.shift
+print i.pop
+i.unshift(0)
+print i.join(":")
+
+i.josephus(3)
+print i.join(":")
nitlanguage / nit.git / commitdiff