private static class RopeByteString.Balancer
extends java.lang.Object
One surprising aspect of the algorithm is the result of balancing is not necessarily balanced, though it is nearly balanced. For details, see BAP95.
Modifier and Type | Field and Description |
---|---|
private java.util.Stack<ByteString> |
prefixesStack |
Modifier | Constructor and Description |
---|---|
private |
Balancer() |
Modifier and Type | Method and 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).
|
private final java.util.Stack<ByteString> prefixesStack
private ByteString balance(ByteString left, ByteString right)
private void doBalance(ByteString root)
private void insert(ByteString byteString)
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.
byteString
- string to place on the balance stackprivate int getDepthBinForLength(int length)