Table of Contents:

1. What are Sets ?
2. Set pros
3. Set cons
4. Set use cases

INTRO - GREETING

• TITLE: Sets

INTRO - FOREWORDS

(What is the purpose of this video ?)
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.

What are Sets ?

• 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:

#var emptySet = {} #The compiler cannot infer the data type of it's elements, so we must use declaration instead
var emptySet: set[char]
echo emptySet

{}

• As you can see curly brackets {} are Set's constructors
• They cannot be accessed via [] brackets, to access them by the index like so:

var accessSet = {'a', 'b'}
#echo accessSet[0] #Nim's Visual Studio Code Extension catches the error
#So instead we do it by calling the element of the Set that we want
if 'a' in accessSet:
  echo "a is in accessSet"

a is in accessSet

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

• Sets can only have unique elements of ordinal types, any duplicates get removed

var deduplicatedSet = {'a', 'a', 'b'}
echo deduplicatedSet

{'a', 'b'}

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:

var
  int8Set: set[int8]
  int16Set: set[int16]
  charSet: set[char]

type
  enumSet = enum
    s1, s2, s3

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:

• succ Successor of the value
• pred Predecessor of the value
• inc Increment the ordinal
• dec Decrement the ordinal
• high Return the highest possible value
• low Return the lowest possible value
• ord Return int value of an ordinal value

Like with every container construct in Nim, we can also use a for loop on them.

for e in deduplicatedSet:
  echo e

a
b

Here is the full list of procs that you can use to operate on Sets:

• incl(A, e) same as A = A + e
• excl(A, e) same as A = A - e
• card(A) the cardinality of A (number of elements in A)
• contains(A, e) A contains element e
• e in A set membership (A contains element e)
• e notin A A does not contain element e
• a * b Intersection
• a + b Union
• a - b Difference
• a == b Set equality
• a <= b subset relation (a is subset of b or equal to b)
• a < b Check if a is a subset of b

Let's start with difference between 2 similar sets

var setA = {'a', 'b'}
var setB = {'a', 'c'}

echo setA - setB

{'b'}

{'b'} is the difference between setA - setB
If we do the same, but reverse the 2 sets

echo setB - setA

{'c'}

We get {'c'} as the element of the difference.
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

echo setA + setB

{'a', 'b', 'c'}

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.

setA.incl 'd'
setB.excl 'a'

echo setA
echo setB

{'a', 'b', 'd'}
{'c'}

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.

setB.incl 'a'
setB.incl 'b'

echo setA * setB
echo setB * setA

{'a', 'b'}
{'a', 'b'}

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.

var setC = {'a', 'd'}

echo setA
echo setB
echo setC
echo ""
echo setB < setA
echo setC < setA

{'a', 'b', 'd'}
{'a', 'b', 'c'}
{'a', 'd'}

false
true

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.
Let's demonstrate:

setB.excl 'c'
setB.incl 'd'

echo setA
echo setB
echo setB < setA

{'a', 'b', 'd'}
{'a', 'b', 'd'}
false

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.

echo setB <= setA

true

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:

echo setA
echo setB
echo setC

echo setA.card
echo setB.card
echo setC.card

{'a', 'b', 'd'}
{'a', 'b', 'd'}
{'a', 'd'}
3
3
2

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.

type
  SandboxFlag = enum
    allowCast, allowInfiniteLoops 

var sandboxFlags: set[SandboxFlag]

sandboxFlags.incl allowCast #E.g allowCast -> Allow unsafe language features
sandboxFlags.incl allowInfiniteLoops 

#A second more gamey example if the first example was not understandable
type
  Flags = enum
    walk, attack, defend

var moves: set[Flags]

moves.incl walk
moves.incl attack
moves.incl defend

echo moves

{walk, attack, defend}

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:

import strutils

proc split(s: string; seps: set[char] = #[strutils.Whitespace]# {' ', '!', '?'}): string = #const Whitespace = {' ', '\t', '\v', '\r', '\n', '\f'}
  var splitString = s
  var c: int

  for sep in seps:
    c = splitString.find(sep)
    splitString.delete(c, c)
  
  result = splitString
        
var myString = "Hello , World !?" 
echo myString

echo myString.split

Hello , World !?
Hello, World 

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.

Set pros

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

Set cons

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

Set use cases

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

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

Past Patrons

• Goose_Egg: From April 4th 2021 to May 10th 2022
• Davide Galilei(1x month)

Current Patrons

• jaap groot (from October 2023)
• Dimitri Lesnoff (from October 2023)

Compiler Information

• Version used: 2.0.0
• Compiler settings used: none, ORC is now the default memory management option
• Timestamps:
  • 00:15 Start of video example

My and General Links

• Twitter
• Patreon
• Video's script/documentation with all of the code styled with nimib as a form of offline tutorial:
• Visual Studio Code Shortcuts

Links to the video's subject

• Set type
• Set operations and extra modules
• Ordinal types
• Ordinal operations
• strutils module for the last example/use case of parsing data