Added cstack and cpque (priority queue) + test.

4 files changed, 223 insertions, 178 deletions

diff --git a/include/stc/cpque.h b/include/stc/cpque.h
index a9bc6b56..9b2939a7 100644
--- a/include/stc/cpque.h
+++ b/include/stc/cpque.h
@@ -21,126 +21,111 @@
  * SOFTWARE.

  */

 

-/*  Priority-Queue adapter (implemented as heap), default uses cvec.

-

-    #include <stc/crandom.h>

-    #include <stc/cpque.h>

-    using_cvec(f, float);

-    using_cpque(f, cvec_f, -c_default_compare); // min-heap (increasing values)

+#ifndef CPQUE_H_INCLUDED

+#define CPQUE_H_INCLUDED

+#include <stdlib.h>

+#include "ccommon.h"

+#include "forward.h"

+#endif

 

-    int main() {

-        stc64_t rng = stc64_init(1234);

-        stc64_uniformf_t dist = stc64_uniformf_init(10.0f, 100.0f);

+#define i_module cpque

+#include "template.h"

 

-        c_forvar (cpque_f queue = cpque_f_init(), cpque_f_del(&queue))

-        {

-            // Push ten million random numbers onto the queue.

-            for (int i=0; i<10000000; ++i)

-                cpque_f_push(&queue, stc64_uniformf(&rng, dist));

+#if !defined i_fwd

+   cx_deftypes(_c_cpque_types, Self, i_val);

+#endif

+typedef i_valraw cx_rawvalue_t;

 

-            // Extract the 100 smallest.

-            for (int i=0; i<100; ++i) {

-                printf("%f ", *cpque_f_top(queue));

-                cpque_f_pop(&queue);

-            }

-        }

-    }

-*/

-#ifndef CPQUEUE_H_INCLUDED

-#define CPQUEUE_H_INCLUDED

+STC_API void cx_memb(_make_heap)(Self* self);

+STC_API void cx_memb(_erase_at)(Self* self, size_t idx);

+STC_API void cx_memb(_push)(Self* self, cx_value_t value);

+STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n);

+STC_API Self cx_memb(_clone)(Self q);

 

-#include "cvec.h"

+STC_INLINE Self cx_memb(_init)(void) 

+    { return (Self){0, 0, 0}; }

+STC_INLINE void cx_memb(_clear)(Self* self) 

+    { while (self->size) i_valdel(&self->data[--self->size]); }

+STC_INLINE size_t cx_memb(_size)(Self q)

+    { return q.size; }

+STC_INLINE bool cx_memb(_empty)(Self q)

+    { return !q.size; }

+STC_INLINE size_t cx_memb(_capacity)(Self q)

+    { return q.capacity; }

+STC_INLINE void cx_memb(_pop)(Self* self)

+    { cx_memb(_erase_at)(self, 0); }

+STC_INLINE cx_value_t* cx_memb(_top)(const Self* self)

+    { return &self->data[0]; }

+    

+STC_INLINE void cx_memb(_push_back_)(Self* self, cx_value_t value) {

+    if (self->size == self->capacity)

+        self->data = realloc(self->data, (self->capacity = self->size*3/2 + 4)*sizeof value);

+    self->data[ self->size++ ] = value;

+}

+STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw)

+    { cx_memb(_push)(self, i_valfrom(raw)); }

 

-#define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__)

+STC_INLINE void cx_memb(_del)(Self* self)

+    { cx_memb(_clear)(self); free(self->data); }

+    

+STC_INLINE int cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) {

+    cx_rawvalue_t rx = i_valto(x), ry = i_valto(y);

+    return i_cmp(&rx, &ry);

+}

 

-#define using_cpque_2(X, ctype) \

