>By Mosh

## What are Logical Operations?

Logical operations are part of Boolean algebra, which is often taught to students of computer science and electronic engineering at University. So, if you’re not familiar with Boolean algebra, here is a brief introduction.

In Boolean algebra, the value of variables can only be **true** or **false**, also denoted 1 and 0 respectively. Unlike elementary algebra, where the main operations are addition, subtraction, etc, the main operations of Boolean algebra are **conjunction** (AND), **disjunction** (OR) and **negation** (NOT).

 

## Logical AND

Let’s assume we have two variables: **x** and **y**. In C#, the logical AND operator is indicated by &&. We can define a Boolean expression as follows:
```cs
z = x && y
```
In this expression, **z** is true if _both_ **x** and **y** are true; otherwise, it’ll be false.

What is a real-world example of this in programming? Imagine you’re developing a loan application. The provider only offers loans to applicants who are over 18 and are citizen of the given country. In this example, we have two variables:

```
x = applicant being over 18
y = application being a citizen
z = is eligible to apply for loan = x && y
```

If _both_ **x** and **y** are true, the applicant is eligible to apply for a loan.\
Later, when we get to conditional statements, you can check to see if the above expression evaluates to true or false, and then, can change the flow of your application.

So, here is the rule of thumb with logical AND: if _both_ **x** and **y** are true, **x && y** will be true; otherwise, it’ll be false.

 

## Logical OR
In C#, logical OR is indicated by two vertical lines `||`. Considering the following expression:

```cs
z = x || y
```
**z** will be true, if _either_ **x** or **y** is true.

What is a real-world example of this? Imagine you’re building software for a recruiter. For a given job application, applicants can apply if they have a degree in computing, or more than 5 years of experience in the field. You can model this using a Boolean expression as follows:

```
x = applicant has a degree in computing
y = applicant has more than 5 years of experience z = application is eligible = x || y
```

If either x or y is true, z will be true.\
So, unlike the logical AND, where both variables must be true, with logical OR, if at least one of them is true, the result will be true.

 

## Logical NOT
The NOT operator in C# is indicated by an exclamation mark (!) and it reverses the value of a given variable or expression:

```cs
y = !x
```
So, here, if **x** is true, **y** will be false, and if **x** is false, **y** will be true.

 

---
## Clean Coding
In all examples here, I used variables **x** and **y**, mainly to relate programming to Boolean algebra. But when it comes to coding, you should avoid using variable names such as x, y, z as they don’t give a clue to other developers reading your code (or even yourself). Instead, use meaningful names. For instance, in the first example, you can replace **x**, **y** and **z** as follows:

>x: isOver18\
>y: isCitizen\
>z: isEligible

Often, it’s a good practice to prefix Boolean names with IS or HAS (if possible).

# The most primitive data structure.

After learning at least one programming language, you have definitely came accross arrays. The array is always statically typed and sized. 


An array store your data one after another on a single line row of memory location. And since each of the element in your array is predefined and fixed. 
```cs
// a byte array
byte[] myArray = new byte[8];
```

The computer can optimally access the location of your data via an index, since all they needed to do is to jump the memory address using simple + or - operators. This is possible as arrays are contiguous. 


![](assets/img/attachments/dsa/array.png)

Each memory address corresponds to a single byte (8bits).

> **Time complexity of accessing an array item via index?** \
> Lookup = `O(1)` \
> Arrays can just access an item in an index by just calculating the memory location of the item based on the size of each item and the given index
{: .prompt-tip}

 

---
## Why are they fast?
Arrays are fast due to the nature of how they are stored in your memory (ram). We know arrays are zero indexed, and statically typed, and that their addresses are contiguous. 

Contiguous memory is important. For example. say I allocate memory for a single float 32.
This allocates 4 bytes of memory and these 4 bytes are continuous one after another without any gaps in between.

```
 1 2 3 4
... ... ...[] [] [] [] .... .... ...
```

 

With continous memory, the CPU does not need to fetch new data from the RAM, instead, CPU could hold these data in their cache, reducing cache misses.

This is what L1, L2, and L3 cache on your CPU is for:

![](/assets/img/attachments/dsa/cpu_cache.png)


 

### Cache Hits Cache miss?
When CPU wants to access data for processing, they do not always find it from the RAM first, and they dont request a single byte. 

Instead they would first check the L1 cache, if they found, its a hit, else then the L2, then L3 and finally if it is not in any of the cache. They will request the RAM for the data, usually in a batch of, 64bits for x64 CPUs. This is called a cache line. 

This is important, as each subsequent levels are larger in capacity, yet also larger in latency. This is why ensuring contiguous memory in ram is important as we want to minimize as little cache misses and we can.


![](/assets/img/attachments/dsa/cache_latency.png)

Non-contiguous memory would result in gaps within our arrays where the CPU will have to refetch from RAM for the subsequent data. This happens often with more complicated data structure such as Linked-lists, and arrayLists. 

 

---
## Array Limitations
Arrays are fast when we perform contiguous operations and calculations. However when it comes to things like query or searches, insertion and deletion. Arrays would suffer some penalty.

 

### Insertion is slow
Since arrays are fixed sized, adding a 6th item to a 5 item sized array would require declaring a new array, copying all the items from the old array.

![](/assets/img/attachments/dsa/array_insertion.png)

 

### Removing is slow
Removing an item from the end of an array is pretty easy. We can look up the last item by its index and clear them.

```
// Best case Delete o(1)
[1][5][1][6] --> [1][5][1][ ]
```

 

However the same cant be said on the first item or at other indexes.
Deletion and inserting items into an array at a specific index would require copying and shifting all the items after the target index. this is computationally expensive. 

```
// worse case Delete O(n)
[1][5][1][6] --> [ ][5][1][6] --> shifting [5][1][6][]
 ^ <------ 
```

 

### Item search is slow
When we want to search if an array contains an item. We have to iterate thru the entire array to look for the item. This tedious brute force method may out weights cache benefits when the array is very large.

This is why complex data structures like dictionaries and trees exist. 

 

---
## Practical: Build a dynamically sized Array

```cs
public class DynamicIntArray {
 private int[] array;
 private int lastInsertedIndex;
 
 public DynamicIntArray(int arraySize) {
 array = new int[arraySize];
 lastInsertedIndex = 0;
 }
 
 public int getItem(int index) {
 if (array.Length - 1 > index) {
 return array[index];
 }
 return 0;
 }
 
 public void insert(int item) {
 if (array.Length - 1 < lastInsertedIndex) {
 int[] temp = new int[array.Length * 2];
 Array.Copy(array, temp, array.Length);
 array = temp;
 }
 array[lastInsertedIndex] = item;
 lastInsertedIndex++;
 }
 
 public void removeAt(int index) {
 if (lastInsertedIndex < index || index < 0)
 throw new IndexOutOfRangeException("Negative and out of range indexes are not accepted");
 
 lastInsertedIndex--;
 for (int i = index; i < lastInsertedIndex; i++) {
 array[i] = array[i + 1];
 }
 int[] temp = new int[lastInsertedIndex];
 Array.Copy(array, temp, lastInsertedIndex);
 array = temp;
 }
 
 public int indexOf(int item) {
 for (int i = 0; i <= lastInsertedIndex; i++) {
 if (array[i] == item)
 return i;
 }
 return -1;
 }
 
 public void print() {
 Console.WriteLine($"[{String.Join(", ", array)}]");
 }
}
```


 

---
## Dynamically sized arrays
Dynamically sized arrays are just like arrays, but they can expand and have no size constrains

An example of a dynamically sized array is the List in C#. Or just list in python.

There are also other examples of dynamic arrays such as ArrayLists. However, there are a clear and distinct difference in their low level representation:

 

### Lists are generic
They are predefined with a type and holds a constrains. This means internally they are an array where each item is lined up one after another in memory address. 

List are about as fast as they typically declared and allocates more memory than you need, allowing some contiguous memory. Under the hood, they are just regular arrays with a bit more mechanism. However one key difference is that they are much faster when it comes to adding and removing elements. 

When it comes to indexing and accessing individual elements, arrays are definitely always faster. 

 

### ArrayLists are non-generic
They do not have a fixed type, value types stored via boxing into a base level object, and stored in the heap. Boxing and unboxing is computationally expensive, therefore it is generally best avoided to use non-generic.

A simple analogy of how it works in the low level. 
Take an int, and convert it into a type base class object which is the base class of all data types. This object is chucked in the heap. Store its memory address in your Array List. Calling and making sense of this item would require casting it back into desired object. [[Boxing and Unboxing|Readmore]]

 

