Section 8: C++ Operator Overloading & Lambdas, Binary Search Trees (BST), Sets (ADT) & Maps (ADT)

# Section 8

## C++ Operator Overloading & Lambdas, Binary Search Trees (BST), Sets (ADT) and Maps (ADT)

##### Presentation by *Asem Alaa*

Section 8 Parts:

1. C++ Operator Overloading & Lambdas
   * {`oo.cpp`}{`lambda.cpp`}
2. Binary Search Trees (BST)
   * {`BST.hpp`}{`bst.cpp`}
3. Sets (ADT) & Maps (ADT)
   * {`Set.hpp`}{`set.cpp`}{`Map.hpp`}{`map.cpp`}

<div class="my-footer" style="bottom:30px;"><span>Demo: <br /><code style="font-size:8pt;">wget -i https://raw.githubusercontent.com/sbme-tutorials/sbme-tutorials.github.io/master/2020/data-structures/snippets/section08/BST/files.txt</code></span></div>

<div class="my-header"><img src="/gallery/cairo.png" style="height: 30px;" /></div>
<div class="my-footer"><span>SBE201 Data Structures and Algorithms  (Spring 2020) - By <em>Asem Alaa</em></span></div>

---
### C++: Operator Overloading (Example 1)

```c++
struct Vec2
{
	double x;
	double y;
};

int main()
{
	Vec2 u{1,1};
	Vec2 v{4,6};
	Vec2 d = u - v;
    // Compiler Err: error: no match for
    // ‘operator-’ (operand types are ‘Vec2’ and ‘Vec2’)
}
```

---
### C++: Operator Overloading (Example 1)

```c++
struct Vec2
{
	double x;
	double y;
    Vec2 operator-(const Vec2 &rhs) const
	{
		return Vec2{ x - rhs.x , y - rhs.y };
	}
};

int main()
{
	Vec2 u{1,1};
	Vec2 v{4,6};
	Vec2 d = u - v;
    // Compiler Happy
}
```

---
### C++: Operator Overloading (Example 1)

```c++
struct Vec2
{
	double x;
	double y;
};
int main()
{
	Vec2 u{1,1};
	Vec2 v{4,6};
	Vec2 d = -(u+v)*(u-v) / (v*u*2);
    std::cout << d;
}
```

---
class: small
### C++: Operator Overloading (Example 1)

```c++
struct Vec2
{
	double x;
	double y;
    Vec2 operator-(const Vec2 &rhs) const{...}
	Vec2 operator-() const {...}
	Vec2 operator+(const Vec2 &rhs) const{...}
	Vec2 operator*(const Vec2 &rhs) const{...}
	Vec2 operator*(double val) const{...}
	Vec2 operator/(const Vec2 &rhs) const{...}

friend std::ostream &operator<<( std::ostream &output, const Vec2 &v ) {
		output << "(" << v.x << "," << v.y << ")";
		return output;
	}
};
int main()
{
	Vec2 u{1,1};
	Vec2 v{4,6};
	Vec2 d = -(u+v)*(u-v) / (v*u*2);
    std::cout << d; // prints: (1.875,2.91667)
}
```

---
class: small
### C++: Operator Overloading (Example 2)

```c++
struct Image
{
	double *data;
	size_t width;
	size_t height;
	Image( size_t w, size_t h )
	{
		width = w;
		height = h;
		data = new double[ w * h ];
	}
};

int main()
{
	Image img = Image(16, 16); // 16x16 image

// How to get pixel at position (9,12)?
	double val1 = img.data[ 9 + 12 * img.width ];
}
```

---
class: small
### C++: Operator Overloading (Example 2)

```c++
struct Image
{
	double *data;
	size_t width;
	size_t height;
	Image( size_t w, size_t h ){
		width = w;
		height = h;
		data = new double[ w * h ];
	}

double &operator()(size_t x, size_t y){
		return data[ x + y * width ];
	}
};
int main()
{
	Image img = Image(16, 16); // 16x16 image
	// How to get pixel at position (9,12)?
	double val1 = img.data[ 9 + 12 * img.width ];
    // Or
	double val2 = img(9, 12);
	// Modify
	img(9, 9) = 1.0;
}
```

---
### C++: Lambda Expressions (Example 1)

Introduced in C++11