-            _c_using_cpque(cpque_##X, ctype, ctype##_value_compare)

-#define using_cpque_3(X, ctype, i_cmp) \

-            _c_using_cpque(cpque_##X, ctype, i_cmp)

+/* -------------------------- IMPLEMENTATION ------------------------- */

+#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp)

 

-#define _c_using_cpque(Self, ctype, i_cmp) \

-    typedef ctype Self; \

-    typedef ctype##_value_t cx_value_t; \

-    typedef ctype##_rawvalue_t cx_rawvalue_t; \

-\

-    STC_INLINE Self           cx_memb(_init)(void) { return ctype##_init(); } \

-    STC_INLINE Self           cx_memb(_clone)(Self pq) { return ctype##_clone(pq); } \

-    STC_INLINE cx_value_t cx_memb(_value_clone)(cx_value_t val) \

-                                { return ctype##_value_clone(val); } \

-    STC_INLINE void         cx_memb(_clear)(Self* self) {ctype##_clear(self); } \

-    STC_INLINE void         cx_memb(_del)(Self* self) {ctype##_del(self); } \

-\

-    STC_INLINE size_t       cx_memb(_size)(Self pq) { return ctype##_size(pq); } \

-    STC_INLINE bool         cx_memb(_empty)(Self pq) { return ctype##_empty(pq); } \

-    \

-    STC_API void            cx_memb(_make_heap)(Self* self); \

-    STC_API void            cx_memb(_erase_at)(Self* self, size_t idx); \

-    STC_INLINE \

-    const cx_value_t*     cx_memb(_top)(const Self* self) { return &self->data[0]; } \

-    STC_INLINE void         cx_memb(_pop)(Self* self) { cx_memb(_erase_at)(self, 0); } \

-    \

-    STC_API void            cx_memb(_push)(Self* self, cx_value_t value); \

-    STC_INLINE void         cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \

-                                { cx_memb(_push)(self, ctype##_value_fromraw(raw)); } \

-    STC_API void            cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n); \

-\

-    _c_implement_cpque(Self, ctype, i_cmp) \

-    struct stc_trailing_semicolon

+STC_API void

+cx_memb(_sift_down_)(cx_value_t* arr, size_t i, size_t n) {

+    size_t r = i, c = i << 1;

+    while (c <= n) {

+        c += (c < n && i_cmp(&arr[c], &arr[c + 1]) < 0);

+        if (i_cmp(&arr[r], &arr[c]) < 0) {

+            cx_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp;

+        } else

+            return;

+        c <<= 1;

+    }

+}

 

+STC_API void

+cx_memb(_make_heap)(Self* self) {

+    size_t n = cx_memb(_size)(*self);

+    cx_value_t *arr = self->data - 1;

+    for (size_t k = n >> 1; k != 0; --k)

+        cx_memb(_sift_down_)(arr, k, n);

+}

 

-/* -------------------------- IMPLEMENTATION ------------------------- */

+STC_API Self cx_memb(_clone)(Self q) { 

+    Self out = {(cx_value_t*) c_malloc(q.size*sizeof(cx_value_t)), q.size, q.size};

+    for (cx_value_t *a = out.data, *b = a + q.size; a != b; ++a) *a = i_valfrom(i_valto(q.data++));

+    return out;

+}

 

-#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

+STC_API void

+cx_memb(_erase_at)(Self* self, size_t idx) {

+    size_t n = cx_memb(_size)(*self) - 1;

+    self->data[idx] = self->data[n];

+    --self->size;

+    cx_memb(_sift_down_)(self->data - 1, idx + 1, n);

+}

 

-#define _c_implement_cpque(Self, ctype, i_cmp) \

-\

-    STC_INLINE void \

-    cx_memb(_sift_down_)(cx_value_t* arr, size_t i, size_t n) { \

-        size_t r = i, c = i << 1; \

-        while (c <= n) { \

-            c += (c < n && i_cmp(&arr[c], &arr[c + 1]) < 0); \

-            if (i_cmp(&arr[r], &arr[c]) < 0) { \

-                cx_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \

-            } else \

-                return; \

-            c <<= 1; \

-        } \

-    } \

-\

-    STC_API void \

-    cx_memb(_make_heap)(Self* self) { \

-        size_t n = cx_memb(_size)(*self); \

-        cx_value_t *arr = self->data - 1; \

-        for (size_t k = n >> 1; k != 0; --k) \

-            cx_memb(_sift_down_)(arr, k, n); \

-    } \

-\

-    STC_API void \

-    cx_memb(_erase_at)(Self* self, size_t idx) { \

-        size_t n = cx_memb(_size)(*self) - 1; \

-        self->data[idx] = self->data[n]; \

-        ctype##_pop_back(self); \

-        cx_memb(_sift_down_)(self->data - 1, idx + 1, n); \

-    } \

-\

-    STC_API void \

-    cx_memb(_push)(Self* self, cx_value_t value) { \

-        ctype##_push_back(self, value); /* sift-up the value */ \

-        size_t n = cx_memb(_size)(*self), c = n; \

-        cx_value_t *arr = self->data - 1; \

-        for (; c > 1 && i_cmp(&arr[c >> 1], &value) < 0; c >>= 1) \

-            arr[c] = arr[c >> 1]; \

-        if (c != n) arr[c] = value; \

-    } \

-\

-    STC_API void \

-    cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) { \

-        for (size_t i = 0; i < n; ++i) \

-            cx_memb(_push)(self, ctype##_value_fromraw(arr[i])); \

-    } \

+STC_API void

+cx_memb(_push)(Self* self, cx_value_t value) {

+    cx_memb(_push_back_)(self, value); /* sift-up the value */

+    size_t n = cx_memb(_size)(*self), c = n;

+    cx_value_t *arr = self->data - 1;

+    for (; c > 1 && i_cmp(&arr[c >> 1], &value) < 0; c >>= 1)

+        arr[c] = arr[c >> 1];

+    if (c != n) arr[c] = value;

+}

 

-#else

-#define _c_implement_cpque(Self, ctype, i_cmp)

-#endif

+STC_API void

+cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) {

+    for (size_t i = 0; i < n; ++i)

+        cx_memb(_push)(self, i_valfrom(arr[i]));

+}

 

 #endif

+#include "template.h"

diff --git a/include/stc/cstack.h b/include/stc/cstack.h
index 30fc4f71..b754525f 100644
--- a/include/stc/cstack.h
+++ b/include/stc/cstack.h
@@ -20,63 +20,60 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  * SOFTWARE.

  */

+

 #ifndef CSTACK_H_INCLUDED

 #define CSTACK_H_INCLUDED

+#include <stdlib.h>

+#include "ccommon.h"

+#include "forward.h"

+#endif

 

-/*  Stack adapter, default uses cvec.

-

-    #include <stc/cstack.h>

-    #include <stdio.h>

-

-    using_cvec(i, int);

-    using_cstack(i, cvec_i);

+#define i_module cstack

+#include "template.h"

 

-    int main() {

-        c_forvar (cstack_i stack = cstack_i_init(), cstack_i_del(&stack))

-        {

-            for (int i=0; i<100; ++i)

-                cstack_i_push(&stack, i*i);

+#if !defined i_fwd

+   cx_deftypes(_c_cstack_types, Self, i_val);

+#endif

+typedef i_valraw cx_rawvalue_t;

 

-            for (int i=0; i<90; ++i)

-                cstack_i_pop(&stack);

+STC_INLINE Self cx_memb(_init)(void) 

+    { return (Self){0, 0, 0}; }

+STC_INLINE void cx_memb(_clear)(Self* self) 

+    { while (self->size) i_valdel(&self->data[--self->size]); }

+STC_INLINE size_t cx_memb(_size)(Self v)

+    { return v.size; }

+STC_INLINE bool cx_memb(_empty)(Self v)

+    { return !v.size; }

+STC_INLINE size_t cx_memb(_capacity)(Self v)

+    { return v.capacity; }

+STC_INLINE void cx_memb(_pop)(Self* self)

+    { --self->size; }

+STC_INLINE cx_value_t* cx_memb(_top)(const Self* self)

+    { return &self->data[self->size - 1]; }

+STC_INLINE void cx_memb(_push)(Self* self, cx_value_t value) {

+    if (self->size == self->capacity)

+        self->data = realloc(self->data, (self->capacity = self->size*3/2 + 4)*sizeof value);

+    self->data[ self->size++ ] = value;

+}

+STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw)

+    { cx_memb(_push)(self, i_valfrom(raw)); }

 

-            printf("top: %d\n", *cstack_i_top(&stack));

-        }

-    }

-*/

-#include "cvec.h"

+STC_INLINE void cx_memb(_del)(Self* self) {

+    size_t i = self->size;

+    while (i--) i_valdel(&self->data[i]);

+    free(self->data);

+}

 

-#define using_cstack(X, ctype) \

-    _c_using_cstack(cstack_##X, ctype)

+STC_INLINE cx_iter_t cx_memb(_begin)(const Self* self)

+    { return c_make(cx_iter_t){self->data}; }

+STC_INLINE cx_iter_t cx_memb(_end)(const Self* self)

+    { return c_make(cx_iter_t){self->data + self->size}; }

+STC_INLINE void cx_memb(_next)(cx_iter_t* it) {++it->ref; }

 

-#define _c_using_cstack(Self, ctype) \

-    typedef ctype Self; \

-    typedef ctype##_value_t cx_value_t; \

-    typedef ctype##_rawvalue_t cx_rawvalue_t; \

-    typedef ctype##_iter_t cx_iter_t; \

-\

-    STC_INLINE Self               cx_memb(_init)(void) { return ctype##_init(); } \

-    STC_INLINE Self               cx_memb(_clone)(Self st) { return ctype##_clone(st); } \

-    STC_INLINE cx_value_t     cx_memb(_value_clone)(cx_value_t val) \

-                                    { return ctype##_value_clone(val); } \

-    STC_INLINE void             cx_memb(_clear)(Self* self) {ctype##_clear(self); } \

-    STC_INLINE void             cx_memb(_del)(Self* self) {ctype##_del(self); } \

-\

-    STC_INLINE size_t           cx_memb(_size)(Self st) { return ctype##_size(st); } \

-    STC_INLINE bool             cx_memb(_empty)(Self st) { return ctype##_empty(st); } \

-    STC_INLINE cx_value_t*    cx_memb(_top)(const Self* self) { return ctype##_back(self); } \

-\

-    STC_INLINE void             cx_memb(_pop)(Self* self) {ctype##_pop_back(self); } \

-    STC_INLINE void             cx_memb(_push)(Self* self, ctype##_value_t value) \

-                                    {ctype##_push_back(self, value); } \

-    STC_INLINE void             cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \

-                                    {ctype##_emplace_back(self, raw); } \

-    STC_INLINE void             cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) \

-                                    {ctype##_emplace_items(self, arr, n); } \

-\

-    STC_INLINE cx_iter_t      cx_memb(_begin)(const Self* self) { return ctype##_begin(self); } \

-    STC_INLINE cx_iter_t      cx_memb(_end)(const Self* self) { return ctype##_end(self); } \

-    STC_INLINE void             cx_memb(_next)(cx_iter_t* it) {ctype##_next(it); } \

-    struct stc_trailing_semicolon

+STC_INLINE Self cx_memb(_clone)(Self v) {

+    Self out = {(cx_value_t*) c_malloc(v.size*sizeof(cx_value_t)), v.size, v.size};

+    for (cx_value_t *a = out.data, *b = a + v.size; a != b; ++a) *a = i_valfrom(i_valto(v.data++));

+    return out;

+}

 

-#endif

+#include "template.h"

diff --git a/include/stc/forward.h b/include/stc/forward.h
index c2ac5e39..78bc9173 100644
--- a/include/stc/forward.h
+++ b/include/stc/forward.h
@@ -23,6 +23,8 @@
 #ifndef STC_FORWARD_H_INCLUDED

 #define STC_FORWARD_H_INCLUDED

 

+#include <stddef.h>

+

 #define forward_carray2(TAG, VAL) _c_carray2_types(carray2##TAG, VAL)

 #define forward_carray3(TAG, VAL) _c_carray3_types(carray2##TAG, VAL)

 #define forward_cdeq(TAG, VAL) _c_cdeq_types(cdeq_##TAG, VAL)

@@ -32,9 +34,9 @@
 #define forward_cset(TAG, KEY) _c_chash_types(cset_##TAG, cset, KEY, KEY, c_false, c_true)

 #define forward_csset(TAG, KEY) _c_aatree_types(csset_##TAG, KEY, KEY, c_false, c_true)

 #define forward_csptr(TAG, VAL) _csptr_types(csptr_##TAG, VAL)

-#define forward_cpque(TAG, ctype) _c_cpque_types(cpque_##TAG, ctype)

-#define forward_cqueue(TAG, ctype) _c_cqueue_types(cqueue_##TAG, ctype)

-#define forward_cstack(TAG, ctype) _c_cstack_types(cstack_##TAG, ctype)

+#define forward_cpque(TAG, VAL) _c_cpque_types(cpque_##TAG, VAL)

+#define forward_cstack(TAG, VAL) _c_cstack_types(cstack_##TAG, VAL)

+//#define forward_cqueue(TAG, VAL) _c_cqueue_types(cqueue_##TAG, VAL)

 #define forward_cvec(TAG, VAL) _c_cvec_types(cvec_##TAG, VAL)

 

 #ifndef MAP_SIZE_T

@@ -131,22 +133,20 @@
         long* use_count; \

     } SELF

 

-#define _c_cpque_types(SELF, ctype) \

-    typedef ctype##_value_t SELF##_value_t; \

-    typedef ctype##_rawvalue_t SELF##_rawvalue_t; \

-    typedef ctype SELF

-

-#define _c_cqueue_types(SELF, ctype) \

-    typedef ctype##_value_t SELF##_value_t; \

-    typedef ctype##_rawvalue_t SELF##_rawvalue_t; \

-    typedef ctype##_iter_t SELF##_iter_t; \

-    typedef struct { ctype rep; size_t size; } SELF

+#define _c_cstack_types(SELF, VAL) \

+    typedef VAL SELF##_value_t; \

+    typedef struct { SELF##_value_t *ref; } SELF##_iter_t; \

+    typedef struct SELF { \

+        SELF##_value_t* data; \

+        size_t size, capacity; \

+    } SELF

 

-#define _c_cstack_types(SELF, ctype) \

-    typedef ctype##_value_t SELF##_value_t; \

-    typedef ctype##_rawvalue_t SELF##_rawvalue_t; \

-    typedef ctype##_iter_t SELF##_iter_t; \

-    typedef ctype SELF

+#define _c_cpque_types(SELF, VAL) \

+    typedef VAL SELF##_value_t; \

+    typedef struct SELF { \

+        SELF##_value_t* data; \

+        size_t size, capacity; \

+    } SELF

 

 #define _c_cvec_types(SELF, VAL) \

     typedef VAL SELF##_value_t; \

diff --git a/include/stc/test_new_cpque.c b/include/stc/test_new_cpque.c
new file mode 100644
index 00000000..d9d66c09
--- /dev/null
+++ b/include/stc/test_new_cpque.c
@@ -0,0 +1,63 @@
+#include <stc/forward.h>

+

+forward_cpque(pnt, struct Point);

+

+struct MyStruct {

+    cpque_pnt priority_queue;

+    int id;

+};

+

+#define i_val int

+#include "cstack.h"

+

+#define i_val int

+#include "cpque.h"

+

+struct Point { int x, y; } typedef Point;

+

+int Point_cmp(const Point* a, const Point* b) {

+    int c = c_default_compare(&a->x, &b->x);

+    return c ? c : c_default_compare(&a->y, &b->y);

+}

+#define f_tag pnt  // f: was forward declared.

+#define i_val Point

+#define i_cmp Point_cmp

+#include "cpque.h"

+

+#include <stdio.h>

+

+int main()

+{

+    cstack_int istk = cstack_int_init();

+    cstack_int_push(&istk, 123);

+    cstack_int_push(&istk, 321);

+    // print

+    c_foreach (i, cstack_int, istk)

+        printf(" %d", *i.ref);

+    cstack_int_del(&istk);

+    puts("");

+

+    cpque_pnt pque = cpque_pnt_init();

+    cpque_pnt_push(&pque, (Point){23, 80});

+    cpque_pnt_push(&pque, (Point){12, 32});

+    cpque_pnt_push(&pque, (Point){54, 74});

+    cpque_pnt_push(&pque, (Point){12, 62});

+    // print

+    while (!cpque_pnt_empty(pque)) {

+        cpque_pnt_value_t *v = cpque_pnt_top(&pque);

+        printf(" (%d,%d)", v->x, v->y);

+        cpque_pnt_pop(&pque);

+    }

+    // free

+    cpque_pnt_del(&pque);

+    puts("");

+

+    cpque_int ique = cpque_int_init();

+    cpque_int_push(&ique, 123);

+    cpque_int_push(&ique, 321);

+    // print

+    for (int i=0; i<cpque_int_size(ique); ++i)

+        printf(" %d", ique.data[i]);

+    cpque_int_del(&ique);

+    puts("");

+}