Efficient data structure to access both end of the sequence.

# 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
# at both ends of the structure (push, pop, shift and unshift) and
# automatic amortized growth.
#
# Therefore it can be used as is or as an 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

lib/core/collection/circular_array.nit:15,1--258,3

module circular_array

Summary

Efficient data structure to access both end of the sequence.

Introduced classes

CircularArray

Efficient data structure to access both end of the sequence.

Introduced classes

class CircularArray[E: nullable Object]

Summary

All class definitions

CircularArray

All class definitions

class CircularArray[E: nullable Object]

Summary

Ancestors

abstract_collection

kernel

Parents

array

Children

collection

Descendants

a_star

a_star-m

abstract_text

abstract_tree

activities

actors

agent_simulation

ai

all

android

android19

angles

api

app

app

app_base

app_kit

array_debug

assets

assets

assets

assets_and_resources

at_boot

attributes

attributes_impl

audio

audio

audio

audio

aware

backtrack

base64

basic_ciphers

bcm2835

binary

bintree

bitmap

bitset

bktree

blink

bmfont

bootstrap

boxes

bucketed_game

bundle

bytes

bytes

c

cache

caching

camera_control

camera_control_android

camera_control_linux

cameras

cameras_cache

cardboard

cardboard

cartesian