common.c (2092B)
1 #include "common.h" 2 3 static inline void order_interval(iv_t *iv) { 4 if (iv->lb > iv->ub) { 5 uint64_t tmp = iv->ub; 6 iv->ub = iv->lb; 7 iv->lb = tmp; 8 } 9 } 10 11 static inline void order_brick(brick_t *b) { 12 size_t i; 13 for (i = 0; i < 3; i++) 14 order_interval(&(b->ivs[i])); 15 } 16 17 static int brick_cmp_z(const void *a, const void *b) { 18 const brick_t *aa = (const brick_t *)a; 19 const brick_t *bb = (const brick_t *)b; 20 21 return aa->ivs[2].lb < bb->ivs[2].lb ? -1 : 1; 22 } 23 24 void sort_bricks(brick_t *bricks, const size_t n) { 25 qsort(bricks, n, sizeof(bricks[0]), brick_cmp_z); 26 } 27 28 void read_bricks(brick_t *bricks, char **lines, const size_t nlines) { 29 size_t i; 30 char *cp; 31 32 for (i = 0; i < nlines; i++) { 33 cp = lines[i]; 34 cp = sread_next_u64(&bricks[i].ivs[0].lb, cp); 35 assert(cp != NULL); 36 cp = sread_next_u64(&bricks[i].ivs[1].lb, cp); 37 assert(cp != NULL); 38 cp = sread_next_u64(&bricks[i].ivs[2].lb, cp); 39 assert(cp != NULL); 40 cp = sread_next_u64(&bricks[i].ivs[0].ub, cp); 41 assert(cp != NULL); 42 cp = sread_next_u64(&bricks[i].ivs[1].ub, cp); 43 assert(cp != NULL); 44 cp = sread_next_u64(&bricks[i].ivs[2].ub, cp); 45 46 order_brick(&bricks[i]); 47 } 48 } 49 50 static inline int iv_nei(const iv_t *a, const iv_t *b) { 51 return (a->lb <= b->ub) && (b->lb <= a->ub); 52 } 53 54 int brick_nei(const brick_t *a, const brick_t *b) { 55 return iv_nei(&(a->ivs[0]), &(b->ivs[0])) && 56 iv_nei(&(a->ivs[1]), &(b->ivs[1])) && 57 iv_nei(&(a->ivs[2]), &(b->ivs[2])); 58 } 59 60 void gravitize(brick_t *a) { 61 a->ivs[2].lb--; 62 a->ivs[2].ub--; 63 } 64 65 int may_gravitize(const brick_t *a, const brick_t *landed, 66 const size_t nlanded) { 67 size_t i; 68 69 if (a->ivs[2].lb <= 1) 70 return 0; 71 72 brick_t b = *a; 73 gravitize(&b); 74 75 for (i = 0; i < nlanded; i++) { 76 if (brick_nei(&b, &landed[i])) 77 return 0; 78 } 79 80 return 1; 81 } 82 83 void gravitize_all(brick_t *bricks, const size_t n) { 84 // assume sorted by l.b. on z, increasingly 85 size_t i; 86 87 for (i = 0; i < n; i++) { 88 while (may_gravitize(&bricks[i], bricks, i)) { 89 gravitize(&bricks[i]); 90 } 91 } 92 }