Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: e119fd3bed95dfc80cb974f92ad7b8db9ed36b76 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
/*******************************************************************************
 * Copyright (c) 2000, 2017 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.team.internal.core.mapping;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.core.runtime.IPath;

/**
 * A tree of objects keyed by path
 */
public class PathTree {

	class Node {
		Object payload;
		Set<IPath> descendantsWithPayload;
		int flags;
		public boolean isEmpty() {
			return payload == null && (descendantsWithPayload == null || descendantsWithPayload.isEmpty());
		}
		public Object getPayload() {
			return payload;
		}
		public void setPayload(Object payload) {
			this.payload = payload;
		}
		public boolean hasDescendants() {
			return descendantsWithPayload != null && !descendantsWithPayload.isEmpty();
		}
		public boolean hasFlag(int propertyBit) {
			return (flags & propertyBit) != 0;
		}
		public void setProperty(int propertyBit, boolean value) {
			if (value)
				flags |= propertyBit;
			else
				flags ^= propertyBit;
		}
		public boolean descendantHasFlag(int property) {
			if (hasDescendants()) {
				for (IPath path : descendantsWithPayload) {
					Node child = getNode(path);
					if (child.hasFlag(property)) {
						return true;
					}
				}
			}
			return false;
		}
	}

	private Map<IPath, Node> objects = new HashMap<>();

	/**
	 * Return the object at the given path or <code>null</code>
	 * if there is no object at that path
	 * @param path the path
	 * @return the object at the given path or <code>null</code>
	 */
	public synchronized Object get(IPath path) {
		Node node = getNode(path);
		if (node == null)
			return null;
		return node.getPayload();
	}

	/**
	 * Put the object at the given path. Return the
	 * previous object at that path or <code>null</code>
	 * if the path did not previously have an object.
	 * @param path the path of the object
	 * @param object the object
	 * @return the previous object at that path or <code>null</code>
	 */
	public synchronized Object put(IPath path, Object object) {
		Node node = getNode(path);
		if (node == null) {
			node = addNode(path);
		}
		Object previous = node.getPayload();
		node.setPayload(object);
		if(previous == null) {
			addToParents(path, path);
		}
		return previous;
	}

	/**
	 * Remove the object at the given path and return
	 * the removed object or <code>null</code> if no
	 * object was removed.
	 * @param path the path  to remove
	 * @return the removed object at the given path and return
	 * the removed object or <code>null</code>
	 */
	public synchronized Object remove(IPath path) {
		Node node = getNode(path);
		if (node == null)
			return null;
		Object previous = node.getPayload();
		node.setPayload(null);
		if(previous != null) {
			removeFromParents(path, path);
			if (node.isEmpty()) {
				removeNode(path);
			}
		}
		return previous;

	}

	/**
	 * Return whether the given path has children in the tree
	 * @param path
	 * @return whether there are children for the given path
	 */
	public synchronized boolean hasChildren(IPath path) {
		if (path.isEmpty()) return !objects.isEmpty();
		Node node = getNode(path);
		if (node == null)
			return false;
		return node.hasDescendants();
	}

	/**
	 * Return the paths for any children of the given path in this set.
	 * @param path the path
	 * @return the paths for any children of the given path in this set
	 */
	public synchronized IPath[] getChildren(IPath path) {
		// OPTIMIZE: could be optimized so that we don't traverse all the deep
		// children to find the immediate ones.
		Set<IPath> children = new HashSet<>();
		Node node = getNode(path);
		if (node != null) {
			Set possibleChildren = node.descendantsWithPayload;
			if(possibleChildren != null) {
				for (Object next : possibleChildren) {
					IPath descendantPath = (IPath)next;
					IPath childPath = null;
					if(descendantPath.segmentCount() == (path.segmentCount() +  1)) {
						childPath = descendantPath;
					} else if (descendantPath.segmentCount() > path.segmentCount()) {
						childPath = descendantPath.removeLastSegments(descendantPath.segmentCount() - path.segmentCount() - 1);
					}
					if (childPath != null) {
						children.add(childPath);
					}
				}
			}
		}
		return children.toArray(new IPath[children.size()]);
	}

