## Monday, June 13, 2016

### Buttercola: Buddy System

Buttercola: Buddy System
Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold:
1. A node's value is 1 iff and only if all its subtree nodes' value are 1
2. A leaf node can have value either 1 or 0.

Implement the following 2 APIs:
set_bit(offset, length), set the bits at range from offset to offset + length - 1
clear_bit(offset, length), clear the bits at range from offset to offset + length - 1

e.g.                 0

/       \
0         0
/   \      /   \
1   0    1    0
/ \   / \   / \   / \
1 1 1 0 1 1 0 0

After calling the clear_bit(1, 3), the binary tree becomes

0

/       \
0         0
/   \      /   \
0   0    1    0
/ \   / \   / \   / \
1 0 0 0 1 1 0 0

For this tree, after call set_bit(1, 5), the binary tree becomes:

Understand the problem:

What's a buddy system? Here the link gives good explanation:
https://www.cs.fsu.edu/~engelen/courses/COP402003/p827.pdf

`  ``private` `int``[][] bits;`
`  ``private` `int` `n;`
`  ``private` `int` `numNodesLastLevel;`
`  `
`  ``public` `Solution (``int` `n) {`
`    ``this``.n = n;`
`    ``this``.numNodesLastLevel = (``int``) Math.pow(``2``, n - ``1``);`
`    ``bits = ``new` `int``[n][numNodesLastLevel];`
`    `
`    `
`  ``}`
`  `
`  ``public` `void` `clearBits(``int` `offset, ``int` `len) {`
`    ``if` `(offset < ``0` `|| offset + len > numNodesLastLevel) {`
`      ``throw` `new` `IndexOutOfBoundsException();`
`    ``}`
`    ``clearBitsHelper(n - ``1``, offset, offset + len - ``1``);`
`  ``}`
`  `
`  ``private` `void` `clearBitsHelper(``int` `level, ``int` `start, ``int` `end) {`
`    ``if` `(level < ``0` `|| start > end) {`
`      ``return``;`
`    ``}`
`    `
`    ``boolean` `containsOne = setToZero(level, start ,end);`
`    ``if` `(containsOne) {`
`      ``clearBitsHelper(level - ``1``, start / ``2``, end / ``2``);`
`    ``}`
`  ``}`
`  `
`  ``public` `void` `setBits(``int` `offset, ``int` `len) {`
`    ``if` `(offset < ``0` `|| offset + len > numNodesLastLevel) {`
`      ``throw` `new` `IndexOutOfBoundsException();`
`    ``}`
`    ``setBitsHelper(n - ``1``, offset, offset + len - ``1``);`
`  ``}`
`  `
`  ``private` `void` `setBitsHelper(``int` `level, ``int` `start, ``int` `end) {`
`    ``if` `(level < ``0` `|| start > end) {`
`      ``return``;`
`    ``}`
`    `
`    ``setToOne(level, start, end);`
`    `
`    ``// if start index is odd`
`    ``if` `((start & ``1``) == ``1``) {`
`      ``start--;`
`    ``}`
`    `
`    ``// if end index is even`
`    ``if` `((end & ``1``) == ``0``) {`
`      ``end++;`
`    ``}`
`    `
`    ``// determine the start position of the next level`
`    ``int` `nextStart = Integer.MAX_VALUE;`
`    ``for` `(``int` `i = start; i < end; i += ``2``) {`
`      ``if` `(bits[level][i] == ``1` `&& bits[level][i + ``1``] == ``1``) {`
`        ``nextStart = i / ``2``;`
`        ``break``;`
`      ``}`
`    ``}`
`    `
`    ``// determien the end position of the next level`
`    ``int` `nextEnd = Integer.MIN_VALUE;`
`    ``for` `(``int` `i = end; i > start; i -= ``2``) {`
`      ``if` `(bits[level][i] == ``1` `&& bits[level][i - ``1``] == ``1``) {`
`        ``nextEnd = i / ``2``;`
`        ``break``;`
`      ``}`
`    ``}`
`    `
`    ``setBitsHelper(level - ``1``, nextStart, nextEnd);`
`  ``}`
`  `
`  ``private` `void` `setToOne(``int` `level, ``int` `start, ``int` `end) {`
`    ``for` `(``int` `i = start; i <= end; i++) {`
`      ``bits[level][i] = ``1``;`
`    ``}`
`  ``}`
`  `
`  ``private` `boolean` `setToZero(``int` `level, ``int` `start, ``int` `end) {`
`    ``boolean` `containsOne = ``false``;`
`    ``for` `(``int` `i = start; i <= end; i++) {`
`      ``if` `(bits[level][i] == ``1``) {`
`        ``containsOne = ``true``;`
`      ``}`
`      `
`      ``bits[level][i] = ``0``;`
`    ``}`
`    `
`    ``return` `containsOne;`
`  ``}`
`  `
`  `
`  `
`  ``private` `void` `printTree() {`
`    ``int` `nodes = ``1``;`
`    ``for` `(``int``[] level : bits) {`
`      ``for` `(``int` `i = ``0``; i < nodes; i++) {`
`        ``System.out.print(level[i] + ``", "``);`
`      ``}`
`      `
`      ``System.out.println(``""``);`
`      ``nodes *= ``2``;`
`    ``}`
`    ``System.out.println(``""``);`
`  ``}`
`  `
`  ``public` `static` `void` `main(String[] args) {`
`    ``Solution sol = ``new` `Solution(``4``);`
`    `
`    ``sol.setBits(``1``, ``5``);`
`    ``sol.printTree();`
`    `
`    ``sol.clearBits(``2``, ``6``);`
`    ``sol.printTree();`
`  ``}`
Several thoughts and optimizations:
1. Why we set and clear bits in level order instead of heap order? That is, for each bit, we set and update its parent and so on, then repeat for the next bit. T

hat is because data is stored continuous in one level of tree. So if we read one level and process then move to its parent level, it can achieve better data locality.

2. For the clear_bits(), actually we don't have to repeat until we reach to the root. We can stop the recursion if all bits in the current level is zero. That's a prune of a recursion.