<!DOCTYPE html>
<!-- Generated by pkgdown: do not edit by hand --><html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Datastructures tutorial • datastructures</title>
<!-- jquery --><script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js" integrity="sha256-CSXorXvZcTkaix6Yvo6HppcZGetbYMGWSFlBw8HfCJo=" crossorigin="anonymous"></script><!-- Bootstrap --><link href="https://cdnjs.cloudflare.com/ajax/libs/bootswatch/3.4.0/lumen/bootstrap.min.css" rel="stylesheet" crossorigin="anonymous">
<script src="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.4.1/js/bootstrap.min.js" integrity="sha256-nuL8/2cJ5NDSSwnKD8VqreErSWHtnEP9E7AySL+1ev4=" crossorigin="anonymous"></script><!-- bootstrap-toc --><link rel="stylesheet" href="../bootstrap-toc.css">
<script src="../bootstrap-toc.js"></script><!-- Font Awesome icons --><link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.12.1/css/all.min.css" integrity="sha256-mmgLkCYLUQbXn0B1SRqzHar6dCnv9oZFPEC1g1cwlkk=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.12.1/css/v4-shims.min.css" integrity="sha256-wZjR52fzng1pJHwx4aV2AO3yyTOXrcDW7jBpJtTwVxw=" crossorigin="anonymous">
<!-- clipboard.js --><script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.6/clipboard.min.js" integrity="sha256-inc5kl9MA1hkeYUt+EC3BhlIgyp/2jDIyBLS6k3UxPI=" crossorigin="anonymous"></script><!-- headroom.js --><script src="https://cdnjs.cloudflare.com/ajax/libs/headroom/0.11.0/headroom.min.js" integrity="sha256-AsUX4SJE1+yuDu5+mAVzJbuYNPHj/WroHuZ8Ir/CkE0=" crossorigin="anonymous"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/headroom/0.11.0/jQuery.headroom.min.js" integrity="sha256-ZX/yNShbjqsohH1k95liqY9Gd8uOiE1S4vZc+9KQ1K4=" crossorigin="anonymous"></script><!-- pkgdown --><link href="../pkgdown.css" rel="stylesheet">
<script src="../pkgdown.js"></script><link href="../extra.css" rel="stylesheet">
<meta property="og:title" content="Datastructures tutorial">
<meta property="og:description" content="datastructures">
<!-- mathjax --><script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js" integrity="sha256-nvJJv9wWKEm88qvoQl9ekL2J+k/RWIsaSScxxlsrv8k=" crossorigin="anonymous"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/config/TeX-AMS-MML_HTMLorMML.js" integrity="sha256-84DKXVJXs0/F8OTMzX4UR909+jtl4G7SPypPavF+GfA=" crossorigin="anonymous"></script><!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body data-spy="scroll" data-target="#toc">
    <div class="container template-article">
      <header><div class="navbar navbar-inverse navbar-fixed-top" role="navigation">
  <div class="container">
    <div class="navbar-header">
      <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
      <span class="navbar-brand">
        <a class="navbar-link" href="../index.html">datastructures</a>
        <span class="version label label-default" data-toggle="tooltip" data-placement="bottom" title="Released version">0.2.9</span>
      </span>
    </div>

    <div id="navbar" class="navbar-collapse collapse">
      <ul class="nav navbar-nav">
<li class="dropdown">
  <a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">
    Vignettes
     
    <span class="caret"></span>
  </a>
  <ul class="dropdown-menu" role="menu">
<li>
      <a href="../articles/datastructures.html">Tutorial</a>
    </li>
  </ul>
</li>
<li>
  <a href="../reference/index.html">Reference</a>
</li>
<li>
  <a href="../news/index.html">News</a>
</li>
      </ul>
<ul class="nav navbar-nav navbar-right">
<li>
  <a href="http://simon-dirmeier.net">
    <span class="fa fa-home fa-2x"></span>
     
  </a>
</li>
<li>
  <a href="https://github.com/dirmeier/datastructures">
    <span class="fa fa-github fa-2x"></span>
     
  </a>
</li>
<li>
  <a href="http://twitter.com/simon_dirmeier/">
    <span class="fa fa fa fa-twitter fa-2x"></span>
     
  </a>
</li>
      </ul>
</div>
<!--/.nav-collapse -->
  </div>
<!--/.container -->
</div>
<!--/.navbar -->

      

      </header><script src="datastructures_files/accessible-code-block-0.0.1/empty-anchor.js"></script><div class="row">
  <div class="col-md-9 contents">
    <div class="page-header toc-ignore">
      <h1 data-toc-skip>Datastructures tutorial</h1>
            
      
      <small class="dont-index">Source: <a href="https://github.com/dirmeier/datastructures/blob/master/vignettes/datastructures.Rmd"><code>vignettes/datastructures.Rmd</code></a></small>
      <div class="hidden name"><code>datastructures.Rmd</code></div>

    </div>

    
    
