On 2/12/10, Tad Glines <[email protected]> wrote: > The construction of DocOpCollector seems unnecessarily complex. > > Here's the relevant snippet: > > private final List<BufferedDocOp> operations = new > ArrayList<BufferedDocOp>(); > > public void add(BufferedDocOp operation) { > ListIterator<BufferedDocOp> iterator = operations.listIterator(); > while (iterator.hasNext()) { > BufferedDocOp nextOperation = iterator.next(); > if (nextOperation == null) { > iterator.set(operation); > return; > } > iterator.set(null); > operation = compose(nextOperation, operation); > } > operations.add(operation); > } > > public BufferedDocOp composeAll() { > BufferedDocOp result = null; > for (BufferedDocOp operation : operations) { > if (operation != null) { > result = (result != null) ? compose(operation, result) : operation; > } > } > operations.clear(); > return result; > } > > This seems like it could be more simply (and efficiently) expresses as: > private BufferedDocOp collectedOp = null; > > public void add(BufferedDocOp operation) { > if (collectedOp == null) > collectedOp = operation; > else > collectedOp = compose(collectedOp, operation); > } > > public BufferedDocOp finish() { > BufferedDocOp result = collectedOp; > collectedOp = null; > return result; > } > > Does anyone see a problem with the proposed change?
The solution you propose has an O(n^2) time complexity for composing a sequence of operations of total size n, whereas the current code has an O(n log n) time complexity. Perhaps I can explain how the DocOpCollector works, since I think it's pretty interesting. If you interpret the operations List as a (little-endian) binary number, where a null in the list indicates a 0 and a non-null operation indicates a 1, then adding an operation to the collector works exactly like incrementing its binary number representation. An interesting byproduct of this algorithm is that interpreting the operations List as a binary number will tell you exactly how many operations have been collected so far. I hope that clears things up. Alex -- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
