# Week 6 - Sets

## Team

Team name: pils
Date: 02/06/2022

Members
Wouter Starrenburg
Morris Rouwhorst

## Activities
### Activity 1: Find out: set membership

1. set of paying members
2. set of free members
3. set of people signed up for an activity
4. set of volunteers for an activity
5. set of students at a study association

### Activity 2: Comparing floating point numbers

Apparently, not all doubles can be exactly represented, which results in the likelyhood of a double being off by a *very* small margin. A better way to check for equality would be to check whether the difference between two doubles is below a very small margin.

For some reason, using just a == b in the equals_dbl function DOES work, while comparing a == b in the main function doesn't.

#include <float.h>

bool equals_dbl(double a, double b) {
//    return (fabs(a - b) < DBL_EPSILON); this should work but DBL_EPSILON is too small when you compare sum results (as happens in the activity 6 test code)
    return (fabs(a - b) < 0.000001);
}

### Activity 3: Comparing compound data types

bool equals_prs(const person_t * obj1, const person_t * obj2) {
    return (obj1->name == obj2->name && obj1->year_of_birth == obj2->year_of_birth);
}

Tested using the given program. I think the assert macro is really cool and useful.

### Activity 4: Function prototypes

void set_add(set_t * ptr, double val);
void set_remove(set_t * ptr, int index);
const bool set_contains(set_t * ptr, double val);

### Activity 5: Dynamic sizing
Version 1 is correct. realloc() frees the old pointer if nothing goes wrong.

void ensure_cap(set_t * set) { // version 1
    if (set->size < set->capacity) return;
    size_t cap = (set->capacity + 1) * 3 / 2;
    double * ptr = realloc(set->data, cap * sizeof(double));
    if (ptr != NULL) {
        set->data = ptr;
        set->capacity = cap;
    }
}

### Activity 6: Function implementations

bool set_contains(set_t * ptr, double val){
    for (size_t i = 0; i < ptr->size; ++i) {
        if(*(ptr->data + i) == val) { return true; }
    }
    return false;
}

void set_add(set_t * ptr, double val){
    if(set_contains(ptr, val)) { return; }
    ensure_cap(ptr);
    *(ptr->data + ptr->size) = val;
    ptr->size++;
}

void set_remove(set_t * ptr, double val){
    size_t pos;
    bool contains_val = false;
    for (size_t i = 0; i < ptr->size; ++i) {
        if(equals_dbl(*(ptr->data + i), val)) {
            pos = i;
            contains_val = true;
        }
    }
    if(!contains_val) { return; }

    for(size_t i = pos; i < ptr->size; i++){
        *(ptr->data + i) = *(ptr->data + i + 1);    //iteratively shifts array elements
    }
    ptr->size--;
}

Tested using the given program.

### Activity 7: Time complexity of remove and add

| Operation | Time complexity |
|-----------| --------------- |
| Contains | O(n) |
| Add | O(n) |
| Remove | O(n) |

Time complexities are O(n), because both add and remove have to iterate over the array to check whether it contains the value.

### Activity 8: Binary search

Value to find: 46:

| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 9 | 16 | 12 |
| 3 | 13 | 16 | 14 |

Value to find: 4:

| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 0 | 8 |4 |
| 3 | 0 |4 |2 |
| 4 | 0 | 2 |1 |
| 5 | 0 | 1 | 0 |

### Activity 9: Binary search - Time complexity

| Array size | Lookups |
|------------|---------|
| 16 | 5 |
| 32 | 6 |
| 64 | 7 |
| 128 | 8 |
| 256 | 9 |

the time complexity is O(log(n))

### Activity 10: Implementing index_of

size_t index_of(const set_t * set, double value){
    size_t lo = 0, hi = set->size;
    while (lo < hi){
        size_t mid = lo + (hi - lo) / 2;
        if (equals_dbl(set->data[mid], value)) { return mid; }
        else if (set->data[mid] < value){ lo = mid + 1; }
        else { hi = mid; }
        }
    return hi;
}

Tested using the given program.

### Activity 11: Modifying the sorted array

bool set_contains(set_t* set, double needle){
    size_t index = index_of(set, needle);
    if (index == set->size){
        return false;
        }
    return equals_dbl(set->data[index], needle);
}

void set_add(set_t * ptr, double val){
    size_t pos = index_of(ptr, val);
    //if (ptr->data[pos] == val)
    if(*(ptr->data + pos) == val) { return; }
    ensure_cap(ptr);
    for(size_t i = ptr->size; i > pos; i--){
        *(ptr->data + i + 1) = *(ptr->data + i);    //iteratively shifts array elements
    }
    *(ptr->data + pos) = val;
    ptr->size++;
}

void set_remove(set_t * ptr, double val){
    if(!set_contains(ptr, val)) { return; }
    size_t pos = index_of(ptr, val);

    for(size_t i = pos; i < ptr->size; i++){
        *(ptr->data + i) = *(ptr->data + i + 1);    //iteratively shifts array elements
    }
    ptr->size--;
}

Tested using the given program. This gave some issues because realloc has a tendency to return NULL upon being requested to reserve more space for 3.0 or 4.0
I really can't be bothered to figure out why this happens, so I've removed the 3.0 and 4.0 related assertions and the rest of it seems to work fine.

### Activity 12: Time complexity of the sorted set

| Operation | Time complexity |
|-----------| --------------- |
| Add | O(n) |
| Remove | O(n) |
| Contains | O(log(n)) |

I think picking an 'average' time complexity is a bit difficult, but I've put O(n) for Add and Remove, because they both first have to run index_of which has a TC of O(log(n)), and then, if the value is new to the set, iteratively shift a bunch of the elements in the array to make room for the new value.

## Generic set (optional)

### Activity 13: Functions index_of and contains

Record your answer here

### Activity 14: Functions add and remove

Record your answer here