<div id="introduction" class="section level2">
<h2 class="hasAnchor">
<a href="#introduction" class="anchor"></a>Introduction</h2>
<p><code>datastructures</code> implements various data structures that are frequently used in computer science. Among these are for example <em>Fibonacci heaps</em>, <em>stacks</em>, <em>queues</em> or <em>hashmaps</em>. Advanced data structures are essential in many computer science and statistics problems, for example graph algorithms or string analysis. The package uses <code>Boost</code> and <code>STL</code> data types and extends these to <code>R</code> with <code>Rcpp</code> modules.</p>
</div>
<div id="fibonacci-and-binomial-heaps" class="section level2">
<h2 class="hasAnchor">
<a href="#fibonacci-and-binomial-heaps" class="anchor"></a>Fibonacci and binomial heaps</h2>
<p>Fibonacci and binomial heaps are priority queue data structures using the minimum heap property. They can be represented using collections of trees or linked lists consisting of <em>nodes</em> of elements. Every node is a pair of keys and values, where the key decides the priority of the <em>node</em> in the heap. Fibonacci heaps have various applications, one of the most famous being in efficiently finding shortest paths using Dijkstra’s algorithm. Fibonacci heaps can add values in amortized <span class="math inline">\(\mathcal{O}(1)\)</span> time and remove the minimum value in <span class="math inline">\(\mathcal{O}(log \, n)\)</span> time making them a good choice in many real world scenarios. Binomial heaps have in general slightly worse asymptotic bounds. However, removing the minimum element (<code>pop</code>) has an asymptotically tight bound of <span class="math inline">\(\Theta(log \, n)\)</span>. The two classes have the exact same methods, so every method explained here is available for the other class, too.</p>
<p>You can create a heap like this:</p>
<div class="sourceCode" id="cb1"><html><body><pre class="r">  <span class="no">fheap</span> <span class="kw">&lt;-</span> <span class="fu">fibonacci_heap</span>(<span class="st">"numeric"</span>)
  <span class="no">bheap</span> <span class="kw">&lt;-</span> <span class="fu">binomial_heap</span>(<span class="st">"numeric"</span>)</pre></body></html></div>
<p>This gives us heaps with <code>numeric</code> keys. You can pick from either <code>integer</code>, <code>numeric</code> or <code>character</code> keys.</p>
<div id="inserting-nodes" class="section level3">
<h3 class="hasAnchor">
<a href="#inserting-nodes" class="anchor"></a>Inserting nodes</h3>
<p>The values an be arbitray, meaning, that you can add <code>data.frames</code>, <code>vectors</code> or any object you like. So if we insert several key-value pairs, the pair with the <em>minimum</em> key would have the highest <em>priority</em>. Let’s insert some values and have a look:</p>
<div class="sourceCode" id="cb2"><html><body><pre class="r">  <span class="no">keys</span>   <span class="kw">&lt;-</span> <span class="fu"><a href="https://rdrr.io/r/base/sample.html">sample</a></span>(<span class="fu"><a href="https://rdrr.io/r/base/seq.html">seq</a></span>(<span class="fl">0</span>, <span class="fl">1</span>, <span class="kw">by</span><span class="kw">=</span><span class="fl">.2</span>))
  <span class="no">values</span> <span class="kw">&lt;-</span> <span class="fu"><a href="https://rdrr.io/r/base/paste.html">paste0</a></span>(<span class="st">"V"</span>, <span class="no">keys</span>)
  <span class="no">fheap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">fheap</span>, <span class="no">keys</span>, <span class="no">values</span>)

  <span class="fu">size</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## [1] 6</code></pre>
<p>There are also some other ways to insert into a heap. If you want to insert a <code>vector</code>ial value, do this:</p>
<div class="sourceCode" id="cb4"><html><body><pre class="r">  <span class="no">fheap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">fheap</span>, -<span class="fl">1</span>, <span class="no">letters</span>[<span class="fl">1</span>:<span class="fl">5</span>])
  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-1`
## [1] "a" "b" "c" "d" "e"</code></pre>
<p>As described above, you can basically add any tope to your heap. Here I add two ke-value pairs. The keys are provided as vectors, while the values are a list of different objects.</p>
<div class="sourceCode" id="cb6"><html><body><pre class="r">  <span class="no">fheap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">fheap</span>, -<span class="fl">2</span>, <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">5</span>))
  <span class="no">fheap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">fheap</span>, -<span class="fl">3</span>, <span class="fu"><a href="https://rdrr.io/r/base/data.frame.html">data.frame</a></span>(<span class="kw">A</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/stats/Normal.html">rnorm</a></span>(<span class="fl">5</span>), <span class="kw">B</span><span class="kw">=</span><span class="fl">1</span>:<span class="fl">5</span>))

  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-3`
