#define MBid(i) ((i)>>logMB)
#define MBfirst(i) ((i) & (~(MB-1)))
#define MBlast(i) ((i) | (MB-1))
-#define max(a,b) \
- ({ __typeof__ (a) _a = (a); \
- __typeof__ (b) _b = (b); \
- _a > _b ? _a : _b; })
+static int min(int a, int b)
+{
+ return (a <= b) ? a : b;
+}
-#define min(a,b) \
- ({ __typeof__ (a) _a = (a); \
- __typeof__ (b) _b = (b); \
- _a <= _b ? _a : _b; })
-
+static int max(int a, int b)
+{
+ return (a >= b) ? a : b;
+}
pb getpat_preorder(pb *b)
{
pb *p,x,w;
n = b->n;
- il = min((SBid(i) + 1) << logSB,n);
+ il = min((SBid(i) + 1) << logSB, n);
p = &b->B[i>>logD];
while (i<il) {
x = *p++;
while (j>0) {
w = (x >> (D-ETW)) & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
- r = fwdtbl[((rel+ETW)<<ETW)+w];
- if (r<ETW && r<j) {
- if (i+r >= n) return NOTFOUND;
- return i+r;
- }
+ r = fwdtbl[((rel+ETW)<<ETW)+w];
+ if (r<ETW && r<j) {
+ if (i+r >= n) return NOTFOUND;
+ return i+r;
+ }
}
r = min(j,ETW);
- rel -= 2*popcount(w)-r;
+ rel -= (popcount(w) << 1)-r;
x <<= r;
i += r;
j -= r;
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || il-i < ETW) {
- r = max(ETW-j,ETW-(il-i));
- w2 = (1<<r)-1;
+ r = max(ETW-j,ETW-(il-i));
+ w2 = (1<<r)-1;
}
v = minmaxtbl_v[0][w | w2];
if (d + v < rel) {
- if (ith > 0) {
+ if (ith > 0) {
#if 0
- for (r = 0; r < ETW; r++) {
- if (w & 0x80) {
- d++;
- } else {
- d--;
- if (d < rel) break;
- if (d == rel) {
- ith--;
- if (ith == 0) {
- *ans = i + r;
- return FOUND;
- }
- }
- }
- w <<= 1;
- }
- return NOTFOUND;
+ for (r = 0; r < ETW; r++) {
+ if (w & 0x80) {
+ d++;
+ } else {
+ d--;
+ if (d < rel) break;
+ if (d == rel) {
+ ith--;
+ if (ith == 0) {
+ *ans = i + r;
+ return FOUND;
+ }
+ }
+ }
+ w <<= 1;
+ }
+ return NOTFOUND;
#else
- r = childtbl2[rel-d+ETW][ith-1][w];
- if (r >= 0) {
- *ans = i + r;
- return FOUND;
- }
- return NOTFOUND;
+ r = childtbl2[rel-d+ETW][ith-1][w];
+ if (r >= 0) {
+ *ans = i + r;
+ return FOUND;
+ }
+ return NOTFOUND;
#endif
- }
- r = ETW-1-minmaxtbl_i[0][w | w2];
- w2 = (1<<r)-1;
- deg += degtbl2[((rel-d+ETW)<<ETW) + (w & (~w2))];
- *ans = deg;
- return END;
+ }
+ r = ETW-1-minmaxtbl_i[0][w | w2];
+ w2 = (1<<r)-1;
+ deg += degtbl2[((rel-d+ETW)<<ETW) + (w & (~w2))];
+ *ans = deg;
+ return END;
}
if (d + v == rel) {
- r = degtbl[w | w2];
- deg += r;
- if (ith > 0) {
- if (ith <= r) {
- *ans = i + childtbl[((ith-1)<<ETW) + (w | w2)];
- return FOUND;
- }
- ith -= r;
- }
+ r = degtbl[w | w2];
+ deg += r;
+ if (ith > 0) {
+ if (ith <= r) {
+ *ans = i + childtbl[((ith-1)<<ETW) + (w | w2)];
+ return FOUND;
+ }
+ ith -= r;
+ }
}
r = min(j,ETW);
if (m < td) {
r = degree_SB(b,i,n,td-d,°tmp,ith);
if (ith > 0) {
- if (r == NOTFOUND) return NOTFOUND;
- *ans = degtmp;
- return FOUND;
+ if (r == NOTFOUND) return NOTFOUND;
+ *ans = degtmp;
+ return FOUND;
} else {
- *ans = deg + degtmp;
- return END;
+ *ans = deg + degtmp;
+ return END;
}
}
if (m == td) {
if (ith > 0) {
- if (ith <= b->sd[SBid(i)]) break;
- ith -= b->sd[SBid(i)];
+ if (ith <= b->sd[SBid(i)]) break;
+ ith -= b->sd[SBid(i)];
}
deg += b->sd[SBid(i)];
}
if (ith > 0) {
if (r == NOTFOUND) return NOTFOUND;
if (r == FOUND) {
- *ans = degtmp;
- return FOUND;
+ *ans = degtmp;
+ return FOUND;
}
} else {
deg += degtmp;
return CONTINUE;
}
-static int partition_range(int s,int t)
+static void partition_range(int s,int t)
{
int i,j,h;
while (s <= t) {
if (s & h) {
if (s+h-1 <= t) {
- printf("[%d,%d] ",s,s+h-1);
- s += h;
+ printf("[%d,%d] ",s,s+h-1);
+ s += h;
}
} else {
if (s+h > t) break;
} else {
deg += degtmp;
if (d == END) {
- return deg;
+ return deg;
}
}
}
}
if (b->mm[i] == td) {
if (ith > 0) {
- if (ith <= b->md[i]) break;
- ith -= b->md[i];
+ if (ith <= b->md[i]) break;
+ ith -= b->md[i];
}
deg += b->md[i];
}
while (sm <= tm) {
if (sm & h) {
if (sm+h-1 <= tm) {
- //printf("[%d,%d] ",sm,sm+h-1);
- j = sm / h;
- if (b->mm[j] < td) {
- h >>= 1;
- break;
- }
- if (b->mm[j] == td) {
- if (ith > 0) {
- if (ith <= b->md[j]) {
- h >>= 1;
- break;
- }
- ith -= b->md[j];
- }
- deg += b->md[j];
- }
- sm += h;
+ //printf("[%d,%d] ",sm,sm+h-1);
+ j = sm / h;
+ if (b->mm[j] < td) {
+ h >>= 1;
+ break;
+ }
+ if (b->mm[j] == td) {
+ if (ith > 0) {
+ if (ith <= b->md[j]) {
+ h >>= 1;
+ break;
+ }
+ ith -= b->md[j];
+ }
+ deg += b->md[j];
+ }
+ sm += h;
}
} else {
if (sm+h > tm) break;
//printf("[%d,%d] ",sm,sm+h-1);
j = sm / h;
if (ith > 0) {
- if (b->mm[j] >= td) {
- if (b->mm[j] == td) {
- if (ith > b->md[j]) {
- ith -= b->md[j];
- sm += h;
- } else {
- deg += b->md[j];
- }
- } else {
- sm += h;
- }
- }
+ if (b->mm[j] >= td) {
+ if (b->mm[j] == td) {
+ if (ith > b->md[j]) {
+ ith -= b->md[j];
+ sm += h;
+ } else {
+ deg += b->md[j];
+ }
+ } else {
+ sm += h;
+ }
+ }
} else {
- if (b->mm[j] >= td) {
- if (b->mm[j] == td) {
- deg += b->md[j];
- }
- sm += h;
- }
+ if (b->mm[j] >= td) {
+ if (b->mm[j] == td) {
+ deg += b->md[j];
+ }
+ sm += h;
+ }
}
}
h >>= 1;
while (j>0) {
w = x & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
- r = bwdtbl[((rel+ETW)<<ETW)+w];
- if (r<ETW && r<j) {
- if (i-r < 0) return NOTFOUND;
- return i-r-1;
- }
+ r = bwdtbl[((rel+ETW)<<ETW)+w];
+ if (r<ETW && r<j) {
+ if (i-r < 0) return NOTFOUND;
+ return i-r-1;
+ }
}
r = min(j,ETW);
rel += 2*popcount(w)-r;
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || t-i < ETW-1) {
- r = max(ETW-j,ETW-1-(t-i));
- w2 = (1<<r)-1;
+ r = max(ETW-j,ETW-1-(t-i));
+ w2 = (1<<r)-1;
}
if (op & OPT_MAX) {
- v = minmaxtbl_v[op][w & (~w2)];
- if (d + v + lr > ds) {
- ds = d + v;
- is = i + minmaxtbl_i[op][w & (~w2)];
- }
+ v = minmaxtbl_v[op][w & (~w2)];
+ if (d + v + lr > ds) {
+ ds = d + v;
+ is = i + minmaxtbl_i[op][w & (~w2)];
+ }
} else {
- v = minmaxtbl_v[op][w | w2];
- if (d + v < ds +lr) {
- ds = d + v;
- is = i + minmaxtbl_i[op][w | w2];
- }
+ v = minmaxtbl_v[op][w | w2];
+ if (d + v < ds +lr) {
+ ds = d + v;
+ is = i + minmaxtbl_i[op][w | w2];
+ }
}
r = min(j,ETW);
if (bp_getbit(b->B,i)==OP) {
d++;
if (op & OPT_MAX) {
- if (d + lr > ds) {
- ds = d; is = i;
- }
+ if (d + lr > ds) {
+ ds = d; is = i;
+ }
}
} else {
d--;
if (!(op & OPT_MAX)) {
- if (d < ds + lr) {
- ds = d; is = i;
- }
+ if (d < ds + lr) {
+ ds = d; is = i;
+ }
}
}
i++;
if (opt & OPT_MAX) {
m = d + b->sM[i] - 1;
if (m + lr > md) {
- md = m; mi = i;
+ md = m; mi = i;
}
} else {
m = d + b->sm[i] - SB;
if (m < md + lr) {
- md = m; mi = i;
+ md = m; mi = i;
}
}
}
for (i=sm; i<=tm; i++) {
if (opt & OPT_MAX) {
if (b->mM[i] + lr > ds) {
- ds = b->mM[i]; is = i - m_ofs; ys = 2;
+ ds = b->mM[i]; is = i - m_ofs; ys = 2;
}
} else {
if (b->mm[i] < ds + lr) {
- ds = b->mm[i]; is = i - m_ofs; ys = 2;
+ ds = b->mm[i]; is = i - m_ofs; ys = 2;
}
}
}
if (opt & OPT_MAX) {
if (b->mM[sm] + lr > ds) {
- ds = b->mM[sm]; is = sm; ys = 2;
+ ds = b->mM[sm]; is = sm; ys = 2;
}
for (i=0; i<=h-2; i++) {
- j = sm>>i;
- if ((j&1) == 0) {
- if (b->mM[j+1] + lr > ds) {
- ds = b->mM[j+1]; is = j+1; ys = 2;
- }
- }
+ j = sm>>i;
+ if ((j&1) == 0) {
+ if (b->mM[j+1] + lr > ds) {
+ ds = b->mM[j+1]; is = j+1; ys = 2;
+ }
+ }
}
for (i=h-2; i>=0; i--) {
- j = tm>>i;
- if ((j&1)==1) {
- if (b->mM[j-1] + lr > ds) {
- ds = b->mM[j-1]; is = j-1; ys = 2;
- }
- }
+ j = tm>>i;
+ if ((j&1)==1) {
+ if (b->mM[j-1] + lr > ds) {
+ ds = b->mM[j-1]; is = j-1; ys = 2;
+ }
+ }
}
if (b->mM[tm] + lr > ds) {
- ds = b->mM[tm]; is = tm; ys = 2;
+ ds = b->mM[tm]; is = tm; ys = 2;
}
if (ys == 2) {
- while (is < m_ofs) {
- is <<= 1;
- if (b->mM[is+1] + lr > b->mM[is]) is++;
- }
- is -= m_ofs;
+ while (is < m_ofs) {
+ is <<= 1;
+ if (b->mM[is+1] + lr > b->mM[is]) is++;
+ }
+ is -= m_ofs;
}
} else { // MIN
if (b->mm[sm] < ds + lr) {
- ds = b->mm[sm]; is = sm; ys = 2;
+ ds = b->mm[sm]; is = sm; ys = 2;
}
for (i=0; i<=h-2; i++) {
- j = sm>>i;
- if ((j&1) == 0) {
- if (b->mm[j+1] < ds + lr) {
- ds = b->mm[j+1]; is = j+1; ys = 2;
- }
- }
+ j = sm>>i;
+ if ((j&1) == 0) {
+ if (b->mm[j+1] < ds + lr) {
+ ds = b->mm[j+1]; is = j+1; ys = 2;
+ }
+ }
}
for (i=h-2; i>=0; i--) {
- j = tm>>i;
- if ((j&1)==1) {
- if (b->mm[j-1] < ds + lr) {
- ds = b->mm[j-1]; is = j-1; ys = 2;
- }
- }
+ j = tm>>i;
+ if ((j&1)==1) {
+ if (b->mm[j-1] < ds + lr) {
+ ds = b->mm[j-1]; is = j-1; ys = 2;
+ }
+ }
}
if (b->mm[tm] < ds + lr) {
- ds = b->mm[tm]; is = tm; ys = 2;
+ ds = b->mm[tm]; is = tm; ys = 2;
}
if (ys == 2) {
- while (is < m_ofs) {
- is <<= 1;
- if (b->mm[is+1] < b->mm[is] + lr) is++;
- }
- is -= m_ofs;
+ while (is < m_ofs) {
+ is <<= 1;
+ if (b->mm[is+1] < b->mm[is] + lr) is++;
+ }
+ is -= m_ofs;
}
}
}