Package com.google.protobuf
Class RopeByteString.Balancer
- java.lang.Object
-
- com.google.protobuf.RopeByteString.Balancer
-
- Enclosing class:
- RopeByteString
private static class RopeByteString.Balancer extends java.lang.Object
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 Modifier and Type Field Description private java.util.ArrayDeque<ByteString>
prefixesStack
-
Constructor Summary
Constructors Modifier Constructor Description private
Balancer()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private 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 Detail
-
prefixesStack
private final java.util.ArrayDeque<ByteString> prefixesStack
-
-
Method Detail
-
balance
private ByteString balance(ByteString left, ByteString right)
-
doBalance
private void doBalance(ByteString root)
-
insert
private void insert(ByteString byteString)
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)
-
-