class_name OldQueue
extends RefCounted

var capacity:int
var head:int = 0
var tail:int = 0
var _block_size:int
var _data:Array = []
var _length:int = 0

func _init(p_capacity:int = 128) -> void:
	_block_size = p_capacity
	capacity = _block_size
	var _block := []
	_block.resize(_block_size)
	_data = [_block]
	_data.resize(len(_data))

func _expand() -> void:
	capacity += _block_size
	var _block := []
	_block.resize(_block_size)
	_data.resize(len(_data) + 1)

func enqueue(item:Variant) -> void:
	if (_length + 1) % capacity == 0:
		_expand()
	@warning_ignore("integer_division")
	_data[tail / _block_size][tail % _block_size] = item
	tail = (tail + 1) % capacity
	_length += 1

func dequeue(shrink:bool = true) -> Variant:
	if is_empty():
		return null
	@warning_ignore("integer_division")
	var item:Variant = _data[head / _block_size][head % _block_size]
	head = (head + 1) % capacity
	_length -= 1
	if shrink:
		_shrink()
	return item

func _shrink() -> void:
	if (_data.size() <= 1) or (capacity <= _block_size) or (_length > capacity - _block_size):
		return

	prints("old head / tail", head, tail)

	var lhs:int = _block_size - (head % _block_size)
	var rhs:int = abs((tail % _block_size) - _block_size)
	var head_block:int = head / _block_size
	var tail_block:int = tail / _block_size
	var move_tail:bool = (head < tail and lhs > rhs) or (head > tail and lhs >= rhs)

	if move_tail:
		for i in range(rhs):
			_data[head_block][i] = _data[tail_block][i]
		tail = (tail - rhs + capacity) % capacity
		_data.erase(tail_block)
	else:
		for i in range(lhs):
			enqueue(dequeue(false))
		_data.erase(head_block)
		head = (head + lhs) % capacity

	prints("new head / tail", head, tail)
	capacity -= _block_size
	_data.resize(capacity)

func peek() -> Variant:
	if is_empty():
		return null
	return _data[head]

func is_empty() -> bool:
	return head == tail

func size() -> int:
	return _length

# This is the iterator index cursor.
var _iter_cursor:int = 0

# This method is an iterator initializer.
func _iter_init(_arg:Variant) -> bool:
	_iter_cursor = head # reset
	return head != tail

# This method checks if the iterator has a next value.
func _iter_next(_arg:Variant) -> bool:
	_iter_cursor = (_iter_cursor + 1) % capacity
	return _iter_cursor < _length

# This method gets the next iterator value.
func _iter_get(_arg:Variant) -> Variant:
	@warning_ignore("integer_division")
	return _data[_iter_cursor / _block_size][_iter_cursor % _block_size]