# Deque, Set, and Dict

The container package provides specialized data structures that technically are all derived from the Container class. As such they share all of the container functions with some of them being overridden to account for the specialized data structure. In particular, all of the derived structures still provide positional element access to still behave similar to base R lists.

## Deque

Deques (double ended queues) are a generalization of stacks and queues and therefore also can be used to mimic these.

### Stack

A stack is a last-in-first-out (LIFO) data structure with two basic operations, push and pop, which in this case are mimicked with ref_add and ref_pop.

# Mimic stack
s = deque()
s
# ||
s
# |1, 2|

ref_pop(s)
# [1] 2
ref_pop(s)
# [1] 1
s
# ||

### Queues

A queue is a first-in-first-out (FIFO) data structure with two basic operations, push and pop_left (or enqueue and dequeue), which in this case are mimicked with ref_add and ref_popleft.

# Mimic queue
q = deque()
q
# ||
q
# |1, 2|

ref_popleft(q)
# [1] 1
ref_popleft(q)
# [1] 2
q
# ||

A double-ended queue works on both ends and also provides rotate and reverse operations.

d = as.deque(1:4)
d
# |1L, 2L, 3L, 4L|
rev(d)
# |4L, 3L, 2L, 1L|
rotate(d, 2)
# |3L, 4L, 1L, 2L|

## Set

All elements of a set are unique. Basic set operations are provided.

s1 = setnew(1, "1", 2, cars)
s2 = setnew(1,      2, 3, iris)

s1 & s2
# {1, 2}
s1 | s2
# {1, "1", 2, <<data.frame(50x2)>>, 3, <<data.frame(150x5)>>}
s1 - s2
# {"1", <<data.frame(50x2)>>}

It is important to note that set comparison for the standard set is not order-invariant, e.g.:

s1 = setnew(1, 2, 3)
s2 = setnew(2, 1, 3)
s1 == s2
# [1] FALSE

This property is intended to allow positional access also in sets (remember that technically the 'Set' class is derived from 'Container').

s1[1:2]
# {1, 2}
s2[1:2]
# {2, 1}

If you want order-invariant sets, just use the OrderedSet.

os1 = as.orderedset(s1)
os2 = as.orderedset(s2)
os1
# {1, 2, 3}
os2
# {1, 2, 3}
os1 == os2
# [1] TRUE

Last but not least, the container package only covers a small range of sets and set functions. For a wide range of set functionality and data structures such as fuzzy sets, multisets, customizable sets and intervals, please refer to the sets package by David Meyer.

## Dict

In a dictionary, each element is mapped to a name. In the container package, dicts are always sorted by name, either after initialization ...

d = dict(z = 2, a = 10)
d
# {a = 10, z = 2}

... or when new elements are added.

d[["x"]] = 1
d
# {a = 10, x = 1, z = 2}

If added using the add function, a name clash is signaled to prevent overwriting existing elements.

add(d, z = 3)
# Error: name 'z' exists already

To overwrite, you can use one of three approaches.

d[["z"]] = 3
replace_at(d, z = 3)
# {a = 10, x = 1, z = 3}
update(d, dict(z = 3))
# {a = 10, x = 1, z = 3}

By design, elements can be accessed by name or position, the latter always based on the ordered elements.

d["x", "a"]
# {a = 10, x = 1}
d[2:1]
# {a = 10, x = 1}

# {a = 10, b = 3}