##            A B
## 1 -1.7522420 1
## 2 -0.4448897 2
## 3 -1.5316760 3
## 4 -0.2565086 4
## 5 -0.7080480 5</code></pre>
<p><strong>NOTE</strong>: for efficienty it is recommended to insert all values at the same time, if you can do this. This should be way faster. If we insert multiple objects, we need to wrap it around a list.</p>
<div class="sourceCode" id="cb8"><html><body><pre class="r">  <span class="no">fheap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">fheap</span>, <span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(-<span class="fl">4</span>, -<span class="fl">5</span>, -<span class="fl">6</span>), <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">2</span>), <span class="no">letters</span>[<span class="fl">1</span>:<span class="fl">4</span>], <span class="st">"hallo"</span>))</pre></body></html></div>
</div>
<div id="peek-and-pop" class="section level3">
<h3 class="hasAnchor">
<a href="#peek-and-pop" class="anchor"></a>Peek and pop</h3>
<p>Since Fibonacci and binomial heaps use the minimum heap property the first element in the heap should be <code>-6 -&gt; "hello</code>, because -6 has the lowest value.</p>
<div class="sourceCode" id="cb9"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-6`
## [1] "hallo"</code></pre>
<div class="sourceCode" id="cb11"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## [1] 12</code></pre>
<p>That worked nicely. <code>peek</code> gives us the first element from the heap <em>without removing it</em>. If we want to have it removed we call the <code>pop</code> function. Of course this changes the priority of the heap:</p>
<div class="sourceCode" id="cb13"><html><body><pre class="r">  <span class="fu">pop</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-6`
## [1] "hallo"</code></pre>
<div class="sourceCode" id="cb15"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## [1] 11</code></pre>
<p>You can alternatively insert values like this:</p>
<div class="sourceCode" id="cb17"><html><body><pre class="r">  <span class="no">fheap</span>[-<span class="fl">10</span>] <span class="kw">&lt;-</span> <span class="st">"V-1"</span>
  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-10`
## [1] "V-1"</code></pre>
<p>This works for all the described <code>insert</code> methods above.</p>
</div>
<div id="decreasing-the-key-of-a-node" class="section level3">
<h3 class="hasAnchor">
<a href="#decreasing-the-key-of-a-node" class="anchor"></a>Decreasing the key of a node</h3>
<p>Sometimes, we want to decrease a key and rearrange its position in the heap. If we have a <em>unique</em> key this can be easily done:</p>
<div class="sourceCode" id="cb19"><html><body><pre class="r">  <span class="fu">decrease_key</span>(<span class="no">fheap</span>, <span class="kw">from</span><span class="kw">=</span>-<span class="fl">10</span>, <span class="kw">to</span><span class="kw">=</span>-<span class="fl">11</span>)</pre></body></html></div>
<pre><code>## An object of class fibonacci_heap&lt;numeric, SEXP&gt;
## 
## Peek: -11 -&gt; character, ...</code></pre>
<div class="sourceCode" id="cb21"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-11`
## [1] "V-1"</code></pre>
<p>The function takes vectors, so you can also pass vectorial <code>to</code> and <code>from</code> arguments:</p>
<div class="sourceCode" id="cb23"><html><body><pre class="r">  <span class="fu">decrease_key</span>(<span class="no">fheap</span>, <span class="kw">from</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(-<span class="fl">4</span>, -<span class="fl">5</span>), <span class="kw">to</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(-<span class="fl">15</span>, -<span class="fl">13</span>))</pre></body></html></div>
<pre><code>## An object of class fibonacci_heap&lt;numeric, SEXP&gt;
## 
## Peek: -15 -&gt; list, ...</code></pre>
<div class="sourceCode" id="cb25"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-15`
## $`-15`$a
## [1] 2</code></pre>
</div>
<div id="getting-node-ids" class="section level3">
<h3 class="hasAnchor">
<a href="#getting-node-ids" class="anchor"></a>Getting node ids</h3>
<p>However, things get more complicated if we have multiple identical keys and want to decrease a specific one. In this case, in order to decrease to correct node, we need to get its <code>handle</code> first:</p>
<div class="sourceCode" id="cb27"><html><body><pre class="r">  <span class="fu">handle</span>(<span class="no">fheap</span>, -<span class="fl">15</span>)</pre></body></html></div>
<pre><code>## [[1]]
## [[1]]$handle
## [1] "handle-9"
## 
## [[1]]$value
## [[1]]$value$a
## [1] 2</code></pre>
<p>The <code>handle</code> method returns the <code>id</code> of the node and the <code>value</code> that is stored for a given <code>key</code> (in this case -15). Thus if we want to decrease a node with ambiguous key, we also need to specify the handle (e.g. the <code>id</code>):</p>
<div class="sourceCode" id="cb29"><html><body><pre class="r">  <span class="no">hand</span> <span class="kw">&lt;-</span> <span class="fu">handle</span>(<span class="no">fheap</span>, -<span class="fl">15</span>)
  <span class="fu">decrease_key</span>(<span class="no">fheap</span>, -<span class="fl">15</span>, -<span class="fl">20</span>, <span class="no">hand</span><span class="kw">[[</span><span class="fl">1</span>]]$<span class="no">handle</span>)</pre></body></html></div>
<pre><code>## An object of class fibonacci_heap&lt;numeric, SEXP&gt;
## 
## Peek: -20 -&gt; list, ...</code></pre>
<div class="sourceCode" id="cb31"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-20`
## $`-20`$a
## [1] 2</code></pre>
<p>The <code>handle</code> method always returns a list where every element represents a node in the heap. The <code>handle</code> function is vectorized, so you can supply are vector of keys and will receive the handles that fit thse:</p>
<div class="sourceCode" id="cb33"><html><body><pre class="r"> <span class="fu">handle</span>(<span class="no">fheap</span>, <span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(-<span class="fl">3</span>))</pre></body></html></div>
<pre><code>## [[1]]
## [[1]]$handle
## [1] "handle-8"
## 
## [[1]]$value
##            A B
## 1 -1.7522420 1
## 2 -0.4448897 2
## 3 -1.5316760 3
## 4 -0.2565086 4
## 5 -0.7080480 5</code></pre>
<p>Sometimes you don’t know the <code>key</code> or <code>handle</code>, but only the <code>value</code> of a node, and you want to do a <code>decrease-key</code> operation. Suppose you want to decrease the key of a node with value <code>V-1</code>, then you would to need to call <code>handle</code> with a value argument and a missing <code>key</code>:</p>
<div class="sourceCode" id="cb35"><html><body><pre class="r">  <span class="no">hands</span> <span class="kw">&lt;-</span> <span class="fu">handle</span>(<span class="no">fheap</span>, <span class="kw">value</span><span class="kw">=</span><span class="st">"V1"</span>)
  <span class="fu">decrease_key</span>(<span class="no">fheap</span>, <span class="kw">from</span><span class="kw">=</span><span class="no">hands</span><span class="kw">[[</span><span class="fl">1</span>]]$<span class="no">key</span>, <span class="kw">to</span><span class="kw">=</span>-<span class="fl">1000</span>, <span class="no">hands</span><span class="kw">[[</span><span class="fl">1</span>]]$<span class="no">handle</span>)</pre></body></html></div>
