package ringdeque

import (
	"iter"
)

// A Ring is a deque, implemented using a circular buffer.
type Ring[T any] struct {
	data         []T    // Is not 'nil'.
	growthFactor uint64 // Is greater than 1.
	size         uint64 // Is not greater than 'len(data)'.
	offset       uint64 // Is not greater than 'size'.
}

// Cap returns the capacity of 'r'.
func (r Ring[T]) Cap() int {
	return len(r.data)
}

// Len returns the number of values in 'r'.
func (r Ring[T]) Len() int {
	return int(r.size)
}

// fetch returns the value of a certain index.
// The index MUST NOT be out of range.
func (r Ring[T]) fetch(index uint64) T {
	if index >= r.size {
		panic("Out of range!")
	}

	return r.data[(r.offset+index)%r.size]
}

// Get returns the value at a certain 'index' in 'r'.
// The index must be within the range of the ring.
func (r Ring[T]) Get(index int) T {
	return r.fetch(uint64(index))
}

// Front returns the first value in 'r'.
// The ring must not be empty.
func (r Ring[T]) Front() T {
	return r.fetch(0)
}

// Back returns the last value in 'r'.
// The ring must not be empty.
func (r Ring[T]) Back() T {
	return r.fetch(r.size - 1)
}

// resize replaces the current data table with a new table a new 'capacity'.
// The new capacity must not be less than [Ring.Len].
func (r *Ring[T]) resize(capacity uint64) {
	if capacity < r.size {
		panic("Resize too small!")
	}

	newData := make([]T, capacity)
	for i, value := range r.Entries() {
		newData[i] = value
	}

	r.offset = 0
	r.data = newData
}

// grow increases the size of the array by its growth factor.
// It is guaranteed to not be [Ring.full].
func (r *Ring[T]) grow() {
	if r.size == 0 {
		r.resize(1)
	} else {
		r.resize(r.size * r.growthFactor)
	}
}

// full returns true if every slot in the data table is full.
func (r Ring[T]) full() bool {
	return r.size == uint64(len(r.data))
}

// shrink decreases the capacity of 'r' by its growth factor.
// The ring must be [Ring.sparse].
func (r *Ring[T]) shrink() {
	r.resize(r.size / r.growthFactor)
}

// space returns true if the data table is empty enough to shrink.
func (r *Ring[T]) sparse() bool {
	return r.size*r.growthFactor < uint64(len(r.data))
}

// set updates the value of a certain index.
// The index must be in range.
func (r Ring[T]) set(index uint64, value T) {
	if index >= r.size {
		panic("Out of range!")
	}

	r.data[(r.offset+index)%r.size] = value
}

func (r *Ring[T]) PushBack(value T) {
	if r.full() {
		r.grow()
	}

	r.size++
	r.set(r.size-1, value)
}

func (r *Ring[T]) PopBack() T {
	value := r.fetch(r.size - 1)
	r.size--

	if r.sparse() {
		r.shrink()
	}

	return value
}

func (r *Ring[T]) PushFront(value T) {
	if r.full() {
		r.grow()
	}

	r.offset--
	r.size++
	r.set(0, value)
}

func (r *Ring[T]) PopFront() T {
	value := r.fetch(0)
	r.size--
	r.offset++

	if r.sparse() {
		r.shrink()
	}

	return value
}

func (r Ring[T]) Entries() iter.Seq2[int, T] {
	return func(yield func(int, T) bool) {
		for i := range r.size {
			if !yield(int(i), r.fetch(i)) {
				return
			}
		}
	}
}

func New[T any](options ...Option) *Ring[T] {
	config := &config{
		growthFactor: DefaultCapacity,
		capacity:     DefaultCapacity,
	}

	for _, option := range options {
		option(config)
	}

	return &Ring[T]{
		data:         make([]T, config.capacity),
		offset:       0,
		size:         0,
		growthFactor: config.growthFactor,
	}
}