Syntax:  <code><b>[</b></code> <span class="t-spar">captures</span> <code><b>]</b></code> <code><b>(</b></code> <span class="t-spar">params</span> <code><b>)</b></code> <code><b>{</b></code> <span class="t-spar">body</span> <code><b>} </b></code>

Simplest lambda: `auto l = [](){};`

```c++
int main()
{
	auto sq = [](double a){ return a*a; };

std::vector< double > u = { 1.0, -2.0, 3.0, -4.0 };
	for( auto &x : u )
		x = sq( x );

for( auto x: u ) std::cout << x << " ";
	std::cout << "\n"; // prints: 1.0 4.0 9.0 16.0
}
```

---
### C++: Lambda Expressions (Example 1)

```c++
int main(){
    // Random number generators
    std::uniform_int_distribution<int> udist(0,100); 
    std::mt19937 sampler;

std::vector< int > v;
	for( int i = 0; i < 10 ; ++i) v.push_back(udist(sampler));

for( auto x: v ) std::cout << x << " ";
    // Prints: 82 13 91 84 12 97 92 22 63 31
    std::cout << "\n";

std::sort( v.begin(), v.end());

for( auto x: v ) std::cout << x << " ";
    // Prints: 12 13 22 31 63 82 84 91 92 97
}
```

---
### C++: Lambda Expressions (Example 2)

```c++
int main(){
  // Random number generators
  std::uniform_int_distribution<int>udist(0,100); std::mt19937 sampler;

std::vector< int > v;
  for( int i = 0; i < 10 ; ++i) v.push_back(udist(sampler));

for( auto x: v ) std::cout << x << " ";
  // Prints: 82 13 91 84 12 97 92 22 63 31
  std::cout << "\n";

std::sort( v.begin(), v.end());

for( auto x: v ) std::cout << x << " ";
  // Prints: 12 13 22 31 63 82 84 91 92 97 
  std::cout << "\n";

std::sort( v.begin(), v.end(), [](int a, int b){return a > b;});
  for( auto x: v ) std::cout << x << " ";
  // Prints: 97 92 91 84 82 63 31 22 13 12 
}
```

---
class: small
### C++: Lambda Expressions (Example 2)

```c++
struct Student
{
	std::string name;
	int grade;
	std::string toString() const {
		std::stringstream s;
		s << "(" << name << "," << grade << ")";
		return s.str(); // returns: (name,grade)
	}
};
int main(){
    std::vector< Student > students({ {"Mahdy", 86}, {"Ahmed", 70},
									  {"Samar", 86}, {"Zyad",  70}});
	std::sort( students.begin(), students.end(), []( Student &a, Student &b ){
		return a.grade > b.grade;
    });
	for( auto &stud : students ) std::cout << stud.toString() << " ";
	std::cout << "\n"; // out: (Mahdy,86) (Samar,86) (Ahmed,70) (Zyad,70)

std::sort( students.begin(), students.end(),[]( Student &a, Student &b ){
		return a.name < b.name;
	});
	for( auto &stud : students ) std::cout << stud.toString() << " ";
    std::cout << "\n"; // out: (Ahmed,70) (Mahdy,86) (Samar,86) (Zyad,70) 
}
```
---
#### Comparing `std::string`s

```c++
#include <string>
int main()
{
    std::string s1 = "batman";
    std::string s2 = "superman";

int comparison = s1.compare( s2 );
}
```

* `comparison  > 0`: `s1` comes after `s2` alphabetically.
* `comparison  < 0`: `s1` precedes `s2` alphabetically.
* `comparison == 0`: `s1` equals `s2`

---
#### Comparing operators `std::string`s

```c++
#include <string>
#include <iostream>
int main()
{
    std::string s1 = "batman";
    std::string s2 = "superman";

if( s1 < s2 )
        std::cout << s1 << " precedes " << s2;
    else 
        std::cout << s2 << " precedes " << s1;
}
```

---
class: small
### Tree

* **Root:** is the top node.
* **Child:** any node that is emerged from an upper node.
* **Parent/Internal Node:** node with at least one child.
* **Siblings:** nodes sharing the same parent.
* **Leaf:** node with no children.
* **Edge:** the link between two nodes.
* **Path:** the sequence of links and nodes to reach from one node to a descedant.
* **Height of node:** the number of links between a node and the furthest leaf.
* **Depth of node:** the number of links between a node and the root.

