This class implements the balancing algorithm of BAP95. In the paper the authors use an array to keep track of pieces, while here we use a stack. The tree is balanced by traversing subtrees in left to right order, and the stack always contains the part of the string we've traversed so far.
One surprising aspect of the algorithm is the result of balancing is not necessarily balanced, though it is nearly balanced. For details, see BAP95.
Definition at line 607 of file RopeByteString.java.
| void com.google.protobuf.RopeByteString.Balancer.insert |
( |
ByteString |
byteString | ) |
|
|
inlineprivate |
Push a string on the balance stack (BAP95). BAP95 uses an array and calls the elements in the array 'bins'. We instead use a stack, so the 'bins' of lengths are represented by differences between the elements of minLengthByDepth.
If the length bin for our string, and all shorter length bins, are empty, we just push it on the stack. Otherwise, we need to start concatenating, putting the given string in the "middle" and continuing until we land in an empty length bin that matches the length of our concatenation.
- Parameters
-
| byteString | string to place on the balance stack |
Definition at line 657 of file RopeByteString.java.