implements an array-based deque

deque.go

/* 
 * Author: Kevin Yonan
 * License: MIT
 */
package deque


type (
	QNode[T any] struct {
		Next, Prev int
		Data       T
	}
	Deque[T any] struct {
		Nodes            []QNode[T]
		Head, Tail, Free int
	}
)

// Deque.Init ... Initializes a queue with a specific size and sets up the internal linked list.
func (q *Deque[T]) Init(init_size int) {
	q.Nodes = make([]QNode[T], init_size)
	for i := range q.Nodes {
		q.Nodes[i].Prev, q.Nodes[i].Next = i - 1, i + 1
	}
	q.Head, q.Tail, q.Nodes[len(q.Nodes) - 1].Next = -1, -1, -1
	q.Free = len(q.Nodes) - 1
}

// Deque.Reset ... Removes all data from the queue.
func (q *Deque[T]) Reset() {
	for i := range q.Nodes {
		q.Nodes[i].Data = nil
		q.Nodes[i].Prev, q.Nodes[i].Next = i - 1, i + 1
	}
	q.Head, q.Tail, q.Nodes[len(q.Nodes) - 1].Next = -1, -1, -1
	q.Free = len(q.Nodes) - 1
}

// Deque.allocNode ... Gets an unused index of a QNode.
// returns -1 if Deque.Free is negative.
func (q *Deque[T]) allocNode() int {
	if q.Free<0 {
		return -1
	}
	i := q.Free
	q.Free = q.Nodes[i].Prev
	if q.Free >= 0 && q.Free < len(q.Nodes) {
		q.Nodes[q.Free].Next = -1
	}
	return i
}

// Deque.freeNode ... Sets a QNode index as unused.
func (q *Deque[T]) freeNode(i int) {
	if i<0 || i >= len(q.Nodes) {
		return
	} else if q.Free<0 {
		q.Free = i
		q.Nodes[i].Next, q.Nodes[i].Prev = -1, -1
	} else {
		q.Nodes[i].Prev = q.Free
		q.Nodes[i].Next = -1
		q.Nodes[q.Free].Next = i
		q.Free = i
	}
}

// Deque.Grow ... Increases the internal QNode buffer of a queue.
func (q *Deque[T]) Grow() {
	old_len := len(q.Nodes)
	q.Nodes = append(q.Nodes, make([]QNode, old_len * 2)...)
	for i := old_len; i < len(q.Nodes); i++ {
		if i==old_len {
			q.Nodes[i].Prev = q.Free
		} else {
			q.Nodes[i].Prev = i - 1
		}
		q.Nodes[i].Next = i + 1
	}
	q.Nodes[len(q.Nodes) - 1].Next = -1
	q.Free = len(q.Nodes) - 1
}

// Deque.Prepend ... Inserts data to the head of the queue.
// returns false if a node couldn't be allocated or data is nil.
func (q *Deque[T]) Prepend(data T) bool {
	if data==nil {
		return false
	} else if q.Free==-1 {
		q.Grow()
	}
	
	i := q.allocNode()
	if i<0 {
		return false
	}
	
	q.Nodes[i].Data = data
	if q.Head < 0 {
		q.Head, q.Tail = i, i
	} else {
		q.Nodes[i].Next = q.Head
		q.Nodes[i].Prev = -1
		q.Nodes[q.Head].Prev = i
		q.Head = i
	}
	return true
}

// Deque.Append ... Inserts data to the tail of the queue.
// returns false if a node couldn't be allocated or data is nil.
func (q *Deque[T]) Append(data T) bool {
	if data==nil {
		return false
	} else if q.Free==-1 {
		q.Grow()
	}
	
	i := q.allocNode()
	if i<0 {
		return false
	}
	
	q.Nodes[i].Data = data
	if q.Tail<0 {
		q.Head, q.Tail = i, i
	} else {
		q.Nodes[i].Prev = q.Tail
		q.Nodes[i].Next = -1
		q.Nodes[q.Tail].Next = i
		q.Tail = i
	}
	return true
}

// Deque.PopFront ... Pops data from the head of the queue.
// returns nil if the head is out of bounds.
func (q *Deque[T]) PopFront() T {
	if q.Head < 0 || q.Head >= len(q.Nodes) {
		return nil
	}
	
	n := q.Head
	q.Head = q.Nodes[n].Next
	q.Nodes[n].Next, q.Nodes[n].Prev = -1, -1
	
	r := q.Nodes[n].Data
	q.Nodes[n].Data = nil
	q.freeNode(n)
	
	if q.Head != -1 {
		q.Nodes[q.Head].Prev = -1
	} else {
		q.Tail = -1
	}
	return r
}

// Deque.PopBack ... Pops data from the tail of the queue.
// returns nil if the tail is out of bounds.
func (q *Deque[T]) PopBack() T {
	if q.Tail<0 || q.Tail >= len(q.Nodes) {
		return nil
	}
	
	n := q.Tail
	q.Tail = q.Nodes[n].Prev
	q.Nodes[n].Next, q.Nodes[n].Prev = -1, -1
	
	r := q.Nodes[n].Data
	q.Nodes[n].Data = nil
	q.freeNode(n)
	
	if q.Tail != -1 {
		q.Nodes[q.Tail].Next = -1
	} else {
		q.Head = -1
	}
	return r
}

// Deque.GetFront ... Retrieves data from the head of the queue.
// returns nil if the head is out of bounds.
func (q *Deque[T]) GetFront() T {
	if q.Head<0 || q.Head >= len(q.Nodes) {
		return nil
	}
	return q.Nodes[q.Head].Data
}

// Deque.GetBack ... Retrieves data from the tail of the queue.
// returns nil if the tail is out of bounds.
func (q *Deque[T]) GetBack() T {
	if q.Tail<0 || q.Tail >= len(q.Nodes) {
		return nil
	}
	return q.Nodes[q.Tail].Data
}

// Deque.FindNode ... Retrieves the integer index of a QNode that has the matching data.
// returns -1 if no node is matched.
func (q *Deque[T]) FindNode(data T, tail bool) int {
	if tail {
		for i := q.Tail; i >= 0; i = q.Nodes[i].Prev {
			if data==q.Nodes[i].Data {
				return i
			}
		}
	} else {
		for i := q.Head; i >= 0; i = q.Nodes[i].Next {
			if data==q.Nodes[i].Data {
				return i
			}
		}
	}
	return -1
}

// Deque.Empty ... returns if the deque contains no nodes.
func (q *Deque[T]) Empty() bool {
	return q.Head<0 && q.Tail<0
}