core :: CircularArray :: defaultinit
# 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
lib/core/collection/circular_array.nit:20,1--247,3