Package com.google.protobuf
Class RopeByteString.Balancer
java.lang.Object
com.google.protobuf.RopeByteString.Balancer
- Enclosing class:
RopeByteString
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.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate ByteString
balance
(ByteString left, ByteString right) private void
doBalance
(ByteString root) private int
getDepthBinForLength
(int length) private void
insert
(ByteString byteString) Push a string on the balance stack (BAP95).
-
Field Details
-
prefixesStack
-
-
Constructor Details
-
Balancer
private Balancer()
-
-
Method Details
-
balance
-
doBalance
-
insert
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
-
getDepthBinForLength
private int getDepthBinForLength(int length)
-