---
### Tree

### Synonyms

* Node = Vertex = Point
* Edge = Link = Arc

---
### Violating Tree Structure

#### The following structure **is not tree**

.center[<img src="/gallery/trees/Directed_graph,_cyclic.svg" style="width:80%;" /> ]

---
### Violating Tree Structure

#### The following structures **is not tree**

.center[<img src="/gallery/trees/Directed_graph_with_branching_SVG.svg" style="height:80%;" />]

---
### Violating Tree Structure

#### The following structures **is not tree**

.center[<img src="/gallery/trees/Directed_graph,_disjoint.svg" style="height:80%;" />]

---
## Binary Search Trees (BST)

* **Binary trees** is a special case of trees where each node can have at most 2 children. 
* Also, these children are named: **left child** or **right child**. 
* A very useful specialization of **binary trees** is **binary search tree (BST)**
* left children < parent < right children, 
* and this rule applies recursively across the tree.

---
## Binary Search Trees (BST)

.center[<img src="/gallery/trees/Binary_search_tree.svg" style="width:80%;" />]

---
## Binary Search Trees (BST)

.center[<img src="/gallery/trees/graphtreevenn.svg" style="width:80%;" />]

---
## Binary Search Trees (BST)

### Motivation

Efficient search/insertion/deletion in *logarithmic* time $O(\log(n))$

* Arrays:
  * .green[efficient search] on sorted arrays $O(\log(n))$,
  * .red[ineffiecient insertion/deletion] $O(n)$.
* Linked lists:
  * .red[inefficient search] $O(n)$,
  * .green[efficient insertion/deletion] $O(1)$.

---
## Binary Search Trees (BST)

### Intuition

* Tree combines the advantages of arrays and linked lists.
* Properties of **BST** (e.g being ordered) makes it potential for many applications.

---
## Binary Search Trees (BST)

### Implementation Using Linked Structures (Pointers)

* Trees can be stored in arrays (like Heaps) or stored as linked nodes (i.e using pointers). 
* We will implement the **BST** using linked nodes. 
* Recursion: Think of each node in a tree as a separate standalone tree.

---
#### Node structure

```c++
template< typename T >
class BST
{
    struct BSTNode
    {
        T data;
        BSTNode *left;
        BSTNode *right;
    };
};
```

---
### Operations (isEmpty)

```c++
template< typename T >
class BST{ //...
    static bool isEmpty( const BSTNode *t )
    {
        return t == nullptr;
    }
};
```

---
### Operations (isLeaf)

```c++
template< typename T >
class BST{ //...
    static bool isLeaf( const BSTNode *t )
    {
        return !isEmpty(t)
                && isEmpty( t->left )
                && isEmpty( t->right );
    }
};
```

---
### Operations (size)

```c++
template< typename T >
class BST{ //...
    static size_t size( const BSTNode *t )
    {
        if ( !isEmpty( t ) )
            return 1 + size( t->left ) + size( t->right );
        else return 0;
    }
};
```

---
### Operations (insert)

---
### Operations (insert)

```c++
template< typename T >
class BST{ //...
    static BSTNode * insert( BSTNode *t, T data )
    {
        if ( isEmpty( t ))
            return new BSTNode{ data , nullptr , nullptr };
        else
        {
            if ( data < t->data )
                t->left = insert( t->left, data );
            else t->right = insert( t->right, data );
            return t;
        }
    }
};
```

---
### Operations (find)

.center[<img src="/gallery/trees/binary-search-tree-sorted-array-animation.gif" />]

---
### Operations (find)

```c++
template< typename T >
class BST{ //...
    static bool find( const BSTNode *t, T data )
    {
        if ( isEmpty( t ))
            return false;
        else
        {
            if ( data == t->data )
                return true;
            else if ( data < t->data )
                return find( t->left , data );
            else return find( t->right , data );
        }
    }
};
```

---
### Traversal Operations

---
#### Traversal Operations: In-order

.center[<img src="/gallery/trees/InorderTrav.gif" style="width:80%;" />]

---
#### Traversal Operations: In-order

