blob: 5d1d08c55cfccd3593313850ba0231d243e9b4d7 [file] [log] [blame]
// Copyright 2015 The Vanadium 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 concurrency
import (
// stack is an implementation of the stack data structure.
type stack struct {
contents []*state
// IncreasingDepth is used to sort states in the increasing order of
// their depth.
type IncreasingDepth []*state
func (states IncreasingDepth) Len() int {
return len(states)
func (states IncreasingDepth) Less(i, j int) bool {
return states[i].depth < states[j].depth
func (states IncreasingDepth) Swap(i, j int) {
states[i], states[j] = states[j], states[i]
// Empty checks if the stack is empty.
func (s *stack) Empty() bool {
return len(s.contents) == 0
// Length returns the length of the stack.
func (s *stack) Length() int {
return len(s.contents)
// Pop removes and returns the top element of the stack. If the stack
// is empty, an error is returned.
func (s *stack) Pop() (*state, error) {
l := len(s.contents)
if l > 0 {
x := s.contents[l-1]
s.contents = s.contents[:l-1]
return x, nil
return nil, errors.New("Stack is empty.")
// Push adds a new element to the top of the stack.
func (s *stack) Push(value *state) {
s.contents = append(s.contents, value)
// Sort sorts the elements of the stack in the decreasing order of
// their depth.
func (s *stack) Sort() {