org.basex.query.up
Class UpdatePrimitiveComparator

java.lang.Object
  extended by org.basex.query.up.UpdatePrimitiveComparator
All Implemented Interfaces:
java.util.Comparator<UpdatePrimitive>

public class UpdatePrimitiveComparator
extends java.lang.Object
implements java.util.Comparator<UpdatePrimitive>

Comparator for UpdatePrimitive.

In general, a list of updates is applied from the highest to the lowest PRE value in BaseX. The higher the actual location of an update the sooner it is applied, hence the 'greater' UpdatePrimitive is applied first. The order further relies on the definition of PrimitiveType.

UpdatePrimitives are identified by their target node's PRE values (T). Depending on the PrimitiveType of the update, a specific PRE value on the table is affected (L). Hence it is not sufficient to order primitives based on T (see case 2,3 below). It is also not sufficient to order them based on L (see case 2,3 below).

The first UpdatePrimitive is referred to as P1, the target node of P1 is referred to as T1, the (optional) insertion sequence for P1 is S1, the actually affected PRE value on disk is L1. For the second P2, T2, S2, L2.

The result of the comparison depends on several things:

  1. The PRE values of T1 and T2. Consider D the document . If P1 is a DeleteNode on N1 and P2 is a DeleteNode on N2, it follows that T2>T1. P2 wins the comparison and is therefore executed first.
  2. Whether the order of P1, P2 must be switched to get the desired result. Consider D the document <\/N1>. If P1 is an InsertInto on N1 and P2 is an InsertInto on N2, it follows that T2>T1. Yet, executing P2 first would lead to the following problem:
    The actually affected PRE value location on disk for both updates is L1=L2=L=4. P2 inserts a sequence of nodes S2 at L. After this P1 inserts a sequence of nodes S1 at the same location L and shifts S2 further back on disk. S1 and S2 are now ordered incorrectly (S1,S2) and invalidate the document.
    Hence the correct order (S2,S1) can only be achieved if P1 is executed first and S1 subsequently shifted by inserting S2.
    The problem can exist if P1 and/or P2 are of the kind InsertInto or InsertAfter and T1+size(T1) is equal T2+size(T2), hence T1 and T2 have the same following node. The correct order is realized by executing the update first, that is on the ancestor axis of the other. In this case P1>P2.
    Another case similar to this is if P1 is an InsertIntoAsFirst on an element T1 and P2 is i.e. a ReplaceNode on an attribute T2 of T1. To get the desired order of insertion sequences (S2,S1) P1 must be executed first, hence P1>P2.
  3. The PrimitiveType of P1, P2. Consider D the document with T=N1. P1 is an InsertBefore on T and P2 is an InsertIntoAsFirst on the same target T. As they both operate on the same target, both have not to be re-located because of their type (see case 2), hence only differ in their PrimitiveType, it follows that P2>P1 as nodes S2 are to be inserted on the following axis of S1.
    Another case: P2 a DeleteNode on T and P1 an InsertBefore on T. As L2=L1, P2, the execution sequence must be (P2,P1). For (P1,P2) S1 would be deleted by P2. The correct order is also determined by the order of PrimitiveType. Here we see that ordering updates simply by the actually affected PRE value L is not sufficient.

Author:
BaseX Team 2005-12, BSD License, Lukas Kircher

Constructor Summary
UpdatePrimitiveComparator()
           
 
Method Summary
 int compare(UpdatePrimitive a, UpdatePrimitive b)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface java.util.Comparator
equals
 

Constructor Detail

UpdatePrimitiveComparator

public UpdatePrimitiveComparator()
Method Detail

compare

public int compare(UpdatePrimitive a,
                   UpdatePrimitive b)
Specified by:
compare in interface java.util.Comparator<UpdatePrimitive>