```c++
template< typename T >
class BST{ //...
    static void inorder( const BSTNode *t )
    {
        if( !isEmpty( t ))
        {
            inorder( t->left );
            std::cout << t->data << " ";
            inorder( t->right );
        }
    }
};
```

---
#### Traversal Operations: Pre-order

.center[<img src="/gallery/trees/PreOrderTrav.gif" style="width:80%;" />]

---
#### Traversal Operations: Pre-order

```c++
template< typename T >
class BST{ //...
    static void preorder( const BSTNode *t )
    {
        if( !isEmpty( t ))
        {
            std::cout << t->data << " ";
            preorder( t->left );
            preorder( t->right );
        }
    }
};
```

---
#### Traversal Operations: Post-order

.center[<img src="/gallery/trees/PostorderTrav.gif" style="width:80%;" />]

---
#### Traversal Operations: Post-order

```c++
template< typename T >
class BST{ //...
    static void postorder( const BSTNode *t )
    {
        if( !isEmpty( t ))
        {
            postorder( t->left );
            postorder( t->right );
            std::cout << t->data << " ";
        }
    }
};
```

---
#### Traversal Operations: Breadth-first

.center[<img src="/gallery/trees/bfs.gif" style="width:80%;" />]

---
#### Traversal Operations: Breadth-first

```c++
template< typename T >
class BST{ //...
    static void breadthfirst( const BSTNode *tree )
    {
        std::queue< const BSTNode * > q;
        q.push( tree );
        while( !q.empty())
        {
            auto t = q.front();
            q.pop();
            if( !isEmpty( t->left )) q.push( t->left );
            if( !isEmpty( t->right )) q.push( t->right );
            std::cout << t->data << " ";
        }
    }
};
```

---
### Operations (clear)

```c++
template< typename T >
class BST{ //...
    static void clear( BSTNode *t )
    {
        if ( !isEmpty( t )) {
            clear( t->left );
            clear( t->right );
            delete t;
        }
    }
};
```

---
### Operations (remove)

##### **Case I:** Node to be removed **has no children**

###### Example: `remove( tree , -4 )`

.center[![bst-del1](/gallery/trees/bst-remove-case-1.png)]

---
### Operations (remove)

##### **Case II:** Node to be removed **has one child**

###### Example: `remove( tree , 18 )`

.center[![bst-del2a](/gallery/trees/bst-remove-case-2-1.png)]

---
### Operations (remove)

##### **Case II:** Node to be removed **has one child**

###### Example: `remove( tree , 18 )`

.center[![bst-del2b](/gallery/trees/bst-remove-case-2-2.png)]

---
### Operations (remove)

##### **Case II:** Node to be removed **has one child**

###### Example: `remove( tree , 18 )`

.center[![bst-del2c](/gallery/trees/bst-remove-case-2-3.png)]

---
### Operations (remove)

##### **Case III:** Node to be removed **has two children**

###### Example: `remove( tree , 12 )`

.center[![bst-del3a](/gallery/trees/bst-remove-case-3-3.png)]

---
### Operations (remove)

##### **Case III:** Node to be removed **has two children**

###### Example: `remove( tree , 12 )`

.center[![bst-del3b](/gallery/trees/bst-remove-case-3-4.png)]

---
### Operations (remove)

##### **Case III:** Node to be removed **has two children**

###### Example: `remove( tree , 12 )`

.center[![bst-del3c](/gallery/trees/bst-remove-case-3-5.png)]

---
### Operations (remove)

##### **Case III:** Node to be removed **has two children**

###### Example: `remove( tree , 12 )`

.center[![bst-del3d](/gallery/trees/bst-remove-case-3-6.png)]

---
### Operations (remove)

```c++
template< typename T >
class BST
{ //...
    static BSTNode * remove( BSTNode *t, T data )
    {
        if ( isEmpty( t )) return nullptr;
        if ( data == t->data ) t = removeNode( t );
        else if ( data < t->data ) t->left = remove( t->left, data );
        else t->right = remove( t->right, data );
        return t;
    }
};
```

---
class:small
### Operations (remove)

