From 6c08336d1e7d79a38ecc2bb7b16c612eb5c8c6c8 Mon Sep 17 00:00:00 2001
From: Jean Privat <jean@pryen.org>
Date: Thu, 17 Feb 2011 05:23:49 -0500
Subject: [PATCH] example: add circular_list.nit

Signed-off-by: Jean Privat <jean@pryen.org>
---
 examples/circular_list.nit  |  171 +++++++++++++++++++++++++++++++++++++++++++
 tests/sav/circular_list.sav |    6 ++
 2 files changed, 177 insertions(+)
 create mode 100644 examples/circular_list.nit
 create mode 100644 tests/sav/circular_list.sav

diff --git a/examples/circular_list.nit b/examples/circular_list.nit
new file mode 100644
index 0000000..8b99d48
--- /dev/null
+++ b/examples/circular_list.nit
@@ -0,0 +1,171 @@
+# 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(":")
diff --git a/tests/sav/circular_list.sav b/tests/sav/circular_list.sav
new file mode 100644
index 0000000..ad5fb1b
--- /dev/null
+++ b/tests/sav/circular_list.sav
@@ -0,0 +1,6 @@
+1
+1:2:3:4:5:6:7
+1
+8
+0:2:3:4:5:6:7
+3:6:2:7:5:0:4
-- 
1.7.9.5