1#ifndef __LB_H__
2#define __LB_H__
3
4#include <stdint.h>
5#include <stddef.h>
6#include <stdbool.h>
7
8// Logic Bitmask
9// Data structure for solving bipartite perfect matching
10
11#define LB_SIZE ((size_t) 256)
12#define LB_BM_SIZE (LB_SIZE / 64)
13struct lb {
14    struct lb_half {
15        uint64_t bs[LB_SIZE][LB_BM_SIZE];
16        uint64_t paired[LB_BM_SIZE];
17        uint64_t pair[LB_SIZE];
18    } halfs[2];
19    uint16_t x_root[LB_SIZE];
20    bool x_has_equivs[LB_SIZE];
21    uint64_t x_equivs[LB_SIZE][LB_BM_SIZE];
22
23    size_t size;
24    bool dirty;
25    bool marked;
26};
27
28void lb_init(struct lb * lb, size_t n);
29void lb_init_equivalent(struct lb * lb, size_t x0, size_t x1);
30
31void lb_mark_positive(struct lb * lb, size_t x, size_t y);
32void lb_mark_negative(struct lb * lb, size_t x, size_t y);
33
34void lb_deduce(struct lb * lb);
35
36#ifdef LB_DEBUG 
37void lb_selftest(void);
38#endif
39
40#endif