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
|
# A Stack object backed by a list. The backing list will grow or shrink as
# the stack changes in size.
Stack <- R6Class(
'Stack',
portable = FALSE,
class = FALSE,
public = list(
initialize = function(init = 20L) {
# init is the initial size of the list. It is also used as the minimum
# size of the list as it shrinks.
private$stack <- vector("list", init)
private$init <- init
},
push = function(..., .list = NULL) {
args <- c(list(...), .list)
new_size <- count + length(args)
# Grow if needed; double in size
while (new_size > length(stack)) {
stack[length(stack) * 2] <<- list(NULL)
}
stack[count + seq_along(args)] <<- args
count <<- new_size
invisible(self)
},
pop = function() {
if (count == 0L)
return(NULL)
value <- stack[[count]]
stack[count] <<- list(NULL)
count <<- count - 1L
# Shrink list if < 1/4 of the list is used, down to a minimum size of `init`
len <- length(stack)
if (len > init && count < len/4) {
new_len <- max(init, ceiling(len/2))
stack <<- stack[seq_len(new_len)]
}
value
},
peek = function() {
if (count == 0L)
return(NULL)
stack[[count]]
},
size = function() {
count
},
# Return the entire stack as a list, where the first item in the list is the
# oldest item in the stack, and the last item is the most recently added.
as_list = function() {
stack[seq_len(count)]
}
),
private = list(
stack = NULL, # A list that holds the items
count = 0L, # Current number of items in the stack
init = 20L # Initial and minimum size of the stack
)
)
|
