View Javadoc

1   /*
2    * $Id: OASTDelta.java,v 1.8 2005/06/01 17:38:37 jlerner Exp $
3    *
4    * Copyright (c) 1999-2004, BBN Technologies, LLC.
5    * All rights reserved.
6    * http://www.daml.org/legal/opensource/bbn_license.html
7    */
8    
9   package com.bbn.swede.core.dom;
10  
11  import java.util.ArrayList;
12  import java.util.Arrays;
13  import java.util.LinkedList;
14  import java.util.List;
15  
16  import com.bbn.swede.core.OWLCore;
17  
18  /***
19   * Concrete implementation of the IOASTDelta interface.  An OAST delta 
20   * represents structural changes in a document's OWL abstract syntax tree
21   * between two discrete points in time.
22   * @author jlerner
23   */
24  public class OASTDelta implements IOASTDelta
25  {
26     private OASTNode _nodeBefore;
27     private OASTNode _nodeAfter;
28     private int _iType;
29     private IOASTDelta[] _aChildren;
30     
31     /***
32      * <p>Creates a delta for the OAST subtree represented by the before and
33      * after states of a modified node.  How the node is created depends on the
34      * delta type specified.</p>
35      * 
36      * <ul>
37      * <li><code>INSERTED</code> - additional <code>INSERTED</code> deltas are
38      * created for all descendant nodes of <code>nodeAfter</code>.  
39      * <code>nodeBefore</code> is ignored.</li>
40      * <li><code>REMOVED</code> - additional <code>REMOVED</code> deltas are
41      * created for all descendant nodes of <code>nodeBefore</code>.
42      * <code>nodeAfter</code> is ignored.</li>
43      * <li><code>CHANGED</code> - the child lists of <code>nodeBefore</code> and
44      * <code>nodeAfter</code> are compared and processed recursively to create
45      * <code>CHANGED</code>, REPLACED, <code>INSERTED</code>, 
46      * and <code>REMOVED</code> deltas.  This delta may be turned into a 
47      * DESCENDANT delta if there turn out not to be any structural changes among 
48      * the node's direct children.</li>
49      * </ul>
50      * 
51      * <p>This constructor should not be used to create <code>DESCENDANT</code>
52      * deltas.  Instead, use {@link #OASTDelta(OASTNode, OASTDelta)} or
53      * {@link #OASTDelta(OASTNode, IOASTDelta[])}.</p>
54      * @param iType one of the delta type constants <code>INSERTED</code>,
55      *              <code>REMOVED</code>, or <code>CHANGED</code>
56      * @param before the node's state before the change.  Ignored if 
57      *               <code>iType</code> is <code>INSERTED</code>.
58      * @param after the node's state after the change.  Ignored if
59      *              <code>iType</code> is <code>REMOVED</code>. 
60      */
61     private OASTDelta(int iType, OASTNode before, OASTNode after)
62     {
63        _iType = iType;
64        _nodeBefore = (iType == INSERTED ? null : before);
65        _nodeAfter = (iType == REMOVED ? null : after);
66        
67        if (iType == INSERTED || iType == REMOVED)
68        {
69           OASTNode[] children = (iType == INSERTED ? _nodeAfter.getChildren() 
70                                                    : _nodeBefore.getChildren());
71           _aChildren = new IOASTDelta[children.length];
72           for (int i = 0; i < children.length; i++)
73           {
74              OASTNode node = children[i];
75              //it's OK to pass node for both before and after here, since
76              //REMOVED will ignore the after node and INSERTED will ignore the
77              //before node
78              _aChildren[i] = new OASTDelta(iType, node, node);
79           }
80        }
81        else
82        {
83           OASTNode[] achildrenBefore = _nodeBefore.getChildren();
84           OASTNode[] achildrenAfter  = _nodeAfter.getChildren();
85           _aChildren = createChildDeltas(achildrenBefore, achildrenAfter);
86           //We already know the QNames and node types of nodeBefore and 
87           //nodeAfter match, but make sure they're text or attribute nodes
88           //and that they did actually change.
89           if (_nodeBefore instanceof TextNode)
90           {
91              TextNode textBefore = (TextNode)_nodeBefore;
92              TextNode textAfter  = (TextNode)_nodeAfter;
93              if (!textBefore.getText().equals(textAfter.getText()))
94              {
95                 return;
96              }
97           }
98           else if (_nodeBefore instanceof AttributeNode)
99           {
100             AttributeNode attBefore = (AttributeNode)_nodeBefore;
101             AttributeNode attAfter  = (AttributeNode)_nodeAfter;
102             if (!attBefore.getValue().equals(attAfter.getValue()))
103             {
104                return;
105             }
106          }
107 
108          _iType = REPLACED;
109 //         _nodeAfter = _nodeBefore;
110 //         _nodeBefore = null;
111       }
112    }
113    
114    /***
115     * Creates a delta of type <code>DESCENDANT</code>.  The delta passed to
116     * this constructor will be attached as the lone child of the new delta.
117     * @param parent the node that is the basis for the <code>DESCENDANT</code>
118     *               delta
119     * @param child The lone child for the <code>DESCENDANT</code> delta
120     */
121    private OASTDelta(OASTNode parent, IOASTDelta child)
122    {
123       _iType = DESCENDANT;
124       _nodeBefore = null;
125       _nodeAfter = parent;
126       _aChildren = new IOASTDelta[] {child};
127    }
128    
129    /***
130     * Creates a delta of type <code>DESCENDANT</code>.  The deltas passed to 
131     * this constructor will be used as the children of the new delta.
132     * @param childDeltas The child deltas for the <code>DESCENDANT</code> delta
133     */
134    private OASTDelta(OASTNode parent, IOASTDelta[] childDeltas)
135    {
136       _iType = DESCENDANT;
137       _nodeBefore = null;
138       _nodeAfter = parent;
139       _aChildren = childDeltas;
140    }
141    
142    /***
143     * Creates a deep copy of an OAST delta.
144     * @param other The delta to clone
145     */
146    public OASTDelta(IOASTDelta other)
147    {
148       _iType = other.getType();
149       _nodeBefore = other.getNodeBefore();
150       _nodeAfter = other.getNodeAfter();
151       IOASTDelta[] otherChildren = other.getChildren();
152       _aChildren = new IOASTDelta[otherChildren.length];
153       for(int i = 0; i < _aChildren.length; i++)
154       {
155          _aChildren[i] = new OASTDelta(otherChildren[i]);
156       }
157    }
158 
159    /***
160     * <p>Creates an OAST delta representing the results of a partial reparse.
161     * This method is only designed for use with partial reparses and makes
162     * the following assumptions:</p>
163     * 
164     * <ul>
165     * <li><code>nodesRemoved</code> is nonempty.</li>
166     * <li><code>nodesInserted</code> is nonempty.</li>
167     * <li>All items in <code>nodesRemoved</code> share a common parent.</li>
168     * <li>Items in <code>nodesInserted</code> will occupy the same space in the
169     * OAST as the nodes being removed; that is, they will share the same common
170     * parent as the items in <code>nodesRemoved</code>.</li>
171     * <li>The reparse that caused the change resulted from an edit to a single
172     * range of text in the document.</li>
173     * </ul>
174     * @param nodesRemoved array of nodes removed before the reparse
175     * @param nodesInserted array of nodes created by the reparse
176     * @return A delta representing the removed and inserted nodes, rooted at
177     *         the top of the OAST, or <code>null</code> if there is no net
178     *         structural change.
179     */
180    public static IOASTDelta createReparseDelta(OASTNode[] nodesRemoved, 
181                                               OASTNode[] nodesInserted)
182    {
183       if (nodesRemoved.length == 0 || nodesInserted.length == 0)
184       {
185          //TODO: throw exception?
186          return null;
187       }
188 
189       OASTNode nodeParent = nodesRemoved[0].getParent();
190       IOASTDelta[] deltas = createChildDeltas(nodesRemoved, nodesInserted);
191       
192       return createAncestorDeltas(nodeParent, deltas);
193    }
194    
195    /***
196     * Creates an OAST delta representing the replacement of one node with 
197     * another node.
198     * @param removed The node removed
199     * @param inserted The node replacing it
200     * @return A delta representing the removed and inserted nodes, rooted at
201     *         the top of the OAST, or <code>null</code> if there is no net
202     *         structural change.
203     */
204    public static IOASTDelta createReplaceDelta(OASTNode removed, OASTNode inserted)
205    {
206       if (removed == null || inserted == null)
207       {
208          //TODO: throw exception?
209          return null;
210       }
211       
212       OASTNode nodeParent = removed.getParent();
213       IOASTDelta[] deltas = createChildDeltas(new OASTNode[]{removed}, new OASTNode[]{inserted});
214       
215       return createAncestorDeltas(nodeParent, deltas);
216    }
217    
218    /***
219     * Creates an OAST delta representing the insertion of one or more
220     * nodes.
221     * @param nodeParent the node that will be the parent of the inserted nodes
222     * @param nodesInserted the inserted nodes
223     * @return A delta representing the node insertion, rooted at the top of
224     *         the OAST.
225     */
226    public static IOASTDelta createInsertDelta(OASTNode nodeParent,
227                                              OASTNode[] nodesInserted)
228    {
229       if (nodesInserted.length == 0)
230       {
231          return null;
232       }
233       
234       IOASTDelta[] deltas = new IOASTDelta[nodesInserted.length];
235       for (int i = 0; i < deltas.length; i++)
236       {
237          deltas[i] = new OASTDelta(INSERTED, null, nodesInserted[i]);
238       }
239       
240       return createAncestorDeltas(nodeParent, deltas);
241    }
242    
243    /***
244     * Creates an OAST delta representing the removal of one or more nodes.
245     * The removed nodes are assumed to share a common parent.
246     * @param nodesRemoved the removed nodes
247     * @return A delta representing the node removal, rooted at the top of the
248     *         OAST.
249     */
250    public static IOASTDelta createRemoveDelta(OASTNode[] nodesRemoved)
251    {
252       if (nodesRemoved.length == 0)
253       {
254          return null;
255       }
256 
257       OASTNode nodeParent = nodesRemoved[0].getParent();
258       IOASTDelta[] deltas = new IOASTDelta[nodesRemoved.length];
259       for (int i = 0; i < deltas.length; i++)
260       {
261          deltas[i] = new OASTDelta(REMOVED, nodesRemoved[i], null);
262       }
263 
264       return createAncestorDeltas(nodeParent, deltas);
265    }
266    
267    /***
268     * Creates <code>DESCENDANT</code> deltas for the parent node of a set of
269     * deltas and all of its ancestors.  The result is a <code>DESCENDANT</code>
270     * delta representing the document root and thus the entire change to the
271     * OAST.
272     * @param parent the parent node of the deltas
273     * @param deltas the set of deltas
274     * @return the root <code>DESCENDANT</code> delta
275     */
276    private static IOASTDelta createAncestorDeltas(OASTNode parent, IOASTDelta[] deltas)
277    {
278       //create DESCENDANT delta for parent node
279       IOASTDelta root = new OASTDelta(parent, deltas);
280 
281       //create DESCENDANT deltas for all ancestors of parent
282       while ((parent = parent.getParent()) != null)
283       {
284          root = new OASTDelta(parent, root);
285       }
286       
287       //return the root DESECENDANT delta
288       return root;
289    }
290    
291    /***
292     * Indicates whether two nodes can be considered equivalent for purposes
293     * of computing a delta.  Generally, this is a simple comparison of node
294     * type, but in the case of generic nodes qnames must also be checked.
295     * @param node1 the first node to compare
296     * @param node2 the second node to compare
297     * @return <code>true</code> if the node types match, 
298     *         <code>false</code> if not
299     */
300    private static boolean matchingTypes(OASTNode node1, OASTNode node2)
301    {
302       if (node1.getNodeType() != node2.getNodeType())
303       {
304          return false;
305       }
306       
307       //this should be sufficient to handle mismatched generic attributes,
308       //classes, and predicates as well as non-default namespaces.
309       //This should also ignore text nodes, which have empty qnames.
310       if (node1.getQName().equals(node2.getQName()))
311       {
312          return true;
313       }
314       
315       return false;
316    }
317    /***
318     * Creates deltas representing the difference between two sets of
319     * child nodes.
320     * @param before the child nodes before the change
321     * @param after  the child nodes after the change
322     * @return an array of <code>INSERTED</code>, <code>REMOVED</code>, 
323     *         <code>DESCENDANT</code>, and <code>CHANGED</code> deltas marking 
324     *         the changes between <code>before</code> and <code>after</code>.
325     */
326    private static IOASTDelta[] createChildDeltas(OASTNode[] before, 
327                                                 OASTNode[] after)
328    {
329       IOASTDelta[] deltas;
330       ArrayList alDeltas = new ArrayList();
331       OASTDelta delta;
332       
333       //search for matching nodes at the beginning of the arrays
334       int iMatch = 0;
335       while (iMatch < before.length && iMatch < after.length
336              && matchingTypes(before[iMatch], after[iMatch]))
337       {
338          iMatch++;
339       }
340       if (iMatch > before.length)
341       {
342          //the last nodes in the after array were inserted
343          for (int i = 0; i < before.length; i++)
344          {
345             delta = new OASTDelta(CHANGED, before[i], after[i]);
346             if (!delta.isEmpty())
347             {
348                alDeltas.add(delta);
349             }
350          }
351          for (int i = iMatch; i < after.length; i++)
352          {
353             alDeltas.add(new OASTDelta(INSERTED, null, after[i]));
354          }
355          deltas = (IOASTDelta[])alDeltas.toArray(new IOASTDelta[0]);
356          return deltas;
357       }
358       else if (iMatch > after.length)
359       {
360          //the last nodes in the before array were removed
361          for (int i = 0; i < after.length; i++)
362          {
363             delta = new OASTDelta(CHANGED, before[i], after[i]);
364             if (!delta.isEmpty())
365             {
366                alDeltas.add(delta);
367             }
368          }
369          for (int i = iMatch; i < before.length; i++)
370          {
371             alDeltas.add(new OASTDelta(REMOVED, before[i], null));
372          }
373          deltas = (IOASTDelta[])alDeltas.toArray(new IOASTDelta[0]);
374          return deltas;
375       }
376       //iMatch now indicates the first mismatch between the remove and insert
377       
378       int iMatchRemoved = before.length - 1;
379       int iMatchInserted = after.length - 1;
380       while (iMatchRemoved >= 0 && iMatchInserted >= 0
381              && iMatchRemoved >= iMatch && iMatchInserted >= iMatch
382              && matchingTypes(before[iMatchRemoved], after[iMatchInserted]))
383       {
384          iMatchRemoved--;
385          iMatchInserted--;
386       }
387       if (iMatchRemoved < 0)
388       {
389          //the first nodes in the after array were inserted
390          for (int i = 0; i <= iMatchInserted; i++)
391          {
392             alDeltas.add(new OASTDelta(INSERTED, null, after[i]));
393          }
394          for (int i = 0, j = iMatchInserted + 1; i < before.length; i++, j++)
395          {
396             delta = new OASTDelta(CHANGED, before[i], after[j]);
397             if (!delta.isEmpty())
398             {
399                alDeltas.add(delta);
400             }
401          }
402          deltas = (IOASTDelta[])alDeltas.toArray(new IOASTDelta[0]);
403          return deltas;
404       }
405       else if (iMatchInserted < 0)
406       {
407          //the first nodes in the before array were removed
408          for (int i = 0; i <= iMatchRemoved; i++)
409          {
410             alDeltas.add(new OASTDelta(REMOVED, before[i], null));
411          }
412          for (int i = iMatchRemoved + 1, j = 0; j < after.length; i++, j++)
413          {
414             delta = new OASTDelta(CHANGED, before[i], after[j]);
415             if (!delta.isEmpty())
416             {
417                alDeltas.add(delta);
418             }
419          }
420          deltas = (IOASTDelta[])alDeltas.toArray(new IOASTDelta[0]);
421          return deltas;
422       }
423       //iMatchR/I now indicates the last mismatch between the remove and insert
424 
425       //if we got here, we have changed nodes at the beginning and end of
426       //the before and afterlists as well as inserted and removed nodes between
427       for (int i = 0; i < iMatch; i++)
428       {
429          delta = new OASTDelta(CHANGED, before[i], after[i]);
430          if (!delta.isEmpty())
431          {
432             alDeltas.add(delta);
433          }
434       }
435       for (int i = iMatch; i <= iMatchRemoved; i++)
436       {
437          alDeltas.add(new OASTDelta(REMOVED, before[i], null));
438       }
439       for (int i = iMatch; i <= iMatchInserted; i++)
440       {
441          alDeltas.add(new OASTDelta(INSERTED, null, after[i]));
442       }
443       for (int i = iMatchRemoved + 1, j = iMatchInserted + 1;
444            i < before.length; i++, j++)
445       {
446          delta = new OASTDelta(CHANGED, before[i], after[j]);
447          if (!delta.isEmpty())
448          {
449             alDeltas.add(delta);
450          }
451       }
452       deltas = (IOASTDelta[])alDeltas.toArray(new IOASTDelta[0]);
453       return deltas;
454    }
455    
456    /* (non-Javadoc)
457     * @see com.bbn.swede.core.dom.IOASTDelta#getNodeBefore()
458     */
459    public OASTNode getNodeBefore()
460    {
461       return _nodeBefore;
462    }
463 
464    /* (non-Javadoc)
465     * @see com.bbn.swede.core.dom.IOASTDelta#getNodeAfter()
466     */
467    public OASTNode getNodeAfter()
468    {
469       return _nodeAfter;
470    }
471 
472    /* (non-Javadoc)
473     * @see com.bbn.swede.core.dom.IOASTDelta#getType()
474     */
475    public int getType()
476    {
477       return _iType;
478    }
479 
480    /* (non-Javadoc)
481     * @see com.bbn.swede.core.dom.IOASTDelta#accept(com.bbn.swede.core.dom.IOASTDeltaVisitor)
482     */
483    public void accept(IOASTDeltaVisitor visitor)
484    {
485       if (!visitor.visit(this))
486       {
487          return;
488       }
489       for (int i = 0; i < _aChildren.length; i++)
490       {
491          _aChildren[i].accept(visitor);
492       }
493    }
494 
495    /* (non-Javadoc)
496     * @see com.bbn.swede.core.dom.IOASTDelta#getChildren()
497     */
498    public IOASTDelta[] getChildren()
499    {
500       return _aChildren;
501    }
502 
503    /* (non-Javadoc)
504     * @see com.bbn.swede.core.dom.IOASTDelta#getChildren(int)
505     */
506    public IOASTDelta[] getChildren(int typeMask)
507    {
508       ArrayList al = new ArrayList();
509       for (int i = 0; i < _aChildren.length; i++)
510       {
511          if ((_aChildren[i].getType() & typeMask) > 0)
512          {
513             al.add(_aChildren[i]);
514          }
515       }
516       return (IOASTDelta[])al.toArray(new IOASTDelta[0]);
517    }
518 
519    /***
520     * Dumps a string representation of this delta and all deltas below it.
521     */
522    /*package*/ void dump()/package-summary/html">class="comment">package*/ void dump()/package-summary.html">/*package*/ void dump()/package-summary.html">class="comment">package*/ void dump()
523    {
524       dump("");
525    }
526    private void dump(String sIndent)
527    {
528       String sType = null;
529       String sChange = null;
530       switch (_iType)
531       {
532          case DESCENDANT:
533             sType = "DESCENDANT ";
534             sChange = _nodeAfter.toString();
535             break;
536          case INSERTED:
537             sType = "INSERTED   ";
538             sChange = _nodeAfter.toString();
539             break;
540          case REMOVED:
541             sType = "REMOVED    ";
542             sChange = _nodeBefore.toString();
543             break;
544          case CHANGED:
545             sType = "CHANGED    ";
546             sChange = _nodeBefore.toString() + " to " + _nodeAfter.toString();
547             break;
548          case REPLACED:
549             sType = "REPLACED   ";
550             sChange = _nodeBefore.toString() + " with " + _nodeAfter.toString();
551             break;
552          default:
553             break;
554       }
555       
556       OWLCore.trace("Delta", sIndent + sType + sChange, false);
557       String sNewIndent = sIndent + " ";
558       for (int i = 0; i < _aChildren.length; i++)
559       {
560          ((OASTDelta)_aChildren[i]).dump(sNewIndent);
561       }
562    }
563    
564    private class EmptyDeltaChecker implements IOASTDeltaVisitor
565    {
566       private boolean _bEmpty = true;
567      
568       /***
569        * Retrieves the flag indicating whether the searched delta was empty.
570        * @return <code>true</code> if the searched delta was empty,
571        *         <code>false</code> if not.
572        */
573       public boolean getEmptyFlag()
574       {
575          return _bEmpty;
576       }
577       /* (non-Javadoc)
578        * @see com.bbn.swede.core.dom.IOASTDeltaVisitor#visit(com.bbn.swede.core.dom.IOASTDelta)
579        */
580       public boolean visit(IOASTDelta delta)
581       {
582          if (!_bEmpty)
583          {
584             return false;
585          }
586          if (delta.getType() != DESCENDANT)
587          {
588             _bEmpty = false;
589             return false;
590          }
591          return true;
592       }
593       
594    }
595    /***
596     * Indicates whether the delta represents any actual change.  A delta tree
597     * is considered empty if it contains only DESCENDANT deltas.
598     * @return <code>true</code> if the delta is empty, <code>false</code> if not
599     */
600    private boolean isEmpty()
601    {
602       EmptyDeltaChecker checker = new EmptyDeltaChecker();
603       accept(checker);
604       return (checker.getEmptyFlag());
605    }
606 
607    /***
608     * Checks a list of deltas to see if any contain a before node that matches
609     * a specified after node.
610     * @param delta The delta to match.
611     * @param candidates The candidates for the match.
612     * @return A delta whose before node matches <code>after</code>, or
613     *         <code>null</code> if no match is found.
614     */
615    private IOASTDelta findMatch(IOASTDelta delta, IOASTDelta[] candidates)
616    {
617       if (delta.getType() == REMOVED)
618       {
619          //match before node to after nodes
620          for(int i = 0; i < candidates.length; i++)
621          {
622             if (candidates[i].getType() == INSERTED
623                 && delta.getNodeBefore().equals(candidates[i].getNodeAfter()))
624             {
625                return candidates[i];
626             }
627          }
628       }
629       else if (delta.getType() == DESCENDANT)
630       {
631          //match after node to after nodes
632          for(int i = 0; i < candidates.length; i++)
633          {
634             if (candidates[i].getType() == DESCENDANT
635                 && delta.getNodeAfter().equals(candidates[i].getNodeAfter()))
636             {
637                return candidates[i];
638             }
639             else if ((candidates[i].getType() & (REMOVED | REPLACED)) > 0
640                      && delta.getNodeAfter().equals(candidates[i].getNodeBefore()))
641             {
642                return candidates[i];
643             }
644          }
645       }
646       else //inserted, changed, or replaced
647       {
648          for(int i = 0; i < candidates.length; i++)
649          {
650             if (candidates[i].getType() == DESCENDANT
651                 && delta.getNodeAfter().equals(candidates[i].getNodeAfter()))
652             {
653                return candidates[i];
654             }
655             else if ((candidates[i].getType() & (REMOVED | REPLACED | CHANGED)) > 0
656                      && delta.getNodeAfter().equals(candidates[i].getNodeBefore()))
657             {
658                return candidates[i];
659             }
660          }
661       }
662       return null;
663    }
664    
665    /***
666     * Merges the changes represented by a subsequent OAST delta into this one.
667     * @param other The subsequent delta to merge.
668     */
669    public void combine(OASTDelta other)
670    {
671 
672       LinkedList llPairs = new LinkedList();
673       for (int i = 0; i < _aChildren.length; i++)
674       {
675          IOASTDelta deltaMatch = findMatch(_aChildren[i], other._aChildren);
676          if (deltaMatch != null)
677          {
678             llPairs.addLast(_aChildren[i]);
679             llPairs.addLast(deltaMatch);
680          }
681       }
682 
683       ArrayList alRemove = new ArrayList();
684       ArrayList alRemoveOther = new ArrayList();
685       while (llPairs.size() > 0)
686       {
687          OASTDelta deltaChild = (OASTDelta)llPairs.removeFirst();
688          OASTDelta deltaMerge = (OASTDelta)llPairs.removeFirst();
689          if (merge(deltaChild, deltaMerge))
690          {
691             alRemove.add(deltaChild);
692          }
693          //Always remove the merged child from its' parent delta after processing it
694          alRemoveOther.add(deltaMerge);
695       }
696       ArrayList al = new ArrayList(Arrays.asList(_aChildren));
697       al.removeAll(alRemove);
698       _aChildren = (IOASTDelta[])al.toArray(new IOASTDelta[0]);
699       al = new ArrayList(Arrays.asList(other._aChildren));
700       al.removeAll(alRemoveOther);
701       other._aChildren = (IOASTDelta[])al.toArray(new IOASTDelta[0]);
702       
703       IOASTDelta[] newChildren = new IOASTDelta[_aChildren.length + other._aChildren.length];
704       System.arraycopy(_aChildren, 0, newChildren, 0, _aChildren.length);
705       System.arraycopy(other._aChildren, 0, newChildren, _aChildren.length, other._aChildren.length);
706       _aChildren = newChildren;
707    }
708    
709    /***
710     * Replaces one of this delta's children with a new delta representing the
711     * composite effect of that child and another delta.
712     * @param deltaChild The child of this delta to replace
713     * @param deltaMerge The delta to merge with <code>deltaChild</code>
714     * @return <code>true</code> to indicate that the caller should remove
715     *         <code>deltaChild</code> from this node's child list,
716     *         <code>false</code> if it should be left in place.
717     *         <code>deltaMerge</code> should always be removed from its parent
718     *         after it is processed.
719     */
720    private boolean merge(OASTDelta deltaChild, OASTDelta deltaMerge)
721    {
722       if (deltaMerge.getType() == DESCENDANT)
723       {
724          //recursively process the combined children and leave deltaChild in place.
725          deltaChild.combine(deltaMerge);
726          return false;
727       }
728       
729       if ((deltaChild.getType() == INSERTED && deltaMerge.getType() == REMOVED)
730           || (deltaChild.getType() == REMOVED && deltaMerge.getType() == INSERTED))
731       {
732          //events cancel, so just make sure deltaChild gets removed by the caller.
733          return true;
734       }
735       
736       if (deltaMerge.getType() == REMOVED)
737       {
738          OASTNode removed = 
739             (deltaChild.getType() == DESCENDANT ? deltaChild.getNodeAfter() 
740                                                 : deltaChild.getNodeBefore());
741          deltaChild._iType = REMOVED;
742          deltaChild._nodeBefore = removed;
743          deltaChild._nodeAfter = null;
744          deltaChild.combine(deltaMerge);
745       }
746       else if (deltaMerge.getType() == REPLACED)
747       {
748          deltaChild._nodeAfter = deltaMerge._nodeAfter;
749          deltaChild.combine(deltaMerge);
750       }
751       else if (deltaMerge.getType() == CHANGED)
752       {
753          deltaChild._nodeAfter = deltaMerge._nodeAfter;
754          //don't need to worry about children, CHANGED only applies to attributes & literals
755       }
756       
757       return false;
758    }
759 
760    /* (non-Javadoc)
761     * @see com.bbn.swede.core.dom.IOASTDelta#getDeltas(int)
762     */
763    public IOASTDelta[] getDeltas(int typeMask)
764    {
765       DeltaCollector dc = new DeltaCollector(typeMask);
766       accept(dc);
767       List l = dc.getDeltas();
768       return (IOASTDelta[])l.toArray(new IOASTDelta[0]);
769    }
770 
771    /* (non-Javadoc)
772     * @see com.bbn.swede.core.dom.IOASTDelta#typeMatches(int)
773     */
774    public boolean typeMatches(int typeMask)
775    {
776       return (getType() & typeMask) > 0;
777    }
778 
779 }