The catch is that to know one element was deleted and a new one was added you need to know which attribute or subelement is the key. Which is a piece of information the diff doesn't have. For the same reason the diff engine cannot handle reordered elements the way you seem to want.

I do not think a generic solution is possible and it's hard to give you a specific solution as we do not know your XML.