From: Jean Privat <jean@pryen.org>
Date: Thu, 3 Dec 2015 19:27:06 +0000 (-0500)
Subject: core: add circular_array
X-Git-Tag: v0.8~57^2~2
X-Git-Url: http://nitlanguage.org?hp=c3bcb932f8f1dcfec1fb1236fcb48d9d6338c04c

core: add circular_array

Signed-off-by: Jean Privat <jean@pryen.org>
---

diff --git a/lib/core/collection/circular_array.nit b/lib/core/collection/circular_array.nit
new file mode 100644
index 0000000..9419853
--- /dev/null
+++ b/lib/core/collection/circular_array.nit
@@ -0,0 +1,258 @@
+# 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.
+
+# Efficient data structure to access both end of the sequence.
+module circular_array
+
+import array
+
+# Efficient data structure to access both end of the sequence.
+#
+# A circular array offers efficient random access,
+# efficient manipulation for both ends of the structure (push, pop, ) and
+# automatic amortized growth.
+#
+# Therefore it can be used as is or as and efficient queue (FIFO/LIFO)
+class CircularArray[E]
+	super Sequence[E]
+
+	# The low-level storage of the items.
+	#
+	# Internally, there is two main configurations
+	#
+	# One part: from `head` to `tail` (inclusive)
+	#
+	# ~~~raw
+	# ...0123...
+	#    h  t
+	# ~~~
+	#
+	# Two parts: from `head` to `capacity-1`,
+	# then from `0` to `tail` (both inclusive)
+	# Test with `head > tail`
+	#
+	# ~~~raw
+	# 345....012
+	#   t    h
+	# ~~~
+	#
+	# For consistency, *length* and *index* are used in the context of the sequence (self) and
+	# *capacity* and *offset* are used in the context of the native array.
+	#
+	# Initially the native is not allocated, the first one is done with `enlarge`
+	private var native: NativeArray[E] is noautoinit
+
+	# The offset of the `first` item in `native`
+	private var head = 0
+
+	# The offset of the `last` item in `native`
+	private var tail: Int = -1
+
+	redef var length = 0
+
+	# Transform an index into an offset.
+	#
+	# The method takes care of the initial gap and the possible wrapping.
+	#
+	# REQUIRE: `0 <= index and index < length`
+	private fun offset(index: Int): Int
+	do
+		assert index >= 0
+		var head = self._head
+		var tail = self._tail
+		var offset = head + index
+
+		if head > tail then
+			# Two parts
+			var capacity = native.length
+			if offset < capacity then
+				return offset
+			end
+			offset -= capacity
+		end
+
+		assert offset <= tail
+		return offset
+	end
+
+	redef fun [](index) do return native[offset(index)]
+
+	redef fun []=(index, item) do
+		var l = length
+		if index == l then
+			push(item)
+			return
+		end
+		native[offset(index)] = item
+	end
+
+	redef fun push(item) do
+		var l = length + 1
+		enlarge(l)
+		length = l
+
+		var native = _native
+		var cap = native.length
+		var t = tail + 1
+		if t >= cap then t -= cap
+
+		native[t] = item
+		tail = t
+	end
+
+	redef fun add_all(items) do
+		enlarge length + items.length
+		super
+	end
+
+	redef fun pop do
+		var l = length - 1
+		assert l >= 0
+		length = l
+
+		var native = _native
+		var t = tail
+		var res = native[t]
+
+		t -= 1
+		if t < 0 then t += native.length
+		tail = t
+
+		return res
+	end
+
+	redef fun unshift(item) do
+		var l = length + 1
+		enlarge(l)
+		length = l
+
+		var native = _native
+		var h = head - 1
+		if h < 0 then h += native.length
+
+		native[h] = item
+		head = h
+	end
+
+	redef fun shift do
+		var l = length - 1
+		assert l >= 0
+		length = l
+
+		var native = _native
+		var h = head
+		var res = native[h]
+
+		h += 1
+		var cap = native.length
+		if h >= cap then h -= cap
+		head = h
+
+		return res
+	end
+
+	# Ensure at least a given capacity
+	#
+	# If the current capacity is enough, then no-op.
+	fun enlarge(capacity: Int)
+	do
+		# First allocation
+		if not isset _native then
+			var new_c = 8
+			while new_c < capacity do new_c *= 2
+			native = new NativeArray[E](new_c)
+			return
+		end
+
+		# Compute more capacity
+		var c = native.length
+		if capacity <= c then return
+		var new_c = c
+		while new_c < capacity do new_c *= 2
+
+		var new_native = new NativeArray[E](new_c)
+
+		# Reallocation: just realign the parts on 0
+		if head > tail then
+			# Two parts
+			native.memmove(head, c-head, new_native, 0)
+			native.memmove(0, tail+1, new_native, c-head)
+		else
+			# One part
+			native.memmove(head, length, new_native, 0)
+		end
+		head = 0
+		tail = length - 1
+		native = new_native
+	end
+
+	redef fun insert(item, index)
+	do
+		# Special insertion at the end (is push)
+		if index >= length then
+			assert index == length
+			push(item)
+			return
+		end
+		assert index >= 0
+
+		var new_len = length + 1
+
+		# TODO be more efficient:
+		# Here, we just allocate a new native and copy everything.
+
+		# Allocate a new native array
+		var c = native.length
+		while c < new_len do c *= 2
+		var new_native = new NativeArray[E](c)
+
+		# Copy everything
+		var i = 0
+		while i < index do
+			new_native[i] = self[i]
+			i += 1
+		end
+		new_native[index] = item
+		var l = length
+		while i < l do
+			new_native[i+1] = self[i]
+			i += 1
+		end
+
+		# Use the new native array
+		length = new_len
+		head = 0
+		tail = new_len - 1
+		native = new_native
+	end
+
+	redef fun clear do
+		length = 0
+		head = 0
+		tail = -1
+	end
+
+	redef fun iterator do return new CircularArrayIterator[E](self)
+end
+
+private class CircularArrayIterator[E]
+	super IndexedIterator[E]
+
+	var array: CircularArray[E]
+
+	redef var index = 0
+	redef fun is_ok do return index < array.length
+	redef fun item do return array[index]
+	redef fun next do index += 1
+end
diff --git a/lib/core/collection/collection.nit b/lib/core/collection/collection.nit
index 0701cc7..2475b68 100644
--- a/lib/core/collection/collection.nit
+++ b/lib/core/collection/collection.nit
@@ -16,6 +16,7 @@ module collection
 import range
 import list
 import array
+import circular_array
 import sorter
 import hash_collection
 import union_find