package types

import (
	"sync/atomic"
	"unsafe"
)

type node[T any] struct {
	val  atomic.Pointer[T]
	next atomic.Pointer[node[T]]
}

type Queue[T any] interface {
	Enqueue(T)
	Dequeue() T
	Len() uint64
}

type queue[T any] struct {
	head, tail *node[T]
	length     atomic.Uint64
}

func NewQueue[T any]() Queue[T] {
	n := node[T]{}
	return &queue[T]{head: &n, tail: &n}
}

func (q *queue[T]) Enqueue(v T) {
	n := node[T]{val: atomic.Pointer[T]{}}
	n.val.Store(&v)
	for {
		if q.tail.next.CompareAndSwap(nil, &n) {
			atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&q.tail)), unsafe.Pointer(&n))
			q.length.Add(1)
			return
		}
	}
}

func (q *queue[T]) Dequeue() T {
	headAddr := (*unsafe.Pointer)(unsafe.Pointer(&q.head))
	for {
		var result T
		head := atomic.LoadPointer(headAddr)
		n := q.head.next.Load()
		if n == nil {
			return result
		}
		if atomic.CompareAndSwapPointer(headAddr, head, unsafe.Pointer(n)) {
			q.length.Add(^uint64(0)) // Переполнение намеренное, это отнимает единицу от счетчика.
			if r := n.val.Load(); r != nil {
				return *r
			}
			return result
		}
	}
}

func (q *queue[T]) Len() uint64 {
	return q.length.Load()
}