linear.go

// Copyright ©2015 The gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package linear provides common linear data structures.
package linear

import (
	"k8s.io/kubernetes/third_party/forked/gonum/graph"
)

// NodeStack implements a LIFO stack of graph.Node.
type NodeStack []graph.Node

// Len returns the number of graph.Nodes on the stack.
func (s *NodeStack) Len() int { return len(*s) }

// Pop returns the last graph.Node on the stack and removes it
// from the stack.
func (s *NodeStack) Pop() graph.Node {
	v := *s
	v, n := v[:len(v)-1], v[len(v)-1]
	*s = v
	return n
}

// Push adds the node n to the stack at the last position.
func (s *NodeStack) Push(n graph.Node) { *s = append(*s, n) }

// NodeQueue implements a FIFO queue.
type NodeQueue struct {
	head int
	data []graph.Node
}

// Len returns the number of graph.Nodes in the queue.
func (q *NodeQueue) Len() int { return len(q.data) - q.head }

// Enqueue adds the node n to the back of the queue.
func (q *NodeQueue) Enqueue(n graph.Node) {
	if len(q.data) == cap(q.data) && q.head > 0 {
		l := q.Len()
		copy(q.data, q.data[q.head:])
		q.head = 0
		q.data = append(q.data[:l], n)
	} else {
		q.data = append(q.data, n)
	}
}

// Dequeue returns the graph.Node at the front of the queue and
// removes it from the queue.
func (q *NodeQueue) Dequeue() graph.Node {
	if q.Len() == 0 {
		panic("queue: empty queue")
	}

	var n graph.Node
	n, q.data[q.head] = q.data[q.head], nil
	q.head++

	if q.Len() == 0 {
		q.head = 0
		q.data = q.data[:0]
	}

	return n
}

// Reset clears the queue for reuse.
func (q *NodeQueue) Reset() {
	q.head = 0
	q.data = q.data[:0]
}