freenet/fred-staging — pull request #231 by bertm (2014-05-25 23:56:28+00:00)
Title: Rewrite sparsebitmap

toad's FIXME at the end of the file was essentially valid for most of the functions contained herein.
In its current shape, SparseBitmaps cannot be used to contain anything but a few ranges of bits. After the rewrite, the contained algorithms make use of the inherent structure of the TreeSet to save time if SparseBitmaps may once be used in a context where more than just a few ranges are contained.

* Complexity of add() was linear in N, is now logarithmic in the total number of ranges N plus linear in the number of merged ranges.
* Complexity of remove() was linear in N, is now logarithmic in N plus linear in the number of removed ranges.
* Complexity of contains() was linear in N, is now logarithmic in N.
* Complexity of notOverlapping() was pseudo-quadratic O((end-start)*(N+1)), is now logarithmic in N plus linear in the number of ranges between start->end.

Additionally, Javadoc comments are added.

This rewrite also solves an internal flaw where now-overlapping ranges were not merged on add(), which was uncovered during testing of the new implementation. This flaw was only externally observable in the String representation, and hence did not cause too much trouble by itself.

As a sidenote, technically there exists a faster implementation of notOverlapping() which runs logarithmic in N. However such an implementation uses a decorated tree, with would need a custom tree implementation and some extra bookkeeping. For now this speed difference is not extremely relevant, so I opted not to implement this.