Priority queue: Difference between revisions
Content added Content deleted
(R: return key and value) |
|||
Line 3,546: | Line 3,546: | ||
keys <- values <- NULL |
keys <- values <- NULL |
||
insert <- function(key, value) { |
insert <- function(key, value) { |
||
ord <- findInterval(key, keys) |
|||
keys <<- append(keys, key, |
keys <<- append(keys, key, ord) |
||
values <<- append(values, value, |
values <<- append(values, value, ord) |
||
} |
} |
||
pop <- function() { |
pop <- function() { |
||
head <- values[[1]] |
head <- list(key=keys[1],value=values[[1]]) |
||
values <<- values[-1] |
values <<- values[-1] |
||
keys <<- keys[-1] |
keys <<- keys[-1] |
||
Line 3,567: | Line 3,567: | ||
pq$insert(2, "Tax return") |
pq$insert(2, "Tax return") |
||
while(!pq$empty()) { |
while(!pq$empty()) { |
||
with(pq$pop(), cat(key,":",value,"\n")) |
|||
}</lang>With output:<lang R> |
}</lang>With output:<lang R>1 : Solve RC tasks |
||
2 : Tax return |
|||
3 : Clear drains |
|||
4 : Feed cat |
|||
5 : Make tea</lang>A similar implementation using R5 classes:<lang R>PriorityQueue <- |
|||
setRefClass("PriorityQueue", |
setRefClass("PriorityQueue", |
||
fields = list(keys = "numeric", values = "list"), |
fields = list(keys = "numeric", values = "list"), |
||
methods = list( |
methods = list( |
||
insert = function(key,value) { |
insert = function(key,value) { |
||
insert.order <- findInterval(key, keys) |
insert.order <- findInterval(key, keys) |
||
keys <<- append(keys, key, insert.order) |
keys <<- append(keys, key, insert.order) |
||
values <<- append(values, value, insert.order) |
values <<- append(values, value, insert.order) |
||
}, |
}, |
||
pop = function() { |
pop = function() { |
||
head <- values[[1]] |
head <- list(key=keys[1],value=values[[1]]) |
||
keys <<- keys[-1] |
keys <<- keys[-1] |
||
values <<- values[-1] |
values <<- values[-1] |
||
return(head) |
return(head) |
||
}, |
}, |
||
empty = function() length(keys) == 0 |
empty = function() length(keys) == 0 |
||
))</lang>The only change in the example would be in the instantiation:<lang R>pq <- PriorityQueue$new()</lang> |
))</lang>The only change in the example would be in the instantiation:<lang R>pq <- PriorityQueue$new()</lang>. |
||
=={{header|Racket}}== |
=={{header|Racket}}== |