linear.go

Documentation: k8s.io/kubernetes/third_party/forked/gonum/graph/internal/linear

     1  // Copyright ©2015 The gonum Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package linear provides common linear data structures.
     6  package linear
     7  
     8  import (
     9  	"k8s.io/kubernetes/third_party/forked/gonum/graph"
    10  )
    11  
    12  // NodeStack implements a LIFO stack of graph.Node.
    13  type NodeStack []graph.Node
    14  
    15  // Len returns the number of graph.Nodes on the stack.
    16  func (s *NodeStack) Len() int { return len(*s) }
    17  
    18  // Pop returns the last graph.Node on the stack and removes it
    19  // from the stack.
    20  func (s *NodeStack) Pop() graph.Node {
    21  	v := *s
    22  	v, n := v[:len(v)-1], v[len(v)-1]
    23  	*s = v
    24  	return n
    25  }
    26  
    27  // Push adds the node n to the stack at the last position.
    28  func (s *NodeStack) Push(n graph.Node) { *s = append(*s, n) }
    29  
    30  // NodeQueue implements a FIFO queue.
    31  type NodeQueue struct {
    32  	head int
    33  	data []graph.Node
    34  }
    35  
    36  // Len returns the number of graph.Nodes in the queue.
    37  func (q *NodeQueue) Len() int { return len(q.data) - q.head }
    38  
    39  // Enqueue adds the node n to the back of the queue.
    40  func (q *NodeQueue) Enqueue(n graph.Node) {
    41  	if len(q.data) == cap(q.data) && q.head > 0 {
    42  		l := q.Len()
    43  		copy(q.data, q.data[q.head:])
    44  		q.head = 0
    45  		q.data = append(q.data[:l], n)
    46  	} else {
    47  		q.data = append(q.data, n)
    48  	}
    49  }
    50  
    51  // Dequeue returns the graph.Node at the front of the queue and
    52  // removes it from the queue.
    53  func (q *NodeQueue) Dequeue() graph.Node {
    54  	if q.Len() == 0 {
    55  		panic("queue: empty queue")
    56  	}
    57  
    58  	var n graph.Node
    59  	n, q.data[q.head] = q.data[q.head], nil
    60  	q.head++
    61  
    62  	if q.Len() == 0 {
    63  		q.head = 0
    64  		q.data = q.data[:0]
    65  	}
    66  
    67  	return n
    68  }
    69  
    70  // Reset clears the queue for reuse.
    71  func (q *NodeQueue) Reset() {
    72  	q.head = 0
    73  	q.data = q.data[:0]
    74  }
    75
View as plain text