AbstractDataTreeNode


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.IPath;
16  import org.eclipse.osgi.util.NLS;
17  
18  /**
19   * This class and its subclasses are used to represent nodes of AbstractDataTrees.
20   * Refer to the DataTree API comments for more details.
21   * @see AbstractDataTree
22   */
23  public abstract class AbstractDataTreeNode {
24      /**
25       * Singleton indicating no children.
26       */
27      static final AbstractDataTreeNode[] NO_CHILDREN = new AbstractDataTreeNode[0];
28      protected AbstractDataTreeNode children[];
29      protected String   name;
30  
31      /* Node types for comparison */
32      public static final int T_COMPLETE_NODE = 0;
33      public static final int T_DELTA_NODE = 1;
34      public static final int T_DELETED_NODE = 2;
35      public static final int T_NO_DATA_DELTA_NODE = 3;
36  
37      /**
38       * Creates a new data tree node
39       *
40       * @param name
41       *  name of new node
42       * @param children
43       *  children of the new node
44       */
45      AbstractDataTreeNode(String   name, AbstractDataTreeNode[] children) {
46          this.name = name;
47          if (children == null || children.length == 0)
48              this.children = AbstractDataTreeNode.NO_CHILDREN;
49          else
50              this.children = children;
51      }
52  
53      /**
54       * Returns a node which if applied to the receiver will produce 
55       * the corresponding node in the given parent tree.
56       *
57       * @param myTree  tree to which the node belongs
58       * @param parentTree  parent tree on which to base backward delta
59       * @param key  key of node in its tree
60       */
61      abstract AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key);
62  
63      /**
64       * If this node is a node in a comparison tree, this method reverses
65       * the comparison for this node and all children
66       */
67      AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
68          return this;
69      }
70  
71      /**
72       * Returns the result of assembling nodes with the given forward delta nodes.
73       * Both arrays must be sorted by name.
74       * The result is sorted by name.
75       * If keepDeleted is true, explicit representations of deletions are kept,
76       * otherwise nodes to be deleted are removed in the result.
77       */
78      static AbstractDataTreeNode[] assembleWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, boolean keepDeleted) {
79  
80          // Optimize the common case where the new list is empty.
81          if (newNodes.length == 0)
82              return oldNodes;
83  
84          // Can't just return newNodes if oldNodes has length 0
85          // because newNodes may contain deleted nodes.
86  
87          AbstractDataTreeNode[] resultNodes = new AbstractDataTreeNode[oldNodes.length + newNodes.length];
88  
89          // do a merge
90          int oldIndex = 0;
91          int newIndex = 0;
92          int resultIndex = 0;
93          while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
94              int compare = oldNodes[oldIndex].name.compareTo(newNodes[newIndex].name);
95              if (compare == 0) {
96                  AbstractDataTreeNode node = oldNodes[oldIndex++].assembleWith(newNodes[newIndex++]);
97                  if (node != null && (!node.isDeleted() || keepDeleted)) {
98                      resultNodes[resultIndex++] = node;
99                  }
100             } else if (compare < 0) {
101                 resultNodes[resultIndex++] = oldNodes[oldIndex++];
102             } else if (compare > 0) {
103                 AbstractDataTreeNode node = newNodes[newIndex++];
104                 if (!node.isDeleted() || keepDeleted) {
105                     resultNodes[resultIndex++] = node;
106                 }
107             }
108         }
109         while (oldIndex < oldNodes.length) {
110             resultNodes[resultIndex++] = oldNodes[oldIndex++];
111         }
112         while (newIndex < newNodes.length) {
113             AbstractDataTreeNode resultNode = newNodes[newIndex++];
114             if (!resultNode.isDeleted() || keepDeleted) {
115                 resultNodes[resultIndex++] = resultNode;
116             }
117         }
118 
119         // trim size of result
120         if (resultIndex < resultNodes.length) {
121             System.arraycopy(resultNodes, 0, resultNodes = new AbstractDataTreeNode[resultIndex], 0, resultIndex);
122         }
123         return resultNodes;
124     }
125 
126     /**
127      * Returns the result of assembling this node with the given forward delta node.
128      */
129     AbstractDataTreeNode assembleWith(AbstractDataTreeNode node) {
130 
131         // If not a delta, or if the old node was deleted,
132         // then the new node represents the complete picture.
133         if (!node.isDelta() || this.isDeleted()) {
134             return node;
135         }
136 
137         // node must be either a DataDeltaNode or a NoDataDeltaNode
138         if (node.hasData()) {
139             if (this.isDelta()) {
140                 // keep deletions because they still need 
141                 // to hide child nodes in the parent.
142                 AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
143                 return new DataDeltaNode(name, node.getData(), assembledChildren);
144             }
145             // This is a complete picture, so deletions 
146             // wipe out the child and are no longer useful
147             AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
148             return new DataTreeNode(name, node.getData(), assembledChildren);
149         }
150         if (this.isDelta()) {
151             AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
152             if (this.hasData())
153                 return new DataDeltaNode(name, this.getData(), assembledChildren);
154             return new NoDataDeltaNode(name, assembledChildren);
155         }
156         AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
157         return new DataTreeNode(name, this.getData(), assembledChildren);
158     }
159 
160     /**
161      * Returns the result of assembling this node with the given forward delta node.
162      */
163     AbstractDataTreeNode assembleWith(AbstractDataTreeNode node, IPath key, int keyIndex) {
164 
165         // leaf case
166         int keyLen = key.segmentCount();
167         if (keyIndex == keyLen) {
168             return assembleWith(node);
169         }
170 
171         // non-leaf case
172         int childIndex = indexOfChild(key.segment(keyIndex));
173         if (childIndex >= 0) {
174             AbstractDataTreeNode copy = copy();
175             copy.children[childIndex] = children[childIndex].assembleWith(node, key, keyIndex + 1);
176             return copy;
177         }
178 
179         // Child not found.  Build up NoDataDeltaNode hierarchy for rest of key
180         // and assemble with that.
181         for (int i = keyLen - 2; i >= keyIndex; --i) {
182             node = new NoDataDeltaNode(key.segment(i), node);
183         }
184         node = new NoDataDeltaNode(name, node);
185         return assembleWith(node);
186     }
187 
188     /**
189      * Returns the child with the given local name.  The child must exist.
190      */
191     AbstractDataTreeNode childAt(String   localName) {
192         AbstractDataTreeNode node = childAtOrNull(localName);
193         if (node != null) {
194             return node;
195         }
196         throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
197     }
198 
199     /**
200      * Returns the child with the given local name.  Returns null if the child
201      * does not exist.
202      *
203      * @param localName
204      *  name of child to retrieve
205      */
206     AbstractDataTreeNode childAtOrNull(String   localName) {
207         int index = indexOfChild(localName);
208         return index >= 0 ? children[index] : null;
209     }
210 
211     /**
212      * Returns the child with the given local name, ignoring case.  
213      * If multiple case variants exist, the search will favour real nodes
214      * over deleted nodes. If multiple real nodes are found, the first one
215      * encountered in case order is returned. Returns null if no matching
216      * children are found.
217      * 
218      * @param localName name of child to retrieve
219      */
220     AbstractDataTreeNode childAtIgnoreCase(String   localName) {
221         AbstractDataTreeNode result = null;
222         for (int i = 0; i < children.length; i++) {
223             if (children[i].getName().equalsIgnoreCase(localName)) {
224                 //if we find a deleted child, keep looking for a real child
225                 if (children[i].isDeleted())
226                     result = children[i];
227                 else
228                     return children[i];
229             }
230         }
231         return result;
232     }
233 
234     /** 
235      */
236     protected static AbstractDataTreeNode[] compareWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparator) {
237 
238         int oldLen = oldNodes.length;
239         int newLen = newNodes.length;
240         int oldIndex = 0;
241         int newIndex = 0;
242         AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[oldLen + newLen];
243         int count = 0;
244 
245         while (oldIndex < oldLen && newIndex < newLen) {
246             DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex];
247             DataTreeNode newNode = (DataTreeNode) newNodes[newIndex];
248             int compare = oldNode.name.compareTo(newNode.name);
249             if (compare < 0) {
250                 /* give the client a chance to say whether it should be in the delta */
251                 int userComparison = comparator.compare(oldNode.getData(), null);
252                 if (userComparison != 0) {
253                     comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
254                 }
255                 ++oldIndex;
256             } else if (compare > 0) {
257                 /* give the client a chance to say whether it should be in the delta */
258                 int userComparison = comparator.compare(null, newNode.getData());
259                 if (userComparison != 0) {
260                     comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
261                 }
262                 ++newIndex;
263             } else {
264                 AbstractDataTreeNode comparedNode = oldNode.compareWith(newNode, comparator);
265                 NodeComparison comparison = (NodeComparison) comparedNode.getData();
266 
267                 /* skip empty comparisons */
268                 if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
269                     comparedNodes[count++] = comparedNode;
270                 }
271                 ++oldIndex;
272                 ++newIndex;
273             }
274         }
275         while (oldIndex < oldLen) {
276             DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex++];
277 
278             /* give the client a chance to say whether it should be in the delta */
279             int userComparison = comparator.compare(oldNode.getData(), null);
280             if (userComparison != 0) {
281                 comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
282             }
283         }
284         while (newIndex < newLen) {
285             DataTreeNode newNode = (DataTreeNode) newNodes[newIndex++];
286 
287             /* give the client a chance to say whether it should be in the delta */
288             int userComparison = comparator.compare(null, newNode.getData());
289             if (userComparison != 0) {
290                 comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
291             }
292         }
293 
294         if (count == 0) {
295             return NO_CHILDREN;
296         }
297         if (count < comparedNodes.length) {
298             System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
299         }
300         return comparedNodes;
301     }
302 
303     /** 
304      */
305     protected static AbstractDataTreeNode[] compareWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparator) {
306 
307         AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[nodes.length];
308         int count = 0;
309         for (int i = 0; i < nodes.length; ++i) {
310             AbstractDataTreeNode node = nodes[i];
311             AbstractDataTreeNode comparedNode = node.compareWithParent(key.append(node.getName()), parent, comparator);
312             NodeComparison comparison = (NodeComparison) comparedNode.getData();
313             // Skip it if it's an empty comparison (and no children).
314             if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
315                 comparedNodes[count++] = comparedNode;
316             }
317         }
318         if (count == 0) {
319             return NO_CHILDREN;
320         }
321         if (count < comparedNodes.length) {
322             System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
323         }
324         return comparedNodes;
325     }
326 
327     abstract AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator);
328 
329     static AbstractDataTreeNode convertToAddedComparisonNode(AbstractDataTreeNode newNode, int userComparison) {
330         AbstractDataTreeNode[] children = newNode.getChildren();
331         int n = children.length;
332         AbstractDataTreeNode[] convertedChildren;
333         if (n == 0) {
334             convertedChildren = NO_CHILDREN;
335         } else {
336             convertedChildren = new AbstractDataTreeNode[n];
337             for (int i = 0; i < n; ++i) {
338                 convertedChildren[i] = convertToAddedComparisonNode(children[i], userComparison);
339             }
340         }
341         return new DataTreeNode(newNode.name, new NodeComparison(null, newNode.getData(), NodeComparison.K_ADDED, userComparison), convertedChildren);
342     }
343 
344     static AbstractDataTreeNode convertToRemovedComparisonNode(AbstractDataTreeNode oldNode, int userComparison) {
345         AbstractDataTreeNode[] children = oldNode.getChildren();
346         int n = children.length;
347         AbstractDataTreeNode[] convertedChildren;
348         if (n == 0) {
349             convertedChildren = NO_CHILDREN;
350         } else {
351             convertedChildren = new AbstractDataTreeNode[n];
352             for (int i = 0; i < n; ++i) {
353                 convertedChildren[i] = convertToRemovedComparisonNode(children[i], userComparison);
354             }
355         }
356         return new DataTreeNode(oldNode.name, new NodeComparison(oldNode.getData(), null, NodeComparison.K_REMOVED, userComparison), convertedChildren);
357     }
358 
359     /**
360      * Returns a copy of the receiver which shares the receiver elements
361      */
362     abstract AbstractDataTreeNode copy();
363 
364     /**
365      * Replaces the receiver's children between "from" and "to", with the children
366      * in otherNode starting at "start".  This method replaces the Smalltalk
367      * #replaceFrom:to:with:startingAt: method for copying children in data nodes
368      */
369     protected void copyChildren(int from, int to, AbstractDataTreeNode otherNode, int start) {
370         int other = start;
371         for (int i = from; i <= to; i++, other++) {
372             this.children[i] = otherNode.children[other];
373         }
374     }
375 
376     /**
377      * Returns an array of the node's children
378      */
379     public AbstractDataTreeNode[] getChildren() {
380         return children;
381     }
382 
383     /**
384      * Returns the node's data
385      */
386     Object   getData() {
387         throw new AbstractMethodError  (Messages.dtree_subclassImplement);
388     }
389 
390     /**
391      * return the name of the node
392      */
393     public String   getName() {
394         return name;
395     }
396 
397     /**
398      * Returns true if the receiver can carry data, false otherwise.
399      */
400     boolean hasData() {
401         return false;
402     }
403 
404     /**
405      * Returns true if the receiver has a child with the given local name, 
406      * false otherwise
407      */
408     boolean includesChild(String   localName) {
409         return indexOfChild(localName) != -1;
410     }
411 
412     /**
413      * Returns the index of the specified child's name in the receiver.
414      */
415     protected int indexOfChild(String   localName) {
416         AbstractDataTreeNode[] nodes = this.children;
417         int left = 0;
418         int right = nodes.length - 1;
419         while (left <= right) {
420             int mid = (left + right) / 2;
421             int compare = localName.compareTo(nodes[mid].name);
422             if (compare < 0) {
423                 right = mid - 1;
424             } else if (compare > 0) {
425                 left = mid + 1;
426             } else {
427                 return mid;
428             }
429         }
430         return -1;
431     }
432 
433     /**
434      * Returns true if the receiver represents a deleted node, false otherwise.
435      */
436     boolean isDeleted() {
437         return false;
438     }
439 
440     /**
441      * Returns true if the receiver represents delta information,
442      * false if it represents the complete information.
443      */
444     boolean isDelta() {
445         return false;
446     }
447 
448     /**
449      * Returns true if the receiver is an empty delta node, false otherwise.
450      */
451     boolean isEmptyDelta() {
452         return false;
453     }
454 
455     /**
456      * Returns the local names of the receiver's children.
457      */
458     String  [] namesOfChildren() {
459         String   names[] = new String  [children.length];
460         /* copy child names (Reverse loop optimized) */
461         for (int i = children.length; --i >= 0;)
462             names[i] = children[i].getName();
463         return names;
464     }
465 
466     /**
467      * Replaces the child with the given local name.
468      */
469     void replaceChild(String   localName, DataTreeNode node) {
470         int i = indexOfChild(localName);
471         if (i >= 0) {
472             children[i] = node;
473         } else {
474             throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
475         }
476     }
477 
478     /**
479      * Set the node's children
480      */
481     protected void setChildren(AbstractDataTreeNode newChildren[]) {
482         children = newChildren;
483     }
484 
485     /**
486      * Set the node's name
487      */
488     void setName(String   s) {
489         name = s;
490     }
491 
492     /** 
493      * Simplifies the given nodes, and answers their replacements.
494      */
495     protected static AbstractDataTreeNode[] simplifyWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparer) {
496 
497         AbstractDataTreeNode[] simplifiedNodes = new AbstractDataTreeNode[nodes.length];
498         int simplifiedCount = 0;
499         for (int i = 0; i < nodes.length; ++i) {
500             AbstractDataTreeNode node = nodes[i];
501             AbstractDataTreeNode simplifiedNode = node.simplifyWithParent(key.append(node.getName()), parent, comparer);
502             if (!simplifiedNode.isEmptyDelta()) {
503                 simplifiedNodes[simplifiedCount++] = simplifiedNode;
504             }
505         }
506         if (simplifiedCount == 0) {
507             return NO_CHILDREN;
508         }
509         if (simplifiedCount < simplifiedNodes.length) {
510             System.arraycopy(simplifiedNodes, 0, simplifiedNodes = new AbstractDataTreeNode[simplifiedCount], 0, simplifiedCount);
511         }
512         return simplifiedNodes;
513     }
514 
515     /** 
516      * Simplifies the given node, and answers its replacement.
517      */
518     abstract AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer);
519 
520     /**
521      * Returns the number of children of the receiver
522      */
523     int size() {
524         return children.length;
525     }
526 
527     /* (non-Javadoc
528      * Method declared on IStringPoolParticipant
529      */
530     public void storeStrings(StringPool set) {
531         name = set.add(name);
532         //copy children pointer in case of concurrent modification
533         AbstractDataTreeNode[] nodes = children;
534         if (nodes != null)
535             for (int i = nodes.length; --i >= 0;)
536                 nodes[i].storeStrings(set);
537     }
538 
539     /**
540      * Returns a unicode representation of the node.  This method is used
541      * for debugging purposes only (no NLS support needed)
542      */
543     public String   toString() {
544         return "an AbstractDataTreeNode(" + this.getName() + ") with " + getChildren().length + " children."; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
545     }
546 
547     /**
548      * Returns a constant describing the type of node.
549      */
550     abstract int type();
551 }
552
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags