# 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.orglicensesLICENSE2.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(":")