---
## Cache Locality in Multidimensional arrays
> from an answer on [Stack overflow](https://stackoverflow.com/questions/34189896/cache-performance-concerning-loops-in-c)

Just generally speaking, the most efficient loops through a matrix are going to cycle through the **last dimension**, not the first ("last" being `c` in `m[a][b][c]`).

For example, given a 2D matrix like an image which has its pixels represented in memory from top-left to bottom-right, the quickest way to sequentially iterate through it is going to be horizontally across each scanline, like so:

```c
for (int y=0; y < h; ++y) {
 for (int x=0; x < w; ++x)
 // access pixel[y][x]
}
```

... not like this:

```c
for (int x=0; x < w; ++x) {
 for (int y=0; y < h; ++y)
 // access pixel[y][x]
}
```

... due to spatial locality. It's because the computer grabs memory from slower, bigger regions of the hierarchy and moves it to faster, small regions in large, aligned chunks (ex: 64 byte cache lines, 4 kilobyte pages, and down to a little teeny 64-bit general-purpose register, e.g.). The first example accesses all the data from such a contiguous chunk immediately and prior to eviction.

`harold` on this site gave me a nice view on how to look at and explain this subject by suggesting not to focus so much on cache misses, but instead focusing on striving to use all the data in a cache prior to eviction. The second example fails to do that for all but the most trivially-small images by iterating through the image vertically with a large, scanline-sized stride rather than horizontally with a small, pixel-sized one.

**_Also, when we increase block size, but keep cache size and associativity constant, does it influence the miss rate? At a certain point increasing block size can cause a higher miss rate, right?_**

The answer here would be "yes", as an increase in block size would naturally equate to more compulsory misses (that would be more simply "misses" though rather than "miss rate") but also just more data to process which won't all necessarily fit into the fastest L1 cache. If we're accessing a large amount of data with a large stride, we end up getting a higher non-compulsory miss rate as a result of more data being evicted from the cache before we utilize it, only to then redundantly load it back into a faster cache.

There is also a case where, if the block size is small enough and aligned properly, all the data will just fit into a single cache line and it wouldn't matter so much how we sequentially access it.

 

## Matrix Multiplication
Now here is a bit more complex case than the previous example above, but the same concepts tend to apply.

Let's look at the first one:

```c
for (i = 0; i < n; i++) {
 for (j = 0; j < n; j++) {
 accum = 0.0;
 for (k = 0; k < n; k++)
 accum += b[j][k] * a[k][i];
 c[j][i] = accum;
 }
}
```

If we look at the innermost `k` loop, we access `b[j][k]`. That's a fairly optimal access pattern: "horizontal" if we imagine a row-order memory layout. However, we also access `a[k][i]`. That's not so optimal, especially for a very large matrix, as it's accessing memory in a vertical pattern with a large stride and will tend to suffer from data being evicted from the fastest but smallest forms of memory before it is used, only to load that chunk of data again redundantly.

If we look at the second `j` loop, that's accessing `c[j][i]`, again in a vertical fashion which is not so optimal.

Now let's have a glance at the second example:
```c
for (j = 0; j < n; j++) {
 for (k = 0; k < n; k++) {
 val = b[j][k];
 for (i = 0; i < n; i++)
 c[j][i] += val * a[k][i];
 }
}
```

If we look at the second `k` loop in this case, it's starting off accessing `b[j][k]` which is optimal (horizontal). Furthermore, it's explicitly memoizing the value to `val`, which might improve the odds of the compiler moving that to a register and keeping it there for the following loop (this relates to compiler concepts related to aliasing, however, rather than CPU cache).

In the innermost `i` loop, we're accessing `c[j][i]` which is also optimal (horizontal) along with `a[k][i]` which is also optimal (horizontal).

So this second version is likely to be more efficient in practice. Note that we can't absolutely say that, as aggressive optimizing compilers can do all sorts of magical things like rearranging and unrolling loops for you. Yet short of that, we should be able to say the second one has higher odds of being more efficient.

## "What's a profiler?"

I just noticed this question in the comments. A profiler is a measuring tool that can give you a precise breakdown of where time is spent in your code, along with possibly further statistics like cache misses and branch mispredictions.

It's not only good for optimizing real-world production code and helping you more effectively prioritize your efforts to places that really matter, but it can also accelerate the learning process of understanding why inefficiencies exist through the process of chasing one hotspot after another.

## Loop Tiling/Blocking

It's worth mentioning an advanced optimization technique which can be useful for large matrices -- loop tiling/blocking. It's beyond the scope of this subject but that one plays to temporal locality.

>**Primitive Types and Expressions**
>By Mosh

## Variables and Constants

A variable is a name that we give to a storage location in memory. We use variables to store temporary values in memory.

A constant is a value that cannot be changed. We use constants in situations where we need to ensure that a value does not change. For example, if you're working on a program where you need to calculate the area of a circle, you need to use the Pi number (3.14). You can define Pi as a constant to ensure you don't accidentally change the value of Pi in computations.


To define a variable, we specify a type and an identifier:
```cs
int number;
```

Here, int represents the integer type, which takes 4 bytes of memory. You can find the most frequently used data types in the next section.
Number is the identifier for our variable. We can optionally set the value of a variable upon declaration. This is called “initializing a variable”:
```cs
int number = 5;
```

Remember: in C#, you cannot read the value of a variable unless you have set it before.

To define a constant. we add the *const* keyword:
```cs
 const int banana = 10;
```

 

> **NOTE**\
> You may declare a variable and not assign it a value, but constants must be initialised
{: .prompt-warning}

 

### Primitive Types

| Type | Bytes |
|---------|-------|
| byte | 1 |
| short | 2 |
| int | 4 |
| long | 8 |
| float | 4 |
| double | 8 |
| decimal | 16 |
| bool | 1 |
| char | 2 |

These types have an equivalent type in .NET Framework. So when you compile your application, the compiler maps your types to the underlying type in .NET Framework.

| C# Type | .NET Type |
|---------|-----------|
| byte | Byte |
| short | Int16 |
| int | Int32 |
| long | Int64 |
| float | Single |
| double | Double |
| decimal | Decimal |
| bool | Boolean |
| char | Char |


The easy way to memorize Int* types is by remembering the number of bytes each type uses. For example, a "short" takes 2 bytes. We have 8 bits in each byte. So a "short" is 16 bits, hence the underlying .NET type is Int16.

We also have a few non-primitive types (string, array, class, struct) that I’ll discuss in the following sections. [](obsidian://open?vault=AbyssArchive&file=CSharp%20Notes%2FCS%20-%20Fundamentals%2FCS%20-%203%20Non%20premitive%20types)


> **Real Numbers**\
> Notice that float and decimal has to be declared with an f and m at the end of the number
>```cs
>float pie = 3.142f;
>double bigPie = 3.142;
>decimal extraBigPie = 3.142m;
>```
{: .prompt-info}

 

---
## Scope

Scope determines where a value has meaning and is accessible. A variable has a scope in the block it is defined and in any child blocks. But it is not accessible outside that block. A block is indicated by curly braces ({ }).

 

---
## Overflowing

Each type, depending on the number of types allocated to it, can store a range of values. If we store a value in a variable, but that value exceeds the boundary of values for the underlying type, overflow happens. For example, we can store any values between 0 and 255 in a byte. If the value of a byte exceeds this boundary during computations, overflow happens. Here is an example:
```cs
byte b = 255; 
b = b + 1;
```

As a result of the second line, the value of b will be 0.


At compile time, if we assigns a value greater than the type. It will throw an exeption:
```cs
byte x = 256 //Error
```

 

---
## Type Conversion

There are times that you need to temporarily convert the value of a variable to a different type. Note that this conversion does not impact the original variable since C# is a _statically-typed language_, which in simple term means: once you declare the type of a variable, you cannot change it. But you may need to convert the "value" of a variable as part of assigning that value to a variable of a different type.

There are a few conversion scenarios:

If types are compatible (e.g. integral numbers and real numbers) and the target type is bigger, you don't need to do anything. The value will be automatically converted by the runtime and stored in the target type.
```cs
byte b = 1; 
int i = b;
```

Here because b is a byte and takes only 1 byte of memory, we can easily convert it to an int, which takes 4 bytes. So we don't need to do anything. This is known as an implicit type conversion.

If the target type, however, is smaller than the source type, the compiler will generate an error. The reason for that is that overflow may happen as part of the conversion. For example, if you have an int with the value 1000, you cannot store it in a byte because the max value a byte can store is 255. In this case, some of the bits will be lost in memory. And that's the reason compiler warns you about these scenarios. If you're sure that no bits will be lost as part of the conversion, you can tell the compiler that you're aware of the overflow and would still like the conversion to happen. In this case, you use a *cast*:

```cs
// Casting
int i = 1;
byte b = (byte)i;
```


In this example, our int holds the value 1, which can perfectly be stored in a byte. So, we use a cast to tell the compiler to ignore the overflow. A cast means prefixing the variable with the target type. So here we are casting the variable i to a byte in the second line.

Finally, if the source and target type are not compatible (eg a string and a number), you need to use the Convert class.
```cs
string s = "1234";
int i = Convert.ToInt32(s);
```

Convert class has a number of methods for converting values to various types.

> **SUMMARY**
>
>```cs
>// Implicit type conversion. 
>byte b = 1;
>int i = b;
>
>// Explicit type conversion.
>int num = 1;
>byte byt = num; // error
>
>// This is called a cast. its how we convert explicitly
>int num = 1;
>byte byt = (byte)num;
>
>// incompatible type conversion.
>string example = "1";
>int myNumber = (int)example; // error
>
>// This is how we do it in c#
>string example2 = "1";
>int myNumber2 = Convert.ToInt32(example); // Using System namespace Convert class
>int myNumber3 = int.Parse(example2); // Using Parse method. 
>```
{: .prompt-tip}

 

---
## Operators

In C# we have 4 types of operators:

•    **Arithmetic**: used for computations

•    **Comparison**: used for comparing values in boolean expressions

•    **Logical**: represent logical AND, OR and NOT

•    **Bitwise**: represent bitwise AND, OR and NOT


### Arithmetic Operators

| Operator | Description |
|:--------:|:---------------------:|
| + | Add |
| - | Subtract |
| * | Multiply |
| / | Divide |
| % | Remainder of Division |
| ++ | Increment by 1 |
| — | Decrement by 1 |


### Comparison Operators

| Operator | Description |
|:--------:|:------------------------:|
| > | Greater than |
| >= | Greater than or equal to |
| < | Less than |
| <= | Less than or equal to |
| .== | Equal |
| != | Not equal |



### Logical operators

| Operator | Description |
|:--------:|:-----------:|
| && | Logical AND |
| \|\| | Logical OR |
| ! | Logical NOT |


### Bitwise Operators

| Operator | Description |
|:--------:| ----------- |
| & | Bitwise AND |
| \| | Bitwise OR |

 

---

### Doing Math in C\#
In C# divisions of 2 type int numbers do not return a float. Instead, it returns an int by truncating the decimals places.

So you must do this instead:
```cs
int a = 3;

int b = 10;

int c =5;

(float)b / (float)a // Casting the int into type float
```


Mathematical operators in c# follows regular math rules. PEMDAS.
```cs
a + b * c; // 53
```

>**Non-primitive Types**\
>By Mosh Hamedani\
>Extras by Zenovak


## Classes
Classes are building blocks of our applications. A class combines related variables (also called fields, attributes or properties) and functions (methods) together.

> **Fields & properties**\
> Fields and properties are technically different in C# but conceptually they mean the same thing. They represent attributes about a class. I’ll explain the difference between fields and properties in detail in my C# Intermediate course.
{: .prompt-tip}

An _object_ is an instance of a class. At runtime, many objects collaborate with each other to provide some functionality. As a metaphor, think of a supermarket. At a supermarket, there are multiple people working together to provide services to customers. Each person has a role and is focused only on one area of functionality. Software is exactly the same. A role in a supermarket is like a class in a C# application. A person filling that role during work hours, is like an object in an application at runtime.

> **NOTE**\
> Even though there is a slight different between the Class and Object, these words are often used interchangeably.
{: .prompt-info}

To create a class:
```cs
public class Person
{
}
```

Here, public is what we call an _access modifier_. It determines whether a class is visible to other classes or not. Access modifiers are beyond the scope of this course and I've covered them in the second part of this course: C# Intermediate.


Here is a class with a field and a method:
```cs
public class Person
{
 public string Name;
 //Here void means this method does not return a value.
 public void Introduce()
 {
 Console.WriteLine("My name is " + Name);
 }
}
```


To create an object, we use the new operator:
```cs
Person person = new Person();
```


A cleaner way of writing the same code is:
```cs
var person = new Person();
```

We use the new operator to allocate memory to an object. In C# you don’t have to worry about de-allocating the memory. CLR has a component called Garbage Collector, which automatically removes unused objects from memory.

Once we have an object, we can access its fields and methods with the dot notation:
```cs
Person person = new Person(); 
erson.Name = "Mosh"; 
person.Introduce();
```

 

### Static modifier
When applied to a class member (field or method), makes that member accessible only via the class, not any objects. So in the earlier example, if the Introduce method was static, we could access it via the Person class:
```cs
Person.Introduce();
```


We use static members in situations where we want only one instance of that member to exist in memory. As an example, the Main method in every program is declared as static, because we need only one entry point to the application.

In the real-world, it’s best to stay away from static as much as you can because that makes writing automated tests for applications hard. Automated testing is the topic for another course, but for now, just remember how to use members that are already declared as static, and prefer not to declare your own class members as static.

 

---
## Structs

A struct (structure) is a type similar to a class. It combines related fields and methods together. Structs are all value types. They do not support inheritance, but you may use Interfaces [[CS - 5 Interfaces|Read more]].
```cs
public struct RgbColor
{
 public int Red; 
 public int Green;
 public int Blue;
}
```

Structs also do not support parameterless constructors, only support constructors with parameters.. Struct members do not support abstract, virtual, or protected. 

Use structs only when creating small lightweight objects. That is for a subtle performance optimization. In the real-world, 99% of the time, you create new types using classes, not structures.

> **NOTE**\
> In .NET, all primitive types are declared as a structure. They are small and lightweight. The biggest primitive type doesn’t take more than 16 bytes.
{: .prompt-info}

 

---
## Arrays
An array is a data structure that is used to store a collection of variables of the same type.

For example, instead of declaring three int variables (that are related), we can create an int array like this:
```cs
int[] numbers = new int[3];
```

An array in C# is actually an instance of the Array class. So, that's why here we have to use the new operator to allocate memory to this object. Here, the number 3 specifies the size of the array. Once an array is created, its size cannot be changed. If you need a list with dynamic size, you need to use the List class (explained later in the course).

To access elements in an array, we use the square bracket notation:
```cs
numbers[0] = 1;
```

> **Important!**\
> C# arrays are zero-indexed. So the first element has index 0.\
> Arrays are also **Reference Types**, any changes you make to the array, will directly affects the original array! Remember this when you write functions that modifies arrays.
{: .prompt-tip}

 

### Reference type effects
Consider the 2 following scenario when we want to make changes to a copy of an array:

```cs
var arrayA = new byte[3] { 1, 2, 3 };
```

 

#### Senario1
```cs
var arrayB = arrayA;
arrayB[0] = 0;
```
In this scenario, because Arrays are reference types, both `arrayB[0]` and `arrayA[0]` has become 0! When you assign an array like this, you are only assigning its memory address to another variable. Under the hood, both variables point to the same array in memory! 

You have made changes to the original array .

 

#### Senario2
```cs
var arrayB = (byte[]) arrayA.Clone();
arrayB[0] = 0;
```
In this scenario we are creating a carbon coby of the arrayA and assign it as arrayB. Changes made to arrayB will not affect arrayA, as we now effectively created 2 arrays in memory!

 

This affect is refected even when you are using functions!

```cs
// Arrays are ref class. This changes the original array.
public static byte[] UpdateArray(byte[] array, byte update) {
 array[0] = update;
 return array;
}

// this performs the changes on a modified copy of the original array.
public static byte[] ShadowChangeArray(byte[] array, byte update) {
 byte[] shadow = new byte[3];
 array.CopyTo(shadow, 0);
 shadow[0] = update;
 return shadow;
}
```

 

### Extra Tips
There are multiple ways to declare an array. We could also use the object initializer to immediately assign some values to the array.
```cs
var numbers = new[] { 1, 2, 3, 7, 5, 9, 8};
var numbers2 = new int[3];
int[] numbers3 = new int[] { 1, 2, };
```

Below are some of the useful methods in dealing with Arrays.
```cs
// Returns the size of an array
numbers.Length;

// Below are static methods from the array class:
// Returns the index of an element in an array.
Array.IndexOf(numbers, 2);

// Clear(). Clears the element of an array.
// Array.Clear(array, startAtindex, stopAfter)
Array.Clear(numbers, 0, 3);

// Copy(). Copy elements from one array to another from first element to the specific index
Array.Copy(numbers3, numbers2, 2);

// Sort(). This sorts the array. Smallest to largest
Array.Sort(numbers);

// Reverse(). This reverse the sorting of the array. Largest to smallest. 
Array.Reverse(numbers);
```

 

### Multidimensional Arrays
![[Pasted image 20230405181927.png]]
We have 2 types of multidimensional array in C# - Rectangular and Jagged Arrays.

- Jagged Array can be said to be a single Dimension Array, that contains multiple elements and each of those elements would represent an array. 
- Rectangular array.


> **NOTE!**\
> CLR is optimised for single Dimension Arrays. Implementing a matrix with jagged arrays is better than with rectangular array.
{: .prompt-tip}

 

### Rectangular Arrays
To declare a rectangular 2D array (alternatively use ``var``): 
```cs
int[,] board = new int[3, 3];
```

We can use the same object initilization synthax:
```cs
var checker = new int[3, 5]
{
 {1, 2, 3, 4, 5},
 {6, 7, 8, 9, 10},
 {11, 12, 13, 14, 15}
}
```


To declare a rectangular 3D array:

```cs
var colors = new int[3, 5, 7]
```

> **Iterations**\
> We can loop thru all values in the rectangular array with a nested for loop:
> ```cs
> for (int i = 0; i < 3; i++) {
> for (int j = 0; j < 5; j++)
> {
> Console.WriteLine(arrays[i, j]);
> }
> }
> ```
{: .prompt-tip}


**3D array indexes and declarations**

```cs
var cube = new int[1,2,3] {
 {
 {1, 2, 3}, {3, 4, 5}
 }
}
```

Its depiction is as follows:
```
Specifies rows (x axis):
{}
{}
{}

Specifies collumns(y axis)
{ , }

Specifies depth (z axis)
{ {}, {} }
```


 

### Jagged Arrays
To declare a jagged array, we must first specify the top level arrays. In this case would be `3`. Then we must initialize the top level arrays:
```cs
// Jagged array declaration
var cartons = new int[3][];

// Initializing the top level arrays
cartons[0] = new int[3];
cartons[1] = new int[5];
cartons[2] = new int[2];

// Alternatively
var arrays = new int[3][]
{
 new int[2] {1, 2},
 new int[4] {1, 2, 3, 4},
 new int[3] {1, 2, 3},
};
```

In jagged arrays. The arrays within them are not fixed sizes. To access a Jagged Array:
```cs
cartons[0][2] = 10;
Console.WriteLine(cartons[0][2]);
```

> **Iterations**\
> We iterate thru jagged arrays using .Length in the ``for`` loops as we dont know the length of the array.
> ```cs
> for (int i = 0; i < arrays.Length; i++) {
> for (int j = 0; j < arrays[i].Length; j++) {
> Console.WriteLine(arrays[i][j]);
> }
> }
> ```
{: .prompt-tip}


```csharp
// Two-dimensional GetLength example.
int[,] two = new int[5, 10];
Console.WriteLine(two.GetLength(0)); // Writes 5
Console.WriteLine(two.GetLength(1)); // Writes 10
```

 

---

## Strings

A string is a sequence of characters. In C# a string is surrounded by double quotes, whereas a character is surrounded by a single quote.
```cs
string name = "Mosh"; 
char ch = 'A';
```


There are a few different ways to create a string:

**Using a string literal:**
```cs
string firstName = "Mosh";
```


**Using concatenation:** useful if you wanna combine two or more strings.
```cs
string name = firstName + " " + lastName;
```


**Using string.Format:** cleaner than concatenating multiple strings since you can see the output.
```cs
string name = string.Format("{0} {1}", firstName, lastName);
```


**Using string.Join:** useful when you have an array and would like to join all elements of that array with a character:
```cs
var numbers = new int[3] { 1, 2, 3 }; 
string list = string.Join(",", numbers);
```


> **NOTE**\
> C# strings are immutable, which means once you create them, you cannot change their value or any of their characters. The String class has a few methods for modifying strings, but all these methods return a new string and do not modify the original string.
{: .prompt-tip}


 

**String vs string**
Remember, all types in C# map to a type in .NET Framework. So, the “string” type in C# (all lowercase), maps to the String class in .NET, which means we can declare a string in either of the following ways:
```cs
string name;
String name;
```


The only difference is that if you use the String type, you need to import the System namespace on top of the file, because that’s where the String class is defined.
```cs
using System;
```

 

### Escape Characters

There are few special characters in C# called escape characters:

| Escape Character | Description |
|:----------------:|:------------------------------ |
| \n | New line |
| \t | Tab |
| \\ | The \ character itself |
| \' | The ' (single quote) character |
| \" | The " (double quote) character |


So if you want to have a new line in your string, you use ``\n.

Since the backslash character is used to prefix escape characters, if you want to use the backslash character itself in your string (eg path to a folder), you need to prefix it with another backslash:
```cs
string path = "c:\\folder\\file.txt";
```

 

### Verbatim Strings

Sometimes if there are many escape characters in a string, that string becomes hard to read and understand.
```cs
var message = "Hi John\nLook at the following path:c:\\folder1\\folder2";
```

Note the ``\n`` and double backslashes (``\\``) here. We can re-write this string using a _verbatim string._ We simply prefix our string with an ``@`` sign, and get rid of escape characters:
```cs
var message = @"Hi John Look at the following path: c:\folder1\folder2";
```

 


---

## Reference Types and Value Types

In C#, we have two main types from which we can create new types: classes and structures (structs).

Classes are _Reference_ _Types_ while structures are _Value_ _Types._
 

### Value Types

When you copy a value type to another variable, a copy of the value stored in the source variable is taken and stored in the target variable. Hence, these two variables will be independent.
```cs
var i = 10; 
var j = i; j++;
```

Here, incrementing j does not impact i.

In practical terms, it means: if you pass an argument to a method and that argument is a value type, its value will be copied. So any modifications made to that argument in the method will be lost upon returning from that method.

Remember: Primitive types are structures so they are value types. Any custom structure you define will also be a value type.

 

### Reference Types

With a reference type, however, the reference (or memory address) of the object is copied to the target variable. This means: if you copy a reference type to another variable, any changes you make to the object referenced by either of these variables, will be visible through the other variable.
```cs
var array1 = new int[3] { 1, 2, 3 }; 
var array2 = array1;

array2[0] = 0;
```

Here, both array1 and array2 reference (or point) the same array object in memory. So, after the third line, the first element of both array1 and array2 will be 0.


> **Remember**\
> Arrays and strings are classes, so they are reference types. Any custom classes you define will also be a reference type.
{: .prompt-tip}

 

---
## Enums

An enum is a data type that represents a set of name/value pairs. Use enums when you need to define multiple related constants. 


> **NOTE**\
> Enums are also often used to for switch statements
{: .prompt-tip}

```cs
// Enums are declared in namespace region
public enum ShippingMethod
{
 Regular = 1,
 Express = 2
}
```

 

Now we can declare a variable of type ShippingMethod enum and use the dot notation to initialize it:
```cs
var method = ShippingMethod.Express;
```

 

Enums are internally integers. So you can easily cast them to and from an int:

```cs
var methodId = 1;
var method = (ShippingMethod)methodId;
```


```cs
var method = ShippingMethod.Express; 
var methodId = (int)method;
```

 

To convert an enum to a string use the ToString method. Every object in C# has this method and can be converted to a string:
```cs
var method = ShippingMethod.Express;
var methodName = method.ToString();
```

 

To convert a string to an enum (called parsing), use Enum.Parse:
```cs
var method = (ShippingMethod)Enum.Parse(typeof(ShippingMethod), methodName);
```

 

---
## ArrayList
ArrayList are a type of Non-generic from the System.Collections namespace. They can store any type of Object, without type specification, and is fully dynamic in size. [[CS - 1 Collections and Generics|More on Collections]]

Here is how we declare an ArrayList:
```cs
var myArrayList = new ArrayList();
```

We can add different data types to ArrayList:
```cs
int number = 10;
string name = "Eddie";
float digits = 2.5f;

myArrayList.Add(number);
myArrayList.Add(name);
myArrayList.Add(digits);
```

To iterate thru ArrayList. We must use ``object`` synthax:
```cs
foreach (object i in myArrayList)
{
 Console.WriteLine(i);
}
```

 

> **Performance Penalty**\
> When using ArrayLists, boxing and unboxing will occur!. It is better to avoid it and use List<> [[QNA Boxing and Unboxing with Generics|See Why]]
{: .prompt-warning}



 

---
## Lists
Lists are like arrays, but they are not restricted in their sizes. We can add more objects to the list without specifiying how many objects we would store., they are dynamic in size. They are constructed from the .NET [[CS - 1 Collections and Generics|Generics]]. We use lists when we dont know ahead of time how many objects will be there in the list.

Here is how we create a list:
```cs
var myList = new list<int>();

// Using object initialize synthax
var myList2 = new list<int>() {1, 2, 3};
```


> **Generics List**\
> Fundamentally List is a .Net Generic, it works like this:
> ```cs
> var myList = new list<T>();
> ```
> Where T represents the specific template / data type that the list would store.
{: .prompt-info}


 

### List Class Methods
```cs
// Adds an item to the list
myList.Add();

// Adds an another list to my list or an array
myList.AddRange();

// Remove an item from the list
myList.Remove();

// Removes all items from the list
myList.RemoveAll();

// Returns the Index of the item in the list
myList.IndexOf();

// Returns bool of whether an item exist in a list
myList.Contains();

// Property. Gets the number of items in the list
Console.WriteLine(myList.Count);
```

# Bits Bytes and Bitwise
In this example we will explore the Bitwise means of storing user information in a game of tictac toe, and other easy to visualize scenarios

 

## Single vs structured data types.
It is actually not very efficient to store true false values in the really large numbers.

Let's start with an RPG game example where the character has a few attributes that are true or false. You may get away with doing something simple like this. 
```cs
// This is known as structured data type:
struct attributes {
 bool hasMagic = true;
 bool hasIntelligence = false;
 bool hasCharisma = true;
 bool canFly = false;
 bool isInvinsible = false;
}
```

 

However, remember Booleans are stored as a byte in c# and other languages as well, This is because the smallest addressible memory is for a CPU is a byte. This is why storing an array of bools is also just as inefficient as a structured approach. We are wasting bit spaces!
![](/assets/img/attachments/dsa/wstedBits.png)

 

## Enter the Bitflags 

Lets think in binary bits, assuming you wish to store the following attributes for your character to save the best space for memory:
```cs
bool hasMagic = true;
bool hasIntelligence = false;
bool hasCharisma = true;
bool canFly = false;
bool isInvinsible = false;
```

We can actually use the individual bits inside an `int` or in our example a ``byte`` to store these attributes , as if we were to represent them as an array the naive way using bool array.
```cs
//essentially your attributes are in an array:
bool[] attributes = new bool[] 
{false, false, false, true, false, true, false, false};
//null, null, null, magic, intel, chars, fly, invisi 

// simplied we just store the corresponding dec base value in byte:
byte attribute = 20;
// binary 0 0 0 1 0 1 00 = 20
```

> This is called the bitflag. A boolean array efficiently represented! A boolean array is also a boolean set. You can use set theory and boolean algebra to simplify expresssions to reduce complexity for efficiency.


Even tho we know which bit in this byte corresponds to which attribute. As a reference for readability, it is common that we declare an enum to keep track:
```cs
enum attributeFlags {
 Invisible = 1,
 Fly = 2,
 Charisma = 4,
 Intelligence = 8,
 Magic = 16,
}
```


> Bit shorthand prefix\
> Instead of calculating what the decimal number for the binary is, we can actually just write the binary representation like this:
> ```cs
> byte attributes = 0b1000;
> ```
> Where '0b' prefix indicates that this is a binary literal.
{: .prompt-info}


 

Simple Bitwise Operators:
``` cs
// AND where (1 & 1 = 1), (1 & 0 = 0), (0 & 0 = 0) 
& 

// OR where (1 & 1 = 1), (1 & 0 = 1), (0 & 0 = 0)
|

// NOT where ( ~1 = 0), (~0 = 1)
~

// XOR where ( 1 ^ 1 = 0), (1 ^ 0 = 1), (0 ^ 0 = 1)
^
```

 

---
## Setting the flags
To begin using this method of storing data. We must first be able to add individual bits to our bitflag. Say we start with the following attribute:
```cs
byte attribute = 4;
// binary = 00 00 01 00
```

 

To set the bitflags to store our data we use the bitflag OR-EQUAL operator. Here's how:
```cs
byte attribute |= 16;
```

> How it works?\
> We use BitWise *OR-EQUAL*, 
> ```
> 00000100
>|= 00010000
>---------------
> 00010100
> ```
> We use this to add a bit to our bitflag. This is called "Setting up the bitflag."\
> Basically W ∪ X
{: .prompt-info}
 
 
 

---
## Remove a bit
To remove a bit we use the AND-EQUAL operator on a compliment of the relavent bit:
```cs
byte attribute &= ~16;
```


> **How it works?**\
> We use BitWise *AND-EQUAL*, on a ~mask
> 
>```
> 00010100
>&= 11101111
> ---------------
> 00000100
>```
> We use this to remove a bit from our bitflag. This is called "clearing bits"\
> ``new attribute is attributes ∩ X' ``
{: .prompt-info}

Notice how in this example we are not using an XOR operator. The reason for that is that an XOR operator flips the bit using the mask, it doesnt neccesarily turn a bit OFF. 

This makes mistaken assumption heavily punished with difficult to find bugs. When working with large numbers of bitwise operations like a calculation jump tables etc. It is best that we stick to reliable, and less error prone operations. 

 

---
## Bitmasking

**Contains?**
Bit masking is a method of filtering whether or not an instance of our bitArray contains the relevant bit. Think of it as:
```cs
if (user.attributes.Contains("magic"))
{
 // DO something
}
```

But how do we apply this checking for our **Bitflags**? How do we check if our character which has magic, and other attributes (`[0, 0, 0, 1, 0, 1, 0, 0]`) with the condition of has 
magic(`[0, 0, 0, 1, 0, 0, 0, 0]`)?

We would use a bitwise *AND* operator ( & ):
```cs
byte attribute = 20;
byte filter = 16;

if ((attribute & filter) != 0)
{
 // Do something
}
```


> How it works?\
> We use BitWise *And*,
> ```
> 00010100
>& 00010000
>---------------
> 00010000
> ```
> any 2 values compared this way, will return a value if there is a match, and returns 0 if there are no matches.\
> Basically if (W ∩ X is not an empty set)
{: .prompt-info}

 

**Fully Contains ?**
We can also use the same logic to check whether an an attribute contains all the relevant bits. 
```
X ∈ W ?
```

We can compare the result of the end operator to see if it is the same as the filter.
```cs
byte attribute = 20;
byte filter = 16;

if ((attribute & filter) == filter)
{
 // Do something
}
```


> How it works?\
> If X is a subset of W, where all elements of X is inside of W then:
> ```
> X ∩ W = X
> ```
{: .prompt-info}



 

---
## Is Equal Comparisions
We can use 2 masking operation to compare 2 flags to see if they both contain the same particular bit.

```cs
if ((attribute1 & mask) == (attribute2 & mask))
{
 // Do something
}
```

 

---
## Non-boolean functions
Since we are using our byte as a kind of boolean array. What if we want to instead do more complex array-like operations like retrive the index of the first `true`, or any Indexing operations. 

Just like set theory, we have to use functions to retrive the relevant sets:


> Example problem\
> Definition: A collection of sets E is said to be indexed by a set A if and only if there is a function F from A onto E . In this case we call A the index set of E , say E is indexed by A, and represent F(a) by Ea . In particular, E is indexed by A means E={Ea}a∈A .\
> ```
> Suppose that we have sets {a,b,c}, {a,d,x,y}, and {c,u}; 
> we can form the collection
>
> E={ {a,b,c},{a,d,x,y},{c,u} }
>
> Now let A={1,2,3}; we can define a function f:A→E by
> 
> f(1) = {a,b,c}
> f(2) = {a,d,x,y}
> f(3) = {c,u}
> ```
{: .prompt-tip}

 

### Non-boolean Operator - shifting
One neccesary operation when working with Bitwises, are shifting operations that would allow us to shift the bits in a bitArray. These operations cannot be done using traditional true false "AND" or "OR" and "XOR" operations. 


**Forward shift**
We use the forward shift operator to shift all the bits forward by an ammount.
```cs
// Given X in binary is 00100
x = x << 1;
// Outputs 01000
```

**Back shift**
To shift a bit backwards, we use the backshift operations:
```cs
// Given X in binary is 00100
x = x >> 1;
// outputs 00010
```

The syntax for bit shifts are as follows:
```
x >> n

Where n represents the shifting ammount in integers. n = 1 would shift 1 bit, 
2 would shift 2 bits...
```


 
 


### Index of First and Last bit
In programming languages like C++ and C, they have a function called "BitScanForward()" that returns the index number of the first "ON" bit in a bit-array.

```c++
// _ndex_ 
// [out] Loaded with the bit position of the first set bit (1) found.

// _Mask_ 
// [in] The 32-bit or 64-bit value to search.

BitScanForward(&index, mask);
```

 

We do not have such functions in C# or any higher level languages, so instead we loop thru the bit-Array using the `>>` or `<<` bit shift operator as increments and return the first matching bit found:

```cs
// Get Least Significant Bit Position (first bit in 000101 is at 0)
static Int32 GetLSBPosition(UInt64 v) {
 UInt64 x = 1;
 for (var i = 0; i < 64; i++) {
 if ((x & v) == x) {
 return i;
 }
 x = x << 1;
 }
 return 0;
}

// Get Most Significant Bit Position (last bit position in 000101 is at 3)
static Int32 GetFSBPosition(UInt64 v) {
 UInt64 x = 1UL << 63;
 for (var i = 63, i >= 0; i--) {
 if ((x & V) == x) {
 return i;
 }
 x = x >> 1;
 }
 return 0;
}
```


> **Not Fast Enough?**\
> There are faster techniques for returning bitArray indexes, known as "De Bruijn sequence approach"\
> https://stackoverflow.com/questions/37083402/fastest-way-to-get-last-significant-bit-position-in-a-ulong-c
{: .prompt-info}

 

### Get bit at an Index 
To retrive a bitMask from a given index position, we can simply access that particular index using shifting operations and shift our mask to the interested bit:

```cs
static byte GetBitMaskAtIndex(byte bitArray, int index){
 return bitArray & (1 << index);
}
```

To retrive a bool from a given bit from a bitArray. We perform a similar operation, but instead we push the particular bit to the first index and "AND" it with 1 to return a boolean value.
```cs
static bool GetBitAtIndex(byte bitArray, int index) {
 return (bitArray >> index) & 1;
}
```

 

---
## Practical Example: Unoptimized Implementations

Let's go with an easy to understand Tictactoe implementation. I will be showing 2 solutions to a tictactoe game. One is a typical beginner's implementation so the logics of implementing the game is easily understood and intuitive, the alternative is with using bitwise operations.

There are a few rules in a tictactoe game. If we were to implement them in code, we need to keep track of coditions of the game states namely:

- Who's turn
- The board
- Winning condition
- Valid moves

 

### The board
Let's start with the most basic feature. We need a data structure to store the state of the game. 
- Is the board empty?
- What squares are being occupied?

Since the game board is a 3 x 3. We could implement a simple 2D array like so:
Where string can be empty (""), "X" or "O". 

```cs
var string[,] = new string[3,3];
```

 

### Turn
Then we need to define who's turn it is. Since there's only 2 possible turns, we can use a bool, where true is X and false is O.

```cs
bool turn = true;
```

 

### Winning condition.
Next we need to check the winning condition of the game. If we make a move, check whether or not our board contains the winner.
In a tictactoe game the winning conditions are defined as if any rows or column contains 3 vertical matches, or 3 horizontal matches, or 3 diagonals. A total of 8 conditions

We can code the logics the brute force way where each turn made, we check wether the board has the same elements in a given row or column or diagonal.

Using early return paradigmn. If there are no winners, then if all squares are occupied, it is a draw, else the game goes on.

```cs
private string _winning_line;
// Wining and Losing Checkings
private string _Winner(out string _winning_line)
{
 for (int i = 0; i < 3; i++) {
 if (grid[i, 0] == grid[i, 1] && grid[i, 0] == grid[i, 2]) {
 _winning_line = "row" + i.ToString();
 return grid[i, 0];
 }
 
 if (grid[0, i] == grid[1, i] && grid[0, i] == grid[2, i])
 { 
 _winning_line = "col" + i.ToString();
 return grid[0, i];
 }
 }
 if (grid[0, 0] == grid[1, 1] && grid[0,0] == grid[2, 2])
 {
 _winning_line = "diagonal1";
 return grid[0, 0];
 }
 else if (grid[0, 2] == grid[1, 1] && grid[0, 2] == grid[2, 0])
 {
 _winning_line = "diagonal2";
 return grid[0, 2];
 }
 else if (!grid.Cast<string>().Any(s => s == null))
 return "Draw";
 else
 {
 _winning_line = "";
 return "";
 }
}
```

 

### Making moves:
It is very simple to implement a make moves function in this case. We first check if the square is empty. If its empty, make the move, else, dont. And we also check the turns and insert the appropriate string.

```cs
public void Move(int row, int col)
{
 if (board[row, col] != "") return;
 if (_turn)
 {
 grid[row, col] = "X";
 _turn = false;
 }
 else
 {
 grid[row, col] = "O";
 _turn = true;
 }
}
```

 

### Putting it together:
Putting everything together, we have something like this.
1. Player makes a move. If move is valid, the board changes
2. Prints the board into the console for visualization.
3. Call a the win condition checking, if it returns anything other than empty or draw. We have a winner

```cs
public void MakeMove(int row, int col) {
 PrintBoard();
 Move(row, col);
 if (_Winner() == "") return;
 if (_Winner() != "Draw"){
 Console.WriteLine("Winner is: " + _Winner + " on " + _winning_line);
 }
 else
 Console.WriteLine("Draw!!");
}
```

 

## Optimized Bitwise Implementations

Now we figured out the basic mechanics of the tictactoe game, we can make much much better optimizations.

 

### The board
Although the more intuitive approach of using a 2D array is pretty easy. In terms of space efficiency, this is too unoptimized. Imagine if you were to implement the same game on an Arduino or any embeded system, this is an unneccasary waste of space.

If it is simple enough we should always use a 1D array to represent our positions. 
```cs
var byte[] board = new byte[9];
```

A byte board is simple enough. a byte is smaller than a string, and each index corresponds to each square in our board now flatten. And the entries could be 0 for empty, 1 for X, 2 for O.
```
0 1 2
3 4 5
6 7 8
```

 

### But we can do better.
Instead of using 9 bytes of data to represent the board. We could use only 4 bytes. This is where the concept of *Bitboard* comes in:
```cs
uint16[] board = new uint16[2];
```

We use 2 uint16 values, but not as an integer number, instead its internal bits as a way to store spatial information. 1 uint16 for each side.
```pseudocode
uint16[] board = {bitArray for X, bitArray for O};
```

so the board would look something like this:
```
// What humans see:
[X, , ]
[O, O, ]
[ , , ]

// What is being stored:
for X for O

1 0 0 0 0 0
0 0 0 1 1 0
0 0 0 0 0 0
```

Since the board only has 9 squares, and a byte is not big enough to store it, we have to use an uint16, as it is the next largest single data type for us to use. The remaining fits can be left unused.


> Why uint16?\
> The U in uint16 stands for unsigned integer, meaning it doesnt have negative numbers. We often use unsigned integers for bitwise operations as the last bit for any integer is usually reserved for negative number representations, we dont want that as it would mess up our expectations of bitwise operations results.\
>\
> In c#'s dotNET standards. we would use `ushort` instead, as `uint16` is depreciated. For the examples here, we use `uint16` as it is more readable.
{: .prompt-info}

 

### Checking for wining conditions
To check for winners we still use the same trick of finding matches by scanning over each rows and columns and diagonals, however, instead of loops and checking each indexes on a row or column for matches. We would use a bitmask. This operation is much much faster. 

A bit mask to represent each possible winning condition. A total of 8. 
```
// internally represented as:
1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1 and some 5 more.

var winingPositions = new uint16[8];
```
In this case it is easy enough to count by hand and paper, and hard code the winning conditions' numeric representation into the array. In larger more complex projects. These are procedurally computed using vector maths and stored in hashsets during the initialization phase.

 

We can perform this following operation to evaluate wherther theres a winner:
```cs
for (var i = 0; i < 8; i++){
 if (board[0] & winingPosition[i] == winingPosition[i])
 return "X is winner!";
 if (board[1] & winingPosition[i] == winingPosition[i])
 return "O is winner!";
}
return "";
```

 

For draws? We would check if all squares are occupied using a bitwise "OR". We know that the 2 position boards never intercepts, so if the union of the 2 boards results in a full board. Then it is a draw.

We know the number that corresponds to 9 bits "ON" state is 511 (Calculated by hand of course)
```cs
if (board[0] | board[1] == 511)
 return "Draw!";
```

 

### Making moves
We can also just as easily mask out the valid moves. In fact, This is the same mechanics as calculating draws. But exposing a move function to the end User, either on a GUI or as a class Method requires some translation, as we shouldnt expect everyone to know bitwise operations, and feeds in a bitmask as input a parameter for a move.

We check if a move is valid by doing the bitmask:
```cs
if ((board[0] | board[i]) & moveMask != 0) {
 // This square is not empty! Cannot make move here
}
else {
 // Since turn is binary and our board is also 2 entries...
 board[turn] &= moveMask;
 turn ^= 1;
 CheckWinners();
}
```
Here we can flip the turn very easily with just a bitwise "XOR" operator.

 

### Calculating the moveMask
How do we calculate the moveMask say if we were to expose our function makeMoves function to an end User, where it accepts an index number or a Vector2 as an input.

There are a few solutions to this: 

1. **Precalculated jump tables**: Write down all possible moveMask by hand, and hard code them into a Dictionary where the values are the moveMask and the keys are in Vector2 or integer index.

2. **Bitshifts by Index ammount** You can compute the moveMask by using bitshifts with the ammount of Index.

3. `1.` and `2.` combined

 

We have to be clear here and set a standard of how we would address an Index or a Vector2 input. Messing up this standard creates lots of bugs, and it gets even messier to diagnose and fix on large projects with hundred of lines of bitwise jump tables. 

```
// where the bottom right corner represents the first bit
Visual: Index: BitArray:
[X, , ] 8 7 6 1 0 0 0 0 0
[O, O, ] 5 4 3 0 0 0 1 1 0
[ , , ] 2 1 0 0 0 0 0 0 0
```


So, we here's how we can compute the bitmask:
```cs
static ushort IndexToBit(int index) {
 ushort outputMask = 1;
 return outputMask << index;
}
```

 

With these references, we can procedurally construct our dictionary during initialization and avoid doing the calculations by hand. 

 

---
# References

Bitwise Operations in Unity: https://www.udemy.com/course/games_mathematics/

## About
App resources are static additional files that your source code uses to build your application. This can be:
- bitmaps (images)
- Layout definitions (XML)
- User Interface strings
- Animation instructions

They are stored inside the `res` folder. Once you store your app resources, you can access them using Resource IDs that are generated in your project's R class.

![](/assets/img/attachments/android/android%20resources.png)

 

> **Best Practice**\
> You should always externalize app resources such as images and strings from your code, so that it can be maintained independently.\
> You should place each type of resources in their respective folders.
{: .prompt-tip}

 

---
## App resources
Some folders such as Animators are not generated by default inside the project template. You can add them later on. 

 

### Animator & anims
Animations work with these few files:
- **animator**: XML files that define property animations
- **anim**: XML files that define tween animations 


> **About animators**\
> Property animations can also be saved in the anim directory, but the animator folder is preferred for property animations to distinguish between the 2 types.
{: .prompt-info}

 

### drawables
They are Bitmap files (.png, . jpg, .gif) or XML files that are compiled into drawable resource subtypes:
- Bitmap files
- Nine-Patches
- State lists
- Shapes
- Animation drawables
- Other drawables

 

### layouts and designs 
The layouts and looks of your app takes a few folders to store:

- **layout** : They store XML files that makes up your user interface, we have seen them when we define your `MainActivity.xml`
- **menu** : XML files that define app menus such as options menu, context Menu, or sub menus.
- **mipmap** : Stores different desity drawable files for your app launcher icon 
- **Font**: Stores font files with extensions like `.ttf` `.otf` `.ttc` or XML files that includes a `<font-family>` element. You can use this to add your own custom fonts.


 

### arbitraries
We have 3 folders that store arbitrary files:
- **XML** : XML files that can be read at runtime by calling `Resources.getXML()`
- **raw** : Arbitary files to save in their raw form.
- **values** : XML files that contain simple values, 

 

---
## raw folder
This folder is used to store raw abitary files, by raw i mean binaries, such as mp3, mp4 etc.

To create this subdirectory:
```
res > New > Android Resource Directory
Resouce type: raw
```

Adding files to this directory is a simple drag and drop.

 

---
## values folder
this folder store files that contains simple values such as strings, integers and colors. 

![](/assets/img/attachments/android/android%20values%20folder.png)

 

### colors.xml
`colors.xml` defines a state list of colors. Here is where you can define custom colors with variable names that you can call inside your project folders. This is automatically generated when you use a color value.

```xml
<?xml version="1.0" encoding="utf-8"?> 
<resources> 
 <color name="black">#FF000000</color> 
 <color name="white">#FFFFFFFF</color> 
</resources>
```

 

You can use them in your layout files like so:
```xml
<TextView
 android:backgound="@color/black">
```


and call this in your java source code like so:
```java
int colorBlack = resources.getColor(R.color.black);
```

 

> **Colors confusion**\
> The colors in android is defined as the following, it is not the same as the standard web Hex code with `#RRGGBBAA` format.
> ```
> #RGB
> #ARGB
> #RRGGBB
> #AARRGGBB
> ```
{: .prompt-warning}

 

### strings.xml
A string resource stores text strings for your application with customizable format and styling. This decouples our application code from things like welcome texts etc.

they are defined this way:
```xml
<?xml version="1.0" encoding="utf-8"?> 
<resources>
 <string name="app_name">ResoucesApp</string>
 <string name="text_welcome">Hello welcome</string>
</resources>
```

 

To use them in our layout:
```xml
<TextView
 android:backgound="@string/text_welcome">
```

To use them in our java source code
```java
String welcome = resources.getString() 
```

 

**String arrays**
We can also declare an array of strings:
```xml
<?xml version="1.0" encoding="utf-8"?> 
<resources>
 ...
 <string name="text_welcome">Hello welcome</string>
 <string-array name="Names">
 <item>Alex</item>
 <item>Steve</item>
 <item>Jeb</item>
 </string-array>
</resources>
```

 

### themes
This subfolder specifies the look of your application based on light / dark modes. 

```xml
<resources xmlns:tools="http://schemas.android.com/tools"> 
  
 <style name="Base.Theme.StoneCamera" parent="Theme.Material3.DayNight.NoActionBar"> 
  
  </style> 
 
 <style name="Theme.StoneCamera" parent="Base.Theme.StoneCamera" /> 
</resources>
```

 

#### Making fullscreen apps
To make your application goes full screen you need to change this line of code within the themes.xml so that it specifies `NoActionBar`

```xml
<style name="Base.Theme.StoneCamera" parent="Theme.Material3.DayNight.NoActionBar"> 
```

This basically hides the ActionBar:
![](/assets/img/attachments/android/android%20action%20bar.png)

 

---
## menu folder
The menu resources is used to define the app menu, options, context menu or submenu. 

To create a menu folder,
```
res > New > Android Resource Directory
Resouce type: menu
```

To create a menu resouce file:
```
menu > New > Menu Resouce File

Name your menufile: main_menu.xml
```

 

Once you have created the menu file you will see that our `menu.xml` contains the following boilerplate:
```xml
<?xml version="1.0" encoding="utf-8"?> 
<menu xmlns:android="http://schemas.android.com/apk/res/android">
 
</menu>
```

To add some menu buttons and setting options, they are called menu items, you must define the `<item/>` like so:

```xml
<?xml version="1.0" encoding="utf-8"?> 
<menu xmlns:android="http://schemas.android.com/apk/res/android">
 <item
 android:id="@+id/new"
 android:icon="@mipmap/ic_launcher"
 android:title="New Game"/>
 <item
 android:id="@+id/save_game"
 android:icon="@mipmap/ic_launcher"
 android:title="Save Game"/>
</menu>
```

To utilize the menu buttons, we must use the following boilerplate in java. This is added to our main activity.
```java
@override
public boolean onCreateOptionsMenu(Menu menu) {
 MenuInflater inflater = getMenuInflater();
 inflater.inflate(R.menu.main_menu, menu);
 return True;
}
```

 

---
## drawable folder
The drawable resouces is a general concept for graphics that can be drawn on the screen. You can retrieve these via the R. class APIS,

The naming convention for drawable files should always be lower snake_case. Do not start with numbers.

Once you have added a resource to drawable, you can add them to a layout attribute:

```xml
android:background="@drawable/mypicture"
```


> **Avoid bad practices**\
> Adding .jpg or .png backgrounds that are above 100kb would be computationaly expensive. Instead, try and see if you could compile your drawable background to a shape type.
> 
> A shape type background with have significantly reduced sizes 1:100kb ratios
{: .prompt-warning}

 

### Drawable shapes (drawable .xml files)

To create a shape for optimizations, 
```
drawable {RIGHT CLICK} > New > Drawable Resource File
File name: my_gradient_shape
Root element: shape
```

You should see a new XML file being generated with the following starting boilerplate:
```xml
<?xml version="1.0" encoding="utf-8"?> 
<shape xmlns:android="http://schemas.android.com/apk/res/android"> 
 
</shape>
```

 

Now we can compile a gradient background this way:
```xml
<?xml version="1.0" encoding="utf-8"?> 
<shape xmlns:android="http://schemas.android.com/apk/res/android"> 
 <gradient
 android:type="linear"
 android:angle="45"
 android:startColor="#560bad"
 android:centerColor="#3f37c9"
 android:endColor="#4cc90f">
</shape>
```


> **Angle values**\
> DO NOT use angle values that are not multiples of 45. This may cause some inconsistent or bad behavior.
{: .prompt-warning}

We can apply them to our layout xml:
```xml
...
android:background="@drawable/my_gradient_shape"
...
```

 

### more about shapes

![](/assets/img/attachments/android/android%20drawable%20shape.png)

Android shapes "objects" can contain the above few properties, by using these properties we can create beautiful custom buttons (with rounded corners etc.)

Example usages of some of the shape properties:

```xml
<?xml version="1.0" encoding="utf-8"?> 
<shape xmlns:android="http://schemas.android.com/apk/res/android"> 
 <gradient
 android:type="linear"
 android:angle="45"
 android:startColor="#560bad"
 android:centerColor="#3f37c9"
 android:endColor="#4cc90f">
 
 
 <corners
 android:radius="12dp"/>
 
 
 <stroke
 android:width="12dp"
 android:color="#eeef20"/>
</shape>
```

We can use this shape in our layout .xml via the background attribute. This can be linked via the file name. 

```
.
.
.
android:background="@drawable/button_shape"/>
```


> **Shape naming conventions**\
> You can name your drawable shapes any that you like, however, it is recommended practice that you add a "shape" suffix. 
{: .prompt-tip}

 

---
## font
You can download and use custom fonts from the internet, they are usually in `.ttf` or `.otf` files.

To add a font subfolder to our res folder:
```
res {RIGHT CLICK} > New > Android Resource File

Directory name: font
Resource type: font
```

We can right away paste our font files inside the font subfolder. Remember, the naming convention for resources dictates we must name the files in lower case snake_case. As an example, my font file will be named `lexand.ttf`

Now we can use our custom fonts in our layout xml like so:
```xml
<TextView
 android:fontFamily="@font/lexand"/>
```

 

---
## Assets folder
You can use this folder to add other files such as PDF files

```
res {RIGHT CLICK} > New > Folder > Assets Folder

Untick "Change Target source"
Finish.
```

You will see the assets folder generated here:
![](/assets/img/attachments/android/android%20assets%20folder.png)

## Arrays with nodes
A linked list stores data fundamentally different from an array. Instead of a collection sitting side by side in memory. A linked list is a single object floating in heap space. It contains some data units, and a reference to the next item (memory address).

![](/assets/img/attachments/dsa/linked%20list.png)

We have 2 types of linked lists, single and double. Single linked lists stores a references to the next node in the list, but not the previous. Double linked lists stores a reference to the next and the previous node.

 

---
## Linked list specs


### Lookup
Lookups in linked lists are always `O(n)` complexity as we can only do sequencial searches. Since every item is stored non continously in memory, we have to traverse the list to find by value, and by index.

![](/assets/img/attachments/dsa/dsa%20linked%20lists%20lookup.png)


### Insertion
Insertions depends on where it is done. Insertions on the head or tail is a `O(1)` complexity, as we can always store a reference to the head or tail, however, the same cant be said for items in the middle

![](/assets/img/attachments/dsa/Pasted%20image%2020230926110132.png)
When we add an item to the head of the list. We create a node that contains the data, we assign its pointer to the original first item. then store this new node as the head. 

For the tail, we create a new note, and have the last note point to it, and assign the new node as the tail.


### Deletion
Deletion for the head is super fast, and is a `O(1)` operation as we simply need to point the head to the second item in the list and remove the first item's reference. 

![](/assets/img/attachments/dsa/Pasted%20image%2020230926110557.png)

However, in single linked lists, deleting the last item is a `O(n)` as we do not have a reference pointing to the second last item, so we need to traverse it.
![](/assets/img/attachments/dsa/Pasted%20image%2020230926110654.png)

For somewhere in the middle, we have to unlink the previous item reference and have it skip the deleted node to point to the next node. Since we have to traverse the node it is an `O(n)` operation.

![](/assets/img/attachments/dsa/Pasted%20image%2020230926110921.png)

 

---
## Implementation: Singular linked lists

A linked list class consists of 2 fundamental structures: an internal `Node` class and the linked lists class:

```cs
public class LinkedLists {
 private Node head;
 private Node tail;
...
}

internal class Node {
 public int data;
 public Node? next;
 public Node(int data, Node? next) {
 this.data = data;
 this.next = next;
 }
}
```

 

### Adding items at begining and end of list
Adding items at the begining and the end of the list is very simple. All we needed to do was to create a new node object to hold a value, and swap the references around.

```cs
public void addLast(int value) {
 var node = new Node(value, null);
 if (head == null) 
 head = node;
 else 
 tail.next = node;
 tail = node;
}
public void addFirst(int value) {
 var node = new Node(value, null);
 if (head == null)
 tail = node;
 else 
 node.next = head;
 head = node;
}
```

 

> **Small improvements**\
> We can also improve the if list is empty check by declaring this method:\
> ```cs
> private bool isEmpty() {
> return (head == null);
> }
> ```
> This way we can do `if (isEmpty()) {..}` instead of `if (head == null) {..}`
{: .prompt-tip}

 

### Index of - search
There are 2 ways we can do an index of search:
1. Recursively traverse the array and return the index once found
2. While loop

#### Recursive solution
You need an index counter, and starting with the first node. Base collapse cases are found and when hit the last node.

```cs
public int indexOf(int value) {
 return find(head, value);
}

private int index = 0;
private int find(Node node, int? item) {
 
 if (node.data == item)
 return index;
 if (node.next == null)
 return -1;
 index++;
 return find(node.next, item);
}
```

#### While loop solution
We define the same breaking case: if found return index; else continue. If `currentNode == null`, breaks out of the while loop, and return -1.
```cs
public int indexOf(int value){
 var index = 0;
 var currentNode = head;
 while (currentNode != null) {
 if (currentNode.data == value)
 return index;
 index++;
 currentNode = currentNode.next;
 }
 return -1;
}
```

 

### contains
This is relatively simple as we can use the indexOf method to iterate through the list and check for -1 returns.
```cs
public bool contains(int value) {
 return (indexOf(value) != -1);
}
```

 

### Removing first and last item
Removing the first item is fairly straight forward. Remove the reference to the second item from the first, then add the second item as a head.
Removing the last item would require traversing the list to get to the second-last item. Set its reference to null, then set it as the new tail.

```cs
public void removeFirst() {
 if (isEmpty())
 throw new InvalidOperationException(
 "cannot remove item from empty list"
 );
 if (head == tail)
 tail = null;
 
 var oldHead = head;
 head = oldHead.next;
 oldHead.next = null;
}

public void removeLast() {
 if (head == null)
 throw new InvalidOperationException("Cannot remove item from empty list");
 
 if (head == tail) {
 head = null;
 tail = null;
 return;
 }
 var currentNode = head;
 while (tail != currentNode.next) {
 currentNode = currentNode.next;
 }
 
 currentNode.next = null;
 tail = currentNode;
}
```

 

### Convertion to array
There are a few ways to convert a linked list into an array. 
Apending them to a list, convert and return it.
```cs
private List<int> items = new List<int>();
public int[] toArray() {
 items.Clear();
 iterate(head);
 return items.ToArray();
}
private void iterate(Node node) {
 if (node.next == null) {
 items.Add(node.data);
 return;
 }
 iterate(node.next);
}
```

More efficiently, utilizing the size of property and allocate an array, populate and return it.
```cs
public int[] toArray() {
 var array = new int[size];
 
 var currentNode = head;
 var index = 0;
 while (currentNode != null) {
 array[index] = currentNode.data; 
 index++;
 currentNode = currentNode.next;
 }
 return array;
}
```

 

---
## Dynamic Arrays vs Linked lists
Arrays have a fixed sizes, while dynamic arrays grow by 50-100% once they hit a capacity, which leads to unnecessary memory usage. 

Linked lists dont waste memory however they do have a slight overhead, because each node stores an address to the next node and a data. 

Use arrays if you know the number of items to store.
![](/assets/img/attachments/dsa/dsa%20arrays%20vs%20linked%20list%20operation%20time%20complexity.png)

 

---
## Double linked lists
Double linked lists has increased performance for deleting items from the end of the list, as it now stores a reference to the previous node. However the performance comes at a cost of overhead, as we are allocating a new field to track the previous node.

![](/assets/img/attachments/dsa/linked%20list.png)

 

---
# References

https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

https://www.simplilearn.com/tutorials/data-structure-tutorial/linked-list-in-data-structure#:~:text=View%20More,reference%20to%20the%20next%20node.

https://www.geeksforgeeks.org/data-structures/linked-list/

## Enhanced if statements / conditional operators
There is a shorter way to write a single if else block:

```cs
string number_confirm;
number_confirm = (a == 10) ? "Yes a is 10" : "no a is not 10";
Console.WriteLine(number_confirm);
```

 

> **Conditional operators**\
> `variable = (condition) ? "Assign this value when true": "assign this value when false";`
{: .prompt-tip}

 

*What about else if blocks?*

```cs
int temp = 100;
var matter = (temp > 100) ? "Gas" : (temp > 0) ? "Liquid" : "Solid"
```

> **Note**\
>``a ? b : c ? d : e `` is evaluated as ``a ? b : (c ? d : e)`` and not 
>``(a ? b : c ) ? d : e``
{: .prompt-info}


 

---
## Switch Cases:
Switch cases are similar to if else statement. Except it can only validate ``==`` operators. We can't use it to validate complex logics.
Often times we use switch cases with ``enum``. We declare enums in the namespace container. 

```cs
namespace ANameSpace
{
	public enum Season
 {
 Spring,
 Summer,
 Autumn,
 Winter,
 }
}
```

 

To use a switch case, in the main method:
```cs
var current_season = Season.Autumn;
switch (current_season)
{
	case Season.Spring:
		Console.WriteLine("Yes its spring flowers are here");
		break;
	case Season.Autumn:
		Console.WriteLine("Its autumn, my leaves has fallen");
		break;
	case Season.Winter:
		Console.WriteLine("Its Winter, let's have a snow flight");
		break;
	default:
		Console.WriteLine("Yuck its summer I/'m melting");
		break;
}
```

The ``default`` here works like the else block. This code will run when non of the previous conditions are true. 

 

We also have to option to use the switch case as it is. without the use of an ``enum``.
```cs
var age = 25;
switch (age)
{
	case 15;
		Console.WriteLine("You can drive");
		break;
	case 21;
		Console.WriteLine("You can drink")
		break;
}
```

 

> **Note!**\
> Switch cases use a jump table to make flows. It works differently than if else blocks and can be said to be more efficient. A rule of thumb to follow is to use switch case when there are a lot of variables to account for, and to use if else if there are only a few. 
{: .prompt-info}

 

---
## Appendix

```cs
namespace ControlFlowStatements
{
 // to use switch case lets create an enum
 public enum Season
 {
 Spring,
 Summer,
 Autumn,
 Winter,
 }
 internal class Program
 {
 static void Main(string[] args)
 {
 Console.WriteLine("Hello, World! Let's test out What is a (say 10, 20, or anything)");
 int a = 10;
 int b = 10;
 // This is an if else block
 if (a == 10 && b ==10)
 {
 Console.WriteLine("a is equal to 10 just like b");
 }
 else if (a== 20)
 {
 Console.WriteLine("a is actually 20");
 }
 else
 {
 Console.WriteLine("I don't know what is a");
 }
			
 // This is a conditional operator
 // variable = (condition) ? "condition is true": "condition is false";
 string number_confirm;
 number_confirm = (a == 10) ? "Yes a is 10" : "no a is not 10";
 Console.WriteLine(number_confirm);
 
 // This is a switch case this format creates an if else block
 var current_season = Season.Autumn;
 switch (current_season)
 {
 case Season.Spring:
 Console.WriteLine("Yes its spring flowers are here");
 break;
 case Season.Autumn:
 Console.WriteLine("Its autumn, my leaves has fallen");
 break;
 case Season.Winter:
 Console.WriteLine("Its Winter, let's have a snow flight");
 break;
 default:
 Console.WriteLine("Yuck its summer I/'m melting");
 break;
 }
			
 // This is a switch case. This is how we do an OR condition.
 // if (current_season == Season.Spring || current_season == Season.Autumn);
 switch (current_season)
 {
 case Season.Spring:
 case Season.Autumn:
 Console.WriteLine("Ah we got promotion for both autumn and spring.");
 break;
 case Season.Winter:
 Console.WriteLine("Its Winter, let's have a snow flight");
 break;
 default:
 Console.WriteLine("Yuck its summer I/'m melting");
 break;
 }
 }
 }
}
```

> **TIPS**\
> For infinite loops. It is recommended to use while loops for infinite loops as for loops will throw an exeption. 
{: .prompt-tip}


## for loops
for loops have an increments and will run until the increments runs out
```cs
for (var i = 0; i < 3; i++)
{
	// Code here will run 3 times
	Console.WriteLine(i);
}
// >>> 0, 1, 2
```

 

## foreach loop
this loops runs thru enumerable objects and iteratables.
```cs
foreach (var item in items)
{

}
```

 

## while loop
this loop will run as long as the codition remainds true. If the condition is false. the loop will not execute

```cs
var condition = true;
while (condition)
{
	// execute this block of code repetively.
}
```

 

## do while loop
Like while loop. This do while loops will run at least once regardless of whether or not the condition is true or false.
```cs
var condition;
do
{
	// This block of code will execute at least once.
	// Will run repetively if condition is true
} while (condition)
```

 

---
## break and continue
break and continues are used in loops to interrupt the loop. Often times from within if else statements. 

### **break**
break statement immediately interrupts the flow and terminates the loop.

The bottom example shows how we would use *break* to break out of the infinite while loop when the user prompts. 
```cs
var numbers = new List<int>();
while (true)
{
	Console.WriteLine("Enter a number");
	var user_input = Console.ReadLine();
	//For simplicity sake. Null and invalid exeption handling are not implemented.
	if (user_input == "ok")
	{
		break;
	}
	else
	{
		numbers.Add(Convert.ToInt32(user_input));
	}
}
```


### **continue**
continue interrupts the flow and skips to the subsequent literation.
```cs
for (var i = 0; i <10; i++)
{
	if (i % 2 == 0)
	{
		Console.WriteLine("{0} is an even number", i);
		continue;
	}
	// This line doesnt execute if the contine statement executes
	Console.WriteLine("An odd number!")
}
```

## Hashtable
Hash tables are a non-primitive data type. They store data in key value pairs. They are from the ``System.Collections`` namespace.

Here is how we define a hash table:
```cs
Hashtable myTable = new Hashtable();
```

To use a Hashtable to store data:
```cs
myTable.Add(key, val);
```

To retrive an item, we must cast the base object back to the original object (Unboxing):
```cs
var item = (val)myTable[key];
```


> **Boxing & Unboxing, Downcasting & Upcasting**\
> Read more [here](/posts/csii-2-inheritance/#boxing-and-unboxing)
{: .prompt-tip}

 

### **Example**:
Say we have this student object that we want to store inside a hash table:
```cs
public class Student
{
	public int Id { get; set; }
	public string Name { get; set; }
	public int Score { get; set; }
	public Student(int id, string name, int score)
	{
		this.Id = id;
		this.Name = name;
		Score = score;
	}
}
```


We will first create our students and our Hashtable, then add the students to our table:
```cs
var studentTable = new Hashtable();

var stud1 = new Student(1, "Alvin", 50);
var stud2 = new Student(2, "Ben", 90);
var stud3 = new Student(3, "Cole", 80);
var stud4 = new Student(4, "Danial", 75);

// Adding Entries into the Hashtable.
studentTable.Add(stud1.Id, stud1);
studentTable.Add(stud2.Id, stud2);
studentTable.Add(stud3.Id, stud3);
studentTable.Add(stud4.Id, stud4);
```

To retrieve the student object, we must use a cast, as all items in Hashtables are boxed.
```cs
var student = (Student)studentTable[1];
Console.WriteLine(student.Name);
```

Entries inside Hashtable's are stored as ``DictionaryEntry`` object. To iterate thru, we can use `foreach` loop:
```cs
foreach (DictionaryEntry entry in studentTable)
{
	var student = (Student)entry.Value
	Console.WriteLine(student.Name);
}

// Alternatively:
foreach (Student item in student.Table.Value)
{
	Console.WriteLine(item.Name)
}
```

 

---
## Dictionary
Like Hashtables. Dictionary store entries in key value pairs. But they implement a type safety therfore avoids boxing and unboxing issues. It is a generic from `System.Collections.Generic` just like lists. 

To declare a dictionary:
```cs
var myDictionary = new Dictionary<int, string>();

// Using object initializer synthax:
var myDictionary2 = new Dictionary<int, string>() 
{
	{1, "Sun"},
	{2, "Moon"},
};
```


> [!INFO] Note
> Fundamentally Dictionary follows the following:
> ```cs
> var myDict = new Dictionary<Tkey, Tvalue>();
> ```
> Where Tkey and Tvalue specifies the object type. 

 

### Iterating dictionaries

```cs
foreach (KeyValuePair<string, string> entry in myDictionary)
{
	// do something with entry.Value or entry.Key
	doSomething(item.Key);
	doSomething(item.Value);
}
```


 

### Removing entires in iterations
Remember, when using foreach emunerable. **You cannot remove entries**
```cs
foreach (var item in myDic)
{
 if (item.key == 42)
		myDic.remove(item.key);
		// Crashes at runtime!!
}
```

One conventional way of doing this is to iterate the entire dictionary, add the entries you wish to remove to an array. Then remove them from the dictionary:
```cs
var itemsToRemove = new List<Tkey>();

foreach(var item in Dictionary){
	if (item.value == 42)
		itemsToRemove.Add(item.key);
}

foreach (var item in itemsToRemove)
 myDic.Remove(item.Key);
```

## A class consists of 2 parts
**Methods and fields**
Method is basically functions that are contained within a class
Fields are variables that are contained in a class

Lets take this analogy
We have a class called 'car'
- it has fields such as num of wheels, seats, colors, brandname etc.
- it has methods, such as Drive(), Turn(), etc. 

Now this car class can be said to be just a blueprint. It tells you how to make a car. An object is an instance of a class. This can be said as a materialization of a class (blueprint) into a "physical" object.

Here is how we declare a class:
```cs
public class Car
{
 // attr and methods
 public string Name;
 public int NumOfWheels;
 public int NumOfDoors;
 public string EngineType;
 // You can also create an attr list that takes in item of obj type Passangers
 public List<Passangers> passangers; 
 
 public void drive()
 {
 Console.WriteLine("Vroom Vroom");
 }
}
```

> **NOTE**\
> Classes are declared in the namespace region. 
> The naming convention for C# classes are in PascalCase.
{: .prompt-info}

 

## Constructors
Constructors allows automatic initiation of fields and call methods uppon the initialization of the class instance/object. It is essentially a method which is called when the object is initialised.

> **Here is how you would declare a constructor**
> 
> ```cs
> public Car()
> {
> 	// Run somecode here
> }
>```
{: .prompt-info}


As per conventions, it is often recommended to declare the constructors after attributes.
```cs
public class Car
{
 public string Name;
 public int NumOfWheels;
 public int NumOfDoors;
 public string EngineType;
 public List<Passangers> passangers; 
 
 public Car()
 {
 this.passangers = new List<Passangers>();
 }
 public void drive()
 {
 Console.WriteLine("Vroom Vroom");
 }
}
```

 

**Overloaded constructors**
Overloaded constructors means you declare multiple constructors, by giving args. However, in the main method. If we were to use this constructor instead, the default args-less constructor would be skipped.
```cs
public Car(string name)
{
 this.Name = name;
}
```

There for we must specify :this() at the end of the overloaded constructor so that it will call the default constructor.

```cs
public Car(string name) : this() 
{
 this.Name = name;
}
public Car(string engineType, int numofwheels) : this()
{
 this.EngineType = engineType;
 this.NumOfWheels = numofwheels;
}
```

 

## Methods
Methods are functions within classes. A constructor is an example of a method. 

```cs
public class Calculator
{
 // This is a default constructor. It takes no params
 public Calculator()
 {
 
 }
 public static int Add(int[] numbers)
 {
 var sum = 0;
 foreach (int number in numbers)
 {
 sum += number;
 }
 return sum;
 }
}
```

In the main(), here's how you would use the Add() method. We use ``new int[]`` because our ``Add()`` method takes an array as arguement, and we do not have an Array.
```cs
internal class Program
{
 static void Main(string[] args)
 {
 Calculator.Add(new int[] {1, 2, 3})
 }
}
```


 

### Methods modifiers
However there is a better way using the *params* modifier. 
```cs
// Calculator.Multiply(10, 10)
public static int Multiply(params int[] numbers)
{
 var product = numbers[0];
 for (var i = 1; i < numbers.Length; i++)
 {
 product *= numbers[i];
 }
 return product;
}
```

With this implementation, you no longer need ``new[] {x, y, z}`` in your main().
```cs
internal class Program
{
 static void Main(string[] args)
 {
 Calculator.Multiply(1, 2, 3)
 }
}
```

 

> **Code Smell**\
> The ref and out modifier, in Hadi's, is a smell in the design of the C# language. Please don’t use it when defining your methods.
{: .prompt-warning}


**ref modifier**
This modifier allows your method to use var parameters as a reference type instead of value.

By default, when we pass a value type (eg int, char, bool) to a method, a copy of that variable is sent to the method. So changes applied to that variable in the method will not be visible upon return from the method. This can be modified using the ref modifier. When we use the ref modifier, a reference to the original variable will be sent to the target method. 

```cs
public static void Minus(ref int a)
{
 a -= 2;
}
```

```cs
// This method can modify value type variables. 
Calculator.Minus(ref a); 
Console.WriteLine(a);
```

 

**out modifier**
The out modifier can be used to return multiple values from a method. Any parameter declared with the out modifier is expected to receive a value at the end of the method.
```cs
public void Weirdo(out int a)
{
 a = 1;
}

// in the main():
int a;
Weirdo(out a);
```

 

---
## Fields
A field can be initialized in two ways: In a constructor, or directly upon declaration. The benefit of initialising a field during declaration is that if your class has one or more constructors, you’ll make sure that the field will always be initialised irrespective of which constructor is going to be called.

```cs
public class Customer
{
 public List<Order> Orders = new List<Order>();
}

```

 

We use the **readonly** modifier to improve the robustness of our code. When a field is declared with readonly, it needs to be initialized either during declaration or in a constructor. The value cannot be changed. This prevents you from accidentally overwriting the value of a field, which can result in an unexpected state. As an example, think of the Orders in the above example. If we accidentally re-initialize this field somewhere else in the class, all the Order objects stored in the list will be lost. So we should declare it as readonly:

```cs
public class Customer
{
 public readonly List<Order> Orders = new List<Order>();
}
```

 

---
## Access Modifiers
In C# we have 5 access modifiers: **public**, **private**, **protected**, **internal** and **protected internal**.

-  A class member declared with **public** is accessible everywhere.

-     A class member declared with **private** is accessible only from inside the class.

-     We’ll learn about the other access modifiers when we get to the [[CS - 2 Inheritance|inheritance]].

We use access modifiers to hide the implementation details of a class. So anything that is about “how” a class does its job should be declared as private. This way, we make sure other parts of the code will not touch the implementation detail of a class. And as a result we improve the robustness of our code. If change the implementation of a class, we only need to make changes inside the class. No other parts of the code will need to be changed.


> **Note**\
> private fields are named in camelCase, with an underscore infront:
> ```cs
> public class Dog
> {
> 	private string _age;
> }
> ```
{: .prompt-info}

 

---
## Properties
A property is a kind of class member that is used for providing access to fields of a class.

> **Notes**\
> As a best practice, we must declare fields as private and create public properties to provide access to them.
{: .prompt-tip}

 

A property encapsulates a get and a set method:

```cs
public class Customer
{
 private string _name;
 public string Name
 {
 get { return _name; } 
 set { _name = value; }
 }
}
```

Inside the get/set methods we can have some logic. If you don’t need to write any specific logic in the get or set method, it’s more efficient to create an auto-implemented property. An auto-implemented property encapsulates a private field behind the scene. So you don’t need to manually create one. The compiler creates one for you:

```cs
public class Customer
{
 public string Name { get; set; }
}
```

> **NOTE**\
> You can use a code snippet in VS code, just type `prop`
{: .prompt-info}

 

### **Example**
Explore the example code below for implementation details:
```cs
public class Person
{
 // Constructor
 public Person(DateTime birthday)
 {
 this.Birthday = birthday;
 }
 
 // Using custom methods to access private fields
 private string _name;
 public void SetName(string name)
 {
 if (!string.IsNullOrEmpty(name))
 this._name = name;
 }
 public string GetName()
 {
 return _name;
 }
 
 
 // Using properties
 // set is private. Use constructor to set bdate
 private DateTime _birthday;
 public DateTime Birthday
 {
 private set { _birthday = value; } 
 get { return _birthday; }
 }
 
 
 // Autoimplementation of properties. 
 public string FamilyName { get; set; }
 
 // Implementing logics in get methods requires manual properties declaration
 // Note this does not have a set method.
 public int Age
 {
 get 
 { 
 var timespan = DateTime.Today - Birthday;
 var years = timespan.Days / 360;
 return years;
 }
 }
}


internal class Program
{
 static void Main(string[] args)
 {
 // Here we see the way to use properties
 var alex = new Person(new DateTime(year: 2000, month: 10, day: 10));
 
 // Properties can be accessed without calling get or set.
 Console.WriteLine(alex.Age);
 }
}
```

 

---
## Indexers
Indexer is a special kind of property that allows accessing elements of a list by an index.

If a class has the semantics of a list, or collection, we can define an indexer property for it. This way it’s easier to get or set items in the collection.

```cs
public class HttpCookie
{
 public string this[string key]
 {
 get {}
 set {}
 }
}

//Example Implementation
// Indexers are properties inplementation for dict type fields
public class Biskuts 
 {
 private Dictionary<string, string> _biskutDetails= new Dictionary<string, string>();
 public string this[string brand]
 {
 get { return _biskutDetails[brand]; }
 set { _biskutDetails[brand] = value; } 
 } 
 }
```

## Access Modifiers
- Your classes should be like a black box. They should have limited visibility from the outside. The implementation, the detail, should be hidden. We use access modifiers (mostly private) to achieve this. This is referred to as Information Hiding (and sometimes Encapsulation) in object-oriented programming.

- Public: is accessible everywhere.

- Private: is accessible only from the class.

- Protected: is accessibly only from the class and its derived classes. Protected breaks encapsulation (because the implementation details of a class will leak into its derived classes) and is better to be avoided.

- Internal: is accessibly only from the same assembly.

- Protected Internal: is accessible only from the same assembly or any derived classes. (Sounds weird? Forget it! It’s not really used.)



> **Constructors and Inheritance**\
> Constructors are not inherited and need to explicitly defined in derived class. When creating an object of a type that is part of an inheritance hierarchy, base class constructors are always executed first. 
> 
> We can use the base keyword to pass control to a base class constructor:
> ```cs
> public class Car : Vehicle 
> { 
> 	public Car(string registration) : base(registration) 
> 	{ 
> 		//code
> 	}
> }
{: .prompt-tip}

 

---
## Upcasting and Downcasting

> *Upcasting*: conversion from a derived class to a base class 
> *Downcasting*: conversion from a base class to a derived class 

See also: [[Boxing and Unboxing]]

> **Note**\
> All objects can be implicitly converted to a base class reference.
{: .prompt-info}

 

Lets say we have the following few classes:
```cs
public class Shape
{
 public int size { get; set; }
}
public class Circle: Shape 
{ 
}
public class Car
{
} 
```

 

In the main() we can see how upcasting and downcasting works:
```cs
// Upcasting. Implicit conversion can happen.
var circle = new Circle();
Shape shape = circle;

// Downcasting. Explicit cast is required.
Circle anotherCircle = (Circle) shape;
```


Below is an example of casting in action:
```cs
// We assign a class into its parent class
var circle = new Circle();
Shape shape = circle;

circle.size = 200;
shape.size = 100;
// what would happen?
Console.WriteLine(circle.size);

//Because shape object is a reference to the same circle object in memory
// circle.size would become 100.
```

 

### **Exceptions**
Casting can throw an exception if the conversion is not successful. We can use the ``as`` keyword to prevent this.

```cs
// If conversion is not successful, null is returned. 
Circle circle = shape as Circle; 
if (circle != null)
{
 //Run code
}
```

We can also use the ``is`` keyword:
```cs
if (shape is Circle)
{
 Console.WriteLine("Yes shape is a Circle");
 // Cast Circle to shape
}
```


> **NOTE**\
> If the cast does not have a child relations. InvalidCastException is thrown.
> ```cs
> Car car = (Car) anotherCircle;
> ```
{: .prompt-warning}

 

---
## Boxing and Unboxing
C# types are divided into two categories: **_value types_** and **_reference types_**. See [[Boxing and Unboxing]] for full explaination by Microsoft.

- **_Value types_** (e.g. `int`, `char`, `bool`, all primitive types and struct) are stored in the stack. 
They have a short life time and as soon as they go out of scope are removed from memory. 

- **_Reference types_** (e.g. all classes) are stored in the heap. Every object can be implicitly cast to a base class reference. 


> **Note**\
> The object class is the parent of all classes in .NET Framework. So a value type instance (eg int) can be implicitly cast to an object reference. 
{: .prompt-info}

Boxing happens when a value type instance is converted to an object reference.
Unboxing is the opposite: when an object reference is converted to a value type.
```cs
// Boxing 
object obj = 1;

// Unboxing 
int i = (int)obj;
```

> **PERFORMANCE**\
> Both boxing and unboxing come with a performance penalty. This is not noticeable when dealing with small number of objects. But if you’re dealing with several thousands or tens of thousands of objects, it’s better to avoid it.
{: .prompt-warning}

> Pulled from: Mosh Hamedani\
> [Programming with Mosh - Learn the Skills to Land Your Dream Job](https://programmingwithmosh.com/)

 

---

## Class Coupling 
A measure of how interconnected classes and subsystems are. 
The more coupled classes, the harder it is to change them. A change in one class may affect many other classes. 
Loosely coupled software, as opposed to tightly coupled software, is easier to change. 

Two types of relationships between classes: Inheritance and Composition.

 

### Inheritance
A kind of relationship between two classes that allows one to inherit code from the other.
- Referred to as Is-A relationship: A Car is a Vehicle 
- Benefits: code re-use and polymorphic behaviour.

```cs
public class Car : Vehicle 
{ 
 // Members
}
```

 

### Composition 
A kind of relationship that allows one class to contain another. 
- Referred to as Has-A relationship: A Car has an Engine 1 
- Benefits: Code re-use, flexibility and a means to loose-coupling

```cs
// Base
public class Animal
{
 public int Age { get; set; }

 public void Eat() 
 {
 Console.WriteLine("Nom Nom");
 }
 public void Breath() 
 {
 Console.WriteLine("Snore snore");
 }
}

// derived with composition
public class Dog
{
 private readonly Animal _Animal;
 
 public Dog()
 {
 
 }
 public Dog(Animal animal)
 {
 _Animal = animal;
 }
 
 public void Eat() 
 {
 _Animal.Eat();
 }
 public void Breath() 
 { 
 _Animal.Breath();
 }
}
```

 

---
## Favour Composition over Inheritance 
- Problems with inheritance: 
 - Easily abused by amateur designers / developers 
 - Leads to large complex hierarchies 
 - Such hierarchies are very fragile and a change may affect many classes 
 - Results in tight coupling 
 

- Benefits of composition: 
 - Flexible
 - Leads to loose coupling
 
- Having said all that, it doesn’t mean inheritance should be avoided at all times. In fact, it’s great to use inheritance when dealing with very stable classes on top of small hierarchies. As the hierarchy grows (or variations of classes increase), the hierarchy, however, becomes fragile. And that’s where composition can give you a better design.

 

---
## Composition variants:

Lets look at 2 slightly different means of composition:
```cs
// Default variant
public class Dog
{
 private readonly Animal _Animal;
 
 public Dog()
 {
 
 }
 public Dog(Animal animal)
 {
 _Animal = animal;
 }
 
 public void Eat() 
 {
 _Animal.Eat();
 }
 public void Breath() 
 { 
 _Animal.Breath();
 }
}
```

 

```cs
// Variant 2
public class Dog 
{ 
 private readonly Animal _Animal; 
 
 public Dog() 
 { 
 _Animal = new Animal(); 
 } 
 
 public void Eat() 
 { 
 _Animal.Eat(); 
 } 
 
 public void Breath() 
 { 
 _Animal.Breath(); 
 } 
}
```


In the first example, the `Dog` class has a "has-a" relationship with the `Animal` class. This means that a `Dog` object has an instance of the `Animal` class as a member variable. The `Dog` class relies on the `Animal` class to provide some of its functionality, specifically the `Eat()` and `Breath()` methods, which are called through the `_Animal` member variable.

In the second example, the `Dog` class creates a new instance of the `Animal` class within its constructor. This means that a `Dog` object has its own `Animal` object as a member variable, rather than relying on an existing `Animal` object that was passed to the constructor.

The main difference between these two approaches is in how the `Animal` object is created and managed. In the first example, the `Animal` object is created externally and passed to the `Dog` constructor, which allows for more flexibility in how the `Dog` object is created and used. For example, you could create multiple `Dog` objects that all share the same `Animal` object. This can be useful in some situations, but it can also make the code more complex.

In the second example, the `Animal` object is created internally by the `Dog` constructor, which simplifies the code somewhat. However, this approach is less flexible, since each `Dog` object has its own `Animal` object and there is no way to share an `Animal` object between multiple `Dog` objects.

So, which approach to use depends on the specific needs of your program. If you need more flexibility and want to be able to share an `Animal` object between multiple `Dog` objects, then the first approach is probably better. If you just need a simple `Dog` object that always has its own `Animal` object, then the second approach may be sufficient.

> Pulled from: Mosh Hamedan

## Method Overriding

^84042a

Method overriding means changing the implementation of an inherited method. 
If we declare a method as virtual in the base class, we can override it in a derived class.
this is one of the polymorphic features.


In c# we override inherited methods using the virtual and override keyword:
```cs
public class Shape
{
 public virtual void Draw()
 {
 // Default implementation
 Console.WriteLine("I draw a box");
 }
 public void outline()
 {
 Console.WriteLine("I draw outline");
 }
}

public class Circle : Shape
{
 public override void Draw()
 {
 // new implamentation
 Console.WriteLine("I draw a circle");
 }
}
```


> **NOTE**\
> This technique allows us to achieve polymorphism. Polymorphism is a great object-oriented technique that allows use get rid of long procedural switch statements (or conditionals)
{: .prompt-info}

 

---
## Abstract Classes and Members
Remember this example of using method overrides?

We can declare a class and its members as abstract instead meaning it has no implementation and let its child classes do the implementation. It is designed specificaly for polymorphic behavior


> **Note**\
> - Abstract modifier states that a class or a member misses implementation. We use abstract members when it doesn’t make sense to implement them in a base class. 
> - For example, the concept of drawing a shape is too abstract. We don’t know how to draw a shape. This needs to be implemented in the derived classes. 
> - When a class member is declared as abstract, that class needs to be declared as abstract as well. That means that class is not complete. In derived classes, we need to override the abstract members in the base class
{: .prompt-info}

 

Here is how we declare an abstract class:
```cs
public abstract class Shape
{
 // This method doesnt have a body
 public abstract void Draw();
}

public class Circle : Shape
{
 public override void Draw()
 {
 // The implimentations...
 Console.WriteLine("Drawing a circle");
 }
}
```

 

> **WARNING**\
> All members declared as abstract in the classes must be override in the child classes, otherwise that derived class is going to be abstract too.\
> Abstract classes **cannot** be instancelized. It will not compile.
{: .prompt-warning}

 

---
## Sealed Classes and Members

> when declared on the class - Prevents derivation of _child class_
> when declared on the methods - Prevents overriding of the _methods_.


> **Note**\
> The string class is declared as sealed, and that’s why we cannot inherit from it
{: .prompt-tip}

 

---
## String class method overrides?
In the string class we can override one useful method `ToString()`. 

Whenever we use this method on class objects, or event built in non-primitive types like Lists It always returns Nonsense. However for our custom classes, we can override it:

Now this object's ToString method would return its fields, intead of nonsense.
```cs
public class Coords
{
 float x;
 float y;
 float z;
 
 public Coords(float _X, float _Y)
 {
 x = _X;
 y = _Y;
 z = 0;
 }
 
 public override string ToString()
 {
 return x + ", " + y ", " + z;
 }
}
```

> Pulled from: Mosh Hamedani

 

## About Interfaces
an interface is like a class but it is of an abstract construct. An interface is simply a declaration of the capabilities (or services) that a class should provide.

 

Here is how you would declare an interface. Do note that we use the `I` convention when declaring interfaces, ``IsystemCore``, ``IFlowRateCalculator`` etc.
```cs
public interface ITaxCalculator
{
 int Calculate(int a, int b);
}
```

 

This interface states a class that wants to play the role of a tax calculator, should provide a method called Calculate() that takes no parameters and returns an int. The implementation of this class might look like this:
```cs
public class TaxCalculator : ItaxCalculator
{
 public int Calculate(int a, int b)
 {
 // Inplementations .....
 }
}
```

 

> **Note**\
> - Interface is purely a declaration. Members of an interface do not have implementation. 
> - An interface can only declare methods and properties, but not fields (because fields are about implementation detail). 
> - Members of an interface do not have access modifiers.
{: .prompt-tip}

 

### Why use Interfaces?
Interfaces help building loosely coupled applications. We reduce the coupling between two classes by putting an interface between them. This way, if one of these classes changes, it will have no impact on the class that is dependent on that (as long as the interface is kept the same).

 

---
## Interfaces and Testability
Unit testing is part of the automated practice which helps improve the quality of our code. With automated testing, we write code to test our own code. This helps catching bugs early on as we change the code. 

In order to unit test a class, we need to isolate it. This means: we need to assume that every other class in our application is working properly and see if the class under test is working as expected. 

 

A class that has tight dependencies to other classes cannot be isolated. 
To solve this problem, we use an interface. Here is an example of how a class uses an interface:

```cs
public class OrderProcessor 
{ 
 private IShippingCalculator _calculator; 
 public Customer(IShippingCalculator calculator)
 {
 _calculator = calculator;
 }
 
 public int Calculate(int a, int b) {
 this._calculator.Calculate(a, b)
 }
 // Other Implementations......
}
```

So here, OrderProcessor is not dependent on the ShippingCalculator class. It’s only dependent on an interface (`IShippingCalculator`). If we change the code inside the `ShippingCalculator` (eg add a new method or change the method implementations) it will have no impact on `OrderProcessor` (as long as the interface is kept the same).

 

---
## Interfaces and Extensibility
We can use interfaces to change our application’s behaviour by “extending” its code (rather than changing the existing code). 

If a class is dependent on an interface, we can supply a different implementation of that interface at runtime. This way, the behaviour of the application changes without any impact on that class. 

For example, let’s assume our DbMigrator class is dependent on an ILogger interface. At runtime, we can supply a ConsoleLogger to log the messages on the console. Later, we may decide to log the messages in a file (or a database). We can simply create a new class that implements the ILogger interface and inject it into DbMigrator.

 

---
## Interfaces and Inheritance 
One of the common misconceptions about interfaces is that they are used to implement multiple inheritance in C#. **This is fundamentally wrong, yet many books and videos make such a false claim. **


>With inheritance, we write code once and re-use it without the need to type all that code again. 


>With interfaces, we simply declare the members the implementing class should contain. Then we need to type all that declaration along with the actual implementation in that class. So, code is not inherited, even the declaration of the members

## Collections
Collections are classes that we can use to a collection of objects. They are not limited to one type of objects, and they have no size constrains.

We use collections to create dynamic arrays. Remember Lists? It is a type of Generic collection. 

There are 2 types of Collections:

### Non Generic
Can store any type of objects.

Located in:
```
System.Collections
```

### Generic
Limited to one type of object
Located in:
```
System.Collections.Generic
```

 

---
## Generics

With generic lists, adding an item of type X will no longer have performance penakty due to boxing and unboxing as we specify the type of list or dict object.\
[[QNA Boxing and Unboxing with Generics#ANSWER|Why?]]

The following are examples of how we can implement our own generic lists and dictonaries.

### Generic Lists
```cs
public class GenericList<T>
{
 public void Add(T value)
 {
 }
 public T this[int Index]
 {
 get { throw new NotImplementedException(); }
 }
}
```

### Generic Dictionary (Key Value)
```cs
public class GenericDictionary<Tkey, Tvalue>
{
 public void Add(Tkey key, Tvalue val)
 {
 }
}
```


> **.NET Built In Generics**\
> We do not need to create our own implementation of generic lists and dictionary as it is already available on .NET : See [[CS - 6 Key Value Pairs#Dictionary|Dictionary]] and [[CS - 3 Non premitive types#Lists|List]]
> ```cs
> > System.Collections.Generic
> ```
{: .prompt-tip}

 

---
## Generics and Comparables.

The following represents a function that returns the largest number.
```cs
public class Utitlies {
 // if a is bigger than b return a, else return b
 public int Max(int a, int b) {
 return a > b ? a : b;
 }
}
```
 

However, if we were to declare a generic method as below, it wont compile because T is not comparable:
```cs
//This code will not compile
public T Max<T>(T a, T b) {
 return a > b ? a : b; 
}
```
 

We must apply some type of constrains:
- `where T : Icomparable`
- `where T : Product`
- `where T : struct`
- `where T : class`
- `where T : new()`

```cs
public T Max<T>(T a, T b) where T : IComparable
{
 return a.CompareTo(b) > 0 ? a : b;
}
```

 

---
## Generic Dictionary and Lambda Expression

Coding Examples:
```cs
using System;
using System.Collections.Generic;

namespace Coding.Exercise
{
 public class Run
 {
 // TODO
 // Expressions
 static Func<float, float, float> Plus = (a, b) => a + b;
 static Func<float, float, float> Minus = (a, b) => a - b;
 static Func<float, float, float> Divide = (a, b) => a / b;
 static Func<float, float, float> Multiply = (a, b) => a * b;
 
 
 static Dictionary<string, Func<float, float, float>> Operators = new Dictionary<string, Func<float, float, float>>()
 {
 {"+", Plus},
 {"-", Minus},
 {"/", Divide},
 {"*", Multiply}
 };
 
 public static Func<float, float, float> OperationGet(string key)
 {
 if (Operators.ContainsKey(key))
 {
 return Operators[key];
 }
 else
 {
 return null;
 }
 }
 }
}
```

DELEGATES
- an object which calls other methods
- a reference to a function/METHOD

> WHY DO WE NEED THEM?
> For designing extensible and flexible applicaitons (eg. frameworks). Its usage is similar to interfaces

> **Interface or Delegates?**\
> Use a delegate when:
> - an eventing design pattern is used
> - the caller doesnt need to access other properties or methods on the object implementing the method
{: .prompt-tip}

We can think of a delegate as a reference to a function or like an interface but for methods, and use them as such. Let's say we want a function that applies an effect on photos like a photo filter, but we leave the implementation details out of the class, and only in the main() where we will specify which method we should use as our implementation. Therefore methods that implements the delegates should have the same arguements types and return types. 


 

---
## The Problem
Everything here in `PhotoProcessorV1` works. This can be considered a type of stored procedure class where the filter processes are executed. But if this is a framework. We may want to add our own methods to the filter, this class would need redeployment and thus not extensible.

````cs
public class PhotoProcessorV1
{	
 public void Process(string path)
 {
 var photo = Photo.Load(path);
 var filter = new Filters();
 filter.Brightness(photo);
 filter.Contrast(photo);
 filter.Resize(photo);
 }
}
````

 

### Now we use a delegate. 
The `PhotoProcessorV2` takes an additional arguement "delegate". This removes the need of redeployment of the class, when adding additional filters to the Process method.

``````cs
public delegate void PhotoFilterHandler(Photo photo);
public class PhotoProcessorV2
{
 public void Process(string path, PhotoFilterHandler filterHandler)
 {
 var photo = Photo.Load(path);
 filterHandler(photo);
 }
}
``````

 

### The Main method
`PhotoProcessorV1` is used as it is in an instance, and all the stored procedure is hard coded into the class. 

`PhotoProcessorV2` implements the delegate. `PhotoFilterHandler` is declared and an instance of the filter method is added to the filterHandler. You can add as many filters to this handler. With the use of method extensions on the filters class, only the Main would need redeployment.

````cs
internal class Program
{
 static void Main(string[] args)
 {
 // Version 1
 var photprocess1 = new PhotoProcessorV1();
 photprocess1.Process("path");
 
 // Version 2 with delegates
 var photprocess2 = new PhotoProcessorV2();
 var filters = new Filters();
 PhotoFilterHandler filterHandler = filters.Brightness;
 photprocess2.Process("path", filterHandler);
 
 // Adding extra items to the delegate to run more filters
 filterHandler += filters.Resize; 
 photprocess2.Process("path", filterHandler);
 
 // Version 3 with .NET Generic delegates
 var photprocess3 = new PhotoProcessorV3();
 var filters2 = new Filters();
 Action<Photo> filterHandler2 = filters2.Brightness;
 photprocess3.Process("path", filterHandler2);
 
 // Adding extra items to the delegate to run more filters
 filterHandler2 += filters.Resize; 
 photprocess3.Process("path", filterHandler2);
 }
}
````
 

---
## Extras

> **Generic Delegates**\
> In C# we have generic delegates
> ```
> // This is used for void methods
> System.Action<T>
>
> // This is used for methods with returns
> System.Func<Targ, Treturn>
> System.Func<Targ1, Targ2, Treturn>
> ....
> ```
{: .prompt-tip}

^fa837d

 

Example of generic delegate implementation
````cs
public class PhotoProcessorV3
{
 public void Process(string path, Action<Photo> filterhander)	
 {
 var photo = Photo.Load(path);
 filterhander(photo);
 }
}


internal class Program
{
 static void Main(string[] args)
 {
 // Version 3 with .NET Generic delegates
 var photprocess3 = new PhotoProcessorV3();
 var filters2 = new Filters();
 Action<Photo> filterHandler2 = filters2.Brightness;
 photprocess3.Process("path", filterHandler2);
 
 // Adding extra items to the delegate to run more filters
 filterHandler2 += filters.Resize; 
 photprocess3.Process("path", filterHandler2);
 }
}
````

<br. 

---
## Anonymous Methods

Below is a simple demonstration of using Anonymous methods:
```cs
// Delegate must be declared in class scope.
public delegate bool lessThanDelegate(int num);

//in main()
static void DisplayResults(List<int> listofNum, lessThanDelegate filter)
{
 foreach (var i in listofNum)
 {
 if(filter(i))
 {
 Console.WriteLine(i);
 }
 }
}


// We declare our anon method:
lessThanDelegate filter5 = delegate(int num)
{
 return num < 5;
}

// Using it...
var myList = new List<int>() {1, 2, 6, 7, 8};
DisplayResults(myList, filter5);
```

 

---
## Appendix
Classes used in this example

This here is the Filters Class. Leaving out implementation details. If we were to add new filters. We would recompile this class or use extensions.
````cs
public class Filters
 {
 public void Brightness(Photo photo)
 {
 Console.WriteLine("Applying brigthness");
 }
 public void Contrast(Photo photo)
 {
 Console.WriteLine("Applying contrast");
 }
 public void Resize(Photo photo)
 {
 Console.WriteLine("Resizing");
 }
 }
````

```cs
public class Photo
 {
 public static Photo Load(string path)
 {
 return new Photo();
 }
 }
```


 

Here's another example of using delegtes
```cs
namespace Exercise_2___Delegates
{
 internal class Program
 {
 //Delegate declaration
 public delegate float OperationDelegate(float x, float y);
 
 
 static void Main(string[] args)
 {
 
 // Opeation methods
 static float ApplyOperation(float x, float y, OperationDelegate operation)
 {
 return operation(x, y);
 }
 
 
 
 // Implementation methods This uses the delegates
 static float Add(float x, float y)
 {
 return x + y;
 }
 static float Subtract(float x, float y)
 {
 return x - y;
 }
 static float Multiply(float x, float y)
 {
 return x * y;
 }
 static float Divide(float x, float y)
 {
 return x / y;
 }
 }
 }
}

```

## About

The gradle build systems allows use to attach and include external binaries or other library modules to our build as dependencies. These dependencies can be located on our PC or from a remote repo like github, and any transit repositories that they require will be automatically included.

To include a dependency into our build, you must specify the dependency inside our `build.gradle` file.



> **What are dependencies**\
> Dependencies or libraries are basically precompiled source codes. Have you noticed that when we write our custom classes inside the java folder, we dont need to do anything special at all, however, when we want to use other libraries, often we do not receive them in a .java file, instead it is often in a `.jar` file.\
> \
> This is basically the java byte code. In this section we will learn how to add these compiled binaries into our project, and use them.
{: .prompt-tip}


Now, when selecting a gradle language, you have the option of either kotlin or grovvy. This guide will show both usecases. Be sure to watch out for the language highlight in the code snippets and infer the synthax differences.


 

---
## build.gradle(Module: )

Essentially these are the dependancies that we are referring to, they are declared within the `build.gradle.kts` (or `build.gradle` for gradle) files: 

```kotlin
dependencies { 
 implementation("androidx.appcompat:appcompat:1.6.1") 
 implementation("com.google.android.material:material:1.8.0") 
 implementation("androidx.constraintlayout:constraintlayout:2.1.4") 
 testImplementation("junit:junit:4.13.2") 
 androidTestImplementation("androidx.test.ext:junit:1.1.5") 
 androidTestImplementation("androidx.test.espresso:espresso-core:3.5.1") 
}
```

 

### Library module dependency

Here's how dependencies work. We declare the library inside the `build.gradle`.kts,
```kotlin
dependencies {
 // Local Library Module Dependency
 implementation project(":mylibrary")
}
```

Then we must also declare them inside the `settings.gradle.kts`, under "include"
```kotlin
pluginManagement { 
 repositories { 
 google() 
 mavenCentral() 
 gradlePluginPortal() 
 } 
} 
dependencyResolutionManagement { 
 repositoriesMode.set(RepositoriesMode.FAIL_ON_PROJECT_REPOS) 
 repositories { 
 google() 
 mavenCentral() 
 } 
} 
 
rootProject.name = "Stone Camera" 
include(":app")
include(:"mylibrary") // Here
```

> **Important**\
> When you build your application, the build system compiles the library module and packages that resulting compile will be included in the app.
{: .prompt-tip}

 

### Local binary dependency
For local binaries (downloaded `.jar` files), Gradle declares dependencies on jar files inside your project's libs folder.

```gradle
dependencies {
 // Local Library Module Dependency
 implementation project(":mylibrary")
 
 // Local binary dependency
 implementation fileTree(dir: "libs", includes: ['*.jar'])
 
 // Alternatively, to specify specific files...
 implement files("libs/myFile.jar", "libs/myOtherfile.jar")
}
```

 

### Remote binary dependency
This will allow gradle to attempt to fetch the files over the internet.
```gradle
dependencies {
 // Local Library Module Dependency
 implementation project(":mylibrary")
 
 // Local binary dependency
 implementation fileTree(dir: "libs", includes: ['*.jar'])
 
 // Alternatively, to specify specific files...
 implement files("libs/myFile.jar", "libs/myOtherfile.jar")
 
 // Remote binary dependencies
 implementation "com.example.android:app-magic:12.3"
}
```


The way it works is to ask gradle to look for the file named "app-magic", version 12.3 from the group/package "com.example.android". A group dependency like this requires that we decalre the approapriate remote repositories where Gradle should look for the library. If the library doesnt already exist locally, they will be pulled from the remote side when the build requires it. 


> **Groovy or kotlin**\
> A lot of times our gradle build files could be written in groovy or kotlin synthax. This maybe confusing. However its important to take node the general context works like this:\
> `type "argument"` this is where a function was redacted; `implements "com.somewhere"`\
> `type functionName("arguments")`\
> `type functionName(kwarg: "argument")`
{: .prompt-tip}

 

---
## Practical Demonstration

Using the glide library which is an image loading and caching library for android focused on smooth scrolling, as our example...

The source code is [here](https://github.com/bumptech/glide). So how do we add a github repo project files into our app?

Well, if we scroll down we can see a few examples and documentations:

![](/assets/img/attachments/android/android-dependencies-glide-library.png)

There are mainly 2 ways to get this library into our project:

 


### Method 1: Use as local binary
The first thing we got to do is to download their `.jar` files and put in inside our project's `libs` folder and include it as a local binary:

 

### Method 2: Have Gradle download it from repo
As previously mentioned, we can have gradle to download this files automatically via the "Remote dependency" method.

So lets copy this code from the readme page:
```gradle
repositories {
 google()
 mavenCentral()
}

dependencies {
 implementation 'com.github.bumptech.glide:glide:4.16.0'
}
```

Into our build.gradle(Project:) gradle, we will often see google and mavenCentral is already preincluded.

```gradle
// Top-level build file where you can add .......
buildscript {
 repositories {
 google()
 mavenCentral()
 }
 dependencies {
 classpath "com.android.tools.build:gradle7.0.4"
 
 // NOTE: Do not place your application dependencies here;
 // they belong in the individual build.gradle files
 }
}

task clean(type: Delete) {
 delete rootProject.buildDir
}
```

Towards our `build.gradle(Module:)` gradle's dependencies section. We will see these code that has already preincluded in a project template. 
All wee need to do is to all ours in:

```gradle
dependencies {
 
 implementation "androidx.appcompat:appcompat:1.2.0"
 implementation "con.google.android.material:material:1.3.0"
 implementation "androidx.constraintlayout:constraintlayout:2.1.2"
 testImplementation "junit:junit4.+"
 androidTestImplementation "androidx.test.ext.junit:1.1.2"
 andoridTestImplementation "androidx.test.espresso:espresso-core:3.3.0"
 
 // Our dependencies code goes here
 implementation "com.github.bumptech.glide:glide:4.12.0"
 annotationProcessor "com.github.bumptech.glide:compiler:4.12.0"
}
```

 

---
## Modern Gradle outlines & Common errors

In 2023 september, our gradle outlines will look vastly different, first of all, our `build.gradle(Project: )` will look like this:



```gradle
// Top-level build file where you can add ......
plugins { 
 id 'com.android.application' version '8.0.2' apply false 
 id 'com.android.library' version '8.0.2' apply false 
}
```

And the settings.gradle(Project settings) will look like this:
```gradle
pluginManagement { 
 repositories { 
 google() 
 mavenCentral() 
 gradlePluginPortal() 
 } 
} 
dependencyResolutionManagement { 
 repositoriesMode.set(RepositoriesMode.FAIL_ON_PROJECT_REPOS) 
 repositories { 
 google() 
 mavenCentral() 
 } 
} 
rootProject.name = "ExampleGlideProject" 
include ':app'
```

So when adding an external dependencies, we will instead declare the repositories inside the project settings instead, and leave the `build.gradle(Project:)` untouched.

The dependencies can be added into the `build.gradle(Module:)` as usual.

 

### Dependencies not fully resolved
This happens from time to time when you have already added the dependencies, yet you still see a missing class error:

![](/assets/img/attachments/android/android-dependencies-missing-class-error.png)

You need to make sure you added the repository into your build settings! Read the documentations carefully.

![](/assets/img/attachments/android/android-studio-pdf-viewer-documentation.png)


Add these repositories into your `settings.gradle(Project settings)` file
```gradle
pluginManagement { 
 repositories { 
 google() 
 mavenCentral() 
 gradlePluginPortal() 
 jcenter() // Add here, usually optional
 } 
} 
dependencyResolutionManagement { 
 repositoriesMode.set(RepositoriesMode.FAIL_ON_PROJECT_REPOS) 
 repositories { 
 google() 
 mavenCentral() 
 jcenter() //Must Add here
 } 
} 
rootProject.name = "ExampleGlideProject" 
include ':app'
```

 

### Duplicate Class errors
This also happens from time to time when we use external libraries. This conflicts usually comes from The external library using its own version of some class implementations. [Details](https://stackoverflow.com/questions/55909804/duplicate-class-android-support-v4-app-inotificationsidechannel-found-in-modules):


#### The fix:
Add these lines of code inside `gradle.properties`. Make sure you dont repeat lines already present:
```gradle
android.useAndroidX=true
android.enableJetifier=true
```


#### Why it works?:
Your project (or one of its sub-projects, or a dependency) is no longer using `android.support` libraries and instead is using `androidx` libraries, which causes conflicts if mixed with `android.support` libraries.

If you want to use `androidx`-namespaced libraries in an old project, you need to set the compile SDK to Android 9.0 (API level 28) or higher but below "API level 31", and set both of the mentioned Android Gradle plugin flags to `true`.

**`android.useAndroidX`**: When this flag is set to `true`, the Android plugin uses the appropriate AndroidX library instead of a Support Library. The flag is `false` by default if it is not specified.

**`android.enableJetifier`**: When this flag is set to `true`, the Android plugin automatically migrates existing third-party libraries to use AndroidX dependencies by rewriting their binaries. The flag is `false` by default if it is not specified.

## About the problem
The momento pattern is one of the most fundamental patterns in design. It is used to implement the undo mechanism. 

Imagine this scenario, we have an editor class
```java
public class Editor {
 private String content;
 
 public String getContent() {
 return content;
 }
 
 public void setContent(String content) {
 this.content = content;
 }
}
```

and we want to implement an undo method which will reset the content:
```java
public static void main(String[] args) {
 var editor = new Editor();
 editor.setContent("a");
 editor.setContent("b");
 editor.setContent("c");
 editor.undo(); // *
}
```

 

---
## Design Pattern - Solution
A straight forward solution would be something like this:
```java
public class Editor {
 private String content;
 private String prevContent;
 
 public String getContent() {
 return content;
 }
 
 public void setContent(String content) {
 this.prevContent = this.content;
 this.content = content;
 }
 
 public void undo() {
 this.content = this.prevContent
 }
}
```

 

### The naive
However, this have a weakness, we cant undo more than once. To do this, we would have to implement a list instead:

```
 __________________
| Editor |
|------------------|
|content: string |
|prevContent: List |
|__________________|
```

However if we were to add an additional fields that we need to track, this would quickly become unscalable:

```
 __________________
| Editor |
|------------------|
|content: string |
|prevContent: List |
| |
|title: string |
|prevTtitle: List |
|__________________|
```

 

### The expert
A better way to implement this is to create a separate `EditorState` class that can be used to track these many fields of changes, which makes it more scalable:

```
 __________________ ____________________
| Editor | | EditorState |
|------------------| Composition |--------------------|
|content: string |#===================>|content: string |
|prevStates: List | |title: string |
| | |____________________|
|__________________|
```

This is a better solution as we can undo multiple times, and we are not polluting the editor class with a bunch of fields and methods. However this implementation **breaks** a fundamental principle of OOP ***Single Responsibility Principle***.

 

---
## Single Responsibility
To build maintainable software we should design our classes to have single responsibility. Our expert design isnt good enough as the Editor class is doing too much work: 
1. State management
2. Providing features for the editor

```
 __________________ ____________________
| Editor | | EditorState |
|------------------| Composition |--------------------|
|content: string |#=======================>|content: string |
|prevStates: List | |title: string |
| | |____________________|
|__________________|
```



 

We need to take all these state management and put it outside. Our editor should not have to keep a list of previous states, so it does not have coupled relationship with `EditorStates`. We need to introduce a new class called `HJistory` which will keep track of all these changes in the state for us.

```
 __________________ ____________________
| Editor | | EditorState |
|------------------| |--------------------|
| content: string | | content: string |
|------------------| | title: string |
| | |____________________|
| | ^
|__________________| | Composition
 |
 ________#_________
 | History |
 |------------------|
 | EditorSate: list |
 |------------------|
 | push(state) |
 | pop() |
 |__________________|
```

 

With this implementation we now see that our `editor` class would still have a relationship on the `EditorState` class. It is a dependency pattern now. We do not store the states but we would use the state to initialize our editor. 

```
 __________________ ____________________
| Editor | | EditorState |
|------------------| Dependency |--------------------|
|content: string |------------------------>|content: string |
|------------------| |title: string |
|createState() | |____________________|
|restore(state) | ^
|__________________| | Composition
 |
 ________#_________
 | History |
 |------------------|
 | EditorState: list|
 |------------------|
 | push(state) |
 | pop() |
 |__________________|
```

 

---
## Implementation

The editor state would be a purely data class which has no logical methods. We use the `final` keyword to make the class more robust so this class is immutable, and should only be destroyed after creation.

```java
public class EditorState {
 private final String content;
 
 public EditorState(String content) {
 this.content = content;
 }
 public String getContent() {
 return this.content;
 }
}
```

 

The editor class should only implement methods that it uses to restore and return a state object. It should not worry about keeping track of the states. It has an external dependency on the state objects. 

```java
public class Editor {
 private String content;
 
 public EditorState createState() {
 return new EditorState(this.content);
 }
 
 public void retore(EditorState state) {
 this.content = state.getContent();
 }
 
 public String getContent() {
 return content;
 }
 
 public void setContent(String content) {
 this.content = content;
 }
}
```

 

The hisotry class would internally use a stacks data structure which is built ideally for this scenario. [[DSA - 3 Stacks|About stacks.]]
```java
public class History {
 private Stack<EditorState> states;
 
 public History() {
 this.states = new Stack<EditorState>();
 }
 
 public void pushState(EditorState state) {
 this.states.push(state);
 }
 public EditorState() {
 return this.states.pop();
 }
}
```

 

### Usage
All the pieces would come together in the main method where the history is an external object compare to the state and editor classes:

```java
public static void main(String[] args) {
 var editor = new Editor();
 var history = new History();
 
 editor.setContent("a");
 history.push(editor.createState());
 
 editor.setContent("b");
 history.push(editor.createState());
 
 editor.setContent("c");
 editor.restore(history.pop());
}
```

This may come as lengthy and boilerplate-ish. "*Why not just have the `setContent()` method automatically store a history*". Well there is one important lesson and consideration here. Having a bloated Editor class would be a nightmare to maintain, extend, and improve.

The trade off may be having more boilerplate. But the history class can be improved without affecting the editor class or the editor state class.

 

---
## Example 2 - Document

```java
public class Document {
 private String content;
 private String fontName;
 private int fontSize;
 
 public String getContent() {
 return content;
 }
 
 public void setContent(String content) {
 this.content = content;
 }
 
 public String getFontName() {
 return fontName;
 }
 
 public void setFontName(String fontName) {\
 this.fontName = fontName;
 }
 
 public int getFontSize() {
 return fontSize;
 }
 
 public void setFontSize(int fontSize) {
 this.fontSize = fontSize;
 }
 
 @Override
 public String toString() {
 return "Document{" +
 "content='" + content + '\'' +
 ", fontName='" + fontName + '\'' +
 ", fontSize=" + fontSize +
 '}';
 }
}
```

The class represents a document in a word processor like MS Word or Apply Pages, we have 3 attributes:

- content
- fontName
- fontSize

We should allow the user to undo the changes to any of these attributes. In the future, we may add additional attributes in this class and these attributes should also be undoable. 

Implement the undo feature using the momento pattern.

 

---
## Recap
What does the momento pattern try to solve?

The momento pattern tries to decouple 2 things. It decouples an object's state, and its history of states from the object itself.

This allows you to easily decouple your applications. Its current configurations and data can be packaged as a state object, and restore from it. A History class is introduced to manage the list of states.

> Java

## About Queues
Queues are opposite of stacks, they are implemented as a ***first in first out*** basis. They are used across many different applications such as printers, and web servers.

![](/assets/img/attachments/dsa/dsa%20queue.png)

It is exactly like a line of queue in the real world. People line up from the back, and is served at the front according to their turn.

 

### Queue Usages in applications
We use queue when programming requires a shared resource among many consumers, these consumers would form a queue and await for resource availability.

a few notable examples:
- Printer Jobs
- Operating system processes
- Web servers
- Live support systems (Live chat customer services)

 

### Common Queue operations
Similiar to stacks, the following common queue operations all run at `O(1)` ***constant time complexity***.

- `enqueue` adds an item to the queue
- `dequeue` removes an item from the queue
- `peek` returns the item in the queue without removing it
- `isEmpty` bool if queue is empty
- `isFull` bool if queue is full.

 

### Conventions in Java
The Java framework provides the queue interface that sets the guidelines of implementing a queue.

```java
public class Queue<E> implements Queue<E> {
 @Override 
 public boolean add(Object o) { 
 return false; 
 } 
 
 @Override 
 public boolean offer(Object o) { 
 return false; 
 } 
 
 @Override 
 public Object remove() { 
 return null; 
 } 
 
 @Override 
 public Object poll() { 
 return null; 
 } 
 
 @Override 
 public Object element() { 
 return null; 
 } 
 
 @Override 
 public Object peek() { 
 return null; 
 } 
 
 @Override 
 public int size() { 
 return 0; 
 } 
 
 @Override 
 public boolean isEmpty() { 
 return false; 
 } 
 
 @Override 
 public boolean contains(Object o) { 
 return false; 
 }
 //... and more
}
```

Here there are 2 note worthy differences in naming conventions:
- `add` & `remove` works the same as `enqueue` and `dequeue`
 
- `offer(E e)` attempts to `enqueue` an item to the queue, will not throw an exception if fails.
 
- `poll(E e)` attempts to `dequeue`, and returns null if the list is empty instead of throwing an exception.
 
- `element()` is an unsafe version of `peek()`, will throw an exception instead of returning null when queue is empty.

 

---
## Usecase: Reverse a queue

We can use a stack to reverse a queue. 
```cs
public static void reverse(Queue<int> queue) {
 var stack = new Stack<int>();
 while(queue.Count > 0) {
 stack.Push(queue.Dequeue());
 }
 
 while(stack.Count > 0) {
 queue.Enqueue(stack.Pop());
 }
}
```

 

---
## Implementations 


### A basic structural bone
A queue implementation using an array. 
```cs
public class Queue<T> {
 private T[] storage;
 private int lastEmptyIndex = 0;
 private int headIndex = 0;
 
 public Queue<T>(int size) {
 storage = new T[size];
 }
 
 public void enqueue(T item) {
 if (isFull()) 
 throw new Exception("Queue is full");
 
 this.storage[lastEmptyIndex++] = item;
 }
 
 public T dequeue() {
 if (isEmpty())
 throw new Exception("Queue is empty");
 
 return this.storage[headIndex++];
 }
 
 public bool isEmpty() {
 return this.lastEmptyIndex < 1;
 }
 
 public bool isFull() {
 return this.lastEmptyIndex >= this.storage.Length;
 }
}
```

However, there are a few limitations with this implementation. The head after dequeuing does not reset. Thus, we cannot add any more items once the rear index is maxed out.
```
On a fully loaded queue
[0] [1] [3] [4] [5]
 ^ ^
 head tail
 
Dequeue. The frame does not shift.
[0] [1] [3] [4] [5]
 ^ ^
 head tail
```

 

### Circular array solution
Let's look at the previous implementation issue and solve it.
```
On a fully loaded queue
[0] [1] [3] [4] [5]
 ^ ^
 head tail
 
Dequeue. 
[0] [1] [3] [4] [5]
 ^ ^
 head tail
 
Enqueue new item.
[0] [1] [3] [4] [5] ...
 ^ ^
 head tail. Out of bounds.
```

Because of the way we keep track of the tail, even when the queue is freed up, our tail will point in an incremental direction.

To solve this efficiently we should not try to resize the array, or perform a copy and frameshift. Instead we should make our tail pointer point back to origin.

```
Dequeue. 
[0] [1] [3] [4] [5]
 ^ ^
 head tail
 
Enqueue new item. 
[0] [1] [3] [4] [5]
 T H Here tail should point back to 0.
```

 

We use the modulus operator to have the head and tail index to always revert back to 0 when they go beyond the size of our array.

Here's the full implementation. 
```cs
public class Queue<T> {
 private int count = 0;
 private int headIndex = 0;
 private int tailIndex = 0;
 
 private T[] storage;
 private int size
 
 public Queue<T>(int size) {
 storage = new T[size];
 this.size = size;
 }
 
 public void enqueue(T item) {
 if (isFull()) 
 throw new Exception("Queue is full");
 
 
 this.storage[tailIndex] = item;
 
 tailIndex = (tailIndex + 1) % size;
 count++;
 }
 
 public T dequeue() {
 if (isEmpty())
 throw new Exception("Queue is empty");
 
 var item = this.storage[headIndex];
 headIndex = (headIndex + 1) % size;
 count--;
 
 return item;
 }
 
 public bool isEmpty() {
 return this.count < 1;
 }
 
 public bool isFull() {
 return this.count >= this.size;
 }
}
```

 

---
## Implementation - using stack

Stacks are exact polar opposites of Queues. Building a Queue using a stack requires reversing the stack order. 

This of course is not an efficient implementation, as everytime we dequeue, we need to reverse the stack order.

```cs
public class Queue<T> {
 private Stack<T> storage
 
 public Queue<T>(int size) {
 storage = new Stack<T>(5);
 }
 
 public void enqueue(T item) {
 storage.push(item);
 }
 
 public T dequeue() {
 var newStorage = new Stack<T>(5);
 
 while (!storage.isEmpty()) {
 newStorage.push(storage.pop())
 }
 var item = newStorage.pop();
 
 while(!newStorage.isEmpty()) {
 storage.push(newStorage.pop());
 }
 
 return item;
 }
}
```

 

---
## Priority Queues

In priority queues objects are process and sorted according to an arbitrary priority not, by its order of insertion

```java
PriorityQueue<Integer> queue = new PriorityQueue();
queue.add(5);
queue.add(1);
queue.add(3);
queue.add(2);

while (!queue.isEmpty()) {
 System.out.println(queue.remove());
}
```

When you add an item to the queue and process them...
```
>>>
1
2
3
4
5

Process finished with exit code 0
```

 

## Implementations
We will implement the Priority queue using an array. The items must be sorted via an ascending order.

The first problem of this implementation is how to shift the numbers in our Array
```
 insert(2)
 [1, 3, 5, 7]
Index: 0 1 2 3
```

If we try to insert the number 2 between 1 and 3. We need to shift 3, 5, and 7. However a tyical loop wont be so ideal as you can see.
```
[1, 3, 5, 7]
 ^
items[i + 1] = items[i]


[1, 3, 3, 7] ?? Doing so lost num 5.
 ^ 
items[i + 1] = items[i]
```

Instead, a common approach is to loop the array in reverse order:
```
[1, 3, 5, 7]
 ^
items[i + 1] = items[i]

[1, 3, 5, 7, 7]
 ^ 
items[i + 1] = items[i]


[1, 3, 5, 7, 7]
 ^ 
items[i + 1] = items[i]

[1, 3, 5, 5, 7]
 ^ 
items[i + 1] = items[i]
```

 

### Array based priority queue
We start by declaring a simple array with a predefined size. We will work on resizing later on.
```java
public class PriorityQueue {
 private int[] queue = new int[5];
 private int count = 0;
 
 public PriorityQueue() {
 
 }
 
 public void enqueue(int item){
 for (int i = count - 1; i >= 0; i--) {
 if (queue[i] > item)
 queue[i + 1] = queue[i];
 else {
 queue[i + 1] = item;
 count++;
 break;
 }
 }
 }
 
 @Override 
 public String toString() {
 return Arrays.toString(queue);
 }
}
```

We can continue and apply an array resizing block that expands the array when its full:
```java
public void enqueue(int item){
 if (count == queue.length) {
 var newQueue = int[count * 2];
 queue = newQueue;
 }
 
 for (int i = count - 1; i >= 0; i--) {
 if (queue[i] > item)
 queue[i + 1] = queue[i];
 else {
 queue[i + 1] = item;
 count++;
 break;
 }
 }
}
```

and a dequeue method that discards the largest item in the queue (from the back of the array):
```java
public int dequeue() {
 if (isEmpty()) {
 throw new IllegalStateException();
 }
 
 return items[--count];
}

public boolean isEmpty() {
 return (count == 0);
}
```

> Reference, Code with mosh

## About - The problem
Let's say we want to build a drawing application like photoshop. So we can have a canvas and a dashboard of tools. We can interact with the canvas and the behavior of the canvas changes depending on the tools that we have selected. 

This canvas object is listening on mouse events like mouse up and mouse down, and what it does is dependant on the selected tools.

We might see pattern like this in our code:
```java
public class State {
 
}

public class Canvas {
 private ToolType currentTool;
 public void mouseDown() {
 if (currentTool == ToolType.Selection)
 Console.WriteLine("Selection icon");
 else if (currentTool == ToolType.Brush)
 Console.WriteLine("Brush icon");
 else if (currentTool == ToolType.Eraser)
 Console.WriteLine("Eraser icon")
 }
 
 public void mouseUp() {
 if (currentTool == ToolType.Selection)
 Console.WriteLine("Draw dashed rectangle");
 else if (currentTool == ToolType.Brush)
 Console.WriteLine("Draw lines");
 else if (currentTool == ToolType.Eraser)
 Console.WriteLine("Erase something")
 }
 
 public ToolType getCurrentTool() {
 return this.currentTool;
 }
 
 public void setCurrentTool(ToolType tool) {
 this.currentTool = tool;
 }
}

public enum ToolType {
 Selection,
 Brush,
 Eraser
}
```

At first it might seem like an easy fix to just use a switch case statement. However the problem is deeper than that. This solution is not extensible, if you decided to add new tools in the future you'll have to change `mouseUp()` and `mouseDown()`. And in real world applications, we have to also listen to keyboard inputs as well. Which means we must also implement these behavior inside: `keyA_pressed()`, `keyX_pressed()` -- very unextensible.

 

---
## Solution

![](/assets/img/attachments/dp/dp%20state%20pattern%20uml.png)

Now, let's think a bit deeper. The canvas's methods implementation changes depending on the selected tool. There are 4 pillars of object oriented programming:
- Encapsulation
- Abstraction
- Inheritance
- Polymorphism

In our case it is obvious that we need a solution that uses polymorphism!

```java
public abstract class UIControl {
 public void enable() {
 Console.WriteLine("Enabled");
 }
 
 public abstract void draw();
}
```

So an implementation of the UIControl class:
```java
public class TextBox extends UIControl {
 public override void draw() {
 Console.WriteLine("Drawing a textbox");
 }
}
```

and in the main method:
```java
public class Main {
 
 public static void main(String args[]) {
 drawUIControl(new TextBox());
 }
 private static void drawUIControl(UIControl control) {
 control.draw();
 }
}
```

 

### UML
Essentially we would have this pattern in UML:
```

 ______ __________________
| Main | Dependency Injection | UIControl |
|------|------------------------->|------------------|
| | | draw() |
|______| |__________________|
 ^
 |
 Inheritance |
 ___________________________
 _____|_______ ________|______
 | TextBox | | CheckBox |
 |-------------| |---------------|
 | | | |
 |-------------| |---------------|
 | draw() | | draw() |
 |_____________| |_______________|
```

 

---
## Implementation

We need an abstract class to represent the different type of tools
```java
public abstract class Tool {
 public abstract void mouseDown();
 public abstract void mouseUp();
}
```

And then our tools that implement this abstract class:
```java
public class BrushTool extends Tool {
 @Override
 public void mouseDown() {
 System.out.println("Brush icon");
 }
 
 @Override
 public void mouseUp() {
 System.out.println("Draw a line");
 }
}


public class SelectionTool extends Tool {
 @Override
 public void mouseDown() {
 System.out.println("Selection icon");
 }
 
 @Override
 public void mouseUp() {
 System.out.println("Draw a dashed rectangle");
 }
}


public class EraserTool extends Tool {
 @Override
 public void mouseDown() {
 System.out.println("Eraser icon");
 }
 
 @Override
 public void mouseUp() {
 System.out.println("Erase something");
 }
}
```

 

So we can use this inside the Canvas:
```java
public class Canvas {
 private Tool currentTool;
 
 public void mouseDown() {
 currentTool.mouseDown();
 }
 
 public void mouseUp() {
 currentTool.mouseUp();
 }
 
 public Tool getCurrentTool() {
 return this.currentTool;
 }
 
 public void setCurrentTool(Tool tool) {
 this.currentTool = tool;
 }
}
```

and in the main class where it all fits together:
```java
public class Main {
 public static void main(String[] args) {
 var canvas = new Canvas();
 canvas.setCurrentTool(new BrushTool()); 
 canvas.mouseDown();
 canvas.mouseUp();
 }
}
```

 

---
## Design smells -- Abusing patterns
Design patterns are great, they help us build extensible and reusable objects. Here's an example:

> John refactors some of the existing codebase to apply new patterns. Every pattern has a context it is designed to solve specific patterns. Blindly applying patterns to a code base introduces design smells.
> 
> It creates an overly complicated design. Keep things simplky and pragmatic. Dont overly use patterns. 

 

## State pattern abuse
Let's take this simple stopwatch example here. The stopwatch behavior changes depending on its current state. If it is running then it stops, if it is stopped, then it runs.

```java
public class Stopwatch {
 private boolean isRunning;
 
 public void click() {
 if (isRunning) {
 isRunning = false;
 System.out.println("Stopped");
 }
 else {
 isRunning = true;
 System.out.println("Running");
 }
 }
}
```

 

Here's an example of implementing this stopwatch with a state pattern abuse. We declare the interface / abstract class that represents the state of the stopwatch. 

```java
public interface State {
 void click();
}

public class RunningState implements State{
 public void click() {
 System.out.println("Stopped");
 }
}

public class StoppedState implements State {
 public void click() {
 System.out.println("Runnning");
 }
}
```

But we are unable to change the state of the stopwatch in this design. To be able to access the stop watch state, we must add a constructor that hold a reference to the stopwatch, and pass the reference around:
```java
public class RunningState implements State{
 private Stopwatch stopwatch;
 
 public RunningState(Stopwatch stopwatch) {
 this.stopwatch = stopwach
 }
 @Override
 public void click() {
 stopwatch.setCurrentState(new StoppedState(this.stopwatch));
 System.out.println("Stopped");
 }
}

public class StoppedState implements State{
 private Stopwatch stopwatch;
 
 public RunningState(Stopwatch stopwatch) {
 this.stopwatch = stopwach
 }
 @Override
 public void click() {
 stopwatch.setCurrentState(new RunningState(this.stopwatch));
 System.out.println("Running");
 }
}
```


Then in the stopwatch class, it has become less bloated. But at the great expense of increased moving parts with interfaces and 2 new implementation classes. 
```java
public class Stopwatch {
 private State state = new StoppedState(this);
 
 public void click() {
 state.click();
 }
 
 public State getState() {
 return this.state;
 }
 
 public void setState(State state) {
 this.state = state;
 }
}
```

 

---
## Dont abuse design patterns

You can see how much complexity has been added to the stopwatch, compared to a simple if else that we did prior. This is counter productive. 

The state pattern is used in cases when extensibility is required where a class may have many states, and multiple method's implementation that changes depending on the state. The stopwatch only ever have 2 states, start and stop. There is no need for such complexity.

Keep in mind when using state pattern. Does the class requires multiple states, are there a lot of methods that the class implements that differs due to its states?

## About
Let's say we want to build a web browser. Every brower has the concept of history where we can visit previous websites using the back button. The problem is very similar to the momento pattern.

```java
public class BrowseHistory {
 private List<String> urls = new ArrayList<>();
 
 public void push(String url) {
 urls.add(url);
 }
 
 public String pop() {
 var lastIndex = url.size() - 1;
 var lastURL = urls.get(lastIndex);
 url.remove(lasIndex);
 
 return lastURL;
 }
}
```

Then in the main:
```java
public void main(Sting[] args) {
 
 var history = new BrowseHistory();
 history.push("website1");
 history.push("website2"); 
 history.push("website3");
}
```

 

### The problem
Let's say we want to iterate over the entire history, and print the url we have visited. Currently the `List<String> url` is set to private.

If we were to expose this as a method for acess by creating a getter:
```java
 ...
 private List<String> urls = new ArrayList<>();
 
 public List<String> getUrls() {
 return this.urls;
 }
 ...
```

Then in main:
```java
public void main(Sting[] args) {
 
 var history = new BrowseHistory();
 history.push("website1");
 history.push("website2"); 
 history.push("website3");
 
 for (var i = 0; i < history.getUrls().size(); i++) {
 System.out.println(history.getUrls()[i]);
 }
}
```

 

However, we have a problem. If we were to change the implementation of our `urls` to some other data structure like a stack or linked list, our main method will break.

```java
 ...
 private String[] urls = new String[10];
 
 // Broken change
 public List<String> getUrls() {
 return this.urls;
 }
 ...

// inside main, broken change, String[] does not have size() and get()
for (var i = 0; i < history.getUrls().size(); i++) {
 System.out.println(history.getUrls().get(i));
 }
```

This is a bad practice for larger applications. Everytime we make a change to the implementation of our class, we introduce breaking changes in other places.

 

---
## Design Pattern - Solution

> We should always encapsulate implementation details inside our class, and dont allow implementation changes to affect public interfaces. 

 

### The naive
We need to introducing iteration friendly methods: `current()`, `hasNext()`, and `next()`

```
 _______________
| BrowseHistory |
|---------------|
| push(url) |
| pop() |
| next() |
| current() |
| hasNext() |
|_______________|
```

So we can write iteration code such as the following:
```java
while (history.hasNext()) {
 var current = history.current();
 // Do soemthing with current
 
 history.next()
}
```

 

### The Expert
However, this implementation breaks the single responsibility principle. The BrowserHistory class is doing too much, it is managing the history and also iterating. We need to split it into 2 classes:

```
 _______________ ___________
| BrowseHistory | | Iterator |
|---------------| |-----------| 
| push(url) | | next() |
| pop() | | current() |
|_______________| | hasNext() |
 |___________|
```

If the `BrowseHistory` class decides to use a new datastructrure internally, then different types of iterator will be required and will need to be derrived. So an iterator should be an interface.

```
 INTERFACE
 __________________ ___________
| BrowseHistory | | Iterator |
|------------------| |-----------| 
| push(url) | Dependency | next() |
| pop() |--------------------->| current() |
| createIterator() | | hasNext() |
|__________________| |___________|
 ^
 |
 ____________________
 | |
 _______|______ ______|________
 | ListIterator | | ArrayIterator |
 |--------------| |---------------|
 |______________| |_______________|
```

We introduce a `createInterator()` method which returns an `Iterator` object, so the **clients** of the `BrowseHistory` class will have no connections to the concrete implementations of the Iterator interface. 

If we change the data structure of `BrowseHistory`, we can simply change the implementation that the `createIterator()` method returns.

```java
// Option1: Returns an ArrayIterator
public Iterator createIterator(){
 
 ...
 return arrayIterator;
}
```

```java
// Option2: Returns a ListIterator
public Iterator createIterator() {
 
 ...
 return listIterator;
}
```

This does not break the main method.

 

---
# Implemetation
We can create a generic interface, and an implementation of this class: 


```java
public interface Iterator<T> {
 public void next();
 public T current();
 public boolean hasNext();
}
```

Then we implement a generic implementation of a ListIterator
```java
public class ListIterator<T> implements Iterator {
 
 private List<T> data;
 
 private int currentIndex;
 
 public ListIterator<T>(List<T> list) {
 this.data = list;
 this.currentIndex = 0;
 }
 
 public void next() {
 currentIndex += 1;
 }
 public T current() {
 return this.data.get(this.currentIndex);
 }
 public boolean hasNext() {
 return (currentIndex < data.size());
 }
}
```

Then we can use them in the BrowserHistory class. 
```java
public class BrowserHistory {
 private List<String> urls = new List<String>();
 
 public void push(String url) {
 urls.add(url);
 }
 
 public String pop() {
 var item = urls.get(urls.size() - 1);
 urls.remove(urls.size() -1);
 
 return item;
 }
 
 public Iterator createIterator() {
 return new ListIterator<String>(this.urls);
 }
}
```

In the main method, we are simply programming towards the iterator interface. 
```java
public void main(Sting[] args) {
 
 var history = new BrowseHistory();
 history.push("website1");
 history.push("website2"); 
 history.push("website3");
 
 Iterator iterator = history.createIterator();
 while (iterator.hasNext()) {
 var url = iterator.current();
 System.out.println(url);
 iterator.next();
 }
}
```

 

> **Exercise**\
> Try changing the implementation detail of the `BrowseHistory` class by changing the ulrs list into a fixed size array.
> You will see this does not introduce a breaking change inside the main method.
{: .prompt-tip}

 

---
## Recap
What does the Iterator Pattern try to solve?

The Iterator patterns allows a data structure class to better encapsulate its internal iteration mechanism without introducing breaking changes to its clients. This is done by introducing an `Iterator` interface

In order to connect to a web service and get resful api responses we need to use the **Retrofit** library.

Making API requests using retrofit requires a little more verbose configurations compared to a typical pythonic way. The retrofit library only handles the complexity of making requests, lower level networkings etc. Not the data convertion

We need to convert a Java object into JSON and vice versal when communicating with a HTTP server, to do that we use the ***GSON library.***


### Requirements

- Retrofit
- [gson](https://github.com/google/gson)


### Dependencies
You need to add the dependencies into your gradle build files and configurations.
```gradle
dependencies {
 implementation 'com.google.code.gson:gson:2.8.9'
 implementation 'com.squareup.retrofit2:retrofit:2.9.0'
 implementation 'com.squareup.retrofit2:converter-gson:2.9.0'
}
```

### Permissions
You will of course need to handle the permission requests inside your application's `onCreate()` method.

```
<uses-permission android:name="android.permisson.INTERNET">
```

 

---
## Using Retrofit

There are 3 components you need to facilitate an effective communication:
- Retrofit Instance
- Interface
- Model class

The retrofit instance works as a singleton. Meaning we only use *1 instance of retrofit per Endpoint* throughout the entire lifecycle of our application.

To send a GET requests to a HTTP server, we need to define 2 important components:
- The request `interface`
- The response `model` class

The request interface represents our API method calls and it's query parameters, while the model class would "model" the expected response data.

 

### Model Class
You have to know before hand, the exact type and format of the JSON response you expected to receive from the API. Here's an example scenario:

Expected JSON payload response:
```json
{
 "user_name": "John",
 "user_id": 1,
 "user_friends": [2, 3, 4]
}
```

So your model class would look like:
```java
public class Example {
 private String user_name;
 
 private Integer user_id;
 
 private Integer[] user_friends;
}
```

 

However, we all know how some JSON formats are a lot more complicated than this, nested lists and objects within lists. Here's where online tools such as jsonpojo comes in handy. 

Use them [here](https://www.jsonschema2pojo.org/). Set output to java class and your expected data response in ***GSON*** annotation.

 

---

## GSON
GSON is a google library that will perform the Java objects to JSON representation conversion. As much as we could say all we needed to do was parse a string. Gson handles that mess for us and provides a handy `toJson()` and `fromJson()` methods.

Using JSONpojo, we get the following Gson representation of our class:

```java
import java.util.List; 
import javax.annotation.Generated; 
import com.google.gson.annotations.Expose; 
import com.google.gson.annotations.SerializedName; 
 
@Generated("jsonschema2pojo") 
public class Example { 
 
 @SerializedName("user_name") 
 @Expose 
 private String userName;

 @SerializedName("user_id") 
 @Expose 
 private Integer userId; 
 
 @SerializedName("user_friends") 
 @Expose 
 private List<Integer> userFriends; 
 
 public String getUserName() { 
 return userName; 
 } 
 
 public void setUserName(String userName) { 
 this.userName = userName; 
 } 
 
 public Integer getUserId() { 
 return userId; 
 } 
 
 public void setUserId(Integer userId) { 
 this.userId = userId; 
 } 
 
 public List<Integer> getUserFriends() { 
 return userFriends; 
 } 
 
 public void setUserFriends(List<Integer> userFriends) { 
 this.userFriends = userFriends; 
 } 
}
```

 

Point your attention to these annotations:
```java
@SerializedName("user_id")
@Expose
private Integer userId;
```

`@SerializedName()` annotates the parser to parse this field's values into json with key set to "user_id".

`@Expose` This annotation is optional. We can see them in the wild as either `@Exposed(serialize = false)` or `@Exposed`. When given the `serialize = false` parameter, this field will be ignored by the parser. 

 

---
## The interface
The Retrofit interface is what we will use to perform the GET, POST API requests. We often name it with a *service* suffix. 

Each method within this service interface can be used to represent an API endpoint path from a baseURL.

 

### GET Requests
Let's say this is our url endpoint: `http://myendpoint/user`. We will only use the specific API endpoint for the interface (`user`), the base URL `http://myendpoint/` will be declared in the `Retrofit` instance.

So first we must create an interface to represent the request params
```java
import retrofit2.http.GET;


public interface GetUserDataService {

 @GET("user")
 Call<Example> getUser();
}
```

`Call<T>` class from retrofit represents the HTTP request object. The `T` generic here represents the expected response body. 

`@GET` annotation indicates that this request is a GET request, and the `"user"` part is the endpoint.

The requests payload is modelled as part of the interface's params. Here's another example:
```java
import retrofit2.http.GET;


public interface GetDataService {

 @GET("user")
 Call<ResponseBody> getEnedisData( 
 @Query("year") String year, 
 @Query("month") String month, 
 @Query("line") String line, 
 @Query("plot_type") String plotType, 
 @Query("unit") String unit 
 );
}
```

 

### POST Requests
On a `POST` request, The JSON payload will be sent as part of the `@Body` params instead. A template model class must be crafted. 

```java
import retorfit2.http.POST;

public interface ApiService {

 @POST("/api/enedis")
 Call<ResponseBody> postEnedisData(@Body EnedisRequest request);
}
```

The model request body class will be parsed and converted also via `GSON` into a JSON payload. So `GSON` synthaxes do apply :
```java
import com.google.gson.annotations.SerializedName; 


public class EnedisRequest { 
 @SerializedName("year")
 private String year; 
 
 @SerializedName("month")
 private String month; 
 
 @SerializedName("line")
 private String line; 
 
 @SerializedName("plot_type")
 private String plotType; 
 
 @SerializedName("unit")
 private String unit; 
 
 // getters and setters...
}
```

As we can see, if an API endpoint expects a JSON payload, then we must prepare a model class. It gets more complicated when we have nested JSON parameters such as a list of elements or another object. These expectations must be met with a request/response model class equivalent.
```json
{
 "user_id": "123",
 "friends": ["John", "Link"]
}
```

 

> **Notice naming convention**\
> In the interface the methods should be named as `postData` or `getData` according to the API requests of type `POST` or `GET`
{: .prompt-info}

 

### Requests with variable paths
Let's assume the following API endpoint. This endpoint has a variable path, `id_number`
```python
# sending an SDP offer to a number 
@app.post("offers/{id_number}") 
def post_offers(id_number, sdp_document: SDPDocument):
 _offers[id_number] = sdp_document 
 return {"status": "complete"}
```

We can just as easily create a request towards this endpoint in our retrofit interface:
```java
public interface SendOfferService {
 @POST("offers/{id_number}")
 Call<Response> sendSDPOffer(@Path("id_number") String idNumber, @Body SDPDocument sdpDocument);
}
```

`{id_number}` is a placeholder for the actual ID number variable path

`@Path("id_number")` annotation binds the `idNumber` method params to the `{id_number}` placeholder in the URL.

 

---
## Retrofit Instance
Fundamentally, to prepare the Retrofit intance for sending an API request, requires 2 build steps: 
- the retrofit intance
- the service instance

Create a `Retrofit` instance to represent the API base endpoint. 
```java
Retrofit retrofit = new Retrofit.Builder()
 .baseUrl("https://myendpoint/")
 .addConverterFactory(GsonConverterFactory.create())
 .build();
```

Create an Instance of the API service:
```java
ApiService apiService = retrofit.create(ApiService.class);
```

 

Since only **1 instance** of` RetrofitService` is needed per base endpoint, a `RetrofitService` singleton class can be made as follows:
```java
public class RetrofitInstance {
 private static Retrofit retrofit = null;
 private static String BASE_URL = "https://myendpoint/";
 
 // constructors etc..

 public static APIService createService() {
 if (retrofit == null) {
 retrofit = new Retrofit
 .Builder()
 .baseUrl(BASE_URL)
 .addConverterFactory(GsonConverterFactory.create())
 .build();
 }
 return retrofit.create(ApiService.class)
 }
}
```
However, there are intances where a lifecycle bound singleton isnt desired. Such as allowing changes to the baseURL in the app settings. 
***Rebuilidng a new instance is preferable when the baseURL is adjustable.***

 

### Making a request
We prepare the request body. This **does not start an Async request or action**, its just a request body.
```java
APIService service = RetrofitInstance.createService();
Call<ResponseBody> call = service.getEnedisData(
 "2023", 
 "November", 
 "someLine", 
 "bar", 
 "kWh"
);
```
Where, `ResponseBody` represents the model data of the API response.


The actual request made is `async`, with an `enqueue` call. 
```java
// Async non-blocking
call.enqueue(new Callback<ResponseBody>() {
 @Override
 public void onResponse(Call<ResponseBody> call, Response<ResponseBody> response) {
 
 if (response.body() != null) {
 ResponseBody responseBody = response.body();
 // Do things with responseBody model class
 }
 }
 
 @Override
 public void onFailure(Call<ResponseBody> call, Throwable t) {
 // Handle the failure
 }
});
```

`null` checks are neccessay or the application will crash, as API requests dont trigger an `onFailure` when something with the server goes wrong.

Alternatively, a synchronous operation is as follows:
```java
try { 
 Response<CaptionModel> response = call.execute(); // Blocking operation
 if (response.isSuccessful() && response.body() != null) 
 return response.body().caption; 
 else 
 Log.i("ImageAnalysis", "API Error, please check server"); 
 
} catch (IOException e) { 
 e.printStackTrace(); 
} 
return "API Error";
```

 

---
## Network Errors:


### Android 8: Cleartext HTTP traffic not permitted
> [Stack overflow](https://stackoverflow.com/questions/45940861/android-8-cleartext-http-traffic-not-permitted)

Starting with Android 9 (API level 28), cleartext support is disabled by default. This basically means you cannot send Restful API request via HTTP, it must be HTTPS. 

You can change your endpoint from: `http://mysite.com/api/` to `https://mysite.com/api/`. However if it does not work, you must configure network security to allow HTTP

Declare a network security configuration as follows:

Inside `res/xml/network_security_config.xml`
```xml
<?xml version="1.0" encoding="utf-8"?>
<network-security-config>
 
 <base-config cleartextTrafficPermitted="false"/>
</network-security-config> 
```

Then declare this file inside manifest:
```xml
.
.
.
<application
 android:networkSecurityConfig="@xml/network_security_config" >
 .
 .
 .
</application>
```

 

---
# References

https://howtoprogram.xyz/2017/02/17/how-to-post-with-retrofit-2/

https://square.github.io/retrofit/

## About
NGINX is a reverse proxy server which allows you to forward an application on localhost be able to be accessed by an external IP with added support for commonly needed protocols like http2 or SSL.

To put it simply, if you have a nextjs or python flask application on a virtual private server like google cloud or digital ocean and you launch your app. It is accessible on localhost, but when you go to your app IP address nothing happens. NGINX fixes that.

We can start by installing NGINX on linux server via:
```
sudo apt-get install nginx
```

Once installed. You should run your web applications on another screen before hand to test out nginx's configurations

 

---
## Configuration basics

Once installed, its time to configure the nginx settings. Go inside the settings file via nano:
```
sudo nano /etc/nginx/sites-available/default
```

You will see a full nginx configuration file with the following details:

```
# Author: Zameer Ansari
# You should look at the following URL's in order to grasp a solid understanding
# of Nginx configuration files in order to fully unleash the power of Nginx.
# http://wiki.nginx.org/Pitfalls
# http://wiki.nginx.org/QuickStart
# http://wiki.nginx.org/Configuration
#
# Generally, you will want to move this file somewhere, and start with a clean
# file but keep this around for reference. Or just disable in sites-enabled.
#
# Please see /usr/share/doc/nginx-doc/examples/ for more detailed examples.
##

# Default server configuration
#
server {
 listen 80 default_server;
 listen [::]:80 default_server;

 # SSL configuration
 #
 # listen 443 ssl default_server;
 # listen [::]:443 ssl default_server;
 #
 # Note: You should disable gzip for SSL traffic.
 # See: https://bugs.debian.org/773332
 #
 # Read up on ssl_ciphers to ensure a secure configuration.
 # See: https://bugs.debian.org/765782
 #
 # Self signed certs generated by the ssl-cert package
 # Don't use them in a production server!
 #
 # include snippets/snakeoil.conf;

 root /var/www/html;

 # Add index.php to the list if you are using PHP
 index index.html index.htm index.nginx-debian.html;

 server_name _;

 location / {
 # First attempt to serve request as file, then
 # as directory, then fall back to displaying a 404.
 try_files $uri $uri/ =404;
	 # proxy_pass http://localhost:8080;
 	# proxy_http_version 1.1;
	 # proxy_set_header Upgrade $http_upgrade;
 	# proxy_set_header Connection 'upgrade';
	 # proxy_set_header Host $host;
 	# proxy_cache_bypass $http_upgrade;
 }

 # pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000
 #
 #location ~ \.php$ {
 # include snippets/fastcgi-php.conf;
 #
 # # With php7.0-cgi alone:
 # fastcgi_pass 127.0.0.1:9000;
 # # With php7.0-fpm:
 # fastcgi_pass unix:/run/php/php7.0-fpm.sock;
 #}

 # deny access to .htaccess files, if Apache's document root
 # concurs with nginx's one
 #
 #location ~ /\.ht {
 # deny all;
 #}
}


# Virtual Host configuration for example.com
#
# You can move that to a different file under sites-available/ and symlink that
# to sites-enabled/ to enable it.
#
#server {
# listen 80;
# listen [::]:80;
#
# server_name example.com;
#
# root /var/www/example.com;
# index index.html;
#
# location / {
# try_files $uri $uri/ =404;
# }
#}
```

This configuration is what is displaying the default nginx welcome page. We are going to change the configurations to point to your application running on localhost instead.

Point your attention to the following block:
```
 location / {
 # First attempt to serve request as file, then
 # as directory, then fall back to displaying a 404.
 try_files $uri $uri/ =404;
	 # proxy_pass http://localhost:8080;
 	# proxy_http_version 1.1;
	 # proxy_set_header Upgrade $http_upgrade;
 	# proxy_set_header Connection 'upgrade';
	 # proxy_set_header Host $host;
 	# proxy_cache_bypass $http_upgrade;
 }
```

Here is where we configure our localhost application to the outside. We can do so by deleting everything here and replace with the following configurations:
```
 location / {
 include proxy_params; 
 proxy_pass http://localhost:5000/; 
 }
```
- `proxy_pass` should be the url for accessing your application.

That's it, save and exit nano.

 

### Getting changes into effect
First we need to run a synthax check to see if we did any mistakes in the configuration file:
```
sudo nginx -t
```

Running this command, a success message as the follwoing will appear:
```
nginx: the configuration file /etc/nginx/nginx.conf syntax is ok
nginx: configuration file /etc/nginx/nginx.conf test is successful
```

Once all is well, we can go ahead restart the nginx to get the settings into effect, then allow the firewall if enabled.
```
sudo systemctl restart nginx
sudo ufw allow 'Nginx Full'
```

That's it. Run your application on localhost and you should see the site on your external IP address.

 

---
## Start, Stop, and Restart Nginx with systemctl

> [manual](https://phoenixnap.com/kb/nginx-start-stop-restart)

About the restart command we did previously...

### Graceful restart (reload)
If you’re refreshing Nginx after changing the configuration, it’s best to gracefully reload the service. That shuts down old processes and restarts new ones with the new configuration.
```
sudo systemctl reload nginx
```

 

### Forceful restart
For major configuration changes, you can force a full restart of Nginx. This force-closes the whole service and sub-processes, and restarts the whole package.

```
sudo systemctl restart nginx
```

 

### Restart vs Reload Nginx
The **`reload`** command keeps the Nginx server running as it reloads updated configuration files. If Nginx notices a syntax error in any of the configuration files, the reload is aborted and the server keeps running based on old config files. **Reloading is safer than restarting Nginx.**

The **`restart`** command will shut down the server including all related services and power it on again. Restart Nginx only when making significant configuration updates, such as changing ports or interfaces. This command will force shut down all worker processes.

# About
Previously we have seen a rough predefined field of the default configuration file, and managed to launch our website. 

This time we will go over setting up some of the other commonly required services like HTTPS.

We can begin by completely deleting the entire contents of the default config site at:
```
sudo nano /etc/nginx/sites-available/default
```
Dont worry, we will learn how to write the configurations ourselfs.

 

## The minimally required block
You may copy the following code into the config file. Change the IP_ADDRESS to the server's external IP address. Do note its just the ip address. not `https://34.150.150.150/` or anything fancy. Once done, save, exit, and restart nginx.

```
server {
 listen 80; 
 server_name IP_ADDRESS;
 
 location / {
 include proxy_params; 
 proxy_pass http://localhost:5000/; 
 }
}
```

- `proxy_pass` here is where your application is running on localhost. Besure to change the port number!
- `listen` defines the port where users from the internet accesses your website. Nginx will forward requests from this port to the `proxy_pass` url
- `server_name` is where NGIX receives requests from. This should be the external ip address of your VPS or your domain name

Once you have restarted nginx you'll notice your site is still running without any issue. This is the minimally required configuration to run your site.

### About server_name
In the default configurations we saw they had used `server_name _;` instead. This is a wildcard declaration of saying "for every server_name I received..."

This will be useful later on when we filter for requests that used a DNS wildcard (`www.site.com` instead of `site.com`) or IP address. But for now, lets keep it using our IP address.

 

---
# Advanced connections


### Websockets
If your application uses websockets to push realtime changes on the webpage, using some of the following libraries:
- socketIO (python)

You will need to extend your configuration to include the following new parameters:
```
...
location / {
 include proxy_params;
 proxy_pass http://localhost:5000/;
 proxy_http_version 1.1;
 proxy_set_header Upgrade $http_upgrade;
 proxy_set_header Connection "upgrade";
 proxy_set_header Host $host;
}
```

 

## SSL (Https)
Our localhost applications will never use a HTTPS unless specified or created otherwise. Enabling HTTPS is often done within nginx configurations.

SSL requires the following components:
- domain name (not IP addresses).
- SSL Certificate 

Luckily we do not need to get the certificate and configure nginx ourself, and we can use certbot for this. [Reference](https://medium.com/@bjnandi/how-to-install-free-ssl-tls-certificate-on-nginx-web-server-in-ubuntu-22-04-lts-ef3d751de166), [2](https://certbot.eff.org/instructions?ws=nginx&os=debianbuster)


> **Dependency**\
> Certbot uses the snap command to install. Besure snap is installed. Get it from here:
> https://snapcraft.io/docs/installing-snap-on-debian
{: .prompt-info}

```
sudo apt-get remove certbot
sudo snap install --classic certbot
sudo ln -s /snap/bin/certbot /usr/bin/certbot
```


Then run the certbot to inject nginx configrations and get our ssl cert automatically:
```
sudo certbot --nginx -d yourdomain.com
```

To confirm that it is working, visit the `https` variant of your website.

 

## SSL(HTTPS) Manual setup
> [*Reference*](https://www.digicert.com/kb/csr-ssl-installation/nginx-openssl.htm)

An option to use SSL without domain name is to do a self signed certificate. Which will show a warning on chrome when a user visits your website.

You will need to configure Nignx SSL and generate your own SSL certificate using openSSL

### Step 1: Generate your 2 SSL files
SSL configuration comes in 2 files, note the file extensions
- `domain.name.pem` or `bundle.crt`
- `domain.name.key`

Here's how each file looks like:
```
-----BEGIN CERTIFICATE-----
MIIEnDCCA4SgAwIBAgIURFoO1AM2RclKdKmWouIlOYD5OfEwDQYJKoZIhvcNAQEL
BQAwgYsxCzAJBgNVBAYTAlVTMRkwFwYDVQQKExBDbG91ZEZsYXJlLCBJbmMuMTQw
MgYDVQQLEytDbG91ZEZsYXJlIE9yaWdpbiBTU0wgQ2VydGlmaWNhdGUgQXV0aG9y
aXR5MRYwFAYDVQQHEw1TYW4gRnJhbmNpc2NvMRMwEQYDVQQIEwpDYWxpZm9ybmlh
MB4XDTI0MDUyOTA4MTcwMFoXDTM5MDUyNjA4MTcwMFowYjEZMBcGA1UEChMQQ2xv
dWRGbGFyZSwgSW5jLjEdMBsGA1UECxMUQ2xvdWRGbGFyZSBPcmlnaW4gQ0ExJjAk
BgNVBAMTHUNsb3VkRmxhcmUgT3JpZ2luIENlcnRpZmljYXRlMIIBIjANBgkqhkiG
9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1F3Y/Ha5ilCwy0h5O4kjS4qYH7yrvMJ89TaQ
7WBXjdaTwf9g7kF3PCka/f/lA/LH4PldgCaTW992ww0suXd11xaC4UOuE1LyCX7W
pm2WdIgwy744cFjKYvq20HOQPfWd3imWn9k6Oxmkh4hkvT+QNJ4fOCbPN7hA+LMR
KU19n3dYsJ2JZN/z9FzgH4uejIufPBkqRccZQaTylCSI+p6pcGpa6JSc6CL5zyv8
vsJkXakvOGAqWDOgLY4UTlZBlP2b+v9j/DoMU6uXJp/ZG2fagQIDAQABo4IBHjCC
ARowDgYDVR0PAQH/BAQDAgWgMB0GA1UdJQQWMBQGCCsGAQUFBwMCBggrBgEFBQcD
ATAMBgNVHRMBAf8EAjAAMB0GA1UdDgQWBBSXxENWD+kbBP7S/+EQDvjOZWliEDAf
BgNVHSMEGDAWgBQk6FNXXXw0QIep65TbuuEWePwppDBABggrBgEFBQcBAQQ0MDIw
MAYIKwYBBQUHMAGGJGh0dHA6Ly9vY3NwLmNsb3VkZmxhcmUuY29tL29yaWdpbl9j
K6AphidodHRwOi8vY3JsLmNsb3VkZmxhcmUuY29tL29yaWdpbl9jYS5jcmwwDQYJ
KoZIhvcNAQELBQADggEBACwVfMjiIcrBpvDrCd9F25xoQh4C86Hb7bq4tZM5Pfx9
QNNyXVfYBt8rK5hb0gK1sbXuRWwLNqk41+CWLyvVEFNmeNirlVsOaWcRkWnWco0n
8lcIecjdWr2KYkP0LlmPFkAZ0AIpPMoKXrblk0lLGLr1D4nVCTs4x9IWgX91Jl1X
pRemeOuc56jjRVvd/B7Pvrrcl1tZuzd2OZuU4W8UgNjTKYdit+NC1y/fppjnAq3q
7DKBnUVcR0v+yySH/b0h2fFrFha1WC4TPRAyZlo4P61PuhnOApBaVXqipJ+RnKWe
Esg6kMEtJ9SkGzz5YuCK7I/290jKMSGxJSlyEOMBtmw=
-----END CERTIFICATE-----
```

```
-----BEGIN PRIVATE KEY-----
MIIEvQIBADANBgkqhkiG9w0BAQEFAASCBKcwggSjAgEAAoIBAQDUXdj8drmKULDL
SHk7iSNLipgfvKu8wnz1NpDtYFeN1pPB/2DuQXc8KRr9/+UD8sfg+V2AJpNb33bD
DSy5d3XXFoLhQ64TUvIJftambZZ0iDDLvjhwWMpi+rbQc5A99Z3eKZaf2To7GaSH
iGS9P5A0nh84Js83uED4sxHfT1lcaHejf1m+VD0HWhMBvPUfMH6mrCyik0jWI6VZ
JIj6nqlwalrolJzoIvnPK/y+wmRdqS84YCpYM6AtjhROVkGU/Zv6/2P8OgxTq5cm
n9kbZ9qBAgMBAAECggEAKjU61ra8Grb95HFTkxcnGjECGjC0C3C2SEBfnqZK0IiI
R9NXQVEMbI66/gQx83aZOVoXs06H6c4nar6bkxeKkEKrHsxr2/21gBiLIVCSiLBn
wwjcUlipKsmrKStMRUTNcpVKJ1Lr0+/JtSBLjsL7hUxWKEQz/WnA14XMTz5ZsVGk
zYHF/KDd0G/i7NT7CYTsyqRMDE84dFXUteT+Rb9cqrIvF4JgbHpkw2qlTEXyG4Ne
UKZgCHoVK9zWpop5Z+bMOEu3aVyNW8pBx0axP0JjBwKBgQD7BSlY8xvyvIGA8DRE
7tEvSonY1TWFVvk1mTOeLxE63J7hdTSY5zIdv6+EMlH3DizxGfEEf7Uapp/Rq9xE
7G21NUHZMiQgXpm2QL/iT16OZNVzom9LfV6/7Xkkwn83d+cDOzBPaM+y209rbrt4
xLByJhF2bN0Jg6t8iqaijhGOvwKBgQDYlGEAkFFjRfcajCADdepqP5ygxh9UnPBd
3g1TrziBTYnZx6LR7mjJXmm/1lglLgraEZjJcIj4yHPeWtgu8AAS2yircU0XBlso
IIj6TP+I8CXfqglfKGtEuXMSp0jbj6zt85ocEhEuixfS1isaXo+mURpj+Oyi5Tvo
sqoRJGImvwKBgD9JVtpZOKOjSRdD+Dmk6FJ+/XAQmRTMD7qmrG/mN/baJqh7D065
g1YivNKciTO7fDMxMiXLONLGTabkKH2sCiDUk4x56sfKcgCUJIyfLBzEaVhlDKBA
tIG5EoDlFIPck/6pjo2GxE64ojZYzaUuGbo9xMtRuQysCLE2l7qGDQErAoGBAITC
Z7e9v3YYFEHctV8Jr/kTJ0LST7BBR4JytD6hAQUZ769klaUT/H27dx1WGdAoqhRE
hyCr7/p4fbZGf5A+I/1rBEIbgMLlbYlqcCzmeBmMA9tX0sjW8PI+r5A2pQ2Zw8pU
8hnU5V1fe+oMyH0wi+PKgV/Y3c14sUGSC3fYkqXnAoGASjvjGodFUG5pexdt7ktw
WKfkb+YF8bdzeeOnjvwJDKrEvnWLnWSAE8t0UiN4n0d+BYb/BCKAK896Z5xQoDdR
Upw57vTbId5QGh1Kobv/v7P0iGm03zX65K9mrgS+VU+/07ZIQcBQlVd+fRf5/Qhx
y+hTSi8wniL5ukxu8up60o4=
-----END PRIVATE KEY-----

```


> **I did not get a `.pem`**\
> Some SSL generators will create bundle files instead of `.pem` this is normal as SSL certificates are consists of a primary and intermediate files (crt) you will have to concatonate them. Read more [here](https://www.digicert.com/kb/csr-ssl-installation/nginx-openssl.htm)
{: .prompt-info}

 

### Step 2: Add them to server
Next you will need to write these contents to your nginx server respectively:
```
sudo nano /etc/ssl/stone.com.pem
sudo nano /etc/ssl/stone.com.key
```

Make sure to use your own domain names!

 

### Step 3: Configure Nginx
Then within the configuration file:
```
sudo nano /etc/nginx/sites-available/default
```

we add the following directive to indicate SSL usage
```
server {
 listen 443 ssl;
 server_name stone.com;
 
 ssl_certificate "/etc/ssl/stone.com.pem";
 ssl_certificate_key "/etc/ssl/stone.com.key";
 
 location / {
 include proxy_params;
 proxy_pass http://localhost:3000/;
 proxy_http_version 1.1;
 proxy_set_header Upgrade $http_upgrade;
 proxy_set_header Connection "upgrade";
 proxy_set_header Host $host;
 }
}
```

That's it. Save, exit, test, and restart nginx. Your site can now be accessed via HTTPS
```
sudo nginx -t
sudo systemctl restart nginx
```


 

---
## Hiding IP Addresses and enforce domain name


### [SSL Security concerns](https://askubuntu.com/questions/1151042/only-allow-access-to-nginx-server-when-using-the-full-domain-name-and-not-the-ip)
When you have registered a domain name, you'll notice how you can still access your website directly via IP, circumventing the domain name. This is not good as it will allow attackers to bypass DNS security infrastructures like Cloudflares'

To address this gap, we must configure our nginx to only allow connections via domain name:
```
sudo nano /etc/nginx/sites-available/default
```

We need to define a default server block in which all connection attempts made via IP will be immediately rejected:
```
# The default always sits on top. 

# Normal http block
server {
 listen 80;
 server_name stone.com;
 location / {
 include proxy_params;
 proxy_pass http://localhost:3000/;
 proxy_http_version 1.1;
 proxy_set_header Upgrade $http_upgrade;
 proxy_set_header Connection "upgrade";
 proxy_set_header Host $host;
 }
}
# The normal SSL block
server {
 listen 443 ssl;
 server_name lwp.asia;
 
 ssl_certificate "/etc/ssl/stone.com.pem";
 ssl_certificate_key "/etc/ssl/stone.com.key";
 
 location / {
 include proxy_params;
 proxy_pass http://localhost:3000/;
 proxy_http_version 1.1;
 proxy_set_header Upgrade $http_upgrade;
 proxy_set_header Connection "upgrade";
 proxy_set_header Host $host;
 }
}

# Our catch all. This will reject all http connection via IP
server {
 listen 80 default_server;
 listen [::]:80 default_server;
 server_name "";
 return 444;
 # Or alternatively redirect to domain
 # return 301 http://stone.com$request_uri;
}
```

But wait, we can also access the website via direct IP using HTTPS! We need extend to our default block for direct HTTPS as well:
```
server {
 listen 80 default_server;
 listen [::]:80 default_server;
 listen 443 default_server;
 listen [::]:443 default_server;

 ssl_reject_handshake on;

 server_name "";
 return 444;
}
```
[*stackoverflow*](https://stackoverflow.com/questions/29104943/how-to-disable-direct-access-to-a-web-site-by-ip-address)

 

### [With Cloudflare, too many redirects](https://stackoverflow.com/questions/41583088/http-to-https-nginx-too-many-redirects)
Sometimes with cloudflare's DNS redirect requests we may encounter too many redirects error when we configure nginx to redirect http requests to https

```
# Normal http block
server {
 listen 80;
 server_name lwp.asia;
 return 301 https://$host$request_uri; 
}
```

The problem is caused by cloudflare always using http to connect to your origin server. To solve this you must configure on cloudflare side to use `strict SSL`, thus rendering your http nginx config not used at all.

## About
Most computers these days have multiple cores, which allows multiple instructions to be carried out simultaneously. Nowadays it is an essential skill to master, and untilize this advantage in parallel computing for performance. 

 

### Process and Thread
![](/assets/img/attachments/java/concurrency%20process%20and%20thread.png)

A **process** is an instance of an application or program. When you run a program, a copy of the program is loaded into a process, which contains some memory, instructions. Our operating system can run multiple processes that the same time. 

For example your antivirus software can run in the background, while you stream music on the browser. This is concurrency at the *process level*. 

![](/assets/img/attachments/java/concurrency%20process.png)

 

### Threads
We can also have concurrency within a process, which is called a thread. Each Process has at least 1 thread called the ***main*** thread. Utilizing multiple threads to run instructions simultaneously is called multithreading.

Applications that utilizes multipole threads are called multithreaded applications. 

We can see threading in action by these following:
```java
public static void main(String[] args) {
 // The number of active threads
 System.out.println(Thread.activeCount());
 
 // The number of maximum available threads
 System.out.println(Runtime.getRuntime().availableProcessors());
}
```

We usually get the following response. 
```
2
8

Process finished with exit copde 0
```

Any barebones stock java program will have 2 threads: The *main* thread and a *background* thread which handles garbage collection. The threads available are hardware dependant. A 4 core 8 thread CPU will have 8 threads. 

Nowadays CPUs usually have 6 cores, which makes 12 threads. To exploit parallel hardware we need to learn how to use threads:
- How to create and start new threads
- How to safely share data between threads

 

---
## Starting new threads

To create a new thread in java we need to create a thread object:
```java
public void main(String[] args) {
 Thread thread = new Thread(...);
}
```

A Thread object constructor is overloaded with additional arguements. 
```java
Thread(Runnable target);

Thread(@Nullable ThreadGroup group, Runnable target);

Thread(@NotNull String name);

Thread(@Nullable ThreadGroup group, @NotNull String name);

Thread(Runnable target, @NonNIs @NotNull String name);

Thread(@Nullable ThreadGroup group, Runnable target, @NotNull String name);

Thread(@Nullable ThreadGroup group, Runnable target, @NotNull String name, long stackSize);

Thread(@Nullable ThreadGroup group, Runnable target, @NotNull String name, long stackSize, boolean inheritThreadLocals);
```

 

## Runnable
The most commonly used constructor is `Runnable target` that implements the `Runnable` interface. It is a very simple interface with 1 method:
```java
public interface Runnable {
 void run();
}
```

Let's say we want to implement a concurrent method for downloading multiple files. We can declare a class that implements the `Runnable` interface.

```java
public class DownloadFileTask implements Runnable {
 @Override
 public void run() {
 // some implementation mechanics
 System.out.println("Downloading");
 }
}
```

 

## Using the new Runnable class:
Once we declare our runnable class, we can use them inside our main method:
```java
public void main(String[] args) {
 Thread thread = new Thread(new DownloadFileTask());
 thread.start();
}
```

We can say that `Runnable` objects are essentially single methods that can run on a separate thread. In some more complex design pattern use-cases, `Runnable` objects can be set to run on the main thread.

An equivalent to a `Runnable` is to think of them as a task object. A task can be done by any thread. It does not have a return value, so a task have to work on an object via reference.

On the lowest level, a thread is what's used to run a `Runnable` task. 

 

> **Thread lifecycle**\
> Threads closes or dies automatically when they finish a task. We do not need to explicitly close them.
{: .prompt-info}

 

---
## Useful methods for threads

### Common Debug methods:
The thread class provides useful static methods that allows us to debug and diagnose threads: 
```java
// Receives the current thread reference
var thread = Thread.currentThread();

// name of current thread.
thread.getName();
```

Together we can see the different threads being activated:
```java
public class DownloadFileTask implements Runnable {
 @Override
 public void run() {
 // some implementation mechanics
 System.out.println("Downloading " + Thread.currentThread().getName());
 }
}

...
// Inside a main method:
public void main(String[] args) {
 System.out.println("Main " + Thread.currentThread().getName());
 Thread thread = new Thread(new DownloadFileTask);
 thread.start();
}
```

We get the following output:
```
Main main
Downloading Thread-0

Process finished with exit code 0
```

 

## Pausing a thread
Threads allow us to pause an execution to stimulate certain situations that requires wait time such as downloading a file or querying a database.

```java
public class DownloadFileTask implements Runnable {
 @Override
 public void run() {
 // some implementation mechanics
 System.out.println("Downloading");
 
 // Pausing a thread (5000 mili-seconds)
 Thread.sleep(5000);
 
 System.out.println("Download complete");
 }
}
```

However, having a raw `Thread.sleep()` makes the compiler unhappy as this is an `Unhandled exception: java.lang.InterruptedException`. So we must always surround a thread sleep with a try catch block:

```java
...
try {
 Thread.sleep(5000);
} catch (InterruptedException e){
 e.printStackTrace();
}
```

 

---
## Thread scheduler

> What happens if I download 100 files concurrently? My machine only has 4 cores, 8 threads how's that gonna work?


The java virtual machine has something called the **Thread Scheduler**. The thread scheduler decides what threads to run and how long. If we have more tasks than the available hardware threads, the scheduler switches between tasks giving them each a slice of the CPU time.

This switching happens very fast giving the illusion of multiple tasks being handled simultaneously. This is parallelism at the software level.

 

---
## Joining a thread
Joining a thread can be said as running a task after a task, back to back. This is required in situations where 1 task needs to be finished before the next can proceed.

We do this by calling the `join()` method on a thread instance. However, doing this inside the main thread will cause it to wait for our download thread to finish. This makes the application unresponsive.
```java
public void main(String[] args) {
 Thread thread = new Thread(new DownloadFileTask());
 thread.start();
 
 try {
 thread.join();
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 
 // Now the next thread can start
}
```


> **Note**\
> Its important to note that the join method is blocking method. Once our main method hits the join, execution will pause.
> 
> If you have multiple threads launched (from a loop), consider adding each thread into a list to keep their references for joining later on.
{: .prompt-tip}

 

---
## Interrupting a thread
Interrupting a thread means stopping a thread while it is running. The way thread interacting works is via event/call-backs. 


We make a thread stops by calling its instance `.interrupt()` method. 
```java
public class DownloadFileTask implements Runnable {
 @Override
 public void run() {
 // some implementation mechanics
 for (int i = 0; i < Integer.MAX_VALUE; i++)
 System.out.println("Downloading "+ (String) i );
 
 System.out.println("Download complete");
 }
}


public void main(String[] args) {
 Thread thread = new Thread(new DownloadFileTask());
 thread.start();
 
 try {
 Thread.sleep(1000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 
 thread.interrupt();
}
```

However, this does not work. Thread interruptions works on requests. We must handle by performing interruption checks. See below.

 

Furthermore, if a thread is asleep. Sending an `interrupt` request will throw an exception. Which is why we must always handle such occasions with the try catch block:
```java
public class DownloadFileTask implements Runnable {
 @Override
 public void run() {
 for (int i = 0; i < Integer.MAX_VALUE; i++)
 // Check if its being interrupted
 if (Thread.currentThread().isInterrupted())
 return;
 
 System.out.println("Downloading "+ (String) i );
 
 System.out.println("Download complete");
 }
}


public void main(String[] args) {
 Thread thread = new Thread(new DownloadFileTask());
 thread.start();
 
 try {
 Thread.sleep(1000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 
 thread.interrupt();
}
```

> Sebastian Lague, [Essential math](https://www.youtube.com/watch?v=DPfxjQ6sqrc), [Godot Vectors](https://docs.godotengine.org/en/4.2/tutorials/math/vector_math.html)
> Complied by zenovak

## Understanding Vectors

In games, we often use Vectors to represent coordinates instead of Carstesians. These are not quite the same, although they are used interchangeably:

A vector is a value with magnitude(distance) and direction in space. It does not specify an origin. A (4. 5) vector can mean anything on a grid. It is a relative measurement, as depicted below. 

![](/assets/img/attachments/gamedev/vector1.png)

When we work in 3D space, we use Vector3, and Vector2 in 2D space:
```
Vector3 = new Vector3(x, y, z);
Vector2 = new Vector2(x, y);
```

We can calculate the magnitude of the vector using pythogarams `a^2 = b^2 + c^2` for length:

![](/assets/img/attachments/gamedev/vectorsMagnitude.png)

To calculate the directions, we divide the x and y value by the magnitude 
`(-4, 3) / 5 = (-0.8, 0.6)`

To get the magnitude of this directional vector, we get 1.
``SquareRoot((-0.8)^2 + (0.6)^2) = 1``

 

### Vector Normalisation
To demostrate this significance, imagine we have a player that presses down the `W` and `A` keys to strave up and left and so we use an input vector of (-1; 1). ^ba50cd

Say we want to move this player 3 units in that direction, we do:
`(-1; 1) * 3 = (-3; 3)`

But if we now measure the magnitude:
![](/assets/img/attachments/gamedev/vectors2.png)
It is more than 3! The mistake we made has allowed player to move faster in the diagonal axis!!

 

To correct this mistake, we must first normalize the vector. We can think of a normalized vector as the circle of directions for our vector. The input vector that we have used previously clearly lies outside the circle.
![](/assets/img/attachments/gamedev/vectors3.png)

To normalize a vector we simple calculate its directions, which gives us `(-0.71; 0.71)` which lies inside the red circle. This is our normalized vector.

Move by 3 units: `(-0.71; 0.71) * 3 = (-2.13; 2.13)` 

The new vector's magnitude: `3.0122748878546926`
Speed is preserved!

 

---
## Practical use of vectors in games
Because vectors conveniently define X, Y (and Z value for Vector3). We use them to simply represents a point in space, like the cartesians. and thus the they are used interchangable. 

>However it is important to keep in mind of this mathematical fact that vectors simply represents magnitude and direction! 

 

### Subtract vectors == Direction & Distance offset
Let's Imagine this, we have a vector to represent the current position of the player object, and another vector to represent an enemy object. 
![](/assets/img/attachments/gamedev/vectors4.png)

 

If we were to subtract the position of the player and the enemy we would get a (-6, -2) vector. 
![](/assets/img/attachments/gamedev/vectors5.png)
This Vector is insignificant if we think of it as a position on the grid. But as a vector it represents the displacement of the player from the enemy position. Its magnitude is the distance between the 2, and if we normalize it, we get the direction!
```cs
var directionToTarget = (targetPosition - myPosition).Normalized();
```

 

### Add Vectors == new Force (Direction & Magnitude)
Let's take 2 vectors. `(0, 0)` and `(1, 0)`. Adding them together can represent a transformation of the vector. 

This is used when we want to move a point around. Instead of positions. Often in this case vectors are treated as direction and magnitude of transformation. Often seen in calculating `force` and `velocity`

Let's take these 2 Vector examples, and assume origin as being the object's centre *(Not game coordinate's centre)*

![](/assets/img/attachments/gamedev/vector%20addition.png)

If we were to treat them not as coordinates, rather as a velocity, with `u = (1, 1)` being its initial velocity. Adding `v = (1, 4)` would make a new velocity.

It represents a new magnitude and direction its going.

![](/assets/img/attachments/gamedev/vector%20addition2.png)

Re-arranging the vectors, you can see what I mean, 

![](/assets/img/attachments/gamedev/vector%20addition3.png)

 

### Vector multiply by factor == add magnitude
We have seen this previously, multiplying a vector with a single number represents adding a scale of magnitude to an existing vector. This is especially useful for normalized vector.

 

---
## Representation of Vectors in Unity

In unity Vectors are written as a struct:
```cs
public struct Vector3
{
	public float x;
	public float y;
	public float z;
	
	// Constructors and methods....
}
```
Reference: [[CS - 3 Non premitive types#Structs|About structs]]

 

In Unity Vectors come with useful methods so we dont have to write ourselves:
```cs
var myCarPos = new Vector3(3, 4, 5);

float speed = myCarPos.magnitude;
Vector3 direction = myCarPos.normalized;
```

 

**Operators**
```cs
// Vector * scalar:
(5, 10, 15) * 2 = (10, 20, 30)

// Vector / scalar:
(5, 10, 15) / 5 = (1, 2, 3)

// Vector + Vector:
(5, 10, 15) + (3, 4, 5) = (8, 14, 20)

// Vector - vector:
(5, 10, 15) - (3, 4, 5) = ( 2, 6, 10)
```

 

---
## Common Computational pitfalls with Squareroots
When calculating the distance between two points in a Cartesian coordinate system (such as a graph), the traditional method involves using the square root of the sum of the squared differences in coordinates. This is known as the Euclidean distance formula, which you might have encountered in school.

However, Square root calculation typically uses the newtonian method of approximation and can be computationally expensive.

 

### How is squareroot computed and why is it slow?
The *newtonian* method is an approximation of calculating a squareroot via iterations. You want to calculate the squaroot of a, and y is the squaroot, and x is a guessing estimate
```
y = x + a/x
 --------
 2
```

For example, 
```
a = 4
x = 3
y = (3 + 4/3) / 2
y = 2.166666667
```

The results get closer to the correct answer if we repeat the formula with x being the new estimate, `2.1666667`.
```
x = y
y = (2.166667 + 4/2.1666667) / 2
y = 2.00641

and repeat again
```

Effectively what we have is an algorithm like the following:
```cs
while (true) {
 y = (x + a/x) / 2;
 if y==x 
 break;
 x = y;
}
```

However, floating point equality is never exact nor accurate so our endcase must be a comparision with epsilon instead. Where epsilon is the absolute smallest value of a float, or 0.00001, basically determines how close is close enough.

```python
if abs(y-x) < epsilon:
 break
```

 

### Case 1 - Find the closest object
When we have many many many points that we need to calculate for e.g. physics simulations, or particle engine. Doing squareroots is not feasible, if we simply want to find the closest object. 
We must use a different method for calculating and comparing distances, called **distance squared checks**.

#### Distance squared checks
Instead of taking the square root, we compare the squared distances directly. In other words, you calculate the sum of the squared differences in coordinates but skip the final square root step. 

The limitation of this is that, we are not returning the actual distances value, it is a truncated algorithm, but it speeds thing up massively for distance checking. 

```cs
// Vector2 is float based.
float DistanceSquared(Vector2 a, Vector2 b){
	var dx = a.x - b.x;
	var dy = a.y - b.y;
	
	return dx**2 + dy**2;
}
```

 

### Case 2 - Normalized Vector (Unit Vector)
As we have seen previously to calculate a normalized vector, we need a distance component, Which is known to be computationally expensive.
```cs
var direction = (targetPosition - currentPosition) / distanceToTarget
```

However, calculating the unit vector doesn't necessarily require a separate square root operation, as the magnitude can be computed and used within the normalization process without extracting its square root explicitly.

![](/assets/img/attachments/gamedev/vectorsformula.png)

This is a common optimization technique when implementing vector normalization functions.

In many programming languages and libraries, vector normalization functions often take advantage of optimized routines and hardware instructions, making the process efficient even if a square root operation is involved. Additionally, some platforms provide intrinsics or functions that allow vectorized operations, further improving performance when dealing with multiple vectors simultaneously.

 

---
## Vectors, Angles, and Rotations

Let's assume another example a player and an enemy position. We know the direction of the enemy from the player via a normalized vector like `[[G3 - Vectors and Math#^ba50cd|previously]]`

![](/assets/img/attachments/gamedev/vector%20addition2.png)

We calculate the angle via tangant:

![](/assets/img/attachments/gamedev/vectorangles3.png)

Often in programming languages, `tan^-1()` functions are provided as `atan(y, x)` or `atan2(y, x)` with `atan2()` being safe for when x == 0;

 

### Radian representation of angles
In game engines, often angles are represented in Radian instead, which is a Pi float representation like:

```
radian = degrees / 180 * PI
```

![](/assets/img/attachments/gamedev/vectorradian.png)

Now, with a radian angle, we can just as easily get our normalized vector back via:
```
normalizedVector = (cos(angle), sin(angle))
```

![](/assets/img/attachments/gamedev/vectorradian2.png)

 

### How it represents rotation of game objects
In game engines, a rotation of our player character can just as easily be represented as a radian value of it, relative to the grid, or some other reference vector.

![](/assets/img/attachments/gamedev/vectorrotation.png)

 

#### In godot
An object's rotation is referenced with the X axis being the origin `(1, 0)`, with pi represented as float. The equivalent of getting `normalizedVector.Angle()`

![](/assets/img/attachments/gamedev/vectorrotation2.png)

 

---
## Computational pitfalls with trigonometry
Sin, Cos, tan are all computationally expensive math functions, just like squareroot, they require multiple CPU cycles to compute.

As we seen how vectors can be easily calculated. There are some common computational work arounds when dealing with radian maths using vectors instead.

 

### Vector dot product
Vector dot products allows us to think about angles in the domain of vectors. Let's assume 2 normalized vectors `v1, v2`:

![](/assets/img/attachments/gamedev/vectordotproduct.png)

Traditionally we can calculate this via inverse tangan, which are computationally expensive.

![](/assets/img/attachments/gamedev/vectordotproduct2.png)


Now, we know the angle between the 2 vectors wont change. We can simplify the calculations of the inverse tangent equation using dot products.
```
dotProduct = (V1x * V2x) + (V1y * V2y)
angle = inverseCos(dotProduct/ magnitude of V1)
```


Example, assume a vector `(1, 1)`, we can calculate its angle with dot product via the following steps, Where the second vector is a constant X-axis projection.
```
var dp = dotProduct((1, 1), (1, 0));
var angle = inverseCos(dp / magnitudeOf((1, 1)); 
// magnitude not needed if vector is normalized
```

![](/assets/img/attachments/gamedev/vectordotproduct3.png)

 

### Rotating a Vector2
https://www.youtube.com/watch?v=MOYiVLEnhrw



 

---
## Vector dot product usecases


### Direction similarity comparision with Normalized vectors
We use vector dot products on normalized vectors to identify their ***similarity in direction***.

Let's assume we have a constant vector direction, `u` being true to the x-axis, right side `(1, 0)`. We test this with different normalized vectors, aiming at different axial directions,
- `Vector2.Right`
- `Vector2.Up`
- `Vector2.Left`
- `Vector2.Down`

The dotproducts are as follows:
- 1
- 0
- -1
- 0

We can assume that facing a similiar direction will give a dotproduct closer to 1, while beyond 90 degrees, will go closer to -1. We can see this in action as:

![](/assets/img/attachments/gamedev/Pasted%20image%2020240116203308.png)

> **dotProduct under unit vector**\
> The demonstated dotProduct behavior only applies to unit vectors (Normalized Vectors). 
{: .prompt-warning}

 

In godot, Vector mathematics has convenient functions such as below to calculate a dot product of 2 vectors.
```cs
float c = a.Dot(b);
float d = b.Dot(a); // These are equivalent.
```

This is important when we compare the similarity of direction of vectors, when used for racing tracks etc.

![](/assets/img/attachments/gamedev/Pasted%20image%2020240116163634.png)

### isFacing? 
We can also check for facing or look-at usecases:
```cs
if (Vector2.DotProduct(player.Rotation, player.DirectionTo(enemy)) < 0)
 Console.WriteLine("You are facing away from enemy")
```
Where `player.Rotation` represents the player's rotation on the global coordinate system in normalized vector format, and `player.DirectionTo()` being a shorthand function to calculate the normalized vector direction on the global coordinate system from the `enemy`

 

Let's try another example. The green arrows `fA` and `fB` are **unit vectors** representing the zombie's facing direction and the blue semicircle represents its field of view. 

![](/assets/img/attachments/gamedev/Pasted%20image%2020240116203715.png)

If the angle between this vector and the facing vector is less than 90°, then the zombie can see the player.
``` cs
var AP = A.DirectionTo(P);
if (AP.Dot(fA) > 0) 
 GD.Print("A sees P!");
```

For zombie `A`, we find the direction vector `AP` pointing to the player using `(P - A).normalized()`, however, Godot has a helper method to do this called `DirectionTo()`. 

 

---
## Vector Normals (Orthogonals)
> [Godot vector math reference](https://docs.godotengine.org/en/stable/tutorials/math/vector_math.html)

A common use of unit vectors is to indicate **normals**. Normal vectors are unit vectors aligned perpendicularly to a surface, defining its direction. They are commonly used for lighting, collisions, and other operations involving surfaces. 

![](/assets/img/attachments/gamedev/vectornormals.png)
The surface normal has a value of `(0, -1)` because this is a horizontal surface.

Calculations for normals are computationally inexpensive as the formula to calculate the normals for a given vector is:
```cs
var normal = new Vector2(-vector.Y, vector.X);
```
The product would be a new vector pointing in the counter clockwise direction, 90 degrees.

In godot, a helper method exists `vector.Orthogonal()`

 

---
## Linear interpolation (Lerp)

Linear interpolation is used for calculating steps to reach a vector location. Say we want to travel from P1 to P2, in 10 seconds.

What are the vector segments can we break this journey down for every second, and what is the vector for when we hit 5 seconds?

![](/assets/img/attachments/gamedev/linearinterpolation.png)

The equation is as simple as:
```
N(time) = NStart + (NEnd - NStart) * time
```

 

### Usecase
Linear interpolation is used for creating approximations to unknown functions, such as particle simulations, smoke etc. Given a noise graph, calculate what is the value at Point X, which sits between known point A and B.

![](/assets/img/attachments/gamedev/lerp2.png)

 

Let's say we want to stimulate a player's movement path. Where `Velocity` is a vector2 and `time` is the time taken to render each physics frame, known as `delta time`
```
displacementTravelled = Velocity * time
```

We can see how we are now in familliar teritory.
![](/assets/img/attachments/gamedev/lerp3.png)

 


---

# Heading 1
## heading 2

### heading 3

#### heading 4

##### heading 5

###### heading 6


```
# Heading 1
## heading 2
### heading 3
#### heading 4
##### heading 5
###### heading 6
```

 

### Line

---

```
---
```

 

> Block quotes

```
> Block quotes
```

 

breakline
```
 
```

 

Warnings and special blocks

> [!NOTE] Title
> Contents


> [!INFO] Title
> Contents


> [!TIP] Title
> Contents


> [!WARNING] Title
> Contents

```
> [!NOTE] Title
> Contents

> [!INFO] Title
> Contents

> [!TIP] Title
> Contents

> [!WARNING] Title
> Contents
```


 

[Links](https://www.youtube.com)

Embeded links or pictures
![Picture](https://buffer.com/cdn-cgi/image/w=1000,fit=contain,q=90,f=auto/library/content/images/size/w1200/2023/09/instagram-image-size.jpg)

```
[Links](https://www.youtube.com)

![Picture](https://buffer.com/cdn-cgi/image/w=1000,fit=contain,q=90,f=auto/library/content/images/size/w1200/2023/09/instagram-image-size.jpg)
```

 

Linking notes & embedding linked notes
```
[[markdown cheat sheet]]
![[markdown cheat sheet]]
```


 

Inline `code`

```
code blocsk
```

Synthax highlighting code block
```cs
public static void hello() {
 Console.WriteLine("Hello world");
}
```


```
Inline `code`

code block (remove the >)
> ```
> code block
> ```

synthax highlighting block (remove the >)
> ```cs
public static void hello() {
 Console.WriteLine("Hello world");
}
> ```


```

## About Stacks
A stack data struture is a fundamental structure. It is the same as a List or array. Single dimension. Stacks are used to implement the `undo` feature. It is used in more complex code such as building compilers (e.g. synthax checking) and evaluating expressions.

![](/assets/img/attachments/dsa/dsa%20stacks.png)

The best way to think of stacks to visualize its structure, is stacks are like a stack of books. You can only remove the top book. To get to the bottom you have to remove all books. This is also called the *Last in first out* (LIFO) principle. This is why we can use stacks to implement undo features.

Internally we use an array or linkedlist to store the items in a stack, so \a stack is just a wrapper around an array or a linked list that gives us a different way of manipulating and accessing the data.

 

For demonstration. Stacks are implemented with a few core features as below. It's important to notice that stacks do not implement lookups. That is not what stacks are used for.
```cs
public class Stack<T>{
	
	private T[] _stackData; 
	public void push(T t){
 	// insert an item to the top of the stack. 
	}
	
	public T pop(){
		// remove the top item and return it
	}
 
 public T peek() {
 // returns the top item in the stack without removing it.
 }
	
	public bool isEmpty(){
	}
	
	public bool isFull(){
	}
}
```


> **Included in .NET**\
> Stacks are already included in .Net framework so we dont have to implement ourselves. Although it is important to learn how one is implemented.
{: .prompt-tip}

 

---
## Specs
All operations in a stack are constant time `O(1)`. This is because adding and removing an item at an edge of a stack or array is always a `O(1)` operation. So is peeking and isEmpty checks.

 

---
## Implementing a stack with Linked list

### The same basic internal structure
Notice how stacks store their data internally as array as well. In this implementation, we will use a half-implemented linked list instead:

```cs
public class Stack<T> {
 public Node head;
 
 public void push(T data) {
 var newNode = new Node<T>(data, head);
 head = newNode;
 }
 
 public T pop() {
 if (head == null)
 throw new Exception("Stack is empty");
 var currentNode = head;
 head = currentNode.next;
 currentNode.next = null;
 return currentNode.data;
 }

 public T peek() {
 if (head == null)
 throw new Exception("Stack is empty")
 return head.data;
 }
 
 
}
// The data class
public class Node<T> {
 public T data;
 public Node? nextNode;
 
 public Node<T>(T data, Node? nextNode) {
 this.data = data;
 this.nextNode = nextNode;
 } 
}
```


> **Linked lists**\
> Ideally in real world application, we would not implement a linked list structure inside a stack, instead we would use readily made available linked list from .NET to store data. However, for demonstration purposes, these raw implementations will be shown.
{: .prompt-tip}

 

---
## Usecase 1: Reverse a string

```cs
var mystring = "Hello Jonh";
```

This is a naive method:
Although we could implement it just fine, however since strings are immutable, everytime we concatonate a string it will create a new object in memory. This leads to large overhead. 
```cs
var stack = new Stacks<String>();
var reversed = "";

foreach (var i in mystring) {
 stack.push(i);
}
foreach (var i in mystring) {
 reversed += stack.pop()
}
```

 

StringBuilder / string buffer method:
To solve the memory overhead, we need to use a mutable version of a string. A string builder.
```cs
var stack = new Stacks<String>();
var sb = new StringBuilder();

foreach (var i in mystring) {
 stack.push(i);
}
foreach (var i in mystring) {
 sb.Append(i);
}
Console.WriteLine(sb);
```

 

---
## Usecase 2: Balanced string
How can we design a synthax checking implementation using stacks. The problem goes something like this:

> Given a string, find the order of open or closed brackets in the string to ensure each open bracket have its closing counter part. Return true if it is balanced, and false if its not balanced.

The algorithm goes like this:
```
stack = new Stack()
foreach character in string {
 if character is open bracket
 stack.add(character)
 if character is closing bracket
 stack.removeTop()
}
return (stack is empty)
```

 

### Implementation
We can simply implement a basic version that checks only for some standard brackets `( )` `<>` `[]` `{}`

```cs
public bool isBalanced(String input) {
 Stack<Char> stack = new Stack<Char>();
 
 foreach (var letter in input) {
 if (letter == '(' || letter == '<' || letter == '[' || letter == '{')
 stack.push(letter);
 
 if (letter == ')' || letter == '>' || letter == ']' || letter == '}') {
 if (stack.isEmpty()) return false;
 stack.pop();
 }
 
 }
 return stack.isEmpty();
}
```

Adding checks for incorrect end cases will result in such spaghetti code:
```cs
public bool isBalanced(String input) {
 Stack<Char> stack = new Stack<Char>();
 
 foreach (var letter in input) {
 if (letter == '(' || letter == '<' || letter == '[' || letter == '{')
 stack.push(letter);
 
 if (letter == ')' || letter == '>' || letter == ']' || letter == '}') {
 if (stack.isEmpty()) return false;
 var top = stack.pop();
 if (
 (letter == ')' && top != '(') ||
 (letter == '>' && top != '<') ||
 (letter == ']' && top != '[') ||
 (letter == '}' && top != '{') 
 ) return false;
 }
 }
 return stack.isEmpty();
}
```

 

### Refactoring
We can extract the boolean logics to make the code more readable:
```cs
public bool isBalanced(String input) {
 Stack<Char> stack = new Stack<Char>();
 
 foreach (var letter in input) {
 if (isOpenBracket(letter.ToString()))
 stack.Push(letter);
 
 if (isCloseBracket(letter.ToString())) {
 if (stack.Count == 0) return false;
 
 var top = stack.Pop();
 if (!isBracketMatch(letter.ToString(), top.ToString())) 
 return false;
 }
 }
 return (stack.Count == 0);
}
```

The rest of the logics can be written in a more concise and extensible matter, store the open brackets and close brackets as a list.

```cs
private List<String> openBrackets = new List<String>() { 
 "<", "(", "{", "["
};
private List<String> closeBrackets = new List<String>() {
 ">", ")", "}", "]"
};

private bool isOpenBracket(String letter) {
 return openBrackets.Contains(letter);
}

private bool isCloseBracket(String letter) {
 return closeBrackets.Contains(letter);
}

private bool isBracketMatch(String leftBracket, String rightBracket) {
 return (openBrackets.IndexOf(leftBracket) == closeBrackets.IndexOf(rightBracket));
}
```

 

---
## Implementing a stack with Arrays

In our previous example a stack was implemented using an internal datastructure of a linked list. Here we will demonstate the same attempt using an array instead.

When it comes to array type implementation, it is easier to implement a fixed sized stack.
```cs
public class Stack<T> {
 private T[] storage;
 public int lastItemIndex = 0;
 
 public Stacks2(int stackSize) {
 storage = new T[stackSize];
 }
 
 public void push(T item) {
 if (isFull())
 throw new StackOverflowException();
 
 storage[lastItemIndex] = item;
 lastItemIndex++;
 }
 
 public T pop() {
 if (isEmpty())
 throw new InvalidOperationException();
 
 var item = storage[lastItemIndex-1];
 storage[lastItemIndex-1] = default;
 lastItemIndex--;
 
 return item;
 }
 
 public bool isEmpty() {
 return lastItemIndex < 1;
 }
 
 public bool isFull() {
 return storage.Length <= lastItemIndex; 
 }
}
```

## The problem
Let's say we have a nextjs frontend and a python backend used to process some data. The current approach of deploying this project:

On the nextjs stack
```
npm install
npm run build
npm run start
```

On the python flask stack:
```
pip install -r requiremnets.txt
python3 app.py 
```

This is complicated and also requires that you configure dependencies like gunicorn, etc.

 

With docker, we can one-click deploy this application. So here's what we need to configure and setup:
- We need to setup a CORS configuration so these 2 stacks can talk to each other without docker to clear configuration confusions.
- We need to containerize both nextjs and python stack
- We need to write a docker file to build this docker image

In docker a common approach to build our application is back to front. That means we should start with 
- dependencies of the backend (Postgres image?)
- backend stack, flask
- frontend stack, nextjs

 

---
## Python stack 
In your python stack, you need to configure a backend API with CORS. You can use the flask-cors package.

```python
from flask import Flask 
from flask_cors import CORS 
 
 
app = Flask(__name__) 
CORS(app) 

 
@app.route("/api/hello_world") 
def hello_world(): 
 return { 
 "message": "Hello, World" 
 } 
 
 
if __name__ == "__main__": 
 app.run(debug=True)
```



### Dockerfile
The `Dockerfile` for this application. You should name it as `flask.dockerfile` as we will be using 1 dockerfile for each stack, it helps with clearer seperation of concern.:
```dockerfile
FROM --platform=$BUILDPLATFORM python:3.11-alpine AS builder

WORKDIR /app

COPY requirements.txt ./

RUN pip install -r "requirements.txt"
 
COPY . .

EXPOSE 4000

CMD ["flask", "run", "--host=0.0.0.0", "--port=4000"]
```

So currently your project's structure from the root should look like this:

```
root:
 backend/
 - venv/
 - app.py
 - flask.dockerfile
 
 fronend/

```


### Compose.yml
Next. we'll create a docker compose file to test our dockerfile, its image and deployment. create a `compose.yml` at the root of the repository.
```yml
services:
 
 # flask service
 flask:
 container_name: flask
 image: flask:1.0.0
 build:
 context: ./backend
 dockerfile: flask.dockerfile
 ports:
 - 4000:4000
```

we can run this docker application via the docker commands:
```
docker compose build flask
docker compose up
```

 

---
## Nextjs stack
First thing to do is configure the proxy, so your backend can be forwarded without a CORS error making a fuss.

Its important to ensure on `fetch()` requests are made using a relative path rather than the docker's expose port path.

Example, your python backend has an endpoint on `localhost:4000/api/hello`. You should make your fetch request in the nextjs frontend as:
```js
// correct
fetch("/api/hello");

// wrong
fetch("http://localhost:4000/api/hello")
```

Then forward the requests by configuring a proxy in `next.config.mjs`
```js
const nextConfig = {
 // other configs...
 async rewrites() {
 return [
 {
 source: '/api/:path*',
 // Proxy to python backend. flask is service name from compose.yml
 destination: 'http://flask:4000/api/:path*', 
 },
 ]
 },
}

// ...
```

We need to use the relative path because, when we deploy on a VPS and a user makes a request. `http://localhost:4000/api/hello` becomes a hard coded value.

Our python backend doesnt sit on `localhost` for the user. it sits on our server, with a URL IP address. Thus its better to allow node to infer the api endpoint destination instead.

 

### Dockerize
The docker file configuration is quite complicated, and thus its recommended to simply follow the template instructions from the official docs [here](https://github.com/vercel/next.js/blob/canary/examples/with-docker/Dockerfile)

You need to copy the docker file, and configure the `next.config.mjs`:
```js
// next.config.js
module.exports = {
 // ... rest of the configuration.
 output: "standalone",
};
```

And then your `compose.yml`
```yml
services:
 # nextjs frontend service
 next:
 container_name: next
 image: next:1.0.0
 build:
 context: ./frontend
 dockerfile: next.dockerfile
 ports:
 - 3000:3000
 depends_on:
 - flask
 
 # flask service
 flask:
 container_name: flask
 image: flask:1.0.0
 build:
 context: ./backend
 dockerfile: flask.dockerfile
 ports:
 - 4000:4000
```

once this is setup we can run our application

```
docker compose up -d next
```

 

---
## Networking pains and gotchas
> [stackoverflow](https://stackoverflow.com/questions/74854996/next-js-fetch-get-an-econnrefused-error-in-docker-strapi-as-backend)

Let's imagine we are running this docker application on our local computer. We can access our 2 stacks via the browser:

- http://localhost:4000/api/hello_world our flask backend
- http://localhost:3000/ our nextjs frontend

However. When we make a http request from the frontend to the backend. There are 2 main ways this goes down.

- The request is made in the client browser. `fetch(http://localhost:4000/api/hello_world)`. Where fetch here is made via a hardcoded URL. 

It works on our local computer, but not on a VPS. To make it work on the VPS we need to make the base URL as an .env variable, and change it to the public facing address of our backend.

 

- We use the `next.config.mjs` to reroute. The request is made in the client browser as `fetch(/api/hello_world)`, nodejs translate this address at runtime **server side**.

we use the **docker service name** `destination: 'http://flask:4000/api/:path*` because, nextjs application sits on in its own container. Thus, its `localhost:4000` is non existent. To talk to the flask container, it must use the flask service name and comunicate via the docker network. 

However when we run flask and nextjs as standalone applications, its sharing a single environment, thus serverside, `localhost:4000` exists

```
On a local computer, the proxy works, by forwarding the requests to localhost:400
 Local computer
 _____________________________
 http://localhost:3000/api/hello | proxy:localhost:4000 |
Dev -------------------------------->| nextjs <----------> flask |
 |_____________________________|
frontend coded as
fetch(/api/hello)


But also asny requests would work on the local computer, as both processes are 
running on localhost
 Local computer
 _____________________________
 http://localhost:4000/api/hello | flask |
Dev -------------------------------->| nextjs |
 http://localhost:3000/ |_____________________________| 

frontend coded as
fetch(http://localhost:4000/api/hello)


But for the user. The processes are not running on their localhost, but the
server's. Thus we must proxy via next.config
 Server
 _____________________________
 http://site.com/api/hello | proxy:localhost:4000 |
User ---------------------------> | nextjs <----------> flask |
 |_____________________________|
frontend coded as
fetch(/api/hello)


But when we containerize our application. The environments are separated, 
in NextJS's container, no processes are running localhost:400,
thus it must be rerouted via docker's. 
The server cannot access flask:4000, as it is not part of the docker network.
 Server w/ docker
 _____________________________________
 http://site.com/api/hello | proxy:flask:4000 | 
User ---------------------------> | _______ | _______ |
 | |nextjs | <==========> | flask | |
frontend coded as | |_______| docker |_______| |
fetch(/api/hello) | | Network | |
 | | | |
 | container container |
 |_____________________________________|


If we use a direct URL from the user to access the flask backend, 
an Nginx proxy will have to be configured.
 Server w/ docker
 _____________________________________
 http://site.com/api/hello | Nginx ---------------- | 
User ---------------------------> | _______ proxy :api/* _|_____ |
 | |nextjs | | flask | |
frontend coded as | |_______| |_______| |
fetch(http://site.com/api/hello) | | | |
 | | | |
 | container container |
 |_____________________________________|
 
```

 

### Share network namespaces instead
Instead of going thru so much headaches of configuring networks. A better way is to allow both of these services to share the server's localhost network

```yml
services:
 
 # flask service
 flask:
 container_name: flask
 image: flask:1.0.0
 build:
 context: ./backend
 dockerfile: flask.dockerfile
 network: host
 ports:
 - 4000:4000
```

NextJS can access the backend via `localhost:4000` on the server side no issues. For the client side making request from the browser. Its still best to configure the `next.config`.


 

---
## References

https://github.com/FrancescoXX/fullstack-flask-app/blob/main/frontend/next.dockerfile

https://github.com/docker/awesome-compose/tree/master/nginx-flask-mongo/flask

https://github.com/vercel/next.js/blob/canary/examples/with-docker/Dockerfile

https://www.youtube.com/watch?v=1afIORRyp58

https://stackoverflow.com/questions/74854996/next-js-fetch-get-an-econnrefused-error-in-docker-strapi-as-backend/78951586#78951586