DataTreeNode


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.*;
14  import org.eclipse.core.runtime.Assert;
15  import org.eclipse.core.runtime.IPath;
16  
17  /**
18   * <code>DataTreeNode</code>s are the nodes of a <code>DataTree</code>.  Their
19   * information and their subtrees are complete, and do not represent deltas on
20   * another node or subtree.
21   */
22  public class DataTreeNode extends AbstractDataTreeNode {
23      protected Object   data;
24  
25      /**
26       * Creates a new node
27       *
28       * @param name name of node
29       * @param data data for node
30       */
31      public DataTreeNode(String   name, Object   data) {
32          super(name, AbstractDataTreeNode.NO_CHILDREN);
33          this.data = data;
34      }
35  
36      /**
37       * Creates a new node
38       *
39       * @param name name of node
40       * @param data data for node
41       * @param children children for new node
42       */
43      public DataTreeNode(String   name, Object   data, AbstractDataTreeNode[] children) {
44          super(name, children);
45          this.data = data;
46      }
47  
48      /**
49       * @see AbstractDataTreeNode#asBackwardDelta(DeltaDataTree, DeltaDataTree, IPath)
50       */
51      AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key) {
52          if (parentTree.includes(key))
53              return parentTree.copyCompleteSubtree(key);
54          return new DeletedNode(name);
55      }
56  
57      /**
58       * If this node is a node in a comparison tree, this method reverses
59       * the comparison for this node and all children.  Returns null
60       * if this node should no longer be included in the comparison tree.
61       */
62      AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
63          NodeComparison comparison = null;
64          try {
65              comparison = ((NodeComparison) data).asReverseComparison(comparator);
66          } catch (ClassCastException   e) {
67              Assert.isTrue(false, Messages.dtree_reverse);
68          }
69  
70          int nextChild = 0;
71          for (int i = 0; i < children.length; i++) {
72              AbstractDataTreeNode child = children[i].asReverseComparisonNode(comparator);
73              if (child != null) {
74                  children[nextChild++] = child;
75              }
76          }
77  
78          if (nextChild == 0 && comparison.getUserComparison() == 0) {
79              /* no children and no change */
80              return null;
81          }
82  
83          /* set the new data */
84          data = comparison;
85  
86          /* shrink child array as necessary */
87          if (nextChild < children.length) {
88              AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[nextChild];
89              System.arraycopy(children, 0, newChildren, 0, nextChild);
90              children = newChildren;
91          }
92  
93          return this;
94      }
95  
96      AbstractDataTreeNode compareWith(DataTreeNode other, IComparator comparator) {
97          AbstractDataTreeNode[] comparedChildren = compareWith(children, other.children, comparator);
98          Object   oldData = data;
99          Object   newData = other.data;
100 
101         /* don't allow comparison of implicit root node */
102         int userComparison = 0;
103         if (name != null) {
104             userComparison = comparator.compare(oldData, newData);
105         }
106 
107         return new DataTreeNode(name, new NodeComparison(oldData, newData, NodeComparison.K_CHANGED, userComparison), comparedChildren);
108     }
109 
110     AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator) {
111         if (!parent.includes(key))
112             return convertToAddedComparisonNode(this, NodeComparison.K_ADDED);
113         DataTreeNode inParent = (DataTreeNode) parent.copyCompleteSubtree(key);
114         return inParent.compareWith(this, comparator);
115     }
116 
117     /**
118      * Creates and returns a new copy of the receiver.
119      */
120     AbstractDataTreeNode copy() {
121         if (children.length > 0) {
122             AbstractDataTreeNode[] childrenCopy = new AbstractDataTreeNode[children.length];
123             System.arraycopy(children, 0, childrenCopy, 0, children.length);
124             return new DataTreeNode(name, data, childrenCopy);
125         }
126         return new DataTreeNode(name, data, children);
127     }
128 
129     /**
130      * Returns a new node containing a child with the given local name in 
131      * addition to the receiver's current children and data.
132      * 
133      * @param localName
134      *  name of new child
135      * @param childNode
136      *  new child node
137      */
138     DataTreeNode copyWithNewChild(String   localName, DataTreeNode childNode) {
139 
140         AbstractDataTreeNode[] children = this.children;
141         int left = 0;
142         int right = children.length - 1;
143         while (left <= right) {
144             int mid = (left + right) / 2;
145             int compare = localName.compareTo(children[mid].name);
146             if (compare < 0) {
147                 right = mid - 1;
148             } else if (compare > 0) {
149                 left = mid + 1;
150             } else {
151                 throw new Error  (); // it shouldn't have been here yet
152             }
153         }
154 
155         AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[children.length + 1];
156         System.arraycopy(children, 0, newChildren, 0, left);
157         childNode.setName(localName);
158         newChildren[left] = childNode;
159         System.arraycopy(children, left, newChildren, left + 1, children.length - left);
160         return new DataTreeNode(this.getName(), this.getData(), newChildren);
161     }
162 
163     /**
164      * Returns a new node without the specified child, but with the rest
165      * of the receiver's current children and its data.
166      *
167      * @param localName
168      *  name of child to exclude
169      */
170     DataTreeNode copyWithoutChild(String   localName) {
171 
172         int index, newSize;
173         DataTreeNode newNode;
174         AbstractDataTreeNode children[];
175 
176         index = this.indexOfChild(localName);
177         if (index == -1) {
178             newNode = (DataTreeNode) this.copy();
179         } else {
180             newSize = this.size() - 1;
181             children = new AbstractDataTreeNode[newSize];
182             newNode = new DataTreeNode(this.getName(), this.getData(), children);
183             newNode.copyChildren(0, index - 1, this, 0); //#from:to:with:startingAt:
184             newNode.copyChildren(index, newSize - 1, this, index + 1);
185         }
186         return newNode;
187     }
188 
189     /**
190      * Returns an array of delta nodes representing the forward delta between
191      * the given two lists of nodes.
192      * The given nodes must all be complete nodes.
193      */
194     protected static AbstractDataTreeNode[] forwardDeltaWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparer) {
195         if (oldNodes.length == 0 && newNodes.length == 0) {
196             return NO_CHILDREN;
197         }
198 
199         AbstractDataTreeNode[] childDeltas = null;
200         int numChildDeltas = 0;
201         int childDeltaMax = 0;
202 
203         // do a merge
204         int oldIndex = 0;
205         int newIndex = 0;
206         while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
207             String   oldName = oldNodes[oldIndex].name;
208             String   newName = newNodes[newIndex].name;
209             int compare = oldName.compareTo(newName);
210             if (compare == 0) {
211                 AbstractDataTreeNode deltaNode = forwardDeltaWithOrNullIfEqual(oldNodes[oldIndex++], newNodes[newIndex++], comparer);
212                 if (deltaNode != null) {
213                     if (numChildDeltas >= childDeltaMax) {
214                         if (childDeltas == null)
215                             childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
216                         else
217                             System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
218                     }
219                     childDeltas[numChildDeltas++] = deltaNode;
220                 }
221             } else if (compare < 0) {
222                 if (numChildDeltas >= childDeltaMax) {
223                     if (childDeltas == null)
224                         childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
225                     else
226                         System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
227                 }
228                 childDeltas[numChildDeltas++] = new DeletedNode(oldName);
229                 oldIndex++;
230             } else {
231                 if (numChildDeltas >= childDeltaMax) {
232                     if (childDeltas == null)
233                         childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
234                     else
235                         System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
236                 }
237                 childDeltas[numChildDeltas++] = newNodes[newIndex++];
238             }
239         }
240         while (oldIndex < oldNodes.length) {
241             if (numChildDeltas >= childDeltaMax) {
242                 if (childDeltas == null)
243                     childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
244                 else
245                     System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
246             }
247             childDeltas[numChildDeltas++] = new DeletedNode(oldNodes[oldIndex++].name);
248         }
249         while (newIndex < newNodes.length) {
250             if (numChildDeltas >= childDeltaMax) {
251                 if (childDeltas == null)
252                     childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
253                 else
254                     System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
255             }
256             childDeltas[numChildDeltas++] = newNodes[newIndex++];
257         }
258 
259         // trim size of result
260         if (numChildDeltas == 0) {
261             return NO_CHILDREN;
262         }
263         if (numChildDeltas < childDeltaMax) {
264             System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[numChildDeltas], 0, numChildDeltas);
265         }
266         return childDeltas;
267     }
268 
269     /**
270      * Returns a node representing the forward delta between
271      * the given two (complete) nodes.
272      */
273     protected AbstractDataTreeNode forwardDeltaWith(DataTreeNode other, IComparator comparer) {
274         AbstractDataTreeNode deltaNode = forwardDeltaWithOrNullIfEqual(this, other, comparer);
275         if (deltaNode == null) {
276             return new NoDataDeltaNode(name, NO_CHILDREN);
277         }
278         return deltaNode;
279     }
280 
281     /**
282      * Returns a node representing the forward delta between
283      * the given two (complete) nodes, or null if the two nodes are equal.
284      * Although typed as abstract nodes, the given nodes must be complete.
285      */
286     protected static AbstractDataTreeNode forwardDeltaWithOrNullIfEqual(AbstractDataTreeNode oldNode, AbstractDataTreeNode newNode, IComparator comparer) {
287         AbstractDataTreeNode[] childDeltas = forwardDeltaWith(oldNode.children, newNode.children, comparer);
288         Object   newData = newNode.getData();
289         if (comparer.compare(oldNode.getData(), newData) == 0) {
290             if (childDeltas.length == 0) {
291                 return null;
292             }
293             return new NoDataDeltaNode(newNode.name, childDeltas);
294         }
295         return new DataDeltaNode(newNode.name, newData, childDeltas);
296     }
297 
298     /**
299      * Returns the data for the node 
300      */
301     public Object   getData() {
302         return data;
303     }
304 
305     /**
306      * Returns true if the receiver can carry data, false otherwise.
307      */
308     boolean hasData() {
309         return true;
310     }
311 
312     /**
313      * Sets the data for the node
314      */
315     void setData(Object   o) {
316         data = o;
317     }
318 
319     /** 
320      * Simplifies the given node, and answers its replacement.
321      */
322     AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer) {
323         /* If not in parent, can't be simplified */
324         if (!parent.includes(key)) {
325             return this;
326         }
327         /* Can't just call simplify on children since this will miss the case
328          where a child exists in the parent but does not in this. 
329          See PR 1FH5RYA. */
330         DataTreeNode parentsNode = (DataTreeNode) parent.copyCompleteSubtree(key);
331         return parentsNode.forwardDeltaWith(this, comparer);
332     }
333 
334     /* (non-Javadoc
335      * Method declared on IStringPoolParticipant
336      */
337     public void storeStrings(StringPool set) {
338         super.storeStrings(set);
339         //copy data for thread safety
340         Object   o = data;
341         if (o instanceof IStringPoolParticipant)
342             ((IStringPoolParticipant) o).shareStrings(set);
343     }
344 
345     /**
346      * Returns a unicode representation of the node.  This method is used
347      * for debugging purposes only (no NLS support needed)
348      */
349     public String   toString() {
350         return "a DataTreeNode(" + this.getName() + ") with " + getChildren().length + " children."; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
351     }
352 
353     /**
354      * Returns a constant describing the type of node.
355      */
356     int type() {
357         return T_COMPLETE_NODE;
358     }
359 }
360
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags