# An unrolled linked list
#
# A sequence implemented as a linked list of arrays.
#
# This data structure is similar to the `List` but it can benefit from
# better cache performance, lower data overhead for the nodes metadata and
# it spares the GC to allocate many small nodes.
class UnrolledList[E]
super Sequence[E]
# Desired capacity for each nodes
#
# By default at `32`, it can be increased for very large lists.
#
# It can be modified anytime, but newly created nodes may still be assigned
# the same capacity of old nodes when created by `insert`.
var nodes_length = 32 is writable
private var head_node: UnrolledNode[E] = new UnrolledNode[E](nodes_length)
private var tail_node: UnrolledNode[E] = head_node
redef var length = 0
redef fun clear
do
head_node = new UnrolledNode[E](nodes_length)
tail_node = head_node
length = 0
end
# Out parameter of `node_at`
private var index_within_node = 0
private fun node_at(index: Int): UnrolledNode[E]
do
assert index >= 0 and index < length
var node = head_node
while index >= node.length do
index -= node.length
node = node.next.as(not null)
end
index_within_node = index
return node
end
private fun insert_node(node: UnrolledNode[E], prev, next: nullable UnrolledNode[E])
do
if prev != null then
prev.next = node
else head_node = node
if next != null then
next.prev = node
else tail_node = node
node.next = next
node.prev = prev
end
redef fun [](index)
do
var node = node_at(index)
index = index_within_node + node.head_index
return node.items[index]
end
redef fun []=(index, value)
do
var node = node_at(index)
index = index_within_node + node.head_index
node.items[index] = value
end
redef fun push(item)
do
var node = tail_node
if not node.full then
if node.tail_index < node.capacity then
# There's room at the tail
node.tail_index += 1
else
# Move everything over by `d`
assert node.head_index > 0
var d = node.head_index / 2 + 1
node.move_head(node.length, d)
for i in d.times do node.items[node.tail_index - i] = null
node.head_index -= d
node.tail_index += -d+1
end
node.items[node.tail_index-1] = item
else
# New node!
node = new UnrolledNode[E](nodes_length)
insert_node(node, tail_node, null)
node.tail_index = 1
node.items[0] = item
end
length += 1
end
redef fun unshift(item)
do
var node = head_node
if not node.full then
if node.head_index > 0 then
# There's room at the head
node.head_index -= 1
else
# Move everything over by `d`
assert node.tail_index < node.capacity
var d = (node.capacity-node.tail_index) / 2 + 1
node.move_tail(0, d)
for i in d.times do node.items[node.head_index+i] = null
node.head_index += d-1
node.tail_index += d
end
node.items[node.head_index] = item
else
# New node!
node = new UnrolledNode[E](nodes_length)
insert_node(node, null, head_node)
node.head_index = node.capacity-1
node.tail_index = node.capacity
node.items[node.capacity-1] = item
end
length += 1
end
redef fun pop
do
assert not_empty
var node = tail_node
while node.length == 0 do
# Delete empty node
var nullable_node = node.prev
assert is_not_empty: nullable_node != null
node = nullable_node
node.next = null
self.tail_node = node
end
var item = node.items[node.tail_index-1]
node.tail_index -= 1
length -= 1
return item
end
redef fun shift
do
assert not_empty
var node = head_node
while node.length == 0 do
# Delete empty node
var nullable_node = node.next
assert is_not_empty: nullable_node != null
node = nullable_node
node.prev = null
self.head_node = node
end
var item = node.items[node.head_index]
node.head_index += 1
length -= 1
return item
end
redef fun insert(item, index)
do
if index == length then
push item
return
end
var node = node_at(index)
index = index_within_node
if node.full then
# Move half to a new node
var new_node = new UnrolledNode[E](nodes_length.max(node.capacity))
# Plug in the new node
var next_node = node.next
insert_node(new_node, node, next_node)
# Move items at and after `index` to the new node
var to_displace = node.length-index
var offset = (new_node.capacity-to_displace)/2
for i in [0..to_displace[ do
new_node.items[offset+i] = node.items[index+i]
node.items[index+i] = null
end
new_node.head_index = offset
new_node.tail_index = offset + to_displace
node.tail_index -= to_displace
# Store `item`
if index > node.capacity / 2 then
new_node.items[offset-1] = item
new_node.head_index -= 1
else
node.items[node.head_index+index] = item
node.tail_index += 1
end
else
if node.tail_index < node.capacity then
# Move items towards the tail
node.move_tail(index, 1)
node.tail_index += 1
node.items[node.head_index + index] = item
else
# Move items towards the head
node.move_head(index, 1)
node.items[node.head_index + index-1] = item
node.head_index -= 1
end
end
length += 1
end
redef fun remove_at(index)
do
var node = node_at(index)
index = index_within_node + node.head_index
# Shift left all the elements after `index`
for i in [index+1 .. node.tail_index[ do
node.items[i-1] = node.items[i]
end
node.tail_index -= 1
node.items[node.tail_index] = null
length -= 1
var next_node = node.next
var prev_node = node.prev
if node.is_empty and (next_node != null or prev_node != null) then
# Empty and non-head or tail node, delete
if next_node != null then
next_node.prev = node.prev
else tail_node = prev_node.as(not null)
if prev_node != null then
prev_node.next = node.next
else head_node = next_node.as(not null)
end
end
redef fun iterator do return new UnrolledIterator[E](self)
end
lib/more_collections/more_collections.nit:351,1--603,3