First redefine the operations to put most (but not all) the work into a container object: We want 4 operations supported by the container object:
1) Construct from a [first,limit) pair of input random access iterators
2) insert(K) finds the value X at position K, inserts a X-1 after it and returns X
3) remove(K) finds the value X at position K, deletes it and returns X
4) size() reports the size of the contents
The work outside the container would just keep track of incremental changes to K:
K += insert(K); K %= size();
or
K += remove(K); K %= size();
Notice the importance of a sequence point before reading size()
The container data is just a root pointing to a node.
struct node {
unsigned weight;
unsigned value;
node* child[2];
unsigned cweight(unsigned s)
{ return child[s] ? child[s]->weight : 0; }
};
The container member functions insert and remove would be wrappers around recursive static insert and remove functions that each take a node*& in addition to K.
The first thing each of either recursive insert or remove must do is:
if (K<cweight(0)) recurse passing (child[0], K);
else if ((K-=cweight(0))>0) recurse passing (child[1], K-1);
else do the basic operation (read the result, create or destroy a node)
After doing that, you fix the weight at each level up the recursive call stack (starting where you did the work for insert or the level above that for remove).
After incrementing or decrementing the weight at the current level, you may need to re-balance, remembering which side you recursively changed. Insert is simpler: If child[s]->weight*4 >= This->weight*3 you need to re-balance. The re-balance is one of the two basic tree rotations and you select which one based on whether child[s]->cweight(s)<child[s]->cweight(1-s). rebalance for remove is the same idea but different details.
This system does a lot more worst case re-balancing than a red-black or AVL tree. But still is entirely logN. Maybe there is a better algorithm for a weight-semi-balanced tree. But I couldn't find that with a few google searches, nor even the real name of nor other details about what I just arbitrarily called a "weight-semi-balanced tree".
Getting the nearly 2X speed up of strangely mixing the read operation into the insert and remove operations, means you will need yet another recursive version of insert that doesn't mix in the read, and is used for the portion of the path below the point you read from (so it does the same recursive weight changes and re-balancing but with different input and output).
Given random access input iterators, the construction is a more trivial recursive function. Grab the middle item from the range of iterators and make a node of it with the total weight of the whole range, then recursively pass the sub ranges before and after the middle one to the same recursive function to create child subtree.
I haven't tested any of this, but I think the following is all the code you need for remove as well as the rebalance needed for both insert and remove. Functions taking node*& are static member function of tree and those not taking node*& are non static.
unsigned tree::remove(unsigned K)
{
node* removed = remove(root, K);
unsigned result = removed->value;
delete removed;
return result;
}
// static
node* tree::remove( node*& There, unsigned K) // Find, unlink and return the K'th node
{
node* result;
node* This = There;
unsigned s=0; // Guess at child NOT removed from
This->weight -= 1;
if ( K < This->cweight(0) )
{
s = 1;
result = remove( This->child[0], K );
}
else
{
K -= This->cweight(0);
if ( K > 0 )
{
result = remove( This->child[1], K-1 );
}
else if ( ! This->child[1] )
{
// remove This replacing it with child[0]
There = This->child[0];
return This; // Nothing here/below needs a re-balance check
}
else
{
// remove This replacing it with the leftmost descendent of child[1]
result = This;
There = This = remove( This->child[1], 0 );
This->child[0] = Result->child[0];
This->child[1] = Result->child[1];
This->weight = Result->weight;
}
}
rebalance( There, s );
return result;
}
// static
void tree::rebalance( node*& There, unsigned s)
{
node* This = There;
node* c = This->child[s];
if ( c && c->weight*4 >= This->weight*3 )
{
node* b = c->child[s];
node* d = c->child[1-s];
unsigned bweight = b ? b->weight : 0;
if ( d && bweight < d->weight )
{
// inner rotate: d becomes top of subtree
This->child[s] = d->child[1-s];
c->child[1-s] = d->child[s];
There = d;
d->child[s] = c;
d->child[1-s] = This;
d->weight = This->weight;
c->weight = bweight + c->cweight(1-s) + 1;
This->weight -= c->weight + 1;
}
else
{
// outer rotate: c becomes top of subtree
There = c;
c->child[1-s] = This;
c->weight = This->weight;
This->child[s] = d;
This->weight -= bweight+1;
}
}
}