<pre><code>## An object of class fibonacci_heap&lt;numeric, SEXP&gt;
## 
## Peek: -1000 -&gt; character, ...</code></pre>
<div class="sourceCode" id="cb37"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">fheap</span>)</pre></body></html></div>
<pre><code>## $`-1000`
## [1] "V1"</code></pre>
<p><strong>NOTE</strong>: Getting the handles from a value is a costly operation, because we need to compare all entries of the heap with the supplied argument value. If your supplied argument is, for instance, a large dataframe this will quickly become slow. So it is recommended to use this function cautiously.</p>
<p>The handle function for values can take multiple elements, too. However, here we need to supply a <code>list</code> and not a vector (for obvious reasons).</p>
<div class="sourceCode" id="cb39"><html><body><pre class="r">  <span class="no">hands</span> <span class="kw">&lt;-</span> <span class="fu">handle</span>(<span class="no">fheap</span>, <span class="kw">value</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="st">"V1"</span>, <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">2</span>)))
  <span class="no">hands</span></pre></body></html></div>
<pre><code>## [[1]]
## [[1]]$handle
## [1] "handle-4"
## 
## [[1]]$key
## [1] -1000
## 
## 
## [[2]]
## [[2]]$handle
## [1] "handle-9"
## 
## [[2]]$key
## [1] -20</code></pre>
</div>
<div id="retrieving-values-from-a-heap" class="section level3">
<h3 class="hasAnchor">
<a href="#retrieving-values-from-a-heap" class="anchor"></a>Retrieving values from a heap</h3>
<p>Finally, you can get all data from a heap, by calling the <code>value</code> function:</p>
<div class="sourceCode" id="cb41"><html><body><pre class="r">  <span class="no">val</span> <span class="kw">&lt;-</span> <span class="fu">values</span>(<span class="no">fheap</span>)
  <span class="no">val</span>[<span class="fl">1</span>:<span class="fl">2</span>]</pre></body></html></div>
<pre><code>## $`-1000`
## $`-1000`$handle
## [1] "handle-4"
## 
## $`-1000`$key
## [1] -1000
## 
## $`-1000`$value
## [1] "V1"
## 
## 
## $`-20`
## $`-20`$handle
## [1] "handle-9"
## 
## $`-20`$key
## [1] -20
## 
## $`-20`$value
## $`-20`$value$a
## [1] 2</code></pre>
<p>In all of these scenarios neither the key nor the value need to be unique, because the handle (node id) always is.</p>
</div>
<div id="clearing-the-heap" class="section level3">
<h3 class="hasAnchor">
<a href="#clearing-the-heap" class="anchor"></a>Clearing the heap</h3>
<p>You can remove all entries from a heap by calling:</p>
<div class="sourceCode" id="cb43"><html><body><pre class="r">  <span class="no">fheap</span> <span class="kw">&lt;-</span> <span class="fu">clear</span>(<span class="no">fheap</span>)
  <span class="no">fheap</span></pre></body></html></div>
<pre><code>## An object of class fibonacci_heap&lt;numeric, SEXP&gt;
## 
## Peek: NULL -&gt; NULL, ...</code></pre>
</div>
<div id="use-case" class="section level3">
<h3 class="hasAnchor">
<a href="#use-case" class="anchor"></a>Use case</h3>
<p>As a last example, consider this use case whre we use a <code>character</code> heap.</p>
<div class="sourceCode" id="cb45"><html><body><pre class="r">  <span class="fu"><a href="https://rdrr.io/r/base/library.html">library</a></span>(<span class="st">'purrr'</span>)
  <span class="no">bheap</span> <span class="kw">&lt;-</span> <span class="fu">binomial_heap</span>(<span class="st">"character"</span>)
  <span class="no">bheap</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">bheap</span>, <span class="no">letters</span>[<span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(<span class="fl">2</span>:<span class="fl">6</span>, <span class="fl">5</span>, <span class="fl">5</span>)], <span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(<span class="fl">2</span>:<span class="fl">6</span>, <span class="fl">5L</span>, <span class="fl">7L</span>))
  <span class="no">bheap</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">bheap</span>, <span class="st">"x"</span>, <span class="fu"><a href="https://rdrr.io/r/base/data.frame.html">data.frame</a></span>(<span class="kw">A</span><span class="kw">=</span><span class="st">"hi"</span>))
  <span class="no">bheap</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">bheap</span>, <span class="st">"x"</span>, <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">2</span>))
  <span class="fu">peek</span>(<span class="no">bheap</span>)</pre></body></html></div>
<pre><code>## $b
## [1] 2</code></pre>
<div class="sourceCode" id="cb47"><html><body><pre class="r">  <span class="no">vector.keys</span> <span class="kw">&lt;-</span> <span class="fu">handle</span>(<span class="no">bheap</span>, <span class="st">"x"</span>) <span class="kw">%&gt;%</span>
    <span class="kw pkg">purrr</span><span class="kw ns">::</span><span class="fu"><a href="https://purrr.tidyverse.org/reference/map.html">map_chr</a></span>(<span class="kw">.f</span> <span class="kw">=</span> <span class="kw">function</span>(<span class="no">x</span>) <span class="no">x</span>$<span class="no">handle</span>)
  <span class="no">vector.keys</span></pre></body></html></div>
