R6DS (version 1.1.0)

RDLL: The RDLL reference class

Description

The RDLL reference class implements the data structure doubly linked list (DLL).

Usage

RDLL

Format

An object of class R6ClassGenerator of length 24.

Immutable Methods

The immutable methods do not change the nodes of the instance.

show(callback=function(val){print(val)}, ...)

The show method takes a funtion input (argument callback) specifying how to handle the value of each node in the DLL. It also takes ... as the additional arguments for the callback function if any. By default, the show method prints the nodes by using the print function.

callback=function(val){print(val)}

provided that val is "printable".

You can see that show is powerful as it makes it possible to freely manipulate the nodes. For example, you can define

func <- function(val, arg1, arg2){ do something here on val by using arg1 and arg2 }

and then

instance$show(func, arg1, arg2)

And you can also store the node values by using instances of reference classes.

func <- function(val, queue){ queue$enqueue(val) }

where queue is an instance of RQueue, and then

queue <- RQueue$new()

instance$show(func, queue)

toList

This is an active method which returns the node values as a list (a copy). Note that you do not need to write the parenthesis.

elem_at(index)

It returns the value (a copy) of the node at position index (a positive integer). index must be a scalar, and if it is a vector of more than one element, only the first element will be considered. If the value of index is out of the scope of the instance, a NULL will be returned.

is_empty

This is an active method which returns a boolean showing if the DLL is empty. Note that you do not need to write the parenthesis.

peekleft

See RDeque.

peek

See RDeque.

Mutable Methods

The mutable methods changes the nodes of the instance.

insert_at(index, val)

This function inserts a new node with the value val at position index. It returns TRUE if the insertion is successful, and FALSE if the index is out of the scope. It will push all the nodes at and after index rightward.

Thus, suppose that instance is an instance of the class.

insert_at(1, val)

is equivalent to appendleft in RDeque, and

insert_at(instance$size+1, val)

is equivalent to append in RDeque, push in RStack, and enqueue in RQueue.

remove_at(index)

This function removes the node at position index and returns the node's value. It returns NULL if the index is out of the scope. It will connect the two nodes at both sides of the node to be removed.

Thus, suppose that instance is an instance of the class.

remove_at(1, val) is equivalent to popleft in RDeque, and

remove_at(instance$size, val) is equivalent to pop in RDeque and RStack, and dequeue in RQueue.

appendleft(..., collapse=NULL)

See RDeque.

append(..., collapse=NULL)

See RDeque.

popleft()

See RDeque.

pop()

See RDeque.

Details

A doubly linked list is an ordered list of items or nodes. Each node in the DLL has three fields: val storing the value of the node, prev pointing to the previous node and next pointing to the next node.

The DLL is a powerful sequantial data structure in the sense that the data structures stack, queue, deque, set and dictionary can be implemented based on it. The RDLL class has all the methods that RDeque has.

However, in this package, the corresponding RStack, RQueue and RDeque are implemented separately, because they do not need all the features of the DLL.

The DLL is much more friendly and flexible as it offers more useful methods to help the user get access to its nodes than RStack, RQueue and RDeque. See below its immutable methods and mutable methods.

It is worth noting that the classes RSet and RDict inherit the RDLL class, and therefor they have all the methods that the RDLL has.

The elements in the DLL are not necessarily to be of the same type, and they can even be of function type.

References

For the details about the DLL data structure, see DLL at Wikipedia.

See Also

RDeque, RSet, RDict, and R6DS for the introduction of the reference class and some common methods

Examples

# NOT RUN {
### create a new instance

# to create a new instance of the class
dll <- RDLL$new()

# the previous RDLL instance will be removed by running the following
# and the memory allocated for that one will be cleared,
# as now, the variable dll points to another instance of the class.
dll <- RDLL$new(0, 1, 2, collapse=list(3, 4))
# the following sentence is equivalent to the above
dll <- RDLL$new(0, 1, 2, 3, 4)
# where the numbers 0, 1, 2, 3, 4 are appended into the DLL

### immutable methods

# is_empty
dll$is_empty

# show
dll$show()

# elem_at
dll$elem_at(1)

# toList
tmp <- dll$toList

### mutable methods

# insert_at
dll$insert_at(1, -1)
dll$insert_at(dll$size+1, "end")

# remove_at
for(iter in 1:dll$size) dll$remove_at(1)

# }

Run the code above in your browser using DataCamp Workspace