RDLL {R6DS}

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.

Details

A doubly linked list is an ordered list of elements with multiple operations. The DLL is a powerful sequantial data structure in the sense that it can be regarded as the generalized version of the data structures stack, queue, deque.

The class RDLL inherits the RDeque class, and therefor it has all the methods that RDeque has.

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

It is worth noting that the classes RSet inherits the RDLL class, and therefor it has all the methods that the RDLL has.

The elements in the DLL are not necessarily to be of the same type, and they can be any R objects.

References

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

Immutable Methods

The immutable methods do not change the instance.

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

The show method takes a funtion input (argument callback) specifying how to handle the elements in the DLL. It also takes ... as the additional arguments for the callback function if any.

By default, the show method prints the elements by using the print function.

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

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

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

and then

instance$show(func, arg1, arg2)

And you can also store the elements by using instances of reference classes. For example,

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

where queue is an instance of RQueue. The code can be

queue <- RQueue$new()

instance$show(func, queue)

elem_at(index)

It returns the element (a copy) 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 bounds of the instance, a NULL will be returned.

peekleft()

See RDeque.

peek()

See RDeque.

Mutable Methods

The mutable methods change the instance.

insert_at(index, val)

This function inserts a new element val at position index. It returns TRUE if the insertion is successful, and FALSE if the index is out of the bounds. It will push all the elements 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 returns and removes the element at position index. It returns NULL if the index is out of the bounds.

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.

Author(s)

Yukai Yang, [e-mail]

See Also

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

Examples

### create a new instance

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

# the previous RDLL instance will be removed if you run
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

# 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)