package queue

type node struct {
	next *node
	val  any
}

var _ Queue = (*Linked)(nil)

// Linked 链表式队列
type Linked struct {
	head     *node
	tail     *node
	length   int
	capacity int
}

func NewLinked(capacity int) *Linked {
	if capacity <= 0 {
		capacity = minCapacity
	}
	if capacity > maxCapacity {
		capacity = maxCapacity
	}
	return &Linked{capacity: capacity}
}

func (lq *Linked) Add(val any) error {
	if lq.length >= lq.capacity {
		return ErrIsFull
	}
	item := &node{
		val: val,
	}
	item.next = lq.head
	lq.head = item
	lq.length++
	return nil
}

func (lq *Linked) AddTail(val any) error {
	if lq.length >= lq.capacity {
		return ErrIsFull
	}
	item := &node{
		val: val,
	}
	if lq.tail == nil {
		lq.head = item
	} else {
		lq.tail.next = item
	}
	lq.length++
	lq.tail = item
	return nil
}

func (lq *Linked) Push(val any) error {
	return lq.Add(val)
}

func (lq *Linked) Pop() any {
	if lq.head != nil {
		val := lq.head.val
		lq.head = lq.head.next
		if lq.head == nil {
			lq.tail = nil
		}
		lq.length--
		return val
	}
	return nil
}

func (lq *Linked) Peek() any {
	if lq.head != nil {
		return lq.head.val
	}
	return nil
}

func (lq *Linked) Empty() bool {
	return lq.head == nil
}

func (lq *Linked) Len() int {
	return lq.length
}

func (lq *Linked) Cap() int {
	return lq.length
}

// Find return index -1 not found.
func (lq *Linked) Find(fn IndexFunc) (any, int) {
	index := 0
	for i := lq.head; i != nil; i = i.next {
		if fn(i.val, index) {
			return i.val, index
		}
		index++
	}
	return nil, -1
}

func (lq *Linked) ToList() []any {
	buf := make([]any, lq.Len())
	index := 0
	for i := lq.head; i != nil; i = i.next {
		buf[index] = i.val
		index++
	}
	return buf
}