# STC Algorithms

---
## Ranged for-loops

### c_foreach, c_foreach_rv, c_forpair

| Usage                                    | Description                               |
|:-----------------------------------------|:------------------------------------------|
| `c_foreach (it, ctype, container)`       | Iteratate all elements                    |
| `c_foreach (it, ctype, it1, it2)`        | Iterate the range [it1, it2)              |
| `c_foreach_rv (it, ctype, container)`    | Iteratate in reverse (cstack, cvec, cdeq) |
| `c_forpair (key, val, ctype, container)` | Iterate with structured binding           |

```c
#define i_key int
#define i_val int
#define i_tag ii
#include <stc/csmap.h>
...
csmap_ii map = c_init(csmap_ii, { {23,1}, {3,2}, {7,3}, {5,4}, {12,5} });

c_foreach (i, csmap_ii, map)
    printf(" %d", i.ref->first);
// 3 5 7 12 23
// same without using c_foreach:
for (csmap_ii_iter i = csmap_ii_begin(&map); i.ref; csmap_ii_next(&i))
    printf(" %d", i.ref->first);

csmap_ii_iter it = csmap_ii_find(&map, 7);
// iterate from it to end
c_foreach (i, csmap_ii, it, csmap_ii_end(&map))
    printf(" %d", i.ref->first);
// 7 12 23

// structured binding:
c_forpair (id, count, csmap_ii, map)
    printf(" (%d %d)", *_.id, *_.count);
// (3 2) (5 4) (7 3) (12 5) (23 1)
```

### c_forlist
Iterate compound literal array elements. Additional to `i.ref`, you can access `i.size` and `i.index` for the input list/element.
```c
// apply multiple push_backs
c_forlist (i, int, {1, 2, 3})
    cvec_i_push_back(&vec, *i.ref);

// insert in existing map
c_forlist (i, cmap_ii_raw, { {4, 5}, {6, 7} })
    cmap_ii_insert(&map, i.ref->first, i.ref->second);

// string literals pushed to a stack of cstr:
c_forlist (i, const char*, {"Hello", "crazy", "world"})
    cstack_str_emplace(&stk, *i.ref);
```

---
## Range algorithms

### c_forrange
Abstraction for iterating sequence of integers. Like python's **for** *i* **in** *range()* loop.

| Usage                                        | Python equivalent                    |
|:---------------------------------------------|:-------------------------------------|
| `c_forrange (stop)`                          | `for _ in range(stop):`              |
| `c_forrange (i, stop) // i type = long long` | `for i in range(stop):`              |
| `c_forrange (i, start, stop)`                | `for i in range(start, stop):`       |
| `c_forrange (i, start, stop, step)`          | `for i in range(start, stop, step):` |

```c
c_forrange (5) printf("x");
// xxxxx
c_forrange (i, 5) printf(" %lld", i);
// 0 1 2 3 4
c_forrange (i, -3, 3) printf(" %lld", i);
// -3 -2 -1 0 1 2
c_forrange (i, 30, 0, -5) printf(" %lld", i);
// 30 25 20 15 10 5
```

