KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > team > internal > core > mapping > PathTree


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.team.internal.core.mapping;
12
13 import java.util.*;
14
15 import org.eclipse.core.runtime.IPath;
16
17 /**
18  * A tree of objects keyed by path
19  */
20 public class PathTree {
21     
22     class Node {
23         Object JavaDoc payload;
24         Set descendantsWithPayload;
25         int flags;
26         public boolean isEmpty() {
27             return payload == null && (descendantsWithPayload == null || descendantsWithPayload.isEmpty());
28         }
29         public Object JavaDoc getPayload() {
30             return payload;
31         }
32         public void setPayload(Object JavaDoc payload) {
33             this.payload = payload;
34         }
35         public boolean hasDescendants() {
36             return descendantsWithPayload != null && !descendantsWithPayload.isEmpty();
37         }
38         public boolean hasFlag(int propertyBit) {
39             return (flags & propertyBit) != 0;
40         }
41         public void setProperty(int propertyBit, boolean value) {
42             if (value)
43                 flags |= propertyBit;
44             else
45                 flags ^= propertyBit;
46         }
47         public boolean descendantHasFlag(int property) {
48             if (hasDescendants()) {
49                 for (Iterator iter = descendantsWithPayload.iterator(); iter.hasNext();) {
50                     IPath path = (IPath) iter.next();
51                     Node child = getNode(path);
52                     if (child.hasFlag(property)) {
53                         return true;
54                     }
55                 }
56             }
57             return false;
58         }
59     }
60     
61     private Map objects = new HashMap();
62
63     /**
64      * Return the object at the given path or <code>null</code>
65      * if there is no object at that path
66      * @param path the path
67      * @return the object at the given path or <code>null</code>
68      */
69     public synchronized Object JavaDoc get(IPath path) {
70         Node node = getNode(path);
71         if (node == null)
72             return null;
73         return node.getPayload();
74     }
75     
76     /**
77      * Put the object at the given path. Return the
78      * previous object at that path or <code>null</code>
79      * if the path did not previously have an object.
80      * @param path the path of the object
81      * @param object the object
82      * @return the previous object at that path or <code>null</code>
83      */
84     public synchronized Object JavaDoc put(IPath path, Object JavaDoc object) {
85         Node node = getNode(path);
86         if (node == null) {
87             node = addNode(path);
88         }
89         Object JavaDoc previous = node.getPayload();
90         node.setPayload(object);
91         if(previous == null) {
92             addToParents(path, path);
93         }
94         return previous;
95     }
96     
97     /**
98      * Remove the object at the given path and return
99      * the removed object or <code>null</code> if no
100      * object was removed.
101      * @param path the path to remove
102      * @return the removed object at the given path and return
103      * the removed object or <code>null</code>
104      */
105     public synchronized Object JavaDoc remove(IPath path) {
106         Node node = getNode(path);
107         if (node == null)
108             return null;
109         Object JavaDoc previous = node.getPayload();
110         node.setPayload(null);
111         if(previous != null) {
112             removeFromParents(path, path);
113             if (node.isEmpty()) {
114                 removeNode(path);
115             }
116         }
117         return previous;
118         
119     }
120     
121     /**
122      * Return whether the given path has children in the tree
123      * @param path
124      * @return whether there are children for the given path
125      */
126     public synchronized boolean hasChildren(IPath path) {
127         if (path.isEmpty()) return !objects.isEmpty();
128         Node node = getNode(path);
129         if (node == null)
130             return false;
131         return node.hasDescendants();
132     }
133     
134     /**
135      * Return the paths for any children of the given path in this set.
136      * @param path the path
137      * @return the paths for any children of the given path in this set
138      */
139     public synchronized IPath[] getChildren(IPath path) {
140         // OPTIMIZE: could be optimized so that we don't traverse all the deep
141 // children to find the immediate ones.
142 Set children = new HashSet();
143         Node node = getNode(path);
144         if (node != null) {
145             Set possibleChildren = node.descendantsWithPayload;
146             if(possibleChildren != null) {
147                 for (Iterator it = possibleChildren.iterator(); it.hasNext();) {
148                     Object JavaDoc next = it.next();
149                     IPath descendantPath = (IPath)next;
150                     IPath childPath = null;
151                     if(descendantPath.segmentCount() == (path.segmentCount() + 1)) {
152                         childPath = descendantPath;
153                     } else if (descendantPath.segmentCount() > path.segmentCount()) {
154                         childPath = descendantPath.removeLastSegments(descendantPath.segmentCount() - path.segmentCount() - 1);
155                     }
156                     if (childPath != null) {
157                         children.add(childPath);
158                     }
159                 }
160             }
161         }
162         return (IPath[]) children.toArray(new IPath[children.size()]);
163     }
164     
165     private boolean addToParents(IPath path, IPath parent) {
166         // this flag is used to indicate if the parent was previously in the set
167 boolean addedParent = false;
168         if (path == parent) {
169             // this is the leaf that was just added
170 addedParent = true;
171         } else {
172             Node node = getNode(parent);
173             if (node == null)
174                 node = addNode(parent);
175             Set children = node.descendantsWithPayload;
176             if (children == null) {
177                 children = new HashSet();
178                 node.descendantsWithPayload = children;
179                 // this is a new folder in the sync set
180 addedParent = true;
181             }
182             children.add(path);
183         }
184         // if the parent already existed and the resource is new, record it
185 if ((parent.segmentCount() == 0 || !addToParents(path, parent.removeLastSegments(1))) && addedParent) {
186             // TODO: we may not need to record the removed subtree
187 // internalAddedSubtreeRoot(parent);
188 }
189         return addedParent;
190     }
191     
192     private boolean removeFromParents(IPath path, IPath parent) {
193         // this flag is used to indicate if the parent was removed from the set
194 boolean removedParent = false;
195         Node node = getNode(parent);
196         if (node == null) {
197             // this is the leaf
198 removedParent = true;
199         } else {
200             Set children = node.descendantsWithPayload;
201             if (children == null) {
202                 // this is the leaf
203 removedParent = true;
204             } else {
205                 children.remove(path);
206                 if (children.isEmpty()) {
207                     node.descendantsWithPayload = null;
208                     if (node.isEmpty())
209                         removeNode(parent);
210                     removedParent = true;
211                 }
212             }
213         }
214         // if the parent wasn't removed and the resource was, record it
215 if ((parent.segmentCount() == 0 || !removeFromParents(path, parent.removeLastSegments(1))) && removedParent) {
216             // TODO: may not need to record this
217 //internalRemovedSubtreeRoot(parent);
218 }
219         return removedParent;
220     }
221
222     /**
223      * Clear all entries from the path tree.
224      */
225     public synchronized void clear() {
226         objects.clear();
227     }
228
229     /**
230      * Return whether the path tree is empty.
231      * @return whether the path tree is empty
232      */
233     public synchronized boolean isEmpty() {
234         return objects.isEmpty();
235     }
236
237     /**
238      * Return the paths in this tree that contain diffs.
239      * @return the paths in this tree that contain diffs.
240      */
241     public synchronized IPath[] getPaths() {
242         List result = new ArrayList();
243         for (Iterator iter = objects.keySet().iterator(); iter.hasNext();) {
244             IPath path = (IPath) iter.next();
245             Node node = getNode(path);
246             if (node.getPayload() != null)
247                 result.add(path);
248         }
249         return (IPath[]) result.toArray(new IPath[result.size()]);
250     }
251
252     /**
253      * Return all the values contained in this path tree.
254      * @return all the values in the tree
255      */
256     public synchronized Collection values() {
257         List result = new ArrayList();
258         for (Iterator iter = objects.keySet().iterator(); iter.hasNext();) {
259             IPath path = (IPath) iter.next();
260             Node node = getNode(path);
261             if (node.getPayload() != null)
262                 result.add(node.getPayload());
263         }
264         return result;
265     }
266
267     /**
268      * Return the number of nodes contained in this path tree.
269      * @return the number of nodes contained in this path tree
270      */
271     public int size() {
272         return values().size();
273     }
274     
275     private Node getNode(IPath path) {
276         return (Node)objects.get(path);
277     }
278     
279     private Node addNode(IPath path) {
280         Node node;
281         node = new Node();
282         objects.put(path, node);
283         return node;
284     }
285     
286     private Object JavaDoc removeNode(IPath path) {
287         return objects.remove(path);
288     }
289     
290     /**
291      * Set the property for the given path and propogate the
292      * bit to the root. The property is only set if the given path
293      * already exists in the tree.
294      * @param path the path
295      * @param property the property bit to set
296      * @param value whether the bit should be on or off
297      * @return the paths whose bit changed
298      */
299     public synchronized IPath[] setPropogatedProperty(IPath path, int property, boolean value) {
300         Set changed = new HashSet();
301         internalSetPropertyBit(path, property, value, changed);
302         return (IPath[]) changed.toArray(new IPath[changed.size()]);
303     }
304     
305     private void internalSetPropertyBit(IPath path, int property, boolean value, Set changed) {
306         if (path.segmentCount() == 0)
307             return;
308         Node node = getNode(path);
309         if (node == null)
310             return;
311         // No need to set it if the value hans't changed
312 if (value == node.hasFlag(property))
313             return;
314         // Only unset the property if no descendants have the flag set
315 if (!value && node.descendantHasFlag(property))
316             return;
317         node.setProperty(property, value);
318         changed.add(path);
319         internalSetPropertyBit(path.removeLastSegments(1), property, value, changed);
320     }
321
322     public synchronized boolean getProperty(IPath path, int property) {
323         if (path.segmentCount() == 0)
324             return false;
325         Node node = getNode(path);
326         if (node == null)
327             return false;
328         return (node.hasFlag(property));
329     }
330
331 }
332
Popular Tags