	private boolean addToParents(IPath path, IPath parent) {
		// this flag is used to indicate if the parent was previously in the set
		boolean addedParent = false;
		if (path == parent) {
			// this is the leaf that was just added
			addedParent = true;
		} else {
			Node node = getNode(parent);
			if (node == null)
				node = addNode(parent);
			Set<IPath> children = node.descendantsWithPayload;
			if (children == null) {
				children = new HashSet<>();
				node.descendantsWithPayload = children;
				// this is a new folder in the sync set
				addedParent = true;
			}
			children.add(path);
		}
		// if the parent already existed and the resource is new, record it
		if ((parent.segmentCount() == 0 || !addToParents(path, parent.removeLastSegments(1))) && addedParent) {
			// TODO: we may not need to record the removed subtree
			// internalAddedSubtreeRoot(parent);
		}
		return addedParent;
	}

	private boolean removeFromParents(IPath path, IPath parent) {
		// this flag is used to indicate if the parent was removed from the set
		boolean removedParent = false;
		Node node = getNode(parent);
		if (node == null) {
			// this is the leaf
			removedParent = true;
		} else {
			Set children = node.descendantsWithPayload;
			if (children == null) {
				// this is the leaf
				removedParent = true;
			} else {
				children.remove(path);
				if (children.isEmpty()) {
					node.descendantsWithPayload = null;
					if (node.isEmpty())
						removeNode(parent);
					removedParent = true;
				}
			}
		}
		//	if the parent wasn't removed and the resource was, record it
		if ((parent.segmentCount() == 0 || !removeFromParents(path, parent.removeLastSegments(1))) && removedParent) {
			// TODO: may not need to record this
			//internalRemovedSubtreeRoot(parent);
		}
		return removedParent;
	}

	/**
	 * Clear all entries from the path tree.
	 */
	public synchronized void clear() {
		objects.clear();
	}

	/**
	 * Return whether the path tree is empty.
	 * @return whether the path tree is empty
	 */
	public synchronized boolean isEmpty() {
		return objects.isEmpty();
	}

	/**
	 * Return the paths in this tree that contain diffs.
	 * @return the paths in this tree that contain diffs.
	 */
	public synchronized IPath[] getPaths() {
		List<IPath> result = new ArrayList<>();
		for (IPath path : objects.keySet()) {
			Node node = getNode(path);
			if (node.getPayload() != null)
				result.add(path);
		}
		return result.toArray(new IPath[result.size()]);
	}

	/**
	 * Return all the values contained in this path tree.
	 * @return all the values in the tree
	 */
	public synchronized Collection<Object> values() {
		List<Object> result = new ArrayList<>();
		for (IPath path : objects.keySet()) {
			Node node = getNode(path);
			if (node.getPayload() != null)
				result.add(node.getPayload());
		}
		return result;
	}

	/**
	 * Return the number of nodes contained in this path tree.
	 * @return the number of nodes contained in this path tree
	 */
	public int size() {
		return values().size();
	}

	private Node getNode(IPath path) {
		return objects.get(path);
	}

	private Node addNode(IPath path) {
		Node node;
		node = new Node();
		objects.put(path, node);
		return node;
	}

	private Object removeNode(IPath path) {
		return objects.remove(path);
	}

	/**
	 * Set the property for the given path and propogate the
	 * bit to the root. The property is only set if the given path
	 * already exists in the tree.
	 * @param path the path
	 * @param property the property bit to set
	 * @param value whether the bit should be on or off
	 * @return the paths whose bit changed
	 */
	public synchronized IPath[] setPropogatedProperty(IPath path, int property, boolean value) {
		Set<IPath> changed = new HashSet<>();
		internalSetPropertyBit(path, property, value, changed);
		return changed.toArray(new IPath[changed.size()]);
	}

	private void internalSetPropertyBit(IPath path, int property, boolean value, Set<IPath> changed) {
		if (path.segmentCount() == 0)
			return;
		Node node = getNode(path);
		if (node == null)
			return;
		// No need to set it if the value hans't changed
		if (value == node.hasFlag(property))
			return;
		// Only unset the property if no descendants have the flag set
		if (!value && node.descendantHasFlag(property))
			return;
		node.setProperty(property, value);
		changed.add(path);
		internalSetPropertyBit(path.removeLastSegments(1), property, value, changed);
	}

	public synchronized boolean getProperty(IPath path, int property) {
		if (path.segmentCount() == 0)
			return false;
		Node node = getNode(path);
		if (node == null)
			return false;
		return (node.hasFlag(property));
	}

}

Back to the top