-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.go
105 lines (89 loc) · 3.05 KB
/
stack.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*******************************************************************************
* Copyright (c) 2009-2022 Crater Dog Technologies™. All Rights Reserved. *
*******************************************************************************
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. *
* *
* This code is free software; you can redistribute it and/or modify it under *
* the terms of The MIT License (MIT), as published by the Open Source *
* Initiative. (See http://opensource.org/licenses/MIT) *
*******************************************************************************/
package collections
import (
fmt "fmt"
)
// STACK IMPLEMENTATION
// This constructor creates a new empty stack with the default capacity.
// The default capacity is 16 values.
func Stack[V Value]() StackLike[V] {
return StackWithCapacity[V](0)
}
// This constructor creates a new empty stack with the specified capacity.
func StackWithCapacity[V Value](capacity int) StackLike[V] {
// Groom the arguments.
if capacity < 1 {
capacity = 16 // The default value.
}
// Return an empty stack.
var values = List[V]()
return &stack[V]{values, values, capacity}
}
// This constructor creates a new stack from the specified sequence. The stack
// uses the default capacity
func StackFromSequence[V Value](sequence Sequential[V]) StackLike[V] {
var v = Stack[V]()
var iterator = Iterator(sequence)
iterator.ToEnd()
for iterator.HasPrevious() {
var value = iterator.GetPrevious()
v.AddValue(value)
}
return v
}
// This type defines the structure and methods associated with a stack of
// values. A stack implements last-in-first-out semantics.
// This type is parameterized as follows:
// - V is any type of value.
type stack[V Value] struct {
// Note: The delegated methods don't see the real collection type.
Sequential[V]
values ListLike[V]
capacity int
}
// LIFO INTERFACE
// This method retrieves the capacity of this stack.
func (v *stack[V]) GetCapacity() int {
return v.capacity
}
// This method adds the specified value to the top of this stack.
func (v *stack[V]) AddValue(value V) {
if v.values.GetSize() == v.capacity {
panic(fmt.Sprintf(
"Attempted to add a value onto a stack that has reached its capacity: %v\nvalue: %v\nstack: %v\n",
v.capacity,
value,
v))
}
v.values.AddValue(value)
}
// This method retrieves from this stack the value that is on top of it.
func (v *stack[V]) GetTop() V {
if v.values.IsEmpty() {
panic("Attempted to retrieve the top of an empty stack!")
}
return v.values.GetValue(-1)
}
// This method removes from this stack the value that is on top of it.
func (v *stack[V]) RemoveTop() V {
if v.values.IsEmpty() {
panic("Attempted to remove the top of an empty stack!")
}
return v.values.RemoveValue(-1)
}
// This method removes all values from this stack.
func (v *stack[V]) RemoveAll() {
v.values.RemoveAll()
}
// GO INTERFACE
func (v *stack[V]) String() string {
return FormatCollection(v)
}