DeltaDataTree


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.dtree;
12  
13  import org.eclipse.core.internal.utils.Messages;
14  import org.eclipse.core.internal.utils.StringPool;
15  import org.eclipse.core.runtime.*;
16  
17  /**
18   * Externally, a <code>DeltaDataTree</code> appears to have the same content as
19   * a standard data tree.  Internally, the delta tree may be complete, or it may
20   * just indicate the changes between itself and its parent.  
21   *
22   * <p>Nodes that exist in the parent but do not exist in the delta, are represented 
23   * as instances of <code>DeletedNode</code>.  Nodes that are identical in the parent
24   * and the delta, but have differences in their subtrees, are represented as
25   * instances of <code>NoDataDeltaNode</code> in the delta tree.  Nodes that differ
26   * between parent and delta are instances of <code>DataDeltaNode</code>.  However,
27   * the <code>DataDeltaNode</code> only contains the children whose subtrees differ
28   * between parent and delta.
29   *
30   * A delta tree algebra is used to manipulate sets of delta trees.  Given two trees,
31   * one can obtain the delta between the two using the method 
32   * <code>forwardDeltaWith(aTree)</code>.  Given a tree and a delta, one can assemble
33   * the complete tree that the delta represents using the method <code>
34   * assembleWithForwardDelta</code>.  Refer to the public API methods of this class
35   * for further details.
36   */
37  
38  public class DeltaDataTree extends AbstractDataTree {
39      private AbstractDataTreeNode rootNode;
40      private DeltaDataTree parent;
41  
42      /**
43       * Creates a new empty tree.
44       */
45      public DeltaDataTree() {
46          this.empty();
47      }
48  
49      /**
50       * Creates a new tree.
51       * @param rootNode
52       *  root node of new tree.
53       */
54      public DeltaDataTree(AbstractDataTreeNode rootNode) {
55          this.rootNode = rootNode;
56          this.parent = null;
57      }
58  
59      protected DeltaDataTree(AbstractDataTreeNode rootNode, DeltaDataTree parent) {
60          this.rootNode = rootNode;
61          this.parent = parent;
62      }
63  
64      /**
65       * Adds a child to the tree.
66       *
67       * @param parentKey parent for new child.
68       * @param localName name of child.
69       * @param childNode child node.
70       */
71      protected void addChild(IPath parentKey, String   localName, AbstractDataTreeNode childNode) {
72          if (!includes(parentKey))
73              handleNotFound(parentKey);
74          childNode.setName(localName);
75          this.assembleNode(parentKey, new NoDataDeltaNode(parentKey.lastSegment(), childNode));
76      }
77  
78      /**
79       * Returns the tree as a backward delta.  If the delta is applied to the tree it
80       * will produce its parent. The receiver must have a forward 
81       * delta representation. I.e.:  Call the receiver's parent A, 
82       * and the receiver B.  The receiver's representation is A->B.
83       * Returns the delta A<-B.  The result is equivalent to A, but has B as its parent.
84       */
85      DeltaDataTree asBackwardDelta() {
86          if (getParent() == null)
87              return newEmptyDeltaTree();
88          return new DeltaDataTree(getRootNode().asBackwardDelta(this, getParent(), rootKey()), this);
89      }
90  
91      /**
92       * This method can only be called on a comparison tree created
93       * using DeltaDataTree.compareWith().  This method flips the orientation
94       * of the given comparison tree, so that additions become removals,
95       * and vice-versa.  This method destructively changes the tree
96       * as opposed to making a copy.
97       */
98      public DeltaDataTree asReverseComparisonTree(IComparator comparator) {
99          /* don't reverse the root node if it's the absolute root (name==null) */
100         if (rootNode.getName() == null) {
101             AbstractDataTreeNode[] children = rootNode.getChildren();
102             int nextChild = 0;
103             for (int i = 0; i < children.length; i++) {
104                 AbstractDataTreeNode newChild = children[i].asReverseComparisonNode(comparator);
105                 if (newChild != null) {
106                     children[nextChild++] = newChild;
107                 }
108             }
109 
110             if (nextChild < children.length) {
111                 AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[nextChild];
112                 System.arraycopy(children, 0, newChildren, 0, nextChild);
113                 rootNode.setChildren(newChildren);
114             }
115         } else {
116             rootNode.asReverseComparisonNode(comparator);
117         }
118         return this;
119     }
120 
121     /**
122      * Replaces a node in the tree with the result of assembling the node
123      * with the given delta node (which represents a forward delta on 
124      * the existing node).
125      *
126      * @param key key of the node to replace.
127      * @param deltaNode delta node to use to assemble the new node.
128      */
129     protected void assembleNode(IPath key, AbstractDataTreeNode deltaNode) {
130         rootNode = rootNode.assembleWith(deltaNode, key, 0);
131     }
132 
133     /**
134      * Assembles the receiver with the given delta tree and answer 
135      * the resulting, mutable source tree.  The given delta tree must be a 
136      * forward delta based on the receiver (i.e. missing information is taken from 
137      * the receiver).  This operation is used to coalesce delta trees.
138      *
139      * <p>In detail, suppose that c is a forward delta over source tree a.
140      * Let d := a assembleWithForwardDelta: c.
141      * d has the same content as c, and is represented as a delta tree
142      * whose parent is the same as a's parent.
143      *
144      * <p>In general, if c is represented as a chain of deltas of length n,
145      * then d is represented as a chain of length n-1.
146      *
147      * <p>So if a is a complete tree (i.e., has no parent, length=0), then d
148      * will be a complete tree too.
149      *
150      * <p>Corollary: (a assembleWithForwardDelta: (a forwardDeltaWith: b)) = b
151      */
152     public DeltaDataTree assembleWithForwardDelta(DeltaDataTree deltaTree) {
153         return new DeltaDataTree(getRootNode().assembleWith(deltaTree.getRootNode()), this);
154     }
155 
156     /**
157      * Compares this tree with another tree, starting from the given path.  The
158      * given path will be the root node of the returned tree.  Both this
159      * tree and other tree must contain the given path.
160      */
161     protected DeltaDataTree basicCompare(DeltaDataTree other, IComparator comparator, IPath path) {
162         DeltaDataTree newTree;
163         if (this == other) {
164             newTree = new DeltaDataTree();
165             newTree.setData(Path.ROOT, new NodeComparison(null, null, 0, 0));
166         } else if (other.hasAncestor(this)) {
167             AbstractDataTreeNode assembled = other.searchNodeAt(path);
168             DeltaDataTree tree = other;
169 
170             /* Iterate through the receiver's ancestors until the receiver is reached */
171             while ((tree = tree.getParent()) != this) {
172                 //ancestor may not contain the given path
173                 AbstractDataTreeNode treeNode = tree.searchNodeAt(path);
174                 if (treeNode != null) {
175                     assembled = treeNode.assembleWith(assembled);
176                 }
177             }
178             AbstractDataTreeNode comparedRoot = assembled.compareWithParent(path, this, comparator);
179             newTree = new DeltaDataTree(comparedRoot);
180         } else if (this.hasAncestor(other)) {
181             AbstractDataTreeNode assembled = this.asBackwardDelta().searchNodeAt(path);
182             DeltaDataTree tree = this;
183 
184             /* Iterate through the receiver's ancestors until the other tree is reached */
185             while ((tree = tree.getParent()) != other) {
186                 assembled = assembled.assembleWith(tree.asBackwardDelta().searchNodeAt(path));
187             }
188             AbstractDataTreeNode comparedRoot = assembled.compareWithParent(path, this, comparator);
189             newTree = new DeltaDataTree(comparedRoot);
190         } else {
191             //revert to naive comparison
192             DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(path);
193             DataTreeNode otherCompleteRoot = (DataTreeNode) other.copyCompleteSubtree(path);
194             AbstractDataTreeNode comparedRoot = thisCompleteRoot.compareWith(otherCompleteRoot, comparator);
195             newTree = new DeltaDataTree(comparedRoot);
196         }
197         newTree.immutable();
198         return newTree;
199     }
200 
201     /**
202      * Collapses this tree so that the given ancestor becomes its
203      * immediate parent.  Afterwards, this tree will still have exactly the
204      * same contents, but its internal structure will be compressed.
205      *
206      * <p> This operation should be used to collapse chains of
207      * delta trees that don't contain interesting intermediate states.
208      *
209      * <p>This is a destructive operation, since it modifies the structure of this 
210      * tree instance.  This tree must be immutable at the start of this operation,
211      * and will be immutable afterwards.  
212      * @return this tree.
213      */
214     public DeltaDataTree collapseTo(DeltaDataTree collapseTo, IComparator comparator) {
215         if (this == collapseTo || getParent() == collapseTo) {
216             //already collapsed
217             return this;
218         }
219         //collapse my tree to be a forward delta of the parent's tree.
220         //c will have the same content as this tree, but its parent will be "parent".
221         DeltaDataTree c = collapseTo.forwardDeltaWith(this, comparator);
222 
223         //update my internal root node and parent pointers.
224         this.parent = collapseTo;
225         this.rootNode = c.rootNode;
226         return this;
227     }
228 
229     /**
230      * Returns a DeltaDataTree that describes the differences between
231      * this tree and "other" tree.  Each node of the returned tree
232      * will contain a NodeComparison object that describes the differences
233      * between the two trees.
234      */
235     public DeltaDataTree compareWith(DeltaDataTree other, IComparator comparator) {
236 
237         DeltaDataTree newTree;
238         if (this == other) {
239             newTree = new DeltaDataTree();
240             newTree.setData(Path.ROOT, new NodeComparison(null, null, 0, 0));
241         } else if (other.hasAncestor(this)) {
242 
243             AbstractDataTreeNode assembled = other.getRootNode();
244             DeltaDataTree tree = other;
245 
246             /* Iterate through the receiver's ancestors until the receiver is reached */
247             while ((tree = tree.getParent()) != this) {
248                 assembled = tree.getRootNode().assembleWith(assembled);
249             }
250             AbstractDataTreeNode comparedRoot = assembled.compareWithParent(rootKey(), this, comparator);
251             newTree = new DeltaDataTree(comparedRoot);
252         } else if (this.hasAncestor(other)) {
253             AbstractDataTreeNode assembled = this.asBackwardDelta().getRootNode();
254             DeltaDataTree tree = this;
255 
256             /* Iterate through the receiver's ancestors until the other tree is reached */
257             while ((tree = tree.getParent()) != other) {
258                 assembled = assembled.assembleWith(tree.asBackwardDelta().getRootNode());
259             }
260             AbstractDataTreeNode comparedRoot = assembled.compareWithParent(rootKey(), this, comparator);
261             newTree = new DeltaDataTree(comparedRoot);
262         } else {
263             //revert to naive comparison if trees have no common ancestry
264             DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(rootKey());
265             DataTreeNode otherCompleteRoot = (DataTreeNode) other.copyCompleteSubtree(rootKey());
266             AbstractDataTreeNode comparedRoot = thisCompleteRoot.compareWith(otherCompleteRoot, comparator);
267             newTree = new DeltaDataTree(comparedRoot);
268         }
269         newTree.immutable();
270         return newTree;
271     }
272 
273     /**
274      * Compares this tree with another tree, starting from the given path.  The
275      * given path will be the root node of the returned tree.
276      */
277     public DeltaDataTree compareWith(DeltaDataTree other, IComparator comparator, IPath path) {
278         /* need to figure out if trees really contain the given path */
279         if (this.includes(path)) {
280             if (other.includes(path))
281                 return basicCompare(other, comparator, path);
282             /* only exists in this tree */
283             return new DeltaDataTree(AbstractDataTreeNode.convertToRemovedComparisonNode(this.copyCompleteSubtree(path), comparator.compare(this.getData(path), null)));
284         }
285         if (other.includes(path))
286             /* only exists in other tree */
287             return new DeltaDataTree(AbstractDataTreeNode.convertToAddedComparisonNode(other.copyCompleteSubtree(path), comparator.compare(null, other.getData(path))));
288         /* doesn't exist in either tree */
289         return DeltaDataTree.createEmptyDelta();
290     }
291 
292     /**
293      * Returns a copy of the tree which shares its instance variables.
294      */
295     protected AbstractDataTree copy() {
296         return new DeltaDataTree(rootNode, parent);
297     }
298 
299     /**
300      * Returns a complete node containing the contents of a subtree of the tree.
301      *
302      * @param key
303      *  key of subtree to copy
304      */
305     public AbstractDataTreeNode copyCompleteSubtree(IPath key) {
306         AbstractDataTreeNode node = searchNodeAt(key);
307         if (node == null) {
308             handleNotFound(key);
309             return null;
310         }
311         if (node.isDelta())
312             return naiveCopyCompleteSubtree(key);
313         //copy the node in case the user wants to hammer the subtree name
314         return node.copy();
315     }
316 
317     /**
318      * @see AbstractDataTree#createChild(IPath, String)
319      */
320     public void createChild(IPath parentKey, String   localName) {
321         createChild(parentKey, localName, null);
322     }
323 
324     /**
325      * @see AbstractDataTree#createChild(IPath, String, Object)
326      */
327     public void createChild(IPath parentKey, String   localName, Object   data) {
328         if (isImmutable())
329             handleImmutableTree();
330         addChild(parentKey, localName, new DataTreeNode(localName, data));
331     }
332 
333     /**
334      * Returns a delta data tree that represents an empty delta.
335      * (i.e. it represents a delta on another (unspecified) tree, 
336      * but introduces no changes).
337      */
338     static DeltaDataTree createEmptyDelta() {
339 
340         DeltaDataTree newTree = new DeltaDataTree();
341         newTree.emptyDelta();
342         return newTree;
343     }
344 
345     /**
346      * Creates and returns an instance of the receiver.
347      * @see AbstractDataTree#createInstance()
348      */
349     protected AbstractDataTree createInstance() {
350         return new DeltaDataTree();
351     }
352 
353     /**
354      * @see AbstractDataTree#createSubtree(IPath, AbstractDataTreeNode)
355      */
356     public void createSubtree(IPath key, AbstractDataTreeNode node) {
357         if (isImmutable())
358             handleImmutableTree();
359         if (key.isRoot()) {
360             setParent(null);
361             setRootNode(node);
362         } else {
363             addChild(key.removeLastSegments(1), key.lastSegment(), node);
364         }
365     }
366 
367     /**
368      * @see AbstractDataTree#deleteChild(IPath, String)
369      */
370     public void deleteChild(IPath parentKey, String   localName) {
371         if (isImmutable())
372             handleImmutableTree();
373         /* If the child does not exist */
374         IPath childKey = parentKey.append(localName);
375         if (!includes(childKey))
376             handleNotFound(childKey);
377         assembleNode(parentKey, new NoDataDeltaNode(parentKey.lastSegment(), new DeletedNode(localName)));
378     }
379 
380     /**
381      * Initializes the receiver so that it is a complete, empty tree. 
382      * @see AbstractDataTree#empty()
383      */
384     public void empty() {
385         rootNode = new DataTreeNode(null, null);
386         parent = null;
387     }
388 
389     /**
390      * Initializes the receiver so that it represents an empty delta.
391      * (i.e. it represents a delta on another (unspecified) tree, 
392      * it introduces no changes).  The parent is left unchanged.
393      */
394     void emptyDelta() {
395         rootNode = new NoDataDeltaNode(null);
396     }
397 
398     /**
399      * Returns a node of the tree if it is present, otherwise returns null
400      *
401      * @param key
402      *  key of node to find
403      */
404     public AbstractDataTreeNode findNodeAt(IPath key) {
405         AbstractDataTreeNode node = rootNode;
406         int segmentCount = key.segmentCount();
407         for (int i = 0; i < segmentCount; i++) {
408             node = node.childAtOrNull(key.segment(i));
409             if (node == null)
410                 return null;
411         }
412         return node;
413     }
414 
415     /**
416      * Returns a forward delta between the receiver and the given source tree,
417      * using the given comparer to compare data objects.  
418      * The result describes the changes which, if assembled with the receiver,
419      * will produce the given source tree.
420      * In more detail, let c = a.forwardDeltaWith(b).
421      * c has the same content as b, but is represented as a delta tree with a as the parent.
422      * Also, c is immutable.
423      *
424      * There is no requirement that a and b be related, although it is usually more
425      * efficient if they are. The node keys are used as the basis of correlation
426      * between trees.
427      * 
428      * Note that if b is already represented as a delta over a, 
429      * then c will have the same internal structure as b.
430      * Thus the very common case of previous forwardDeltaWith: current
431      * is actually very fast when current is a modification of previous.
432      *
433      * @param sourceTree second delta tree to create a delta between
434      * @param comparer the comparer used to compare data objects
435      * @return the new delta
436      */
437     public DeltaDataTree forwardDeltaWith(DeltaDataTree sourceTree, IComparator comparer) {
438         DeltaDataTree newTree;
439         if (this == sourceTree) {
440             newTree = this.newEmptyDeltaTree();
441         } else if (sourceTree.hasAncestor(this)) {
442             AbstractDataTreeNode assembled = sourceTree.getRootNode();
443             DeltaDataTree treeParent = sourceTree;
444 
445             /* Iterate through the sourceTree's ancestors until the receiver is reached */
446             while ((treeParent = treeParent.getParent()) != this) {
447                 assembled = treeParent.getRootNode().assembleWith(assembled);
448             }
449             newTree = new DeltaDataTree(assembled, this);
450             newTree.simplify(comparer);
451         } else if (this.hasAncestor(sourceTree)) {
452             //create the delta backwards and then reverse it
453             newTree = sourceTree.forwardDeltaWith(this, comparer);
454             newTree = newTree.asBackwardDelta();
455         } else {
456             DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(rootKey());
457             DataTreeNode sourceTreeCompleteRoot = (DataTreeNode) sourceTree.copyCompleteSubtree(rootKey());
458             AbstractDataTreeNode deltaRoot = thisCompleteRoot.forwardDeltaWith(sourceTreeCompleteRoot, comparer);
459             newTree = new DeltaDataTree(deltaRoot, this);
460         }
461         newTree.immutable();
462         return newTree;
463     }
464 
465     /**
466      * @see AbstractDataTree#getChildCount(IPath)
467      */
468     public int getChildCount(IPath parentKey) {
469         return getChildNodes(parentKey).length;
470     }
471 
472     /**
473      * Returns the child nodes of a node in the tree.
474      */
475     protected AbstractDataTreeNode[] getChildNodes(IPath parentKey) {
476 
477         /* Algorithm:
478          *   for each delta in chain (going backwards),
479          *     get list of child nodes, if any in delta
480          *     assemble with previously seen list, if any
481          *     break when complete tree found, 
482          *   report error if parent is missing or has been deleted
483          */
484 
485         AbstractDataTreeNode[] childNodes = null;
486         int keyLength = parentKey.segmentCount();
487         for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
488             AbstractDataTreeNode node = tree.rootNode;
489             boolean complete = !node.isDelta();
490             for (int i = 0; i < keyLength; i++) {
491                 node = node.childAtOrNull(parentKey.segment(i));
492                 if (node == null) {
493                     break;
494                 }
495                 if (!node.isDelta()) {
496                     complete = true;
497                 }
498             }
499             if (node != null) {
500                 if (node.isDeleted()) {
501                     break;
502                 }
503                 if (childNodes == null) {
504                     childNodes = node.children;
505                 } else {
506                     // Be sure to assemble(old, new) rather than (new, old).
507                     // Keep deleted nodes if we haven't encountered the complete node yet.
508                     childNodes = AbstractDataTreeNode.assembleWith(node.children, childNodes, !complete);
509                 }
510             }
511             if (complete) {
512                 if (childNodes != null) {
513                     return childNodes;
514                 }
515                 // Not found, but complete node encountered, so should not check parent tree.
516                 break;
517             }
518         }
519         if (childNodes != null) {
520             // Some deltas carry info about children, but there is
521             // no complete node against which they describe deltas.
522             Assert.isTrue(false, Messages.dtree_malformedTree);
523         }
524 
525         // Node is missing or has been deleted.
526         handleNotFound(parentKey);
527         return null;//should not get here
528     }
529 
530     /**
531      * @see AbstractDataTree#getChildren(IPath)
532      */
533     public IPath[] getChildren(IPath parentKey) {
534         AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
535         int len = childNodes.length;
536         if (len == 0)
537             return NO_CHILDREN;
538         IPath[] answer = new IPath[len];
539         for (int i = 0; i < len; ++i)
540             answer[i] = parentKey.append(childNodes[i].name);
541         return answer;
542     }
543 
544     /**
545      * Returns the data at a node of the tree.
546      *
547      * @param key
548      *  key of node for which to return data.
549      */
550     public Object   getData(IPath key) {
551 
552         /* Algorithm:
553          *   for each delta in chain (going backwards),
554          *     get node, if any in delta
555          *     if it carries data, return it
556          *     break when complete tree found
557          *   report error if node is missing or has been deleted
558          */
559 
560         int keyLength = key.segmentCount();
561         for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
562             AbstractDataTreeNode node = tree.rootNode;
563             boolean complete = !node.isDelta();
564             for (int i = 0; i < keyLength; i++) {
565                 node = node.childAtOrNull(key.segment(i));
566                 if (node == null) {
567                     break;
568                 }
569                 if (!node.isDelta()) {
570                     complete = true;
571                 }
572             }
573             if (node != null) {
574                 if (node.hasData()) {
575                     return node.getData();
576                 } else if (node.isDeleted()) {
577                     break;
578                 }
579             }
580             if (complete) {
581                 // Not found, but complete node encountered, so should not check parent tree.
582                 break;
583             }
584         }
585         handleNotFound(key);
586         return null; //can't get here
587     }
588 
589     /**
590      * @see AbstractDataTree#getNameOfChild(IPath, int)
591      */
592     public String   getNameOfChild(IPath parentKey, int index) {
593         AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
594         return childNodes[index].name;
595     }
596 
597     /**
598      * Returns the local names for the children of a node of the tree.
599      *
600      * @see AbstractDataTree#getNamesOfChildren(IPath)
601      */
602     public String  [] getNamesOfChildren(IPath parentKey) {
603         AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
604         int len = childNodes.length;
605         String  [] namesOfChildren = new String  [len];
606         for (int i = 0; i < len; ++i)
607             namesOfChildren[i] = childNodes[i].name;
608         return namesOfChildren;
609     }
610 
611     /** 
612      * Returns the parent of the tree.
613      */
614     public DeltaDataTree getParent() {
615         return parent;
616     }
617 
618     /**
619      * Returns the root node of the tree.
620      */
621     protected AbstractDataTreeNode getRootNode() {
622         return rootNode;
623     }
624 
625     /**
626      * Returns true if the receiver's parent has the specified ancestor
627      *
628      * @param ancestor the ancestor in question
629      */
630     protected boolean hasAncestor(DeltaDataTree ancestor) {
631         DeltaDataTree myParent = this;
632         while ((myParent = myParent.getParent()) != null) {
633             if (myParent == ancestor) {
634                 return true;
635             }
636         }
637         return false;
638     }
639 
640     /**
641      * Returns true if the receiver includes a node with
642      * the given key, false otherwise.
643      */
644     public boolean includes(IPath key) {
645         return searchNodeAt(key) != null;
646     }
647     
648     public boolean isEmptyDelta() {
649         return rootNode.getChildren().length == 0;
650     }
651 
652     /**
653      * Returns an object containing:
654      *  - the node key
655      *  - a flag indicating whether the specified node was found
656      *  - the data for the node, if it was found
657      *
658      * @param key  key of node for which we want to retrieve data.
659      */
660     public DataTreeLookup lookup(IPath key) {
661         int keyLength = key.segmentCount();
662         for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
663             AbstractDataTreeNode node = tree.rootNode;
664             boolean complete = !node.isDelta();
665             for (int i = 0; i < keyLength; i++) {
666                 node = node.childAtOrNull(key.segment(i));
667                 if (node == null) {
668                     break;
669                 }
670                 complete |= !node.isDelta();
671             }
672             if (node != null) {
673                 if (node.hasData()) {
674                     return DataTreeLookup.newLookup(key, true, node.getData(), tree == this);
675                 } else if (node.isDeleted()) {
676                     break;
677                 }
678             }
679             if (complete) {
680                 // Not found, but complete node encountered, so should not check parent tree.
681                 break;
682             }
683         }
684         return DataTreeLookup.newLookup(key, false, null);
685     }
686 
687     /**
688      * Returns an object containing:
689      *  - the node key
690      *  - a flag indicating whether the specified node was found
691      *  - the data for the node, if it was found
692      * 
693      * This is a case-insensitive variant of the <code>lookup</code>
694      * method.
695      *
696      * @param key  key of node for which we want to retrieve data.
697      */
698     public DataTreeLookup lookupIgnoreCase(IPath key) {
699         int keyLength = key.segmentCount();
700         for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
701             AbstractDataTreeNode node = tree.rootNode;
702             boolean complete = !node.isDelta();
703             for (int i = 0; i < keyLength; i++) {
704                 node = node.childAtIgnoreCase(key.segment(i));
705                 if (node == null) {
706                     break;
707                 }
708                 complete |= !node.isDelta();
709             }
710             if (node != null) {
711                 if (node.hasData()) {
712                     return DataTreeLookup.newLookup(key, true, node.getData(), tree == this);
713                 } else if (node.isDeleted()) {
714                     break;
715                 }
716             }
717             if (complete) {
718                 // Not found, but complete node encountered, so should not check parent tree.
719                 break;
720             }
721         }
722         return DataTreeLookup.newLookup(key, false, null);
723     }
724 
725     /**
726      * Converts this tree's representation to be a complete tree, not a delta.
727      * This disconnects this tree from its parents.
728      * The parent trees are unaffected.
729      */
730     public void makeComplete() {
731         AbstractDataTreeNode assembled = getRootNode();
732         DeltaDataTree myParent = getParent();
733         while (myParent != null) {
734             assembled = myParent.getRootNode().assembleWith(assembled);
735             myParent = myParent.getParent();
736         }
737         setRootNode(assembled);
738         setParent(null);
739     }
740 
741     /**
742      * Returns a complete node containing the contents of the subtree 
743      * rooted at <code>key</code> in the receiver.  Uses the public API.
744      *
745      * @param key
746      *  key of subtree whose contents we want to copy.
747      */
748     protected AbstractDataTreeNode naiveCopyCompleteSubtree(IPath key) {
749         String  [] childNames = getNamesOfChildren(key);
750         int numChildren = childNames.length;
751         AbstractDataTreeNode[] childNodes;
752         if (numChildren == 0) {
753             childNodes = AbstractDataTreeNode.NO_CHILDREN;
754         } else {
755             childNodes = new AbstractDataTreeNode[numChildren];
756             /* do for each child */
757             for (int i = numChildren; --i >= 0;) {
758                 childNodes[i] = copyCompleteSubtree(key.append(childNames[i]));
759             }
760         }
761         return new DataTreeNode(key.lastSegment(), getData(key), childNodes);
762     }
763 
764     /**
765      * Returns a new tree which represents an empty, mutable delta on the
766      * receiver.  It is not possible to obtain a new delta tree if the receiver is
767      * not immutable, as subsequent changes to the receiver would affect the
768      * resulting delta.
769      */
770     public DeltaDataTree newEmptyDeltaTree() {
771         if (!isImmutable())
772             throw new IllegalArgumentException  (Messages.dtree_notImmutable);
773         DeltaDataTree newTree = (DeltaDataTree) this.copy();
774         newTree.setParent(this);
775         newTree.emptyDelta();
776         return newTree;
777     }
778 
779     /**
780      * Makes the receiver the root tree in the list of trees on which it is based.
781      * The receiver's representation becomes a complete tree, while its parents'
782      * representations become backward deltas based on the receiver.
783      * It is not possible to re-root a source tree that is not immutable, as this
784      * would require that its parents be expressed as deltas on a source tree
785      * which could still change.
786      *
787      * @exception RuntimeException
788      *  receiver is not immutable
789      */
790     public DeltaDataTree reroot() {
791         /* self mutex critical region */
792         reroot(this);
793         return this;
794     }
795 
796     /**
797      * Makes the given source tree the root tree in the list of trees on which it is based.
798      * The source tree's representation becomes a complete tree, while its parents'
799      * representations become backward deltas based on the source tree.
800      * It is not possible to re-root a source tree that is not immutable, as this
801      * would require that its parents be expressed as deltas on a source tree
802      * which could still change.
803      *
804      * @param sourceTree
805      *  source tree to set as the new root
806      * @exception RuntimeException
807      *  sourceTree is not immutable
808      */
809     protected void reroot(DeltaDataTree sourceTree) {
810         if (!sourceTree.isImmutable())
811             handleImmutableTree();
812         DeltaDataTree sourceParent = sourceTree.getParent();
813         if (sourceParent == null)
814             return;
815         this.reroot(sourceParent);
816         DeltaDataTree backwardDelta = sourceTree.asBackwardDelta();
817         DeltaDataTree complete = sourceParent.assembleWithForwardDelta(sourceTree);
818         sourceTree.setRootNode(complete.getRootNode());
819         sourceTree.setParent(null);
820         sourceParent.setRootNode(backwardDelta.getRootNode());
821         sourceParent.setParent(sourceTree);
822     }
823 
824     /**
825      * Returns a complete node containing the contents of a subtree of the tree.
826      * Returns null  if the node at this key does not exist.  This is a thread-safe
827      * version of copyCompleteSubtree
828      *
829      * @param key key of subtree to copy
830      */
831     public AbstractDataTreeNode safeCopyCompleteSubtree(IPath key) {
832         AbstractDataTreeNode node = searchNodeAt(key);
833         if (node == null)
834             return null;
835         if (node.isDelta())
836             return safeNaiveCopyCompleteSubtree(key);
837         //copy the node in case the user wants to hammer the subtree name
838         return node.copy();
839     }
840 
841     /**
842      * Returns a complete node containing the contents of the subtree 
843      * rooted at @key in the receiver.  Returns null if this node does not exist in
844      * the tree.  This is a thread-safe version of naiveCopyCompleteSubtree
845      *
846      * @param key
847      *  key of subtree whose contents we want to copy.
848      */
849     protected AbstractDataTreeNode safeNaiveCopyCompleteSubtree(IPath key) {
850         try {
851             String  [] childNames = getNamesOfChildren(key);
852             int numChildren = childNames.length;
853             AbstractDataTreeNode[] childNodes;
854             if (numChildren == 0) {
855                 childNodes = AbstractDataTreeNode.NO_CHILDREN;
856             } else {
857                 childNodes = new AbstractDataTreeNode[numChildren];
858                 /* do for each child */
859                 int actualChildCount = 0;
860                 for (int i = numChildren; --i >= 0;) {
861                     childNodes[i] = safeCopyCompleteSubtree(key.append(childNames[i]));
862                     if (childNodes[i] != null)
863                         actualChildCount++;
864                 }
865                 //if there are less actual children due to concurrent deletion, shrink the child array
866                 if (actualChildCount < numChildren) {
867                     AbstractDataTreeNode[] actualChildNodes = new AbstractDataTreeNode[actualChildCount];
868                     for (int iOld = 0, iNew = 0; iOld < numChildren; iOld++)
869                         if (childNodes[iOld] != null)
870                             actualChildNodes[iNew++] = childNodes[iOld];
871                     childNodes = actualChildNodes;
872                 }
873             }
874             return new DataTreeNode(key.lastSegment(), getData(key), childNodes);
875         } catch (ObjectNotFoundException e) {
876             return null;
877         }
878     }
879 
880     /**
881      * Returns the specified node.  Search in the parent if necessary.  Return null
882      * if the node is not found or if it has been deleted
883      */
884     protected AbstractDataTreeNode searchNodeAt(IPath key) {
885         int keyLength = key.segmentCount();
886         for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
887             AbstractDataTreeNode node = tree.rootNode;
888             boolean complete = !node.isDelta();
889             for (int i = 0; i < keyLength; i++) {
890                 node = node.childAtOrNull(key.segment(i));
891                 if (node == null) {
892                     break;
893                 }
894                 if (!node.isDelta()) {
895                     complete = true;
896                 }
897             }
898             if (node != null) {
899                 if (node.isDeleted())
900                     break;
901                 return node;
902             }
903             if (complete) {
904                 // Not found, but complete node encountered, so should not check parent tree.
905                 break;
906             }
907         }
908         return null;
909     }
910 
911     /**
912      * @see AbstractDataTree#setData(IPath, Object)
913      */
914     public void setData(IPath key, Object   data) {
915         if (isImmutable())
916             handleImmutableTree();
917         if (!includes(key))
918             handleNotFound(key);
919         assembleNode(key, new DataDeltaNode(key.lastSegment(), data));
920     }
921 
922     /**
923      * Sets the parent of the tree.
924      */
925     protected void setParent(DeltaDataTree aTree) {
926         parent = aTree;
927     }
928 
929     /**
930      * Sets the root node of the tree
931      */
932     void setRootNode(AbstractDataTreeNode aNode) {
933         rootNode = aNode;
934     }
935 
936     /**
937      * Simplifies the receiver:
938      *  - replaces any DataDelta nodes with the same data as the parent 
939      *    with a NoDataDelta node
940      *  - removes any empty (leaf NoDataDelta) nodes
941      */
942     protected void simplify(IComparator comparer) {
943         if (parent == null)
944             return;
945         setRootNode(rootNode.simplifyWithParent(rootKey(), parent, comparer));
946     }
947 
948     /* (non-Javadoc
949      * Method declared on IStringPoolParticipant
950      */
951     public void storeStrings(StringPool set) {
952         //copy field to protect against concurrent changes
953         AbstractDataTreeNode root = rootNode;
954         DeltaDataTree dad = parent;
955         if (root != null)
956             root.storeStrings(set);
957         if (dad != null)
958             dad.storeStrings(set);
959     }
960 }
961
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags