# Week 1 - Array

## Team

Team name: Group 5
Date: 2/12/2021

Members: Max Thielen, Mihail Bachvarov, Nicky Ichov, Bogdan Iliescu

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Bogdan Iliescu |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Nicky Ichov |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Mihail Bachvarov |

## Activities

### Activity 1: Fixed-sized arrays

The array data structure is able to store a **fixed amount of varibles** of the same type. Since the size of the array has to be defined when initializing the data structure, a certain chunk of memory is reserved and can be accessed and assigned by index. However once initialized the size is unable to change so a lot of the time **memory ends up getting wasted** because running out of room in an array is very inconvinient. The fixed-sized array does not only come with disatvanteges, since in cases where the **amount of data required is know** the array is the simplest and fastest way to store in one place. In the example below an array of size 100 is initialized and then filled with a for loop, since the size is always know the for loop becomes very convient for this action.

int size = 100;
int values[size];

for(int i=0; i<size; i++){
    array[i] = i;
}

$dza: That's ok. A great advantage of fixed sized array is their use when memory is limited. With fixed sizes the memory usage of a program can be checked statically by a compiler - this way you are sure you never run out of memory. Moreover, all the trouble of allocating and freeing is gone.

### Activity 2: Random access

Random(direct) access implies the ability to access any entry in a array **independently of its position in the array** and of the array's size. Sometimes, however we can only use sequential access memory. An example of that is a **cassette tape** where the data written on the cassette can only be read by playing through the tape. Another example of where random access memory is not used is when working with **linked lists**. The primary benefit of a linked list over a conventional array is the fact that elements can easily be inserted or removed from the list, because they are not stored contiguously.

int size = 10;
int array[size];

for(int i=0; i<size; i++){
    array[i] = i;
}

//grabbing both ints takes the same amount of time
int var1 = array[0];
int var2 = array[9]; 

### Activity 3: The sizeof operator

The sizeof operator returns the **amount of memory allocated to that data type**.
A single object uses different number of memory adresses - 2,4,8, etc. However the amount of used memory depends of the data type. This however doesn't hold true for pointers in C. Their size is dependant on the architecture of the machine. We can see below that the size for all pointers stays consitently 4 bytes.

int *p1;
float *p2;
double *p3;
    
printf("the size of p1 is: %d\n",sizeof(p1)); //prints out 4
printf("the size of p1 is: %d\n",sizeof(p2)); //also prints out 4
printf("the size of p3 is: %d\n",sizeof(p3)); //the output is still 4

### Activity 4: The sizeof operator and arrays

In order to find the size of an array with sizeof operator, you can divide the total size of the array by the size of the array elements within it.

int array[10];

//divide sizeof(array) by sizeof(element in array)
int array_size = sizeof(array)/sizeof(array[0]); 

### Activity 5: Variables in function scope

The scope of a variable is determined by where it is declared, which **defines the part of the program where the variable is used and can be accessed**. Variables declared outside any function are considered "global" and it can be accessed from anywhere in the code, while variables declared inside a function are cosidere "local" and are used only by that particular function or any nested functions.

typedef struct Array_T{
    int capacity;
    int count;
    int *values;
} Array;

void initArray(Array *pArray, int capacity){
    int values[capacity];
    pArray->capacity = capacity;
    pArray->values = values;
    pArray->count = 0;
}

The function above uses the structure Array and initializes an instance of it using an Array pointer and the desired capacity. When executed, the function creats an array with the capacity as the size and then sets all of the required values for the structure using the array created in step one for the pointer array values. This functions works however, it is a more complex way of simply initalizing an array like seen in earlier activities.

$dza: No, the function doesn't work as intended. You are assigning a stack-allocated, function-scope array to a pointer. When this function exits, this array will be automatically deleted. At this moment the pointer will point to a variable that no longer exists. This is called a *dangling pointer*. Generally speaking, returning pointers to stack variables is always an error.

### Activity 6: Stack vs. heap

When a function is called, a block is reserved on the top of the stack for local variables. When that function returns, the block becomes unused and it can be used the next time a function is called. That basically means that the most recent reserved block is always the next block to be freed. So that makes it really simple to keep track on it.
Meanwhile the heap is memory that get dynamic allocation. There is no enforced pattern to the allocation and dealloacation of blocks from the heap.The blocks can be allocated and freed at any time. That makes it way more complicated to keep track of.

### Activity 7: Using malloc

The **malloc()** function is able to allocate memory of a pointer specified by the arguement. This becomes useful since using malloc then allows the **realloc()** function to be used to resize the array and also deallocate memory with the **free()** function. This gives more control over the memory reserved for a certain array.

unsigned long *num1 = (unsigned long*)malloc(sizeof(unsigned long));

float *num2 = (float*)malloc(265*sizeof(float));

int* allocateMemory(int counter){
    int *ptr = (int*)malloc(counter*sizeof(int));
    return ptr;
}

$dza: A pointer returned by `malloc` needs not to be casted, this suffices:

float* numbers = malloc(sizeof(float[10]));

### Activity 8: Limits of malloc
The malloc() function reserves a block of storage of size bytes. The function does not initialize all elements to 0. The maximum size of malloc() is **16711568 bytes**.

### Activity 9: Creating an array with dynamic capacity
Using the structure and fucntion in Activity 5 the new array_init fucntion uses malloc instead of a newly initialized array. This way the initilized array is able to be resized if needed.

void array_init(Array *pArray, int capacity)
{
    pArray->values = malloc(capacity*sizeof(Array));
    pArray->capacity = capacity;
    pArray->count = 0;
}

### Activity 10: Dangerous frees
The **free()** function takes a pointer as an argument and deallocates its memory without returning anything. However the pointer sent into the function has to have been initalized with **malloc()** otherwise the program will complain and **throw an error**. Simply passing a NULL pointer wont do anything though since there is no memory to be deallocated.

int* ptr = (int*)123456789;
free(ptr);

int* null_ptr = NULL;
free(null_ptr);

$dza: calling `free` on `NULL` is, as per standard, always allowed and results in no-operation

### Activity 11: Infinite memory?
Before the lifetime of the last pointer that stores the return value of a call to a standard memory allocation function has ended, a free() function needs to be used with that pointer value.
If dynamically allocated memory is not freed, it results in a memory leak and the system will run out of memory.

enum { BUFFER_SIZE = 32 };
 
int f(void) {
  char *text_buffer = (char *)malloc(BUFFER_SIZE);
  if (text_buffer == NULL) {
    return -1;
  }
  return 0;
}

If the memory is not freed in a long run it might cause the program to take up more storage.

### Activity 12: Resizing an Array

void resize(Array *pArray, int newCapacity)
{
    pArray->values = realloc(pArray->values, newCapacity*sizeof(Array));
    pArray->capacity = newCapacity;
    // $dza: why this last line?
    pArray->values[pArray->capacity-1]=0;
}

### Activity 13: Array insertion

At first we need to check if the array is full and if it is, we expand it by 1. Then we need to move all the elements before the index of insertion back. Then we can finally insert the value. This is an example:

void array_insert(Array *pArray, int index, int value)
{
    if(pArray->count==pArray->capacity){
        resize(pArray,pArray->capacity++);
    }

    for (int i=(pArray->capacity); i>=index; i--){
        pArray->values[i] = pArray->values[i--];
    }
    pArray->values[index] = value;
    pArray->count++;
}

$dza: You used post-increment for `capacity`. It means the the value of `capacity` will be incremented only after the call to `resize` has returned. This, in turn, means that the capacity you passed to `resize` is your old, unchanged capacity. Either use pre-increment (`resize(pArray, ++pArray->capacity)`) or just do it explicitly (`resize(pArray,pArray->capacity + 1)`) and increment afterwards.

### Activity 14: Basic list operations

void array_append(Array *pArray, int element)
{
    // $dza: what it there is not enough capacity?
    pArray->values[pArray->count] = element;
    pArray->count++;
}

void array_remove(Array *pArray, int index)
{
    // $dza: the loop contition should be `i < pArray->count`
    for(int i=index; i<pArray->capacity--; i++){
        pArray->values[i] = pArray->values[i+1];
    }
    pArray->values[pArray->capacity--] = 0;
    pArray->count--;
}

void array_clear(Array *pArray)
{
    for(int i=0; i<pArray->capacity; i++){
        pArray->values[i] = 0;
    }
    pArray->count = 0;
}

void array_insert(Array *pArray, int index, int value)
{
    if(pArray->count==pArray->capacity){
        // $dza: again post-increment instead of pre-increment
        resize(pArray,pArray->capacity++);
    }

    // $dza: the loop contition should be `i < pArray->count`
    for (int i=(pArray->capacity); i>=index; i--){
        pArray->values[i] = pArray->values[i--];
    }
    pArray->values[index] = value;
    pArray->count++;
}

void array_swap(Array *pArray, int index_a, int index_b)
{
    int temp_a=pArray->values[index_a];
    pArray->values[index_a] = pArray->values[index_b];
    pArray->values[index_b] = temp_a;
}

### Activity 15: Test your code

typedef struct Array_T
{
    int *values;
    int capacity;
    int count;
} Array;

void array_init(Array *pArray, int capacity)
{
    pArray->values = malloc(capacity*sizeof(Array));
    pArray->capacity = capacity;
    pArray->count = 0;
}

void resize(Array *pArray, int newCapacity)
{
    pArray->values = realloc(pArray->values, newCapacity*sizeof(Array));
    pArray->capacity = newCapacity;
    pArray->values[pArray->capacity--] = 0;
}


void array_append(Array *pArray, int element)
{
    pArray->values[pArray->count] = element;
    pArray->count++;
}

void array_remove(Array *pArray, int index)
{
    for(int i=index; i<pArray->capacity--; i++){
        pArray->values[i] = pArray->values[i+1];
    }
    pArray->values[pArray->capacity--] = 0;
    pArray->count--;
}

void array_clear(Array *pArray)
{
    for(int i=0; i<pArray->capacity; i++){
        pArray->values[i] = 0;
    }
    pArray->count = 0;
}

void array_insert(Array *pArray, int index, int value)
{
    if(pArray->count==pArray->capacity){
        resize(pArray,pArray->capacity++);
    }

    for (int i=(pArray->capacity); i>=index; i--){
        pArray->values[i] = pArray->values[i--];
    }
    pArray->values[index] = value;
    pArray->count++;
}

void array_swap(Array *pArray, int index_a, int index_b)
{
    int temp_a=pArray->values[index_a];
    pArray->values[index_a] = pArray->values[index_b];
    pArray->values[index_b] = temp_a;
}
void array_print(const Array * array)
{
    int count;
    int values;
    int capacity;
    printf("[");
    if(array->count>0)
        printf("%d", array->values[0]);
    for(int i=1; i< array->count; i++)
        printf(", %d",array->values[i]);
    printf("] (capacity: %d)\n", array -> capacity);
}

int main()
{
    Array array;
    array_init(&array, 4);
    array_append(&array, 0);
    array_print(&array);
    array_append(&array, -1);
    array_print(&array);
    array_append(&array, -2);
    array_print(&array);
    array_append(&array, -3);
    array_print(&array);
    array_insert(&array, 4, -4);
    array_print(&array);
    array_insert(&array, 2, 42);
    array_print(&array);
    array_remove(&array, 3);
    array_print(&array);
    array_swap(&array, 1, 3);
    array_print(&array);

    return 0;
}

### Activity 16: Solve the partitioning problem

void partition(Array *pArray)
{
    int index;

    if(pArray->values[0]>=0){index=0;}
    else{index=1;}

    for(int i=0; i<pArray->capacity; i++){
        // $dza: please, please do read about how post- and pre-increment work
        if(pArray->values[i++]<0 && pArray->values[i]>=0){
            array_swap(pArray, i++, index);
            index++;
            while(pArray->values[index]<0){
                index++;
            }
            //array_print(pArray);
        }
    }
}

$dza: your idea for partitioning was good. However, I'm afraid you applied way too much kool-aid++ to it.

## Look back

### What we've learnt

Staring this week, we had prior knowlege of the basic array functions like the fixed-size and random access. Using an array like this has already been super usefull, however throughout these exercises we learned that arrays can be made even more powerful through the malloc(), realloc(), and free() functions by taking control of the memory allocation manually. With these three functions we were able to use an array outside of its pre-designed applications and solve a sorting problem alot easier.

### What were the surprises

Our group was unaware of the amount of controll over memory available in C. The ability to resize an array post initialization is really impressive and suprisingly useful.

### What problems we've encountered

We had some issues with the code at first, since creating it pice by pice and then putting it together threw alot of errors. Especially in the begging we failed to see the big picture and how it all was going to connect so we had to go back through some of the activites to adjust the code a bit until it all worked harmonimously together.

### What was or still is unclear

The free() and realloc() functions were challenging to grasp and understand exaclty what was going on with the memory and pointers, but the practice helped solidify the knowlege.

### How did the group perform?

The team worked fairly well together. Of course it was hard to do these activities remotely and still collaborate efficiently but discord meetings helped alot with this. Another challenge was spliting up the work since the activites build up and use prior code so the group memebers could not go too far ahead of each other. Nonetheless, towards the end it was better anyway to simply all work together on one activity since they became progressivly harder and extensive.