On 01/05/2012 09:18 AM, Tom Roche wrote:
William Dunlap Wed, 4 Jan 2012 22:54:41 +0000
R functions [can] use their enclosing environments to save state.
Aha!
makeStack<- function () {
stack<- list()
list(pop = function() {
if (length(stack) == 0) { # get from an enclosing env.
retval<- NULL
} else {
retval<- stack[[length(stack)]] # get from an enclosing env.
stack<<- stack[-length(stack)] # assign in an enclosing env.
}
retval
}, push = function(x) {
stack[[length(stack) + 1]]<<- x # assign in an enclosing env.
invisible(x)
})
}
Thanks, that's quite clear.
One point is that subsetting with "[" or extending with
stack[[length(stack) + 1]] triggers a copy of stack. Better to pre-allocate
stack <- vector("list", 100)
curr <- 0L
and fill, e.g., push with
curr <<- curr + 1L
stack[[curr]] <<- x
plus bounds check and perhaps growth when necessary.
There are various encapsulations of this method in R. See, e.g.,
"reference classes" or the "proto" package.
I can't see a reference-class implementation, but I did find
Probably Bill was pointing to ?ReferenceClasses. My attempt at
implementing a stack as a reference class led, ironically, to copying
issues anyway (below; maybe there's a different implementation?)
Efficient R programming usually involves operations on vectors, rather
than the iteration implied by a stack. This might change your conclusion
that a stack-based solution is appropriate.
Martin
Reference class implementation
.Stack <- setRefClass("Stack",
fields=list(stack="list", curr="integer"),
methods=list(
initialize=function(stackSize=100L, ...) {
callSuper(stack=vector("list", stackSize), curr=0L, ...)
},
push=function(val) {
curr <<- curr + 1L
if (curr > length(stack))
## double size; could be a bad choice
length(stack) <<- 2L * length(stack)
stack[[curr]] <<- val
invisible(val)
},
pop=function() {
if (curr == 0L)
NULL # sentinel: empty
else {
val <- stack[[curr]]
curr <<- curr - 1L
val
}
},
show=function() {
cat("Class:", class(.self), "\n")
cat("current size:", .self$curr, "\n")
cat("maximum size:", length(.self$stack), "\n")
if (.self$curr) {
cat("head:\n")
print(.self$stack[[1L]])
}
}))
and then
> stack <- .Stack$new()
> tracemem(stack$stack)
[1] "<0x1afc090>"
> stack$push(10)
tracemem[0x1afc090 -> 0x9283a0]: <Anonymous>
tracemem[0x9283a0 -> 0xb96450]: <Anonymous> <Anonymous>
> stack$push(10)
tracemem[0xb96450 -> 0x1b2a7d0]: <Anonymous> <Anonymous>
> stack
Class: Stack
current size: 2
maximum size: 100
head:
[1] 10
> while (!is.null(val <- stack$pop()))
+ cat("val:", val, "\n")
val: 10
val: 10
https://stat.ethz.ch/pipermail/r-help/2010-March/230353.html (slightly edited)
[Subject:] [R] Stack type
[From:] Gabor Grothendieck ggrothendieck at gmail.com
[Date:] Tue Mar 2 14:33:43 CET 2010
library(proto)
Stack<- proto(new = function(.) proto(Stack,
stack = NULL,
push = function(., el) { .$stack<- c(list(el), .$stack) },
pop = function(.) {
stopifnot(length(.$stack)> 0)
out<- .$stack[[1]]
.$stack[[1]]<- NULL
out
}))
mystack<- Stack$new()
mystack$push( 1 )
mystack$push( letters )
mystack$pop()
mystack$pop()
mystack$pop() # gives an error
Thanks again! Tom Roche<tom_ro...@pobox.com>
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
--
Computational Biology
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N. PO Box 19024 Seattle, WA 98109
Location: M1-B861
Telephone: 206 667-2793
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
