// Returns the value at given position and its rank
uint wt_node_internal::access(uint pos, uint &rank)
{
- // p is the internal node we are pointing our finger at each step
- wt_node_internal *p = this;
-
- while(1)
+ bool is_set = bitmap->access(pos);
+ if(!is_set)
{
- bool is_set = p->bitmap->access(pos);
-// cout << "is_set = " << is_set << ", pos = " << pos << ", rank0 = " << bitmap->rank0(pos) << ", rank1 = " << bitmap->rank1(pos) << endl;
- if(!is_set)
- {
- // recurse left
- pos = p->bitmap->rank0(pos)-1;
- wt_node_internal *tmp = dynamic_cast<wt_node_internal *>(p->left_child);
- if (tmp == NULL)
- {
- // it's a leaf
- rank = pos+1;
- return p->left_child->access(0);
- }
- p = tmp; // new internal node
- }
- else
- {
- // recurse right
- pos = p->bitmap->rank1(pos)-1;
- wt_node_internal *tmp = dynamic_cast<wt_node_internal *>(p->right_child);
- if (tmp == NULL)
- {
- // it's a leaf
- rank = pos+1;
- return p->right_child->access(0);
- }
- p = tmp; // new internal node
- }
+ // recurse left
+ pos = bitmap->rank0(pos)-1;
+ return left_child->access(pos, rank);
+ }
+ else
+ {
+ // recurse right
+ pos = bitmap->rank1(pos)-1;
+ return right_child->access(pos, rank);
}
}
+
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);