<pre><code>## [1] "handle-7" "handle-8"</code></pre>
<div class="sourceCode" id="cb49"><html><body><pre class="r">  <span class="fu">decrease_key</span>(<span class="no">bheap</span>, <span class="kw">from</span><span class="kw">=</span><span class="st">"x"</span>, <span class="kw">to</span><span class="kw">=</span><span class="st">"b"</span>, <span class="kw">handle</span><span class="kw">=</span><span class="no">vector.keys</span>[<span class="fl">1</span>])</pre></body></html></div>
<pre><code>## An object of class binomial_heap&lt;character, SEXP&gt;
## 
## Peek: b -&gt; data.frame, ...</code></pre>
<div class="sourceCode" id="cb51"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">bheap</span>)</pre></body></html></div>
<pre><code>## $b
##    A
## 1 hi</code></pre>
<div class="sourceCode" id="cb53"><html><body><pre class="r">  <span class="no">hand</span> <span class="kw">&lt;-</span> <span class="fu">handle</span>(<span class="no">bheap</span>, <span class="kw">key</span> <span class="kw">=</span> <span class="st">"b"</span>)
  <span class="no">hand</span></pre></body></html></div>
<pre><code>## [[1]]
## [[1]]$handle
## [1] "handle-0"
## 
## [[1]]$value
## [1] 2
## 
## 
## [[2]]
## [[2]]$handle
## [1] "handle-7"
## 
## [[2]]$value
##    A
## 1 hi</code></pre>
<div class="sourceCode" id="cb55"><html><body><pre class="r">  <span class="fu">decrease_key</span>(<span class="no">bheap</span>, <span class="kw">from</span><span class="kw">=</span><span class="st">"b"</span>, <span class="kw">to</span><span class="kw">=</span><span class="st">"a"</span>, <span class="kw">handle</span><span class="kw">=</span><span class="no">hand</span><span class="kw">[[</span><span class="fl">2</span>]]$<span class="no">handle</span>)</pre></body></html></div>
<pre><code>## An object of class binomial_heap&lt;character, SEXP&gt;
## 
## Peek: a -&gt; data.frame, ...</code></pre>
<div class="sourceCode" id="cb57"><html><body><pre class="r">  <span class="fu">pop</span>(<span class="no">bheap</span>)</pre></body></html></div>
<pre><code>## $a
##    A
## 1 hi</code></pre>
<div class="sourceCode" id="cb59"><html><body><pre class="r">  <span class="fu">pop</span>(<span class="no">bheap</span>)</pre></body></html></div>
<pre><code>## $b
## [1] 2</code></pre>
</div>
</div>
<div id="hashmaps-bimaps-and-multimaps" class="section level2">
<h2 class="hasAnchor">
<a href="#hashmaps-bimaps-and-multimaps" class="anchor"></a>Hashmaps, bimaps and multimaps</h2>
<p>Maps use hash functions to store key-value pairs. Given a key, the hash function computes a <em>bucket</em> where the value is stored, making lookup, insertion and deletion on average possible in <span class="math inline">\(\mathcal{O}(1)\)</span> time. In the worst case these runtimes decrease to <span class="math inline">\(\mathcal{O}(n)\)</span> time, where <span class="math inline">\(n\)</span> is the number of entries in a bucket. The difference between the three classes is that hashmaps and multimaps compute a mapping from keys to values (the hash function) <span class="math display">\[ \, f: \mathcal{K} \rightarrow \mathcal{V} \, \]</span> in <strong>‘one direction’</strong>, while bimaps also compute a mapping <span class="math display">\[ \, f: \mathcal{V} \rightarrow \mathcal{K} \, \]</span> in the <strong>‘other direction’</strong>. So a bimap is essentially a combination of two hashmaps. The difference between a hashmap and a multimap is that for hashs only <em>one</em> unique key can be stored for a value, while multimaps allow storing the same key several times fur multiple values,</p>
<p>Hashmaps and multimaps define mappings in a single direction, for that reason we can use arbitrary R objects as values. For bimaps we can only use primitive types, otherwise it will be difficult to access certain key-value pairs.</p>
<p>Let’s quickly have a look at some examples. We define <code>character</code> hashmap and mulimaps and <code>character/integer</code> bimap.</p>
<div class="sourceCode" id="cb61"><html><body><pre class="r">  <span class="no">hash</span>  <span class="kw">&lt;-</span> <span class="fu">hashmap</span>(<span class="st">"character"</span>)
  <span class="no">mm</span>    <span class="kw">&lt;-</span> <span class="fu">multimap</span>(<span class="st">"character"</span>)
  <span class="no">bimap</span> <span class="kw">&lt;-</span> <span class="fu">bimap</span>(<span class="st">"character"</span>, <span class="st">"integer"</span>)</pre></body></html></div>
