Create a gist now

Instantly share code, notes, and snippets.

@natsugiri /VEB.cpp
Last active Oct 12, 2016

//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
// VEB
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
struct VEB_BASE {
static const unsigned INVALID = ~0;
unsigned mi, ma;
VEB_BASE() : mi(INVALID), ma(0) { }
inline unsigned min() const { return mi; }
inline unsigned max() const { return mi <= ma? ma: INVALID; }
inline bool empty() const { return ma < mi; }
};
// van Emde Boas Tree 2P-bit (upper P-bit and lower P-bit, 0 ~ 2^(2P)-1);
template<const unsigned P> struct VEB_NODE : VEB_BASE {
typedef VEB_NODE<(P>>1)> Child;
int ch_len;
Child aux, *ch;
VEB_NODE() : VEB_BASE(), ch_len(0), aux(), ch(NULL) { }
VEB_NODE(int n_) : VEB_BASE(), ch_len(0), aux(), ch(NULL) {
int r = n_ & ((1u<<P) - 1u);
ch_len = (n_ >> P) + (bool)r;
ch = new Child[ch_len];
if (r) {
for (int i=0; i<ch_len-1; i++) ch[i] = Child(1u << P);
ch[ch_len-1] = Child(r);
} else {
for (int i=0; i<ch_len; i++) ch[i] = Child(1u << P);
}
aux = Child(ch_len);
}
unsigned next(unsigned u) const {
if (ma <= u) return INVALID;
if (u < mi) return mi;
unsigned hi = u >> P, lo = u & ((1u << P) - 1u);
if (lo < ch[hi].ma) return (hi << P) | ch[hi].next(lo);
hi = aux.next(hi);
return (hi << P) | ch[hi].mi;
}
unsigned prev(unsigned u) const {
if (u <= mi) return INVALID;
if (ma < u) return ma;
unsigned hi = u >> P, lo = u & ((1 << P) - 1u);
if (ch[hi].mi < lo) return (hi << P) | ch[hi].prev(lo);
hi = aux.prev(hi);
return hi == INVALID? mi: (hi << P) | ch[hi].ma;
}
bool find(unsigned u) const {
return !empty() && (u == min() || ch[u >> P].find(u & ((1u << P) - 1u)));
}
bool insert(unsigned u) {
if (empty()) {
mi = ma = u;
return true;
}
if (u < mi) swap(mi, u);
if (mi < u) {
unsigned hi = u >> P, lo = u & ((1u << P) - 1u);
if (ma < u) ma = u;
if (ch[hi].empty()) aux.insert(hi);
return ch[hi].insert(lo);
}
return false;
}
bool erase(unsigned u) {
if (empty()) {
return false;
} else if (mi == u) {
if (ma == u) {
mi = INVALID; ma = 0;
return true;
} else {
mi = u = (aux.mi << P) | ch[aux.mi].mi;
}
}
if (ch[u >> P].erase(u & ((1u << P) - 1u))) {
if (ch[u >> P].empty()) aux.erase(u >> P);
if (ma == u) {
if (aux.empty()) ma = mi;
else ma = (aux.ma << P) | ch[aux.ma].ma;
}
return true;
} else {
return false;
}
}
void clear() {
if (ch) {
for (int i=0; i<ch_len; i++) ch[i].clear();
aux.clear();
delete[] ch; ch = NULL;
}
}
};
// vEB 6-bit (0 ~ 63);
template<> struct VEB_NODE<3> : VEB_BASE {
unsigned long long mask;
VEB_NODE() : VEB_BASE(), mask(0) { }
VEB_NODE(int n_) : VEB_BASE(), mask(0) { }
static inline unsigned ctz(unsigned long long u) {
#ifdef __GNUC__
return __builtin_ctzll(u);
#else
// When __builtin_ctzll is not defined;
unsigned n = 0;
if ((u & 0x00000000FFFFFFFFULL) == 0) { u >>= 32; n += 32; }
if ((u & 0x000000000000FFFFULL) == 0) { u >>= 16; n += 16; }
if ((u & 0x00000000000000FFULL) == 0) { u >>= 8; n += 8; }
if ((u & 0x000000000000000FULL) == 0) { u >>= 4; n += 4; }
static const unsigned ctz_4bit[16] = { 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, };
return n + ctz_4bit[u & 0xFULL]; // if u == 0: return 64;
#endif
}
static inline unsigned lg(unsigned long long u) {
#ifdef __GNUC__
return __lg(u);
#else
// When __builtin_clzll and __lg are not defined;
unsigned n = 0;
if (u & 0xFFFFFFFF00000000ULL) { u >>= 32; n += 32; }
if (u & 0x00000000FFFF0000ULL) { u >>= 16; n += 16; }
if (u & 0x000000000000FF00ULL) { u >>= 8; n += 8; }
if (u & 0x00000000000000F0ULL) { u >>= 4; n += 4; }
static const unsigned lg_4bit[16] = { 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, };
return n + lg_4bit[u]; // if u == 0: return 0;
#endif
}
unsigned next(unsigned u) const {
if (ma <= u) return INVALID; // empty or ma <= u;
if (u < mi) return mi;
return ctz(mask & ~((1ULL << (u+1)) - 1));
}
unsigned prev(unsigned u) const {
if (u <= mi) return INVALID; // empty or u <= mi;
if (ma < u) return ma;
unsigned long long k = mask & ((1ULL << u) - 1);
return k? lg(k): mi;
}
bool find(unsigned u) const {
return !empty() && (min() == u || (mask & (1ULL << u)));
}
bool insert(unsigned u) {
if (empty()) {
mi = ma = u;
return true;
}
if (u < mi) swap(mi, u);
if (mi < u) {
if (ma < u) ma = u;
if (mask & (1ULL << u)) return false;
mask |= 1ULL << u;
return true;
}
return false;
}
bool erase(unsigned u) {
if (mi == u) {
if (ma == u) {
mi = INVALID; ma = 0;
return true;
}
mi = ctz(mask); mask &= ~(1ULL << mi);
return true;
} else if (u == ma) {
mask &= ~(1ULL << u);
if (mask) ma = lg(mask);
else ma = mi;
return true;
} else if (mi < u) { // if mi < u < ma;
if (mask & (1ULL << u)) {
mask &= ~(1ULL << u);
return true;
}
}
return false;
}
void clear() { // has nothing to clear;
}
};
// vEB 24-bit;
typedef VEB_NODE<12> VEB;
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// VEB
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment