} else {
right_child = NULL;
}
-// delete [] left; // already deleted
-// delete [] right;
+ delete [] left; // already deleted if count_left > 0
+ delete [] right;
}
// cout << "recursion to leftchild at l = " << l << ", symbol = " << (uchar)symbol << ", rank0 = " << bitmap->rank0(pos) << ", rank1 = " << bitmap->rank1(pos) << endl;
// check left child for symbols <= givenSymbol
- if (result != -1 || left_child == NULL)
+ if (result != (uint)-1 || left_child == NULL)
return result;
return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1);
}
using std::endl;
// cout << "pos = " << pos << ", symbol = " << (uchar)symbol << endl;
- if (pos == -1)
- return -1;
+ if (pos == (uint)-1)
+ return (uint)-1;
if(right_child!=NULL)
result = right_child->rankLessThan(symbol, bitmap->rank1(pos)-1);
- if(result == -1 && left_child!=NULL)
+ if(result == (uint)-1 && left_child!=NULL)
return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1);
return result;
}
}
}
+void wt_node_internal::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot)
+{
+ uint symbol = pivot | (1 << l);
+// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+ if (j < i || max < min)
+ return;
+
+ if (min < symbol)
+ {
+ // Recurse left
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank0(i - 1);
+ uint newj = bitmap->rank0(j);
+
+ uint newmax = max < symbol - 1 ? max : symbol - 1;
+ if (left_child != NULL && newj > 0)
+ left_child->access(result, newi, newj-1, min, newmax, l-1, pivot);
+ }
+
+ if (max >= symbol)
+ {
+ // Recurse right
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank1(i - 1);
+ uint newj = bitmap->rank1(j);
+
+ uint newmin = min > symbol ? min : symbol;
+ if (right_child != NULL && newj > 0)
+ right_child->access(result, newi, newj-1, newmin, max, l-1, symbol);
+ }
+}
+
+void wt_node_internal::access(vector<int> &result, uint i, uint j)
+{
+// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+ if (j < i)
+ return;
+
+ {
+ // Recurse left
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank0(i - 1);
+ uint newj = bitmap->rank0(j);
+
+ if (left_child != NULL && newj > 0)
+ left_child->access(result, newi, newj-1);
+ }
+
+ {
+ // Recurse right
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank1(i - 1);
+ uint newj = bitmap->rank1(j);
+
+ if (right_child != NULL && newj > 0)
+ right_child->access(result, newi, newj-1);
+ }
+}
+
+
+uint wt_node_internal::access(uint i, uint j, uint min, uint max, uint l, uint pivot)
+{
+ uint count = 0;
+ uint symbol = pivot | (1 << l);
+// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+ if (j < i || max < min)
+ return 0;
+
+ if (min < symbol)
+ {
+ // Recurse left
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank0(i - 1);
+ uint newj = bitmap->rank0(j);
+
+ uint newmax = max < symbol - 1 ? max : symbol - 1;
+ if (left_child != NULL && newj > 0)
+ count += left_child->access(newi, newj-1, min, newmax, l-1, pivot);
+ }
+
+ if (max >= symbol)
+ {
+ // Recurse right
+ uint newi = 0;
+ if (i > 0)
+ newi = bitmap->rank1(i - 1);
+ uint newj = bitmap->rank1(j);
+
+ uint newmin = min > symbol ? min : symbol;
+ if (right_child != NULL && newj > 0)
+ count += right_child->access(newi, newj-1, newmin, max, l-1, symbol);
+ }
+ return count;
+}
+
+
uint wt_node_internal::size() {
uint s = bitmap->size()+sizeof(wt_node_internal);
if(left_child!=NULL)