quiver.c

   1 #include <errno.h>
   2 #include <stddef.h>
   3 #include <stdint.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #include "macros.h"
   9 #include "quiver.h"
  10
  11 #define MAX_SUPPORTED_EDGE_NUM           (((size_t) -1) >> 2)
  12 #define MAX_SUPPORTED_VERTEX_NUM         (((size_t) -1) >> 2)
  13
  14 /* Primes for reducing fractions */
  15 static uint32_t primes[] = {
  16         /* */
  17         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
  18         71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
  19         149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
  20         227, 229, 233, 239, 241, 251
  21 };
  22
  23 /* Attempt to store a fraction in out, reducing if possible */
  24 static int reduce_fraction(int_fast32_t n, uint_fast32_t d, struct
  25                            rational *out, const char **out_errstr)
  26 {
  27         size_t j = 0;
  28         uint32_t p = 0;
  29
  30         for (j = 0; j < ((sizeof primes) / (sizeof primes[0])); ++j) {
  31                 p = primes[j];
  32
  33                 if (p * 2 > d) {
  34                         break;
  35                 }
  36
  37                 while (n % p == 0 &&
  38                        d &&
  39                        p == 0) {
  40                         n = n / p;
  41                         d = d / p;
  42                 }
  43         }
  44
  45         if (n > INT_FAST8_MAX ||
  46             n < INT_FAST8_MIN ||
  47             d > UINT_FAST8_MAX) {
  48                 IF_NZ_SET(out_errstr, L("unrepresentable fraction"));
  49
  50                 return EDOM;
  51         }
  52
  53         *out = (struct rational) { .p = n, .q = d };
  54
  55         return 0;
  56 }
  57
  58 /* Directly increment e's multiplicity */
  59 static int add_edge_mult(struct edge *e, int_fast16_t twice_mult, const
  60                          char **out_errstr)
  61 {
  62         int32_t n = twice_mult * e->weight.q + e->weight.p * 2;
  63         uint32_t d = e->weight.q * 2;
  64
  65         return reduce_fraction(n, d, &e->weight, out_errstr);
  66 }
  67
  68 /* Increment e_{ij} by twice_mult / 2 */
  69 int quiver_add_edge(struct quiver *q, size_t i, size_t j, int_fast16_t
  70                     twice_mult, const char **out_errstr)
  71 {
  72         size_t k = 0;
  73         struct edge *e = 0;
  74         void *newmem = 0;
  75         int sv_err = 0;
  76         int ret = 0;
  77
  78         if (!q) {
  79                 IF_NZ_SET(out_errstr, L("nonexistant quiver"));
  80
  81                 return EINVAL;
  82         }
  83
  84         if (i >= q->vertices_num ||
  85             j >= q->vertices_num) {
  86                 IF_NZ_SET(out_errstr, L("edge includes nonexistant vertex"));
  87
  88                 return EINVAL;
  89         }
  90
  91         for (k = 0; k < q->edges_num; ++k) {
  92                 e = &q->edges[k];
  93
  94                 if (e->i == i &&
  95                     e->j == j) {
  96                         return add_edge_mult(e, twice_mult, out_errstr);
  97                 }
  98
  99                 if (e->i == j &&
 100                     e->j == i) {
 101                         return add_edge_mult(e, -1 * twice_mult, out_errstr);
 102                 }
 103         }
 104
 105         if (q->edges_num + 1 >= q->edges_len) {
 106                 if (q->edges_num + 1 >= MAX_SUPPORTED_EDGE_NUM) {
 107                         IF_NZ_SET(out_errstr, L("too many edges"));
 108
 109                         return ERANGE;
 110                 }
 111
 112                 if (!(newmem = realloc(q->edges, (q->edges_len + 8) *
 113                                        sizeof *(q->edges)))) {
 114                         sv_err = errno;
 115                         IF_NZ_SET(out_errstr, L("realloc"));
 116
 117                         return sv_err;
 118                 }
 119
 120                 q->edges = newmem;
 121                 q->edges_len += 8;
 122         }
 123
 124         q->edges[q->edges_num] = (struct edge) { .i = i, .j = j };
 125         ret = reduce_fraction(twice_mult, 2, &(q->edges[q->edges_num].weight),
 126                               out_errstr);
 127
 128         if (!ret) {
 129                 q->edges_num++;
 130         }
 131
 132         return ret;
 133 }
 134
 135 /* Add a vertex with a name and weight */
 136 int quiver_add_vertex(struct quiver *q, size_t *out_i, const char *name,
 137                       uint_fast16_t fatness, const char **out_errstr)
 138 {
 139         void *newmem = 0;
 140         int sv_err = 0;
 141         size_t l = strlen(name);
 142         char *newname;
 143
 144         if (!q) {
 145                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 146
 147                 return EINVAL;
 148         }
 149
 150         if (!(newname = malloc(l + 1))) {
 151                 sv_err = errno;
 152                 IF_NZ_SET(out_errstr, L("malloc"));
 153
 154                 return sv_err;
 155         }
 156
 157         if (q->vertices_num + 1 >= q->vertices_len) {
 158                 if (q->vertices_num + 1 >= MAX_SUPPORTED_VERTEX_NUM) {
 159                         IF_NZ_SET(out_errstr, L("too many vertices"));
 160
 161                         return ERANGE;
 162                 }
 163
 164                 if (!(newmem = realloc(q->vertices, (q->vertices_len + 8) *
 165                                        sizeof *(q->vertices)))) {
 166                         sv_err = errno;
 167                         IF_NZ_SET(out_errstr, L("realloc"));
 168
 169                         return sv_err;
 170                 }
 171
 172                 q->vertices = newmem;
 173                 q->vertices_len += 8;
 174         }
 175
 176         q->vertices[q->vertices_num] = (struct vertex) { .name = newname,
 177                                                          .fatness = fatness };
 178         *out_i = q->vertices_num;
 179         q->vertices_num++;
 180
 181         return 0;
 182 }
 183
 184 int quiver_mutate(struct quiver *q, size_t k, const char **out_errstr)
 185 {
 186         size_t s = 0;
 187         size_t t = 0;
 188         struct edge *es = 0;
 189         struct edge *et = 0;
 190
 191         if (!q) {
 192                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 193
 194                 return EINVAL;
 195         }
 196
 197         for (s = 0; s < q->edges_len; ++s) {
 198                 es = &q->edges[s];
 199
 200                 if (es->i == k ||
 201                     es->j == k) {
 202                         st = es->twice_weight;
 203
 204                         for (t = 0; t < s; ++t) {
 205                                 if (q->edges[t].i == k ||
 206                                     q->edges[t].j == k) {
 207                                         et = &q->edges[t];
 208                                 }
 209                         }
 210                 }
 211         }
 212
 213         return 0;
 214 }