MerkleTree implements Serializable { public static List<LeafNode> difference(@NotNull MerkleTree one, @Nullable MerkleTree two) { checkNotNull(one, "Expected tree is required!"); if (null == two) { return one.getLeafNodes(); } Deque<HashableNode> nodes1 = new ArrayDeque<>(); Deque<HashableNode> nodes2 = new ArrayDeque<>(); HashableNode current1 = one.root; HashableNode current2 = two.root; List<LeafNode> diff = new ArrayList<>(); while ((!nodes1.isEmpty() || current1 != null) && (!nodes2.isEmpty() || current2 != null)) { if (current1 != null && current2 != null && current1 instanceof LeafNode && current2 instanceof LeafNode && !current1.equals(current2)) { log.debug("Nodes are diff {} : {}", current1, current2); diff.add((LeafNode) current2); } if (current1 instanceof BranchNode) { HashableNode rightNode = ((BranchNode) current1).getRight(); if (rightNode != null) { nodes1.push(rightNode); } current1 = ((BranchNode) current1).getLeft(); } else { if (!nodes1.isEmpty()) { current1 = nodes1.pop(); } else { current1 = null; } } if (current2 instanceof BranchNode) { HashableNode rightNode = ((BranchNode) current2).getRight(); if (rightNode != null) { nodes2.push(rightNode); } current2 = ((BranchNode) current2).getLeft(); } else { if (!nodes2.isEmpty()) { current2 = nodes2.pop(); } else { current2 = null; } } } return diff; } MerkleTree(Range<Long> fullRange, int maxDepth); void calculate(); @Override String toString(); List<LeafNode> getLeafNodes(); static void fillTree(@NotNull MerkleTree tree, @NotNull SortedMap<Long, Block> blocks); static List<LeafNode> difference(@NotNull MerkleTree one, @Nullable MerkleTree two); HashableNode getRoot(); static final int MAX_LEVEL; }
@Test public void difference() throws InterruptedException { IdGeneratorService service = new IdGeneratorService(); List<Block> originalBlocks = new ArrayList<>(); long min = 0, max = 0; int offset = 0; for (int i = 0; i < 10000; i++) { long id = service.generate(1); int length = random.nextInt(65536); originalBlocks.add(new Block(id, Arrays.asList(new BlockElt(id, 0, offset, length, 42)))); offset += length; if (min == 0) { min = id; } max = id; Thread.sleep(1); } SortedMap<Long, Block> blocks = originalBlocks.stream() .collect(toMap(Block::getId, Function.<Block>identity(), Utils.throwingMerger(), TreeMap::new)); SortedMap<Long, Block> blocks2 = originalBlocks.stream() .limit(9500) .collect(toMap(Block::getId, Function.<Block>identity(), Utils.throwingMerger(), TreeMap::new)); Range<Long> ranges = Range.openClosed(min - 1, max); MerkleTree tree = new MerkleTree(ranges, 64); MerkleTree.fillTree(tree, blocks); MerkleTree tree2 = new MerkleTree(ranges, 64); MerkleTree.fillTree(tree2, blocks2); assertEquals( MerkleTree.difference(tree, tree2) .stream() .count(), 4); }