Chrinkus / libcgs

A C library of data structures and algorithms
MIT License
1 stars 0 forks source link

Develop a Plan for Iterators #21

Open Chrinkus opened 1 year ago

Chrinkus commented 1 year ago

Iterators

Iterators have been brealy thought of up to this point. Vectors hardly need them, the RBT usage hasn't required one (yet!), heaps don't need them, etc.

Functionality

The only real need for iterators is a next() function. Beyond this, reverse iterators may be desired as well as bi-directional iterators. The former I would often use with vectors or ordered sets for sure. Use-cases for the latter..? Maybe a binary search in a linked-list? Who even wants to do that? Either way, a reverse iterator would be the struct type and it would still just need a next() function.

Let's stick with next() being the main goal. If a serious case can be made for the others then I'll revisit them later.

Naming

Naming can get out of hand. I needed an iterator in the hash table and it looked like this:

struct cgs_hashtab_iter_mut {
    struct cgs_bucket** tab;
    struct cgs_bucket** end;
    struct cgs_bucket* cur;
};

The ridiculousness of the excessive name-spacing combined with the looseness of the bucket type is a mess. Then function calls add more tags:

void*
cgs_hashtab_iter_mut_next(struct cgs_hashtab_iter_mut* it);

This gets long and affects usability. Instead I propose making "iter" the primary tag and shortening the rest:

struct cgs_iter_ht;
struct cgs_iter_ht_mut;

struct cgs_iter_vec;
struct cgs_iter_vec_mut;

struct cgs_iter_rbt;
struct cgs_iter_rbt_mut;

Is two characters too short to identify it as a "hashtab" iterator? How about "htab"?

struct cgs_iter_htab;
struct cgs_iter_htab_mut;

struct cgs_iter_hset;
struct cgs_iter_hset_mut;

Location

Where should iterators go? In their own modules that get included with each data structure? I already do that with variants in hash-tables and rb-trees so the precedent is already set. Testing would depend on the respective data structure but that falls in line with my new desire to prefer end-to-end testing.

Chrinkus commented 1 year ago

The previous assertion that vectors did not need iterators is a joke! Consider the following:

// for-loopin'
for (size_t i = 0; i < cgs_vector_length(&v); ++i) {
    const int* p = cgs_vector_get(&v, i);
    // use p
}

// iteratin'
struct cgs_iter_vec it = cgs_vector_iter(&v);
while (cgs_iter_vec_next(&v)) {
    const int* p = cgs_iter_vec_get(&it);
}

Hmm.. actually they both look messy..