package queue

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
)

/*
	front->item->item->tail 元素个数为3
	item->tail->front-item  元素个数为3
	循环队列，循环队列的好处是增加和删除元素的渐进时间复杂度都是O(1)
*/
type LoopQueue struct {
	/*
		存放数据的数组
	*/
	data []interface{}

	/*
		队首和队尾index的标记
	*/
	front, tail int

	/*
		循环队列中元素的个数.
		size可以使用front和tail计算出来。但是维护一个size会减少一些计算逻辑
	*/
	size int
}

/*
	~=O(1)
	循环队列的进队操作
*/
func (l *LoopQueue) Enqueue(item interface{}) {
	// 当队尾位置+1对数组的容量取余等于队首的时候表示循环队列已经满了
	// 或者直接使用GetSize()==GetCapacity(),元素个数等于容量.
	if (l.tail+1)%cap(l.data) == l.front {
		// 容量扩充为原来的2倍
		l.resize(l.GetCapacity() * 2)
	}
	// 赋值最后一个元素
	l.data[l.tail] = item
	// tail+1对cap取余
	l.tail = (l.tail + 1) % cap(l.data)
	// 数组容量加1
	l.size++
}

/**
~=O(1)
*/
func (l *LoopQueue) Dequeue() (interface{}, error) {
	if l.IsEmpty() {
		return nil, common.IndexError{}
	}
	// 先获取出队的元素
	dequeueItem := l.data[l.front]
	// 避免内存占用
	l.data[l.front] = nil
	// 队首位置+1对容量取余
	l.front = (l.front + 1) % cap(l.data)
	// 元素个数-1
	l.size--
	// 如果元素个数等于当前总容量的四分之一的时候进行缩容操作，容量缩小一半,避免复杂度的震荡.且容量的最小大小不是0
	if l.size <= l.GetCapacity()/4 && l.GetCapacity()/2 != 0 {
		// 缩容为当前大小的1/2倍，也是当前容量的一半
		l.resize(l.GetCapacity() / 2)
	}
	return dequeueItem, nil
}

func (l *LoopQueue) GetFront() (interface{}, error) {
	if l.IsEmpty() {
		return nil, common.IndexError{}
	}
	return l.data[l.front], nil
}

/*
	循环队列中元素的个数
*/
func (l *LoopQueue) GetSize() int {
	return l.size
}

/*
	当队首和队尾相等的时候循环队列是空的
*/
func (l *LoopQueue) IsEmpty() bool {
	return l.front == l.tail
}

func (l *LoopQueue) String() string {
	res := fmt.Sprintf("Queue: size = %d , capacity = %d ", l.size, l.GetCapacity())
	res += "["
	// 使用另一种方式遍历循环队列
	for i := l.front; i != l.tail; i = (i + 1) % cap(l.data) {
		res += fmt.Sprintf("%v", l.data[i])
		// 最后一个元素不带,
		if (i+1)%cap(l.data) != l.tail {
			res += ", "
		}
	}
	res += "]"
	return res
}

/*
	获取循环队列的容量
*/
func (l *LoopQueue) GetCapacity() int {
	return cap(l.data) - 1
}

func (l *LoopQueue) resize(newCapacity int) {
	// 创建创建新slice
	newArray := make([]interface{}, newCapacity+1, newCapacity+1)
	// 复制原slice到新slice，把队首变成0,队尾部变成原cap(l.data),将元素重新分布
	for i := 0; i < l.size; i++ {
		// 从原l.data的front位置开始遍历赋值给newArray
		newArray[i] = l.data[(i+l.front)%cap(l.data)]
	}
	l.data = newArray
	l.front = 0
	//l.size就是原slice的最后一个index,l.tail等于原slice最后一个的index
	l.tail = l.size
}