96 lines
1.7 KiB
Go
96 lines
1.7 KiB
Go
package collection
|
||
|
||
import (
|
||
. "gitea.zaclys.com/bvaudour/gob/option"
|
||
)
|
||
|
||
// Queue représente une file d’élément.
|
||
// Une file est une collection où les éléments suivant la logique “premier arrivé, premier servi“.
|
||
type Queue[T any] struct {
|
||
first *chain[T]
|
||
last *chain[T]
|
||
size uint
|
||
}
|
||
|
||
// Len retourne le nombre d’éléments de la file.
|
||
func (q Queue[T]) Len() uint {
|
||
return q.size
|
||
}
|
||
|
||
func (q *Queue[T]) push(e T) {
|
||
var (
|
||
isEmpty = q.size == 0
|
||
oldLast Option[*chain[T]]
|
||
)
|
||
|
||
if !isEmpty {
|
||
oldLast = Some(q.last)
|
||
}
|
||
q.last = nextChain(e, oldLast)
|
||
|
||
if isEmpty {
|
||
q.first = q.last
|
||
}
|
||
q.size++
|
||
}
|
||
|
||
// Push ajoute tous les éléments d’entrée dans la file.
|
||
func (q *Queue[T]) Push(elems ...T) {
|
||
for _, e := range elems {
|
||
q.push(e)
|
||
}
|
||
}
|
||
|
||
// Concatenate concatène deux files.
|
||
func (q1 *Queue[T]) Concatenate(q2 *Queue[T]) {
|
||
c, l := q2.first, q2.size
|
||
for i := uint(0); i < l; i++ {
|
||
q1.push(c.value)
|
||
c = c.next
|
||
}
|
||
}
|
||
|
||
// Pop dépile le premier élément de la file et le retourne.
|
||
func (q *Queue[T]) Pop() (e Option[T]) {
|
||
if q.size > 0 {
|
||
e = Some(q.first.value)
|
||
q.first = q.first.next
|
||
q.size--
|
||
if q.size == 0 {
|
||
q.last = q.first
|
||
}
|
||
}
|
||
|
||
return
|
||
}
|
||
|
||
// ToSlice convertit une file en slice.
|
||
func (q *Queue[T]) ToSlice() (sl []T) {
|
||
sl = make([]T, q.size)
|
||
c := q.first
|
||
for i := uint(0); i < q.size; i++ {
|
||
sl[i] = c.value
|
||
c = c.next
|
||
}
|
||
|
||
return
|
||
}
|
||
|
||
// ToStack convertit une file en pile.
|
||
func (q *Queue[T]) ToStack() (s *Stack[T]) {
|
||
s = &Stack[T]{
|
||
first: q.first,
|
||
size: q.size,
|
||
}
|
||
|
||
return
|
||
}
|
||
|
||
// NewQueue retourne une file initialisée à partir des données d’entrées.
|
||
func NewQueue[T any](elems ...T) (q *Stack[T]) {
|
||
q = new(Stack[T])
|
||
q.Push(elems...)
|
||
|
||
return
|
||
}
|