### crange
A number sequence generator type, similar to [boost::irange](https://www.boost.org/doc/libs/release/libs/range/doc/html/range/reference/ranges/irange.html). The **crange_value** type is `long long`. Below *start*, *stop*, and *step* are of type *crange_value*:
```c
crange      crange_make(stop);              // will generate 0, 1, ..., stop-1
crange      crange_make(start, stop);       // will generate start, start+1, ... stop-1
crange      crange_make(start, stop, step); // will generate start, start+step, ... upto-not-including stop
                                            // note that step may be negative.
crange_iter crange_begin(crange* self);
crange_iter crange_end(crange* self);
void        crange_next(crange_iter* it);

// 1. All primes less than 32:
crange r1 = crange_make(3, 32, 2);
printf("2"); // first prime
c_forfilter (i, crange, r1, isPrime(*i.ref))
    printf(" %lld", *i.ref);
// 2 3 5 7 11 13 17 19 23 29 31

// 2. The first 11 primes:
printf("2");
crange range = crange_make(3, INT64_MAX, 2);
c_forfilter (i, crange, range,
    isPrime(*i.ref) &&
    c_flt_take(10)
){
    printf(" %lld", *i.ref);
}
// 2 3 5 7 11 13 17 19 23 29 31
```

### c_forfilter
Iterate a container/range with chained range filtering.

| Usage                                               | Description                            |
|:----------------------------------------------------|:---------------------------------------|
| `c_forfilter (it, ctype, container, filter)`        | Filter out items in chain with &&      |
| `c_forfilter_it (it, ctype, startit, filter)`       | Filter from startit position           |

| Built-in filter                   | Description                                |
|:----------------------------------|:-------------------------------------------|
| `c_flt_skip(it, numItems)`        | Skip numItems (inc count)                  |
| `c_flt_take(it, numItems)`        | Take numItems (inc count)                  |
| `c_flt_skipwhile(it, predicate)`  | Skip items until predicate is false        |
| `c_flt_takewhile(it, predicate)`  | Take items until predicate is false        |
| `c_flt_counter(it)`               | Increment current and return count         |
| `c_flt_getcount(it)`              | Number of items passed skip*/take*/counter |

[ [Run this example](https://godbolt.org/z/n9aYrYPv8) ]
```c
#include <stc/calgo.h>
#include <stdio.h>

bool isPrime(long long i) {
    for (long long j=2; j*j <= i; ++j)
        if (i % j == 0) return false;
    return true;
}

int main(void) {
    // Get 10 prime numbers starting from 1000. Skip the first 15 primes,
    // then select every 25th prime (including the initial).
    crange R = crange_make(1001, INT64_MAX, 2); // 1001, 1003, ...

    c_forfilter (i, crange, R,
                    isPrime(*i.ref)            &&
                    c_flt_skip(i, 15)          &&
                    c_flt_counter(i) % 25 == 1 &&
                    c_flt_take(i, 10)
    ){
        printf(" %lld", *i.ref);
    }
}
// out: 1097 1289 1481 1637 1861 2039 2243 2417 2657 2803
```
Note that `c_flt_take()` and `c_flt_takewhile()` breaks the loop on false.

---
## Generic algorithms

### c_init, c_drop

Make any container from an initializer list:
```c
#define i_key_str // owned cstr string value type
#include <stc/cset.h>

#define i_key int
#define i_val int
#include <stc/cmap.h>
...
// Initializes with const char*, internally converted to cstr!
cset_str myset = c_init(cset_str, {"This", "is", "the", "story"});

int x = 7, y = 8;
cmap_int mymap = c_init(cmap_int, { {1, 2}, {3, 4}, {5, 6}, {x, y} });
```
Drop multiple containers of the same type:
```c
c_drop(cset_str, &myset, &myset2);
```

### c_find_if, c_erase_if, c_eraseremove_if
Find or erase linearily in containers using a predicate
- For `c_find_if(iter, C, c, pred)`, ***iter*** is in/out and must be declared prior to call.
- Use `c_erase_if(iter, C, c, pred)` with **clist**, **cmap**, **cset**, **csmap**, and **csset**.
- Use `c_eraseremove_if(iter, C, c, pred)` with **cstack**, **cvec**, **cdeq**, and **cqueue**.
```c
// Search vec for first value > 2:
cvec_i_iter i;
c_find_if(i, cvec_i, vec, *i.ref > 2);
if (i.ref) printf("%d\n", *i.ref);

// Erase all values > 2 in vec:
c_eraseremove_if(i, cvec_i, vec, *i.ref > 2);

// Search map for a string containing "hello" and erase it:
cmap_str_iter it, it1 = ..., it2 = ...;
c_find_if(it, csmap_str, it1, it2, cstr_contains(it.ref, "hello"));
if (it.ref) cmap_str_erase_at(&map, it);

// Erase all strings containing "hello" in a sorted map:
c_erase_if(i, csmap_str, map, cstr_contains(i.ref, "hello"));
```

### sort_n_ - two times faster qsort

The **sort_n**, **sort_ij** algorithm is about twice as fast as *qsort()*, and often simpler to use.
You may customize `i_tag` and the comparison function `i_cmp` or `i_less`.  

There is a [benchmark/test file here](../misc/benchmarks/various/csort_bench.c).
```c
#define i_key int
#include <stc/algo/sort.h>
#include <stdio.h>

int main(void) {
    int nums[] = {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4};
    intarray_sort_n(nums, c_arraylen(nums));
    c_forrange (i, c_arraylen(arr)) printf(" %d", arr[i]);
}
```
Containers with random access may also be sorted. Even sorting cdeq/cqueue (with ring buffer) is
possible and very fast. Note that `i_more` must be defined to retain specified template parameters for use by sort:
```c
#define i_type MyDeq
#define i_key int
#define i_more
#include <stc/cdeq.h> // deque
#include <stc/algo/sort.h>
#include <stdio.h>

int main(void) {
    MyDeq deq = c_init(MyDeq, {5, 3, 5, 9, 7, 4, 7, 2, 4, 9, 3, 1, 2, 6, 4});
    MyDeq_sort_n(&deq, MyDeq_size(&deq));
    c_foreach (i, MyDeq, deq) printf(" %d", *i.ref);
    MyDeq_drop(&deq);
}
```

### c_new, c_delete

- `c_new(Type, val)` - Allocate *and init* a new object on the heap
- `c_delete(Type, ptr)` - Drop *and free* an object allocated on the heap. NULL is OK.
```c
#include <stc/cstr.h>

cstr *str_p = c_new(cstr, cstr_from("Hello"));
printf("%s\n", cstr_str(str_p));
c_delete(cstr, str_p);
```

### c_malloc, c_calloc, c_realloc, c_free
Memory allocator wrappers that uses signed sizes.

### c_arraylen
Return number of elements in an array. array must not be a pointer!
```c
int array[] = {1, 2, 3, 4};
intptr_t n = c_arraylen(array);
```

### c_swap, c_const_cast
```c
// Safe macro for swapping internals of two objects of same type:
c_swap(cmap_int, &map1, &map2);

// Type-safe casting a from const (pointer):
const char cs[] = "Hello";
char* s = c_const_cast(char*, cs); // OK
int* ip = c_const_cast(int*, cs);  // issues a warning!
```

### Predefined template parameter functions

**crawstr** - Non-owned `const char*` "class" element type: `#define i_keyclass crawstr`
```c
typedef     const char* crawstr;
int         crawstr_cmp(const crawstr* x, const crawstr* y);
bool        crawstr_eq(const crawstr* x, const crawstr* y);
uint64_t    crawstr_hash(const crawstr* x);
```
Default implementations
```c
int         c_default_cmp(const Type*, const Type*);    // <=>
bool        c_default_less(const Type*, const Type*);   // <
bool        c_default_eq(const Type*, const Type*);     // == 
uint64_t    c_default_hash(const Type*);
Type        c_default_clone(Type val);                  // return val
Type        c_default_toraw(const Type* p);             // return *p
void        c_default_drop(Type* p);                    // does nothing
```

---
## Coroutines
This is a much improved implementation of 
[Simon Tatham's coroutines](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html),
which utilizes the *Duff's device* trick. Tatham's implementation is not typesafe,
and it always allocates the coroutine's internal state dynamically. But crucially,
it does not let the coroutine do self-cleanup on early finish - i.e. it
only frees the initial dynamically allocated memory.

In this implementation, a coroutine may have any signature, but it should
take a struct pointer as parameter, which must contain the member `int cco_state;`
The struct should normally store all the *local* variables to be used in the
coroutine. It can also store input and output data if desired.

The coroutine example below generates Pythagorian triples, but the calling loop
skips the triples which are upscaled version of smaller ones, by checking 
the gcd() function. It also ensures that it stops when the diagonal size >= 100:

[ [Run this code](https://godbolt.org/z/coqqrfbd5) ]
```c
#include <stc/calgo.h>
#include <stdio.h>

struct triples {
    int n; // input: max number of triples to be generated.
    int a, b, c;
    int cco_state; // required member
};

int triples(struct triples* i) { // coroutine
    cco_routine(i) {
        for (i->c = 5; i->n; ++i->c) {
            for (i->a = 1; i->a < i->c; ++i->a) {
                for (i->b = i->a + 1; i->b < i->c; ++i->b) {
                    if ((int64_t)i->a*i->a + (int64_t)i->b*i->b == (int64_t)i->c*i->c) {
                        cco_yield();
                        if (--i->n == 0)
                            cco_return;
                    }
                }
            }
        }
        cco_cleanup:
        puts("done");
    }
    return 0;
}

int gcd(int a, int b) { // greatest common denominator
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main(void)
{
    struct triples t = {.n=INT32_MAX};
    int n = 0;

    while (triples(&t)) {
        // Skip triples with GCD(a,b) > 1
        if (gcd(t.a, t.b) > 1)
            continue;
        
        // Stop when c >= 100
        if (t.c < 100)
            printf("%d: [%d, %d, %d]\n", ++n, t.a, t.b, t.c);
        else
            cco_stop(&t); // cleanup in next coroutine call/resume
    }
}
```
### Coroutine API
To resume the coroutine from where it was suspended with *cco_yield()*: call the coroutine again.

**Note**: *cco_yield()* / *cco_await()* may not be called inside a `switch` statement from a
cco_routine scope; Use `if-else-if` constructs instead.

|           |  Function / operator                 | Description                             |
|:----------|:-------------------------------------|:----------------------------------------|
|`cco_result` | `CCO_DONE`, `CCO_AWAIT`, `CCO_YIELD` | Default set of return values from coroutines |
|           | `cco_cleanup:`                       | Label for cleanup position in coroutine |
| `bool`    | `cco_done(co)`                       | Is coroutine done?                      |
|           | `cco_routine(co) {}`                 | The coroutine scope                     |
|           | `cco_yield();`                       | Yield/suspend execution (return CCO_YIELD)|
|           | `cco_yield_v(ret);`                  | Yield/suspend execution (return ret)    |
|           | `cco_yield_final();`                 | Yield final suspend, enter cleanup-state |
|           | `cco_yield_final(ret);`              | Yield a final value                     |
|           | `cco_await(condition);`              | Suspend until condition is true (return CCO_AWAIT)|
|           | `cco_call_await(cocall);`            | Await for subcoro to finish (returns its ret value) |
|           | `cco_call_await(cocall, retbit);`    | Await for subcoro's return to be in (retbit \| CCO_DONE)  |
|           | `cco_return;`                        | Return from coroutine (inside cco_routine) |
|           | Task objects:                        |                                         |
|           | `cco_task_struct(Name, ...);`        | Define a coroutine task struct          |
|           | `cco_task_await(task, cco_runtime* rt);`| Await for task to finish             |
|           | `cco_task_await(task, rt, retbit);`  | Await for task's return to be in (retbit \| CCO_DONE) |
|`cco_result`| `cco_task_resume(task, rt);`       | Resume suspended task                   |
|           | Semaphores:                          |                                         | 
|           | `cco_sem`                            | Semaphore type                          |
| `cco_sem` | `cco_sem_from(long value)`           | Create semaphore                        |
|           | `cco_sem_set(sem, long value)`       | Set semaphore value                     |
|           | `cco_sem_await(sem)`                 | Await for the semaphore count > 0       |
|           | `cco_sem_release(sem)`               | Signal the semaphore (count += 1)       |
|           | Timers:                              |                                         | 
|           | `cco_timer`                          | Timer type                              |
|           | `cco_timer_await(tm, double sec)`    | Await secs for timer to expire (usec prec.)|
|           | `cco_timer_start(tm, double sec)`    | Start timer for secs duration           |
|           | `cco_timer_restart(tm)`              | Restart timer with same duration        |
| `bool`    | `cco_timer_expired(tm)`              | Return true if timer is expired         |
| `double`  | `cco_timer_elapsed(tm)`              | Return seconds elapsed                  |
| `double`  | `cco_timer_remaining(tm)`            | Return seconds remaining                |
|           | From caller side:                    |                                         | 
| `void`    | `cco_stop(co)`                       | Next call of coroutine finalizes        |
| `void`    | `cco_reset(co)`                      | Reset state to initial (for reuse)      |
| `void`    | `cco_call_blocking(cocall) {}`       | Run blocking until cocall is finished   |
| `void`    | `cco_call_blocking(cocall, int* outres) {}`| Run blocking until cocall is finished |
|           | `cco_task_blocking(task) {}`         | Run blocking until task is finished |
|           | `cco_task_blocking(task, rt, STACKSZ) {}`| Run blocking until task is finished |
|           | Time functions:                      |                                         |
| `double`  | `cco_time(void)`                     | Return secs with usec prec. since Epoch |
|           | `cco_sleep(double sec)`              | Sleep for seconds (msec or usec prec.)  |

---
## RAII scope macros
General ***defer*** mechanics for resource acquisition. These macros allows you to specify the
freeing of the resources at the point where the acquisition takes place.
The **checkauto** utility described below, ensures that the `c_auto*` macros are used correctly.

| Usage                                  | Description                                               |
|:---------------------------------------|:----------------------------------------------------------|
| `c_defer (drop...)`                    | Defer `drop...` to end of scope                           |
| `c_scope (init, drop)`                 | Execute `init` and defer `drop` to end of scope           |
| `c_scope (init, pred, drop)`           | Adds a predicate in order to exit early if init failed    |
| `c_with (Type var=init, drop)`         | Declare `var`. Defer `drop...` to end of scope            |
| `c_with (Type var=init, pred, drop)`   | Adds a predicate in order to exit early if init failed    |
| `c_auto (Type, var1,...,var4)`         | `c_with (Type var1=Type_init(), Type_drop(&var1))` ...    |
| `continue`                             | Exit a defer-block without resource leak                  |

```c
#include <stc/algo/raii.h> // or <stc/calgo.h>
...
// `c_defer` executes the expression(s) when leaving scope.
//  Note: does not require inclusion of "raii.h".
cstr s1 = cstr_lit("Hello"), s2 = cstr_lit("world");
c_defer (cstr_drop(&s1), cstr_drop(&s2))
{
    printf("%s %s\n", cstr_str(&s1), cstr_str(&s2));
}

// `c_scope` syntactically "binds" initialization and defer.
static pthread_mutex_t mut;
c_scope (pthread_mutex_lock(&mut), pthread_mutex_unlock(&mut))
{
    /* Do syncronized work. */
}

// `c_with` is similar to python `with`: declare a variable and defer the drop call.
c_with (cstr str = cstr_lit("Hello"), cstr_drop(&str))
{
    cstr_append(&str, " world");
    printf("%s\n", cstr_str(&str));
}

// `c_auto` automatically initialize and drops up to 4 variables:
c_auto (cstr, s1, s2)
{
    cstr_append(&s1, "Hello");
    cstr_append(&s1, " world");
    cstr_append(&s2, "Cool");
    cstr_append(&s2, " stuff");
    printf("%s %s\n", cstr_str(&s1), cstr_str(&s2));
}
```
**Example 1**: Use multiple **c_with** in sequence:
```c
bool ok = false;
c_with (uint8_t* buf = malloc(BUF_SIZE), buf != NULL, free(buf))
c_with (FILE* fp = fopen(fname, "rb"), fp != NULL, fclose(fp))
{
    int n = fread(buf, 1, BUF_SIZE, fp);
    if (n <= 0) continue; // auto cleanup! NB do not break or return here.
    ...
    ok = true;
}
return ok;
```
**Example 2**: Load each line of a text file into a vector of strings:
```c
#include <errno.h>
#define i_implement
#include <stc/cstr.h>

#define i_key_str
#include <stc/cvec.h>

// receiver should check errno variable
cvec_str readFile(const char* name)
{
    cvec_str vec = {0}; // returned
    c_with (FILE* fp = fopen(name, "r"), fp != NULL, fclose(fp))
    c_with (cstr line = {0}, cstr_drop(&line))
        while (cstr_getline(&line, fp))
            cvec_str_emplace(&vec, cstr_str(&line));
    return vec;
}

int main(void)
{
    c_with (cvec_str vec = readFile(__FILE__), cvec_str_drop(&vec))
        c_foreach (i, cvec_str, vec)
            printf("| %s\n", cstr_str(i.ref));
}
```

### The **checkauto** utility program (for RAII)
The **checkauto** program will check the source code for any misuses of the `c_auto*` macros which
may lead to resource leakages. The `c_auto*`- macros are implemented as one-time executed **for-loops**,
so any `return` or `break` appearing within such a block will lead to resource leaks, as it will disable
the cleanup/drop method to be called. A `break` may originally be intended to break a loop or switch
outside the `c_auto` scope.

NOTE: One must always make sure to unwind temporary allocated resources before a `return` in C. However, by using `c_auto*`-macros,
- it is much easier to automatically detect misplaced return/break between resource acquisition and destruction.
- it prevents forgetting to call the destructor at the end.

The **checkauto** utility will report any misusages. The following example shows how to correctly break/return
from a `c_auto` scope:
```c
int flag = 0;
for (int i = 0; i<n; ++i) {
    c_auto (cstr, text)
    c_auto (List, list)
    {
        for (int j = 0; j<m; ++j) {
            List_push_back(&list, i*j);
            if (cond1())
                break;  // OK: breaks current for-loop only
        }
        // WRONG:
        if (cond2())
            break;      // checkauto ERROR! break inside c_auto.

        if (cond3())
            return -1;  // checkauto ERROR! return inside c_auto

        // CORRECT:
        if (cond2()) {
            flag = 1;   // flag to break outer for-loop
            continue;   // cleanup and leave c_auto block
        }
        if (cond3()) {
            flag = -1;  // return -1
            continue;   // cleanup and leave c_auto block
        }
        ...
    }
    // do the return/break outside of c_auto
    if (flag < 0) return flag;
    else if (flag > 0) break;
    ...
}
```