<p>Insertion to maps works just like before, by calling the <code>insert</code> function or using a subset operator. As explained for hashmap and multimap we can use all kinds of <code>values</code>, for bimaps we need to define the a primitive type as well.</p>
<div class="sourceCode" id="cb62"><html><body><pre class="r">  <span class="no">keys</span>   <span class="kw">&lt;-</span> <span class="fu"><a href="https://rdrr.io/r/base/paste.html">paste0</a></span>(<span class="st">"V"</span>, <span class="fl">1</span>:<span class="fl">5</span>)
  <span class="no">values</span> <span class="kw">&lt;-</span> <span class="fl">1</span>:<span class="fl">5</span>

  <span class="no">hash</span>   <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">hash</span>, <span class="no">keys</span>[<span class="fl">1</span>:<span class="fl">4</span>], <span class="no">values</span>[<span class="fl">1</span>:<span class="fl">4</span>])
  <span class="no">mm</span>     <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">mm</span>, <span class="no">keys</span>[<span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(<span class="fl">2</span>, <span class="fl">2</span>)], <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">1</span>), <span class="fu"><a href="https://rdrr.io/r/base/data.frame.html">data.frame</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/stats/Normal.html">rnorm</a></span>(<span class="fl">5</span>), <span class="fl">2</span>, <span class="fl">3</span>)))
  <span class="no">bimap</span>  <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">bimap</span>, <span class="no">keys</span>[<span class="fl">1</span>:<span class="fl">4</span>], <span class="no">values</span>[<span class="fl">1</span>:<span class="fl">4</span>])

  <span class="no">hash</span>[<span class="no">keys</span>[<span class="fl">5</span>]]  <span class="kw">&lt;-</span> <span class="no">values</span>[<span class="fl">5</span>]
  <span class="no">bimap</span>[<span class="no">keys</span>[<span class="fl">5</span>]] <span class="kw">&lt;-</span> <span class="no">values</span>[<span class="fl">5</span>]
  <span class="no">mm</span>[<span class="no">keys</span>[<span class="fl">5</span>]]    <span class="kw">&lt;-</span> <span class="fu"><a href="https://rdrr.io/r/base/diag.html">diag</a></span>(<span class="fl">5</span>)</pre></body></html></div>
