Nim for Beginners Sets(final)
This is the nimib styled form of a offline tutorial. Save as .html and run in the browser to view.
unknown
html
2 years ago
48 kB
121
No Index
<!DOCTYPE html>
<html lang="en-us">
<head>
<title>Video Data\documentation.nim</title>
<link rel="icon" href="data:image/svg+xml,<svg xmlns=%22http://www.w3.org/2000/svg%22 viewBox=%220 0 100 100%22><text y=%22.9em%22 font-size=%2280%22>🐳</text></svg>">
<meta content="text/html; charset=utf-8" http-equiv="content-type">
<meta content="width=device-width, initial-scale=1" name="viewport">
<meta content="nimib 0.3.9" name="generator">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/water.css@2/out/dark.min.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/default.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<script src="https://cdn.jsdelivr.net/gh/pietroppeter/nimib@main/assets/highlight.min.js"></script>
<script>hljs.highlightAll();</script>
<style>
.nb-box {
display: flex;
align-items: center;
justify-content: space-between;
}
.nb-small {
font-size: 0.8rem;
}
button.nb-small {
float: right;
padding: 2px;
padding-right: 5px;
padding-left: 5px;
}
section#source {
display:none
}
pre > code {
font-size: 1.2em;
}
.nb-output {
line-height: 1.15;
}
</style>
</head>
<body>
<header>
<div class="nb-box">
<span><a href="..">🏡</a></span>
<span><code>Video Data\documentation.nim</code></span>
<span></span>
</div>
<hr>
</header><main>
<h2>Table of Contents:</h2>
<ol>
<li><a href="#what-are-sets-?">What are Sets ?</a></li>
<li><a href="#set-pros">Set pros</a></li>
<li><a href="#set-cons">Set cons</a></li>
<li><a href="#set-use-cases">Set use cases</a></li>
</ol>
<h2>INTRO - GREETING</h2>
<ul>
<li>TITLE: Sets</li>
</ul>
<h2>INTRO - FOREWORDS</h2>
<p><b>(What is the purpose of this video ?)</b><br>
In this video we will learn about Sets, their pros and cons, as well as their use cases.</p>
<p>The code for this video and it's script/documentation styled with nimib,
is in the link in the description as a form of offline tutorial.</p>
<p><a name = "what-are-sets-?"></a></p>
<h1>What are Sets ?</h1>
<hr />
<ul>
<li>
<p>Sets are a data type that can only have ordinal types for it's elements.
They model a mathematical notion of a set.
In short Sets are a simple data type that is extremely performant and can be operated upon,
with distinct mathematics operations, that makes it very easy to determine what belongs to what.
Here is an example to make you more interested:</p>
</li>
<li>
<p>Say you want to download somefiles from a remote computer via the File Transfer Protocol/FTP.
You can create a "set" with a listing of your local files and another with a listing of the remote files.</p>
<p>Then you can easily create a set of only the files you need to download.</p>
<ul>
<li>files_to_download = remote_files - local_files</li>
</ul>
</li>
<li>
<p>Now let's get into the details of Sets:</p>
<ul>
<li>They are allocated on the stack(hashSets are on the heap)</li>
<li>The size of a Set when using singed integers(normal ints, not the unsigned uint ones we haven't covered yet),
is 0 .. DefaultSetElements-1, where DefaultSetElements is currently always 2^8(0 .. 2^8-1).
While the maximum range length for the base type of a set, is MaxSetElements which is 2^16.
Types with bigger range than 2^16 are forced into this range.
This is because Sets are implemented as high performance bit vectors.</li>
<li>The order of it's elements is unordered</li>
<li>There are also HashSets that can have more types than just ordinal and can be ordered,
but that is the subject of another video</li>
</ul>
</li>
<li>
<p>Empty Set declaration an initialization:</p>
</li>
</ul>
<pre><code class="nohighlight hljs nim"><span class="hljs-comment">#var emptySet = {} #The compiler cannot infer the data type of it's elements, so we must use declaration instead</span>
<span class="hljs-keyword">var</span> emptySet: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>]
<span class="hljs-keyword">echo</span> emptySet</code></pre><pre class="nb-output">{}</pre>
<ul>
<li>As you can see curly brackets {} are Set's constructors</li>
<li>They cannot be accessed via [] brackets, to access them by the index like so:</li>
</ul>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">var</span> accessSet = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-comment">#echo accessSet[0] #Nim's Visual Studio Code Extension catches the error</span>
<span class="hljs-comment">#So instead we do it by calling the element of the Set that we want</span>
<span class="hljs-keyword">if</span> <span class="hljs-string">'a'</span> <span class="hljs-keyword">in</span> accessSet:
<span class="hljs-keyword">echo</span> <span class="hljs-string">"a is in accessSet"</span></code></pre><pre class="nb-output">a is in accessSet</pre>
<p>You can also use the "contains" proc to do the same as with the "in" proc
The reverse as in negated version of the above is done with the "notin" proc</p>
<ul>
<li>Sets can only have unique elements of ordinal types, any duplicates get removed</li>
</ul>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">var</span> deduplicatedSet = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-keyword">echo</span> deduplicatedSet</code></pre><pre class="nb-output">{'a', 'b'}</pre>
<p>As you can see, we had 2x 'a' characters as elements of the Set, but displaying them only shown one.
Again, only unique elements. This is one of the use cases of Sets,
to convert to a Set and back quickly and efficiently.</p>
<ul>
<li>Now that i have mentioned that Sets can only have ordinal types multiple times,
let's see what those actually are in code:</li>
</ul>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">var</span>
int8Set: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">int8</span>]
int16Set: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">int16</span>]
charSet: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>]
<span class="hljs-keyword">type</span>
enumSet = <span class="hljs-keyword">enum</span>
s1, s2, s3</code></pre>
<p>Maximum size of a Set is 2^16 bits for reasons of performance. HashSets do not have such limitations.
Here is a list of all the unique procs for ordinal types:</p>
<ul>
<li><b>succ</b> Successor of the value</li>
<li><b>pred</b> Predecessor of the value</li>
<li><b>inc</b> Increment the ordinal</li>
<li><b>dec</b> Decrement the ordinal</li>
<li><b>high</b> Return the highest possible value</li>
<li><b>low</b> Return the lowest possible value</li>
<li><b>ord</b> Return int value of an ordinal value</li>
</ul>
<p>Like with every container construct in Nim, we can also use a for loop on them.</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">for</span> e <span class="hljs-keyword">in</span> deduplicatedSet:
<span class="hljs-keyword">echo</span> e</code></pre><pre class="nb-output">a
b</pre>
<p>Here is the full list of procs that you can use to operate on Sets:</p>
<ul>
<li><span style="color:pink"><b>incl</b></span>(A, e) same as A = A + e</li>
<li><span style="color:pink"><b>excl</b></span>(A, e) same as A = A - e</li>
<li><span style="color:pink"><b>card</b></span>(A) the cardinality of A (number of elements in A)</li>
<li><span style="color:pink"><b>contains</b></span>(A, e) A contains element e</li>
<li>e <span style="color:pink"><b>in</b></span> A set membership (A contains element e)</li>
<li>e <span style="color:pink"><b>notin</b></span> A A does not contain element e</li>
<li>a <span style="color:pink"><b>*</b></span> b Intersection</li>
<li>a <span style="color:pink"><b>+</b></span> b Union</li>
<li>a <span style="color:pink"><b>-</b></span> b Difference</li>
<li>a <span style="color:pink"><b>==</b></span> b Set equality</li>
<li>a <span style="color:pink"><b><=</b></span> b subset relation (a is subset of b or equal to b)</li>
<li>a <span style="color:pink"><b><</b></span> b Check if a is a subset of b</li>
</ul>
<p>Let's start with difference between 2 similar sets</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">var</span> setA = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-keyword">var</span> setB = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'c'</span>}
<span class="hljs-keyword">echo</span> setA - setB</code></pre><pre class="nb-output">{'b'}</pre>
<p>{'b'} is the difference between setA - setB<br>
If we do the same, but reverse the 2 sets</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">echo</span> setB - setA</code></pre><pre class="nb-output">{'c'}</pre>
<p>We get {'c'} as the element of the difference.<br>
What is happening here, is that setA has element 'a' and 'b',
using "-" setB, it will compare the 2 sets. It will check what setA has that setB doesn't,
and that is character 'b', or 'c' if we reverse it.</p>
<p>Second explanation if you did not understand:
It's basically like subtraction in Math.
If setA has {'a', 'b'} and setB has {'a', 'b', 'c'},
then if we do the difference between the two,
setA being on the left and setB on the right,
then 'a' - 'a' = 0, 'b' - 'b' = 0 and setA has no elements left and the result is empty,
but if we reverse it, setB will still have element 'c'.</p>
<p>By using the + sign with the 2 sets, it will simply join both set's elements and ignore any duplicates</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">echo</span> setA + setB</code></pre><pre class="nb-output">{'a', 'b', 'c'}</pre>
<p>As you can see, only one character 'a' is shown. This is also called a Union(joining) in discrete math.</p>
<p>In order to add or remove elements of sets, instead of using the "add" and "del" procs that sequences use
(strings only have add), we use "incl" short for include and "excl" short for exclude.</p>
<pre><code class="nohighlight hljs nim">setA.incl <span class="hljs-string">'d'</span>
setB.excl <span class="hljs-string">'a'</span>
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB</code></pre><pre class="nb-output">{'a', 'b', 'd'}
{'c'}</pre>
<p>As you can see, setA now has a third element of char 'd', while setB lost char element 'a'</p>
<p>Equality operation "==" checks if both sets members and size is equal, so they have to be exactly the same.</p>
<p>Let's continue with the intersection operation which is done with the star sign "*".
Intersection means elements common/shared between both sets. Right now our sets have none of those,
so let's add them.</p>
<pre><code class="nohighlight hljs nim">setB.incl <span class="hljs-string">'a'</span>
setB.incl <span class="hljs-string">'b'</span>
<span class="hljs-keyword">echo</span> setA * setB
<span class="hljs-keyword">echo</span> setB * setA</code></pre><pre class="nb-output">{'a', 'b'}
{'a', 'b'}</pre>
<p>As you can see reversing doesn't do anything here.</p>
<p>Now let's continue with subsets. Subset meaning if setB has the same elements that setA has,
but not all of them, just a part of them since in order for a subset to exist,
there has to be a set larger than it's subset.
The best way to demonstrate this is with 2x subsets, so let's add another.
Let's also display all 3 before hand to easly see what is going on.</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">var</span> setC = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'d'</span>}
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setC
<span class="hljs-keyword">echo</span> <span class="hljs-string">""</span>
<span class="hljs-keyword">echo</span> setB < setA
<span class="hljs-keyword">echo</span> setC < setA</code></pre><pre class="nb-output">{'a', 'b', 'd'}
{'a', 'b', 'c'}
{'a', 'd'}
false
true</pre>
<p>Here we go, as you can see setC is a subset of setA, but setB is not,
since it's third element of char 'c' is not in setA.
Now even if we remove the different element in setB and make setB identical to setA,
setB will still not be a subset of setA, that is because again, it has to be a subset,
a smaller set than the one we are comparing to.
<br>Let's demonstrate:</p>
<pre><code class="nohighlight hljs nim">setB.excl <span class="hljs-string">'c'</span>
setB.incl <span class="hljs-string">'d'</span>
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setB < setA</code></pre><pre class="nb-output">{'a', 'b', 'd'}
{'a', 'b', 'd'}
false</pre>
<p>As you can see, both sets are identical but the result is false, since a subset has to be smaller.</p>
<p>There is also the smaller or equal operator "<=" which does NOT require for the subset to be smaller,
and will return true in this case.</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">echo</span> setB <= setA</code></pre><pre class="nb-output">true</pre>
<p>Lastly there is the "card" proc, which returns the cardinality of a "set", it's number of elements.
Let's echo all 3 and then "card" all 3:</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setC
<span class="hljs-keyword">echo</span> setA.card
<span class="hljs-keyword">echo</span> setB.card
<span class="hljs-keyword">echo</span> setC.card</code></pre><pre class="nb-output">{'a', 'b', 'd'}
{'a', 'b', 'd'}
{'a', 'd'}
3
3
2</pre>
<p>You can also still use the "len" proc to get the same result of number of elements.</p>
<p>There are also integer sets, intsets module for efficient int sets.
There is also the std/setutils module for a bit more utility for Sets</p>
<p>Now let's move on to 2 very useful use cases for Sets,
the first being using Sets with Enumerators to produce flags.</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">type</span>
<span class="hljs-type">SandboxFlag</span> = <span class="hljs-keyword">enum</span>
allowCast, allowInfiniteLoops
<span class="hljs-keyword">var</span> sandboxFlags: <span class="hljs-built_in">set</span>[<span class="hljs-type">SandboxFlag</span>]
sandboxFlags.incl allowCast <span class="hljs-comment">#E.g allowCast -> Allow unsafe language features</span>
sandboxFlags.incl allowInfiniteLoops
<span class="hljs-comment">#A second more gamey example if the first example was not understandable</span>
<span class="hljs-keyword">type</span>
<span class="hljs-type">Flags</span> = <span class="hljs-keyword">enum</span>
walk, attack, defend
<span class="hljs-keyword">var</span> moves: <span class="hljs-built_in">set</span>[<span class="hljs-type">Flags</span>]
moves.incl walk
moves.incl attack
moves.incl defend
<span class="hljs-keyword">echo</span> moves</code></pre><pre class="nb-output">{walk, attack, defend}</pre>
<p>Not much different on the first glance, than when we used a similar enumerator with a sequence,
but the operations you can do with enumerators in a Set, change the game.</p>
<p>Now the second use case is for Parsing data. In the following example,
we are going to make a "split" proc that will use a set of characters,
in order to search and destroy any of the characters specified in our Set:</p>
<pre><code class="nohighlight hljs nim"><span class="hljs-keyword">import</span> strutils
<span class="hljs-keyword">proc</span> split(s: <span class="hljs-built_in">string</span>; seps: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>] = <span class="hljs-comment">#[strutils.Whitespace]#</span> {<span class="hljs-string">' '</span>, <span class="hljs-string">'!'</span>, <span class="hljs-string">'?'</span>}): <span class="hljs-built_in">string</span> = <span class="hljs-comment">#const Whitespace = {' ', '\t', '\v', '\r', '\n', '\f'}</span>
<span class="hljs-keyword">var</span> splitString = s
<span class="hljs-keyword">var</span> c: <span class="hljs-built_in">int</span>
<span class="hljs-keyword">for</span> sep <span class="hljs-keyword">in</span> seps:
c = splitString.find(sep)
splitString.delete(c, c)
<span class="hljs-literal">result</span> = splitString
<span class="hljs-keyword">var</span> myString = <span class="hljs-string">"Hello , World !?"</span>
<span class="hljs-keyword">echo</span> myString
<span class="hljs-keyword">echo</span> myString.split</code></pre><pre class="nb-output">Hello , World !?
Hello, World </pre>
<p>Here we go.</p>
<p>Now let's move on to Set pros, cons and use cases, many of which i have already mentioned,
but it's always good to have such a list of condensed data,
so that one may check it again to know when to use Sets.</p>
<p><a name = "set-pros"></a></p>
<h1>Set pros</h1>
<hr />
<ul>
<li>
<p>Extremely fast due to bitwise operations happening behind the scenes,
along with being limited to 16 bytes/ordinal types.</p>
</li>
<li>
<p>A ton of powerful operations you can do with them
(membership testing, deduplication, distinct mathematical operations)</p>
</li>
</ul>
<p><a name = "set-cons"></a></p>
<h1>Set cons</h1>
<hr />
<ul>
<li>
<p>No easy way to access an element's data without changing a Set's data to a Sequence,
or another container construct</p>
</li>
<li>
<p>Sets can only store elements of a single data type,
and only ordinal types(there are also HashSets which can be ordered and of any type you want,
but obviously a bit slower, use them if you need Set operations, and normal sets don't cover your data type)</p>
</li>
<li>
<p>Sets are unordered, don't use them if you REALLY need order</p>
<p>Example: you want objects of say bullets in a game,
ordered by time created, so that you can destroy them to free memory and not have the game crash,
due to way too many bullets being rendered in a game. One way of optimizing games with bullets,
is to remove them after a certain amount of time, another is to remove them when they go out of bounds, etc)</p>
</li>
</ul>
<p><a name = "set-use-cases"></a></p>
<h1>Set use cases</h1>
<hr />
<ul>
<li>
<p>Say you want to download some files from a remote computer via the File Transfer Protocol/FTP.
You can create a "set" with a listing of your local files and another with a listing of the remote files.
Then you can easily create a set of only the files you need to download.</p>
<p>files_to_download = remote_files - local_files</p>
</li>
<li>
<p>Removing duplicates/deduplication</p>
</li>
<li>
<p>Ownership checking</p>
</li>
<li>
<p>Say you made your game with a bunch of controller objects,
which are then checked for their existence.
And if they do exist say objectSFX, then sound effects will play,
otherwise the game will have no soud effects.
Or if you want to enable or disable debug mode.
This can again be done with other such constructs,
but if your game has a ton of objects that work in such a way,
then they could all be checking for existence of controller objects to do their function,
which would get really slow with Sequences.</p>
</li>
<li>
<p>Setting compiler flags by using Sets with Enumerators(or moves a unit in a game can do)</p>
</li>
<li>
<p>Parsing data(example 2 just before Set pros)</p>
</li>
</ul>
<h2>OUTRO - AFTERWORDS</h2>
<p>Okay, that's it for this video, thanks for watching like, share and subscribe,
aswell as click the bell icon if you liked it and want more,
you can also follow me on twitter of the same name, and support me on Patreon.
If you had any problems with any part of the video,
let me know in the comment section,
the code of this video, script and documentation, are in the link in the description,
as a form of offline tutorial.</p>
<h3>Thanks to my past and current Patrons</h3>
<p><b>Past Patrons:</b></p>
<ul>
<li>Goose_Egg: From April 4th 2021 to May 10th 2022</li>
<li>Davide Galilei(1x month)</li>
</ul>
<p><b>Current Patrons</b></p>
<ul>
<li>None</li>
</ul>
<p><b>Compiler information</b></p>
<ul>
<li>Version used: 2.0.0</li>
<li>Compiler settings used: none, ORC is now the default memory management option</li>
<li>Timestamps:
<ul>
<li>00:15 Start of video example</li>
</ul>
</li>
</ul>
<p><b>LINKS:</b></p>
<ul>
<li><a href="https://twitter.com/Kiloneie" title="My Twitter">Twitter</a></li>
<li><a href="https://www.patreon.com/Kiloneie?fan_landing=true" title="Patreon">Patreon</a></li>
<li>Video's script/documentation with all of the code styled with nimib as a form of offline tutorial:</li>
<li><a href="https://code.visualstudio.com/shortcuts/keyboard-shortcuts-windows.pdf" title="Visual Studio Code Shortcuts">Visual Studio Code Shortcuts</a></li>
</ul>
<p><b>LINKS to this video's subject:</b></p>
<ul>
<li><a href="https://nim-lang.org/docs/manual.html#types-set-type" title="Set type">Set type</a></li>
<li><a href="https://nim-lang.org/docs/system.html#system-module-sets" title="Set operations and extra modules">Set operations and extra modules</a></li>
<li><a href="https://nim-lang.org/docs/manual.html#types-ordinal-types" title="Ordinal types">Ordinal types</a></li>
<li><a href="https://nim-lang.org/docs/system.html#system-module-ordinals" title="Ordinal operations">Ordinal operations</a></li>
<li><a href="https://nim-lang.org/docs/strutils.html" title="strutils module for the last example/use case parsing data">strutils module for the last example/use case of parsing data</a></li>
</ul>
</main>
<footer>
<div class="nb-box">
<span><span class="nb-small">made with <a href="https://pietroppeter.github.io/nimib/">nimib 🐳</a></span></span>
<span></span>
<span><button class="nb-small" id="show" onclick="toggleSourceDisplay()">Show Source</button></span>
</div>
</footer>
<section id="source">
<pre><code class="nohighlight nim hljs"><span class="hljs-comment">#Do NOT use {} inside nbText: hlMdF""" """ fields... </span>
<span class="hljs-comment">#When using - to make a line a list item, you cannot have ANY one of the lines be an empty line</span>
<span class="hljs-comment">#Use spaces by a factor of 1x and then 2x for every indentation level</span>
<span class="hljs-keyword">import</span> nimib, std/strutils <span class="hljs-comment">#You can use nimib's custom styling or HTML & CSS</span>
nbInit()
nb.darkMode()
<span class="hljs-comment">#nbShow() #This will auto open this file in the browser, but it does not check if it is already open</span>
<span class="hljs-comment">#so it keeps bloody opening one after another, i just want a way to update changes quickly</span>
<span class="hljs-comment"># customize source highlighting:</span>
nb.context[<span class="hljs-string">"highlight"</span>] = <span class="hljs-string">"""
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/default.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>"""</span>
<span class="hljs-comment"># a custom text block that shows markdown source</span>
<span class="hljs-keyword">template</span> nbTextWithSource*(body: <span class="hljs-built_in">untyped</span>) =
newNbBlock(<span class="hljs-string">"nbTextWithSource"</span>, <span class="hljs-literal">false</span>, nb, nb.blk, body):
nb.blk.output = body
nb.blk.context[<span class="hljs-string">"code"</span>] = body
nb.renderPlans[<span class="hljs-string">"nbTextWithSource"</span>] = @[<span class="hljs-string">"mdOutputToHtml"</span>]
nb.partials[<span class="hljs-string">"nbTextWithSource"</span>] = <span class="hljs-string">"""{{&outputToHtml}}
<pre><code class=\"language-markdown\">{{code}}</code></pre>"""</span>
<span class="hljs-comment"># how to add a ToC</span>
<span class="hljs-keyword">var</span>
nbToc: <span class="hljs-type">NbBlock</span>
<span class="hljs-keyword">template</span> addToc =
newNbBlock(<span class="hljs-string">"nbText"</span>, <span class="hljs-literal">false</span>, nb, nbToc, <span class="hljs-string">""</span>):
nbToc.output = <span class="hljs-string">"## Table of Contents:</span><span class="hljs-meta">\n</span><span class="hljs-meta">\n</span><span class="hljs-string">"</span>
<span class="hljs-keyword">template</span> nbSection(name:<span class="hljs-built_in">string</span>) =
<span class="hljs-keyword">let</span> anchorName = name.toLower.replace(<span class="hljs-string">" "</span>, <span class="hljs-string">"-"</span>)
nbText <span class="hljs-string">"<a name = </span><span class="hljs-meta">\"</span><span class="hljs-string">"</span> & anchorName & <span class="hljs-string">"</span><span class="hljs-meta">\"</span><span class="hljs-string">></a></span><span class="hljs-meta">\n</span><span class="hljs-string"># "</span> & name & <span class="hljs-string">"</span><span class="hljs-meta">\n</span><span class="hljs-meta">\n</span><span class="hljs-string">---"</span>
<span class="hljs-comment"># see below, but any number works for a numbered list</span>
nbToc.output.add <span class="hljs-string">"1. <a href=</span><span class="hljs-meta">\"</span><span class="hljs-string">#"</span> & anchorName & <span class="hljs-string">"</span><span class="hljs-meta">\"</span><span class="hljs-string">>"</span> & name & <span class="hljs-string">"</a></span><span class="hljs-meta">\n</span><span class="hljs-string">"</span>
<span class="hljs-comment">#If you get an error from the above line, addToc must be ran before any nbSection </span>
<span class="hljs-comment">#TABLE OF CONTENTS - MUST BE RUN BEFORE ANY nbSection !!!</span>
addToc()
<span class="hljs-comment">#Do NOT forget to have the .html file OPEN at all times, otherwise </span>
<span class="hljs-comment">#live preview will NOT work! ANY live preview!</span>
<span class="hljs-comment">###############</span>
<span class="hljs-comment">#START OF FILE#</span>
<span class="hljs-comment">###############</span>
<span class="hljs-comment">#Adding hlMd or hlMdf enables nimiboost's markdown highlight mode</span>
nbText: <span class="hljs-string">hlMdF"""
## INTRO - GREETING
- TITLE: Sets
## INTRO - FOREWORDS
<b>(What is the purpose of this video ?)</b><br>
In this video we will learn about Sets, their pros and cons, as well as their use cases.
The code for this video and it's script/documentation styled with nimib,
is in the link in the description as a form of offline tutorial.
"""</span>
nbSection <span class="hljs-string">"What are Sets ?"</span>
nbText: <span class="hljs-string">hlMd"""
- Sets are a data type that can only have ordinal types for it's elements.
They model a mathematical notion of a set.
In short Sets are a simple data type that is extremely performant and can be operated upon,
with distinct mathematics operations, that makes it very easy to determine what belongs to what.
Here is an example to make you more interested:
- Say you want to download somefiles from a remote computer via the File Transfer Protocol/FTP.
You can create a "set" with a listing of your local files and another with a listing of the remote files.
Then you can easily create a set of only the files you need to download.
- files_to_download = remote_files - local_files
- Now let's get into the details of Sets:
- They are allocated on the stack(hashSets are on the heap)
- The size of a Set when using singed integers(normal ints, not the unsigned uint ones we haven't covered yet),
is 0 .. DefaultSetElements-1, where DefaultSetElements is currently always 2^8(0 .. 2^8-1).
While the maximum range length for the base type of a set, is MaxSetElements which is 2^16.
Types with bigger range than 2^16 are forced into this range.
This is because Sets are implemented as high performance bit vectors.
- The order of it's elements is unordered
- There are also HashSets that can have more types than just ordinal and can be ordered,
but that is the subject of another video
- Empty Set declaration an initialization:
"""</span>
nbCode:
<span class="hljs-comment">#var emptySet = {} #The compiler cannot infer the data type of it's elements, so we must use declaration instead</span>
<span class="hljs-keyword">var</span> emptySet: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>]
<span class="hljs-keyword">echo</span> emptySet
nbText: <span class="hljs-string">hlMd"""
- As you can see curly brackets {} are Set's constructors
- They cannot be accessed via [] brackets, to access them by the index like so:
"""</span>
nbCode:
<span class="hljs-keyword">var</span> accessSet = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-comment">#echo accessSet[0] #Nim's Visual Studio Code Extension catches the error</span>
<span class="hljs-comment">#So instead we do it by calling the element of the Set that we want</span>
<span class="hljs-keyword">if</span> <span class="hljs-string">'a'</span> <span class="hljs-keyword">in</span> accessSet:
<span class="hljs-keyword">echo</span> <span class="hljs-string">"a is in accessSet"</span>
nbText: <span class="hljs-string">hlMd"""
You can also use the "contains" proc to do the same as with the "in" proc
The reverse as in negated version of the above is done with the "notin" proc
"""</span>
nbText: <span class="hljs-string">hlMd"""
- Sets can only have unique elements of ordinal types, any duplicates get removed
"""</span>
nbCode:
<span class="hljs-keyword">var</span> deduplicatedSet = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-keyword">echo</span> deduplicatedSet
nbText: <span class="hljs-string">hlMd"""
As you can see, we had 2x 'a' characters as elements of the Set, but displaying them only shown one.
Again, only unique elements. This is one of the use cases of Sets,
to convert to a Set and back quickly and efficiently.
- Now that i have mentioned that Sets can only have ordinal types multiple times,
let's see what those actually are in code:
"""</span>
nbCode:
<span class="hljs-keyword">var</span>
int8Set: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">int8</span>]
int16Set: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">int16</span>]
charSet: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>]
<span class="hljs-keyword">type</span>
enumSet = <span class="hljs-keyword">enum</span>
s1, s2, s3
nbText: <span class="hljs-string">hlMd"""
Maximum size of a Set is 2^16 bits for reasons of performance. HashSets do not have such limitations.
Here is a list of all the unique procs for ordinal types:
- <b>succ</b> Successor of the value
- <b>pred</b> Predecessor of the value
- <b>inc</b> Increment the ordinal
- <b>dec</b> Decrement the ordinal
- <b>high</b> Return the highest possible value
- <b>low</b> Return the lowest possible value
- <b>ord</b> Return int value of an ordinal value
Like with every container construct in Nim, we can also use a for loop on them.
"""</span>
nbCode:
<span class="hljs-keyword">for</span> e <span class="hljs-keyword">in</span> deduplicatedSet:
<span class="hljs-keyword">echo</span> e
nbText: <span class="hljs-string">hlMd"""
Here is the full list of procs that you can use to operate on Sets:
- <span style="color:pink"><b>incl</b></span>(A, e) same as A = A + e
- <span style="color:pink"><b>excl</b></span>(A, e) same as A = A - e
- <span style="color:pink"><b>card</b></span>(A) the cardinality of A (number of elements in A)
- <span style="color:pink"><b>contains</b></span>(A, e) A contains element e
- e <span style="color:pink"><b>in</b></span> A set membership (A contains element e)
- e <span style="color:pink"><b>notin</b></span> A A does not contain element e
- a <span style="color:pink"><b>*</b></span> b Intersection
- a <span style="color:pink"><b>+</b></span> b Union
- a <span style="color:pink"><b>-</b></span> b Difference
- a <span style="color:pink"><b>==</b></span> b Set equality
- a <span style="color:pink"><b><=</b></span> b subset relation (a is subset of b or equal to b)
- a <span style="color:pink"><b><</b></span> b Check if a is a subset of b
Let's start with difference between 2 similar sets
"""</span>
nbCode:
<span class="hljs-keyword">var</span> setA = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>}
<span class="hljs-keyword">var</span> setB = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'c'</span>}
<span class="hljs-keyword">echo</span> setA - setB
nbText: <span class="hljs-string">hlMd"""
{'b'} is the difference between setA - setB<br>
If we do the same, but reverse the 2 sets
"""</span>
nbCode:
<span class="hljs-keyword">echo</span> setB - setA
nbText: <span class="hljs-string">hlMd"""
We get {'c'} as the element of the difference.<br>
What is happening here, is that setA has element 'a' and 'b',
using "-" setB, it will compare the 2 sets. It will check what setA has that setB doesn't,
and that is character 'b', or 'c' if we reverse it.
Second explanation if you did not understand:
It's basically like subtraction in Math.
If setA has {'a', 'b'} and setB has {'a', 'b', 'c'},
then if we do the difference between the two,
setA being on the left and setB on the right,
then 'a' - 'a' = 0, 'b' - 'b' = 0 and setA has no elements left and the result is empty,
but if we reverse it, setB will still have element 'c'.
By using the + sign with the 2 sets, it will simply join both set's elements and ignore any duplicates
"""</span>
nbCode:
<span class="hljs-keyword">echo</span> setA + setB
nbText: <span class="hljs-string">hlMd"""
As you can see, only one character 'a' is shown. This is also called a Union(joining) in discrete math.
In order to add or remove elements of sets, instead of using the "add" and "del" procs that sequences use
(strings only have add), we use "incl" short for include and "excl" short for exclude.
"""</span>
nbCode:
setA.incl <span class="hljs-string">'d'</span>
setB.excl <span class="hljs-string">'a'</span>
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
nbText: <span class="hljs-string">hlMd"""
As you can see, setA now has a third element of char 'd', while setB lost char element 'a'
Equality operation "==" checks if both sets members and size is equal, so they have to be exactly the same.
Let's continue with the intersection operation which is done with the star sign "*".
Intersection means elements common/shared between both sets. Right now our sets have none of those,
so let's add them.
"""</span>
nbCode:
setB.incl <span class="hljs-string">'a'</span>
setB.incl <span class="hljs-string">'b'</span>
<span class="hljs-keyword">echo</span> setA * setB
<span class="hljs-keyword">echo</span> setB * setA
nbText: <span class="hljs-string">hlMd"""
As you can see reversing doesn't do anything here.
Now let's continue with subsets. Subset meaning if setB has the same elements that setA has,
but not all of them, just a part of them since in order for a subset to exist,
there has to be a set larger than it's subset.
The best way to demonstrate this is with 2x subsets, so let's add another.
Let's also display all 3 before hand to easly see what is going on.
"""</span>
nbCode:
<span class="hljs-keyword">var</span> setC = {<span class="hljs-string">'a'</span>, <span class="hljs-string">'d'</span>}
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setC
<span class="hljs-keyword">echo</span> <span class="hljs-string">""</span>
<span class="hljs-keyword">echo</span> setB < setA
<span class="hljs-keyword">echo</span> setC < setA
nbText: <span class="hljs-string">hlMd"""
Here we go, as you can see setC is a subset of setA, but setB is not,
since it's third element of char 'c' is not in setA.
Now even if we remove the different element in setB and make setB identical to setA,
setB will still not be a subset of setA, that is because again, it has to be a subset,
a smaller set than the one we are comparing to.
<br>Let's demonstrate:
"""</span>
nbCode:
setB.excl <span class="hljs-string">'c'</span>
setB.incl <span class="hljs-string">'d'</span>
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setB < setA
nbText: <span class="hljs-string">hlMd"""
As you can see, both sets are identical but the result is false, since a subset has to be smaller.
There is also the smaller or equal operator "<=" which does NOT require for the subset to be smaller,
and will return true in this case.
"""</span>
nbCode:
<span class="hljs-keyword">echo</span> setB <= setA
nbText: <span class="hljs-string">hlMd"""
Lastly there is the "card" proc, which returns the cardinality of a "set", it's number of elements.
Let's echo all 3 and then "card" all 3:
"""</span>
nbCode:
<span class="hljs-keyword">echo</span> setA
<span class="hljs-keyword">echo</span> setB
<span class="hljs-keyword">echo</span> setC
<span class="hljs-keyword">echo</span> setA.card
<span class="hljs-keyword">echo</span> setB.card
<span class="hljs-keyword">echo</span> setC.card
nbText: <span class="hljs-string">hlMd"""
You can also still use the "len" proc to get the same result of number of elements.
There are also integer sets, intsets module for efficient int sets.
There is also the std/setutils module for a bit more utility for Sets
Now let's move on to 2 very useful use cases for Sets,
the first being using Sets with Enumerators to produce flags.
"""</span>
nbCode:
<span class="hljs-keyword">type</span>
<span class="hljs-type">SandboxFlag</span> = <span class="hljs-keyword">enum</span>
allowCast, allowInfiniteLoops
<span class="hljs-keyword">var</span> sandboxFlags: <span class="hljs-built_in">set</span>[<span class="hljs-type">SandboxFlag</span>]
sandboxFlags.incl allowCast <span class="hljs-comment">#E.g allowCast -> Allow unsafe language features</span>
sandboxFlags.incl allowInfiniteLoops
<span class="hljs-comment">#A second more gamey example if the first example was not understandable</span>
<span class="hljs-keyword">type</span>
<span class="hljs-type">Flags</span> = <span class="hljs-keyword">enum</span>
walk, attack, defend
<span class="hljs-keyword">var</span> moves: <span class="hljs-built_in">set</span>[<span class="hljs-type">Flags</span>]
moves.incl walk
moves.incl attack
moves.incl defend
<span class="hljs-keyword">echo</span> moves
nbText: <span class="hljs-string">hlMd"""
Not much different on the first glance, than when we used a similar enumerator with a sequence,
but the operations you can do with enumerators in a Set, change the game.
Now the second use case is for Parsing data. In the following example,
we are going to make a "split" proc that will use a set of characters,
in order to search and destroy any of the characters specified in our Set:
"""</span>
nbCode:
<span class="hljs-keyword">import</span> strutils
<span class="hljs-keyword">proc</span> split(s: <span class="hljs-built_in">string</span>; seps: <span class="hljs-built_in">set</span>[<span class="hljs-built_in">char</span>] = <span class="hljs-comment">#[strutils.Whitespace]#</span> {<span class="hljs-string">' '</span>, <span class="hljs-string">'!'</span>, <span class="hljs-string">'?'</span>}): <span class="hljs-built_in">string</span> = <span class="hljs-comment">#const Whitespace = {' ', '\t', '\v', '\r', '\n', '\f'}</span>
<span class="hljs-keyword">var</span> splitString = s
<span class="hljs-keyword">var</span> c: <span class="hljs-built_in">int</span>
<span class="hljs-keyword">for</span> sep <span class="hljs-keyword">in</span> seps:
c = splitString.find(sep)
splitString.delete(c, c)
<span class="hljs-literal">result</span> = splitString
<span class="hljs-keyword">var</span> myString = <span class="hljs-string">"Hello , World !?"</span>
<span class="hljs-keyword">echo</span> myString
<span class="hljs-keyword">echo</span> myString.split
nbText: <span class="hljs-string">hlMd"""
Here we go.
Now let's move on to Set pros, cons and use cases, many of which i have already mentioned,
but it's always good to have such a list of condensed data,
so that one may check it again to know when to use Sets.
"""</span>
nbSection <span class="hljs-string">"Set pros"</span>
nbText: <span class="hljs-string">hlMd"""
- Extremely fast due to bitwise operations happening behind the scenes,
along with being limited to 16 bytes/ordinal types.
- A ton of powerful operations you can do with them
(membership testing, deduplication, distinct mathematical operations)
"""</span>
nbSection <span class="hljs-string">"Set cons"</span>
nbText: <span class="hljs-string">hlMd"""
- No easy way to access an element's data without changing a Set's data to a Sequence,
or another container construct
- Sets can only store elements of a single data type,
and only ordinal types(there are also HashSets which can be ordered and of any type you want,
but obviously a bit slower, use them if you need Set operations, and normal sets don't cover your data type)
- Sets are unordered, don't use them if you REALLY need order
Example: you want objects of say bullets in a game,
ordered by time created, so that you can destroy them to free memory and not have the game crash,
due to way too many bullets being rendered in a game. One way of optimizing games with bullets,
is to remove them after a certain amount of time, another is to remove them when they go out of bounds, etc)
"""</span>
nbSection <span class="hljs-string">"Set use cases"</span>
nbText: <span class="hljs-string">hlMd"""
- Say you want to download some files from a remote computer via the File Transfer Protocol/FTP.
You can create a "set" with a listing of your local files and another with a listing of the remote files.
Then you can easily create a set of only the files you need to download.
files_to_download = remote_files - local_files
- Removing duplicates/deduplication
- Ownership checking
- Say you made your game with a bunch of controller objects,
which are then checked for their existence.
And if they do exist say objectSFX, then sound effects will play,
otherwise the game will have no soud effects.
Or if you want to enable or disable debug mode.
This can again be done with other such constructs,
but if your game has a ton of objects that work in such a way,
then they could all be checking for existence of controller objects to do their function,
which would get really slow with Sequences.
- Setting compiler flags by using Sets with Enumerators(or moves a unit in a game can do)
- Parsing data(example 2 just before Set pros)
"""</span>
nbText: <span class="hljs-string">hlMd"""
## OUTRO - AFTERWORDS
Okay, that's it for this video, thanks for watching like, share and subscribe,
aswell as click the bell icon if you liked it and want more,
you can also follow me on twitter of the same name, and support me on Patreon.
If you had any problems with any part of the video,
let me know in the comment section,
the code of this video, script and documentation, are in the link in the description,
as a form of offline tutorial.
### Thanks to my past and current Patrons
<b>Past Patrons:</b>
- Goose_Egg: From April 4th 2021 to May 10th 2022
- Davide Galilei(1x month)
<b>Current Patrons</b>
- None
<b>Compiler information</b>
- Version used: 2.0.0
- Compiler settings used: none, ORC is now the default memory management option
- Timestamps:
- 00:15 Start of video example
"""</span>
nbText: <span class="hljs-string">hlMdF"""
<b>LINKS:</b>
- [Twitter](https://twitter.com/Kiloneie "My Twitter")
- [Patreon](https://www.patreon.com/Kiloneie?fan_landing=true "Patreon")
- Video's script/documentation with all of the code styled with nimib as a form of offline tutorial:
- [Visual Studio Code Shortcuts](https://code.visualstudio.com/shortcuts/keyboard-shortcuts-windows.pdf "Visual Studio Code Shortcuts")
<b>LINKS to this video's subject:</b>
- [Set type](https://nim-lang.org/docs/manual.html#types-set-type "Set type")
- [Set operations and extra modules](https://nim-lang.org/docs/system.html#system-module-sets "Set operations and extra modules")
- [Ordinal types](https://nim-lang.org/docs/manual.html#types-ordinal-types "Ordinal types")
- [Ordinal operations](https://nim-lang.org/docs/system.html#system-module-ordinals "Ordinal operations")
- [strutils module for the last example/use case of parsing data](https://nim-lang.org/docs/strutils.html "strutils module for the last example/use case parsing data")
"""</span>
nbSave()</code></pre>
</section><script>
function toggleSourceDisplay() {
var btn = document.getElementById("show")
var source = document.getElementById("source");
if (btn.innerHTML=="Show Source") {
btn.innerHTML = "Hide Source";
source.style.display = "block";
} else {
btn.innerHTML = "Show Source";
source.style.display = "none";
}
}
</script></body>
</html>Editor is loading...