```c++
template< typename T >
class BST{ //...
    static BSTNode * minNode( BSTNode *t ){
        auto min = t;
        while( min->left ) min = min->left;
        return min;
    }
    static BSTNode * removeNode( BSTNode *t ){
        if ( !isEmpty( t->left ) && !isEmpty( t->right )){
            BSTNode *minRight = minNode( t->right );
            t->data = minRight->data;
            t->right = remove( t->right, t->data );
        } else {
            BSTNode *discard = t;
            if ( isLeaf( t )) t = nullptr;
            else if ( !isEmpty( t->left )) t = t->left;
            else t = t->right;
            delete discard;
        }
        return t;
    }
};
```

---
class: left, top

## Abstract Data Types (ADT) based on BST

### Set

* **BST**: efficient insertions and removals.
* **modification**: in `insert` function, only insert unique values,

```c++
int main()
{
    std::mt19937 sampler; // random number sampler
    std::uniform_int_distribution<int> udist(0,100); // distribution
    std::set< int > s;
    for( int i = 0; i < 100 ; ++i)
        s.insert( udist(sampler) );
    for( auto x : s2 )
        std::cout << x << " ";
}
```

---
#### Set: Add

* Slight modification of `BST::insert`,
* Insertion is done only when the key doesn't exist.

--
##### BST Insertion

```c++
template< typename T >
class BST{ //...
    static BSTNode * insert( BSTNode *t, T data ){
        if ( isEmpty( t ))
            return new BSTNode{ data , nullptr , nullptr };
        else
        {
            if ( data < t->data )
                t->left = insert( t->left, data );
            else t->right = insert( t->right, data );
            return t;
        }
    }
};
```

---
#### Set Insertion (solution 1)

```c++
template< typename T >
class Set
{ //...
    static SetNode * insert( SetNode *t, T data ){
        if ( isEmpty( t ))
            return new SetNode{ data , nullptr , nullptr };
        else if ( data != t->data )
        {
            if ( data < t->data )
                t->left = insert( t->left, data );
            else t->right = insert( t->right, data );
        }
        return t;
    }
};
```

---
##### Set: Insertion (solution 2)

1. use `find` to check if the element doesn't already exist,
2. if so, use `insert`.

```c++
template< typename T >
class Set{ //...
public:
    void add( T data )
    {
        if ( !find( data ))
            insert( data );
    }
};
```

---
#### Excercises: Set Union

* `union`: given two sets $S_1$ and $S_2$ make a new data structure $S_3 = S_1  \cup S_2$

##### possible implementation:

1. make an empty set `S3`,
1. iterate over elements of `S1` inserting each element to `S3`, and similarly for `S2`.

---
#### Excercises: Set Intersection

* `intersect`: given two sets $S_1$ and $S_2$ make a new data structure $S_3 = S_1  \cap S_2$

##### possible implementation:

1. make an empty set `S3`,
1. iterate over elements of `S1` inserting each element that also exists in `S2` into `S3`.

---
#### Excercises: Set Equality

* `equals`: given two sets $S_1$ and $S_2$, check the equality of the two sets,

##### possible implementation:
  
1. first, check that $S_1$ and $S_2$ sizes are equal,
2. then what?

---
### Map

Synonyms: Associative containers, dictionary, symbol table.

A **map** is a collection of searchable key-value pairs, where each key has a value.

#### Map: Example Application 1

We can have a **map** (aka **dictionary**) to represent the count of words in a page or textbook, such that:

1. the **key** here is the *word* (`std::string`)
1. the **value** is the count of this word (`int`).

---
#### Map: Example Application 2

for the function that counts characters in **DNA**:

```c++
int countCharacter( std::string dna, char query ){
    int count = 0;
    for ( int i = 0; i < dna.size(); ++i)
        if ( query == dna[i] ) ++count;
    return count;
}
int main( int argc, char **argv ){
    std::string dna = readStream();
    int countA = countCharacter( dna , 'A');
    int countC = countCharacter( dna , 'C');
    int countG = countCharacter( dna , 'G');
    int countT = countCharacter( dna , 'T');
}
```

---
#### Map: Example Application 2

##### Map Elegant solution

* `countCharacter` was called four times (i.e to count **A**, **C**, **G**, and **T**).
* However, by using **map** data structure we can run this function to count all characters in a single run!

```c++
#include <map>
int main( int argc, char **argv ){
    std::string dna = readStream();
    std::map< char, int > dnaCounter;
    for( int i = 0 ; i < dna.size() ; ++i )
        dnaCounter[ dna[i] ]++;
    return 0;
}
```