<p>Values (and keys in the case of bimaps) can then be accessed like this:</p>
<div class="sourceCode" id="cb63"><html><body><pre class="r">  <span class="fu">at</span>(<span class="no">hash</span>, <span class="no">keys</span>[<span class="fl">1</span>])</pre></body></html></div>
<pre><code>## [[1]]
## [1] 1</code></pre>
<div class="sourceCode" id="cb65"><html><body><pre class="r">  <span class="no">hash</span>[<span class="no">keys</span>[<span class="fl">1</span>]]</pre></body></html></div>
<pre><code>## [[1]]
## [1] 1</code></pre>
<div class="sourceCode" id="cb67"><html><body><pre class="r">  <span class="fu">at</span>(<span class="no">bimap</span>, <span class="no">keys</span>[<span class="fl">1</span>], <span class="st">"values"</span>)</pre></body></html></div>
<pre><code>## [1] 1</code></pre>
<div class="sourceCode" id="cb69"><html><body><pre class="r">  <span class="fu">at</span>(<span class="no">bimap</span>, <span class="no">values</span>[<span class="fl">2</span>], <span class="st">"keys"</span>)</pre></body></html></div>
<pre><code>## [1] "V2"</code></pre>
<div class="sourceCode" id="cb71"><html><body><pre class="r">  <span class="fu">at</span>(<span class="no">bimap</span>, <span class="no">keys</span>[<span class="fl">1</span>])</pre></body></html></div>
<pre><code>## [1] 1</code></pre>
<div class="sourceCode" id="cb73"><html><body><pre class="r">  <span class="fu">at</span>(<span class="no">mm</span>, <span class="no">keys</span>[<span class="fl">2</span>])</pre></body></html></div>
<pre><code>## [[1]]
##            a X2 X3
## 1  0.1351150  2  3
## 2  0.4606338  2  3
## 3 -0.4498902  2  3
## 4  0.1067527  2  3
## 5 -0.1667827  2  3
## 
## [[2]]
## [[2]]$a
## [1] 1</code></pre>
<div class="sourceCode" id="cb75"><html><body><pre class="r">  <span class="no">mm</span>[<span class="no">keys</span>[<span class="fl">5</span>]]</pre></body></html></div>
<pre><code>## [[1]]
##  [1] 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1</code></pre>
<p>For hashmaps and multimaps the subset-operator <code><a href="https://rdrr.io/r/base/Extract.html">[</a></code> is also supported for accessing elements. This does not make so much sense for bimaps, because here we have to choose whether we want to access keys or values. In the example on the top we showed how both is possible by either providing <code>keys</code> or <code>values</code> as third argument to the <code>get</code> function. If you leave it out, then the third argument defaults to <code>values</code>.</p>
<p>If you want to directly access <code>keys</code> or <code>values</code> as vectors or have a look at a few random elements, you would call:</p>
<div class="sourceCode" id="cb77"><html><body><pre class="r">  <span class="fu">keys</span>(<span class="no">bimap</span>)</pre></body></html></div>
<pre><code>## [1] "V1" "V2" "V3" "V4" "V5"</code></pre>
<div class="sourceCode" id="cb79"><html><body><pre class="r">  <span class="fu">values</span>(<span class="no">hash</span>)</pre></body></html></div>
<pre><code>## [[1]]
## [1] 5
## 
## [[2]]
## [1] 3
## 
## [[3]]
## [1] 2
## 
## [[4]]
## [1] 4
## 
## [[5]]
## [1] 1</code></pre>
<div class="sourceCode" id="cb81"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">bimap</span>)</pre></body></html></div>
<pre><code>## $V1
## [1] 1
## 
## $V2
## [1] 2
## 
## $V3
## [1] 3
## 
## $V4
## [1] 4
## 
## $V5
## [1] 5</code></pre>
<p>Removing entries in all of the three map classes works like this:</p>
<div class="sourceCode" id="cb83"><html><body><pre class="r">  <span class="no">hash</span> <span class="kw">&lt;-</span> <span class="fu">erase</span>(<span class="no">hash</span>, <span class="no">keys</span>[<span class="fl">1</span>])
  <span class="no">hash</span></pre></body></html></div>
<pre><code>## An object of class hashmap&lt;character,T&gt;
## 
## V2 -&gt; integer
## V3 -&gt; integer
## V4 -&gt; integer
## V5 -&gt; integer</code></pre>
<div class="sourceCode" id="cb85"><html><body><pre class="r">  <span class="no">mm</span> <span class="kw">&lt;-</span> <span class="fu">erase</span>(<span class="no">mm</span>, <span class="no">keys</span>[<span class="fl">2</span>])</pre></body></html></div>
<pre><code>## Note: method with signature 'map#vector#missing' chosen for function 'erase',
##  target signature 'multimap#character#missing'.
##  "multimap#vector#ANY" would also be valid</code></pre>
<div class="sourceCode" id="cb87"><html><body><pre class="r">  <span class="no">mm</span></pre></body></html></div>
<pre><code>## An object of class multimap&lt;character,T&gt;
## 
## V5 -&gt; numeric</code></pre>
<p>As you can see for multimaps, all key-value pairs get removed, when the function is called as above. If you are interested in only one specific key-value pair, you additionally need to supply the respective value:</p>
<div class="sourceCode" id="cb89"><html><body><pre class="r">  <span class="no">mm</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">mm</span>, <span class="no">keys</span>[<span class="fu"><a href="https://rdrr.io/r/base/c.html">c</a></span>(<span class="fl">2</span>, <span class="fl">2</span>)], <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">1</span>), <span class="fu"><a href="https://rdrr.io/r/base/data.frame.html">data.frame</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fu"><a href="https://rdrr.io/r/stats/Normal.html">rnorm</a></span>(<span class="fl">5</span>), <span class="fl">2</span>, <span class="fl">3</span>)))
  <span class="no">mm</span> <span class="kw">&lt;-</span> <span class="fu">erase</span>(<span class="no">mm</span>, <span class="no">keys</span>[<span class="fl">2</span>], <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">1</span>))
  <span class="no">mm</span>[ <span class="no">keys</span>[<span class="fl">2</span>] ]</pre></body></html></div>
<pre><code>## [[1]]
##             a X2 X3
## 1 -0.43713121  2  3
## 2  0.59779861  2  3
## 3  0.07946596  2  3
## 4 -0.05497089  2  3
## 5 -1.85216964  2  3</code></pre>
<p>For bimaps we can also remove from the other side, i.e. when we provide a value:</p>
<div class="sourceCode" id="cb91"><html><body><pre class="r">  <span class="no">bimap</span> <span class="kw">&lt;-</span> <span class="fu">erase</span>(<span class="no">bimap</span>, <span class="kw">value</span><span class="kw">=</span><span class="no">values</span>[<span class="fl">1</span>])
  <span class="no">bimap</span></pre></body></html></div>
<pre><code>## An object of class bimap&lt;character,T&gt;
## 
## V2 &lt;--&gt; integer
## V3 &lt;--&gt; integer
## V4 &lt;--&gt; integer
## V5 &lt;--&gt; integer</code></pre>
<p>For multimaps, where we allow having the same key several times, removing an entry as above removes <em>all</em> the key-value pairs with the</p>
<p>The three different map types support to easily clear the entire data structure using:</p>
<div class="sourceCode" id="cb93"><html><body><pre class="r">  <span class="fu">clear</span>(<span class="no">bimap</span>)</pre></body></html></div>
<pre><code>## An object of class bimap&lt;character,T&gt;
## 
## NULL &lt;--&gt; NULL</code></pre>
<div class="sourceCode" id="cb95"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">bimap</span>)</pre></body></html></div>
<pre><code>## [1] 0</code></pre>
<div class="sourceCode" id="cb97"><html><body><pre class="r">  <span class="fu">clear</span>(<span class="no">hash</span>)</pre></body></html></div>
<pre><code>## An object of class hashmap&lt;character,T&gt;
## 
## NULL -&gt; NULL</code></pre>
<div class="sourceCode" id="cb99"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">hash</span>)</pre></body></html></div>
<pre><code>## [1] 0</code></pre>
<div class="sourceCode" id="cb101"><html><body><pre class="r">  <span class="fu">clear</span>(<span class="no">mm</span>)</pre></body></html></div>
<pre><code>## An object of class multimap&lt;character,T&gt;
## 
## NULL -&gt; NULL</code></pre>
<div class="sourceCode" id="cb103"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">mm</span>)</pre></body></html></div>
<pre><code>## [1] 0</code></pre>
</div>
<div id="queues-and-stacks" class="section level2">
<h2 class="hasAnchor">
<a href="#queues-and-stacks" class="anchor"></a>Queues and stacks</h2>
<p>Queues and stackes are two list datastructures using the <code>STL</code>’s <code>std::deque</code> in the backend, i.e. insertion at the end and getting the first element can be done in constant time <span class="math inline">\(\mathcal{O}(1)\)</span> . Queues and stacks are for example used in <em>depths-first-search</em> and <em>breadth-first-search</em> making them versatile datastructures. While queues use the <em>first-in-first-out</em> principle, stacks use the <em>last-in-first-out</em> principle.</p>
<p>The two datatypes use the exact same methods. You can instantiate a stack or a queue using:</p>
<div class="sourceCode" id="cb105"><html><body><pre class="r">  <span class="no">qu</span> <span class="kw">&lt;-</span> <span class="fu">queue</span>()
  <span class="no">st</span> <span class="kw">&lt;-</span> <span class="fu"><a href="https://rdrr.io/r/utils/stack.html">stack</a></span>()</pre></body></html></div>
<p>As we heaps and hashmap/multimaps you acn pack anything you want into the containers. Now, let’s again insert some data. Single values can just be supplied as argument, while multiple values need to be packed into a list again.</p>
<div class="sourceCode" id="cb106"><html><body><pre class="r">  <span class="no">qu</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">qu</span>, <span class="fl">1</span>)
  <span class="no">qu</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">qu</span>, <span class="fu"><a href="https://rdrr.io/r/base/list.html">list</a></span>(<span class="fu"><a href="https://rdrr.io/r/stats/Normal.html">rnorm</a></span>(<span class="fl">5</span>), <span class="fl">1</span>, <span class="fu"><a href="https://rdrr.io/r/base/diag.html">diag</a></span>(<span class="fl">3</span>)))
  <span class="no">st</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">st</span>, <span class="fu"><a href="https://rdrr.io/r/base/list.html">as.list</a></span>(<span class="fu"><a href="https://rdrr.io/r/stats/Normal.html">rnorm</a></span>(<span class="fl">5</span>)))
  <span class="no">st</span> <span class="kw">&lt;-</span> <span class="fu">insert</span>(<span class="no">st</span>, <span class="fu"><a href="https://rdrr.io/r/base/data.frame.html">data.frame</a></span>(<span class="kw">a</span><span class="kw">=</span><span class="fl">1</span>:<span class="fl">3</span>, <span class="kw">b</span><span class="kw">=</span><span class="fl">3</span>:<span class="fl">1</span>))</pre></body></html></div>
<p><strong>BEWARE:</strong> If you add <em>one</em> <code>vector</code> to queues and stacks it will add <em>one</em> element:</p>
<div class="sourceCode" id="cb107"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">qu</span>)</pre></body></html></div>
<pre><code>## [1] 1</code></pre>
<div class="sourceCode" id="cb109"><html><body><pre class="r">  <span class="fu">peek</span>(<span class="no">st</span>)</pre></body></html></div>
<pre><code>##   a b
## 1 1 3
## 2 2 2
## 3 3 1</code></pre>
<p>If you want to remove elements, call the <code>pop</code> function which will remove the head of the data structure.</p>
<div class="sourceCode" id="cb111"><html><body><pre class="r">  <span class="fu">pop</span>(<span class="no">st</span>)</pre></body></html></div>
<pre><code>##   a b
## 1 1 3
## 2 2 2
## 3 3 1</code></pre>
<div class="sourceCode" id="cb113"><html><body><pre class="r">  <span class="fu">pop</span>(<span class="no">st</span>)</pre></body></html></div>
<pre><code>## [1] -0.6635281</code></pre>
<p>For a <code>queue</code> <code>pop</code> and <code>peek</code> return the <em>first</em> element that got inserted, while a stack returns the <em>last</em> element that was inserted.</p>
<p>The size of a deque can be computed by calling:</p>
<div class="sourceCode" id="cb115"><html><body><pre class="r">  <span class="fu">size</span>(<span class="no">qu</span>)</pre></body></html></div>
<pre><code>## [1] 4</code></pre>
<p>Stacks and queues can be emptied like this:</p>
<div class="sourceCode" id="cb117"><html><body><pre class="r">  <span class="no">qu</span> <span class="kw">&lt;-</span> <span class="fu">clear</span>(<span class="no">qu</span>)
  <span class="no">qu</span></pre></body></html></div>
<pre><code>## An object of class queue&lt;SEXP&gt;
## 
## Peek: NULL, ...</code></pre>
</div>
<div id="session-info" class="section level2">
<h2 class="hasAnchor">
<a href="#session-info" class="anchor"></a>Session info</h2>
<div class="sourceCode" id="cb119"><html><body><pre class="r">  <span class="fu"><a href="https://rdrr.io/r/utils/sessionInfo.html">sessionInfo</a></span>()</pre></body></html></div>
<pre><code>## R version 4.0.2 (2020-06-22)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 20.04.1 LTS
## 
## Matrix products: default
## BLAS/LAPACK: /usr/lib/x86_64-linux-gnu/openblas-openmp/libopenblasp-r0.3.8.so
## 
## locale:
##  [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=de_CH.UTF-8        LC_COLLATE=en_US.UTF-8    
##  [5] LC_MONETARY=de_CH.UTF-8    LC_MESSAGES=en_US.UTF-8   
##  [7] LC_PAPER=de_CH.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=de_CH.UTF-8 LC_IDENTIFICATION=C       
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] purrr_0.3.4          datastructures_0.2.9 Rcpp_1.0.5          
## 
## loaded via a namespace (and not attached):
##  [1] codetools_0.2-16 rprojroot_1.3-2  digest_0.6.25    crayon_1.3.4    
##  [5] assertthat_0.2.1 MASS_7.3-51.6    R6_2.4.1         backports_1.1.8 
##  [9] magrittr_1.5     evaluate_0.14    stringi_1.4.6    rlang_0.4.7     
## [13] rstudioapi_0.11  fs_1.5.0         rmarkdown_2.3    pkgdown_1.5.1   
## [17] desc_1.2.0       tools_4.0.2      stringr_1.4.0    yaml_2.2.1      
## [21] xfun_0.16        compiler_4.0.2   memoise_1.1.0    htmltools_0.5.0 
## [25] knitr_1.29</code></pre>
</div>
  </div>

  <div class="col-md-3 hidden-xs hidden-sm" id="pkgdown-sidebar">

        <nav id="toc" data-toggle="toc"><h2 data-toc-skip>Contents</h2>
    </nav>
</div>

</div>



      <footer><div class="copyright">
  <p>Developed by <a href="http://www.simon-dirmeier.net">Simon Dirmeier</a>.</p>
</div>

<div class="pkgdown">
  <p>Site built with <a href="https://pkgdown.r-lib.org/">pkgdown</a> 1.5.1.</p>
</div>

      </footer>
</div>

  


  </body>
</html>
