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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#[derive(Debug)]
pub struct Stack<T> {
pub sp: usize,
pub contents: Vec<T>,
}
impl<T> Stack<T> {
/// the constructor is need tuple for initializing Stack
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack = structure::Stack::new(vec![1,3,5,7,9]);
/// ```
pub fn new(contents: Vec<T>) -> Stack<T> {
Stack {
sp: contents.len() + 1,
contents: contents,
}
}
/// the constructor is need capacity for allocating memories for Stack\ndon't forget to
/// annotate type
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack : structure::Stack<u8> = structure::Stack::allocate(100); //
/// ```
pub fn allocate(cap: usize) -> Stack<T> {
Stack {
sp: 0,
contents: Vec::with_capacity(cap),
}
}
/// push the value on the top of stack.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack : structure::Stack<u8> = structure::Stack::allocate(100); //
/// stack.push(3);
/// assert_eq!(stack.contents[0],3);
/// ```
pub fn push(&mut self, element: T) {
self.contents.push(element);
self.sp += 1;
}
/// pop the value by the top of stack.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack : structure::Stack<u8> = structure::Stack::allocate(100); //
/// stack.push(3);
/// assert_eq!(stack.pop().unwrap(),3);
/// ```
pub fn pop(&mut self) -> Option<T> {
if self.sp == 0 {
println!("Error! the stack doesn't have enough to pop the value!");
return None;
}
self.sp -= 1;
self.contents.pop()
}
/// get the value by the top of stack without changing contents.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack : structure::Stack<u8> = structure::Stack::allocate(100); //
/// stack.push(3);
/// assert_eq!(*stack.top().unwrap(),3);
/// assert_eq!(stack.pop().unwrap(),3);
/// ```
pub fn top(&self) -> Option<&T> {
if self.sp == 0 {
println!("Error! the stack is empty then coundn't get the contents!");
return None;
}
Some(&self.contents[self.contents.len() - 1])
}
}
impl<T: Clone> Stack<T> {
/// get the value by the base of stack without changing contents.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut stack : structure::Stack<u8> = structure::Stack::allocate(100); //
/// stack.push(3);
/// stack.push(2);
/// assert_eq!(stack.base(),3);
/// assert_eq!(stack.pop().unwrap(),2);
/// ```
pub fn base(&self) -> T {
if self.sp == 0 {
eprintln!("Invalid access out of range");
}
self.contents[0].clone()
}
}
pub struct ArrayStack<T> {
pub size: usize,
pub cap: usize,
pub contents: Vec<T>,
}
impl<T: Clone> ArrayStack<T> {
pub fn new(src: Vec<T>) -> Self {
Self {
size: src.len(),
cap: src.capacity(),
contents: src,
}
}
/// get the value with specifying position.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut arys : structure::ArrayStack<u8> = structure::ArrayStack::new(vec![1,2]);
/// assert_eq!(arys.get(1),2);
/// assert_eq!(arys.get(0),1);
/// ```
pub fn get(&self, index: usize) -> T {
if 0 > index || self.size < index {
eprintln!("Invalid access out of range");
}
self.contents[index].clone()
}
/// set the value with specifying position.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut arys : structure::ArrayStack<u8> = structure::ArrayStack::new(vec![1,2]);
/// assert_eq!(arys.set(1,10),2);
/// assert_eq!(arys.get(1),10);
/// ```
pub fn set(&mut self, index: usize, x: T) -> T {
if 0 > index || self.size < index {
eprintln!("invalid access out of range");
}
let ret: T = self.get(index);
self.contents[index] = x;
ret
}
pub fn update(&mut self) {
self.size = self.contents.len();
self.cap = self.contents.capacity();
}
/// add the value with resizing contents capacities.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut arys : structure::ArrayStack<u8> = structure::ArrayStack::new(vec![1,2]);
/// arys.add(0,100);
/// assert_eq!(arys.get(0),100);
/// ```
pub fn add(&mut self, index: usize, x: T) {
if self.size + 1 >= self.cap {
self.resize();
}
let mut idx: usize = self.size;
loop {
if idx == index {
break;
}
if idx == self.size {
self.contents.push(self.contents[idx - 1].clone());
} else {
self.contents[idx] = self.contents[idx - 1].clone();
}
idx -= 1;
}
self.contents[index] = x;
self.update();
}
/// remove the value with resizing contents capacities.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut arys : structure::ArrayStack<u8> = structure::ArrayStack::new(vec![1,2,3,4,5]);
/// assert_eq!(arys.cap,5);
/// arys.resize();
/// assert_eq!(arys.cap,10);
/// assert_eq!(arys.size,5);
/// assert_eq!(arys.contents.len(),5);
/// ```
pub fn resize(&mut self) {
let mut dst: Vec<T> = Vec::with_capacity(std::cmp::max(self.size * 2, 1));
for idx in 0..self.size {
dst.push(self.contents[idx].clone());
}
self.contents = dst;
self.update();
}
/// remove the value with resizing contents capacities.
///
/// # Examples
///
/// ```
/// extern crate drumatech;
/// use drumatech::structure;
/// let mut arys : structure::ArrayStack<u8> = structure::ArrayStack::new(vec![1,2,3,4,5]);
/// arys.remove(4);
/// assert_eq!(arys.get(0),1);
/// arys.remove(2);
/// assert_eq!(arys.get(2),4);
/// assert_eq!(arys.contents.len(),3);
/// ```
pub fn remove(&mut self, index: usize) -> T {
let x: T = self.contents[index].clone();
for idx in index..self.size - 1 {
self.contents[idx] = self.contents[idx + 1].clone();
}
self.contents.resize(self.size - 1, x.clone());
self.update();
x
}
}