X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2Flibbp.git;a=blobdiff_plain;f=bp-core.c;fp=bp-core.c;h=67cc78081d50e6affdc9b1c4af581e9ffc5c863a;hp=70a0959b4313fac866d2ab29f59eef7f31497e0b;hb=5382b5fde5add82ebd492e97a458a824503fbd8d;hpb=35d38c5681c54a22125452a2e43dc4b8305c588f

diff --git a/bp-core.c b/bp-core.c
index 70a0959..67cc780 100644
--- a/bp-core.c
+++ b/bp-core.c
@@ -119,11 +119,11 @@ int search_SB_r(bp *b, int i, int rel)
     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;
@@ -274,55 +274,55 @@ int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith)
       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);
@@ -360,18 +360,18 @@ int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
     if (m < td) {
       r = degree_SB(b,i,n,td-d,&degtmp,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)];
     }
@@ -386,8 +386,8 @@ int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
     if (ith > 0) {
       if (r == NOTFOUND) return NOTFOUND;
       if (r == FOUND) {
-	*ans = degtmp;
-	return FOUND;
+        *ans = degtmp;
+        return FOUND;
       }
     } else {
       deg += degtmp;
@@ -407,8 +407,8 @@ static void partition_range(int s,int t)
   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;
@@ -474,7 +474,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
     } else {
       deg += degtmp;
       if (d == END) {
-	return deg;
+        return deg;
       }
     }
   }
@@ -493,8 +493,8 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
     }
     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];
     }
@@ -515,23 +515,23 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
   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;
@@ -543,25 +543,25 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
       //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;
@@ -605,11 +605,11 @@ int search_SB_l(bp *b, int i, int rel)
     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;
@@ -742,22 +742,22 @@ int rmq_SB(bp *b, int s, int t, int opt, int *dm)
       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);
@@ -772,16 +772,16 @@ int rmq_SB(bp *b, int s, int t, int opt, int *dm)
     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++;
@@ -809,12 +809,12 @@ int rmq_MB(bp *b, int s, int t, int opt, int *dm)
     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;
       }
     }
   }
@@ -896,11 +896,11 @@ int bp_rmq(bp *b, int s, int t, int opt)
   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;
       }
     }
   }
@@ -915,63 +915,63 @@ int bp_rmq(bp *b, int s, int t, int opt)
 
     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;
       }
     }
   }