Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: 287092b64f2e1c786344f82308d47b45167a77d2 (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
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
/*******************************************************************************
 * Copyright (c) 2006, 2013 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/

package org.eclipse.debug.internal.ui.viewers.model;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import org.eclipse.jface.viewers.TreePath;


/**
 * Helper class to support filtering in virtual tree viewer.
 * Translates indexes from viewer to model coordinate space (and visa versa).
 * <p>
 * This filter transform maintains a tree representing filtered elements in the
 * viewer. The filtering is performed dynamically as elements are 'replaced' in the tree
 * by a lazy tree content provider.
 * </p>
 * <p>
 * This class not intended to be subclassed or instantiated. For internal use only.
 * </p>
 * @since 3.3
 */
public class FilterTransform {

	private Node root = new Node();

	class Node {
		private int[] filteredIndexes = null;
		private Object[] filteredElements = null;
		private Map<Object, Node> children = null; // only set for parent nodes,
													// indexed by child

		Node() {
		}

		boolean addFilter(TreePath path, int childIndex, int pathIndex, Object filtered) {
			if (pathIndex == path.getSegmentCount()) {
				if (filteredIndexes == null) {
					filteredIndexes = new int[]{childIndex};
					filteredElements = new Object[]{filtered};
					return true;
				}
				int location = Arrays.binarySearch(filteredIndexes, childIndex);
				if (location >= 0) {
					return false;
				}
				location = 0 - (location + 1);
				int[] next = new int[filteredIndexes.length + 1];
				Object[] filt = new Object[next.length];
				if (location == 0) {
					next[0] = childIndex;
					filt[0] = filtered;
					System.arraycopy(filteredIndexes, 0, next, 1, filteredIndexes.length);
					System.arraycopy(filteredElements, 0, filt, 1, filteredElements.length);
				} else if (location == filteredIndexes.length) {
					next[filteredIndexes.length] = childIndex;
					filt[filteredElements.length] = filtered;
					System.arraycopy(filteredIndexes, 0, next, 0, filteredIndexes.length);
					System.arraycopy(filteredElements, 0, filt, 0, filteredElements.length);
				} else {
					System.arraycopy(filteredIndexes, 0, next, 0, location);
					System.arraycopy(filteredElements, 0, filt, 0, location);
					next[location] = childIndex;
					filt[location] = filtered;
					System.arraycopy(filteredIndexes, location, next, location + 1, filteredIndexes.length - location);
					System.arraycopy(filteredElements, location, filt, location + 1, filteredElements.length - location);
				}
				filteredIndexes = next;
				filteredElements = filt;
				return true;
			}

			if (children == null) {
				children = new HashMap<>();
			}
			Object element = path.getSegment(pathIndex);
			Node node = children.get(element);
			if (node == null) {
				node = new Node();
				children.put(element, node);
			}
			return node.addFilter(path, childIndex, pathIndex + 1, filtered);
		}

		boolean clear(TreePath path, int pathIndex) {
			if (pathIndex == path.getSegmentCount()) {
				return true;
			}
			if (children == null) {
				return false;
			}
			Object child = path.getSegment(pathIndex);
			Node node = children.get(child);
			if (node != null) {
				if (node.clear(path, pathIndex + 1)) {
					children.remove(child);
				}
			}
			return children.isEmpty() && (filteredIndexes == null || filteredIndexes.length == 0);
		}

		boolean clear(TreePath path, int childIndex, int pathIndex) {
			if (pathIndex == path.getSegmentCount()) {
				if (filteredIndexes != null) {
					int location = Arrays.binarySearch(filteredIndexes, childIndex);
					if (location >= 0) {
						// remove it
						if (location == 0 && filteredIndexes.length == 1) {
							filteredIndexes = null;
							filteredElements = null;
							return true;
						}
						int[] next = new int[filteredIndexes.length - 1];
						Object[] filt = new Object[next.length];
						if (location == 0) {
							System.arraycopy(filteredIndexes, 1, next, 0, next.length);
							System.arraycopy(filteredElements, 1, filt, 0, filt.length);
						} else if (location == (filteredIndexes.length - 1)) {
							System.arraycopy(filteredIndexes, 0, next, 0, location);
							System.arraycopy(filteredElements, 0, filt, 0, location);
						} else {
							System.arraycopy(filteredIndexes, 0, next, 0, location);
							System.arraycopy(filteredElements, 0, filt, 0, location);
							System.arraycopy(filteredIndexes, location + 1, next, location, next.length - location);
							System.arraycopy(filteredElements, location + 1, filt, location, filt.length - location);
						}
						filteredIndexes = next;
						filteredElements = filt;
						return false;
					}
				} else {
					return false;
				}
			}
			if (children == null) {
				return false;
			}
			Object element = path.getSegment(pathIndex);
			Node node = children.get(element);
			if (node == null) {
				return false;
			}
			boolean remove = node.clear(path, childIndex, pathIndex + 1);
			if (remove) {
				children.remove(element);
				return filteredIndexes == null && children.isEmpty();
			} else {
				return false;
			}
		}

		Node find(TreePath path, int pathIndex) {
			if (pathIndex == path.getSegmentCount()) {
				return this;
			}
			if (children == null) {
				return null;
			}
			Object child = path.getSegment(pathIndex);
			Node node = children.get(child);
			if (node != null) {
				return node.find(path, pathIndex + 1);
			}
			return null;
		}

		int viewToModel(int childIndex) {
			if (filteredIndexes == null) {
				return childIndex;
			}
			// If there are filtered children, then we want to find the
			// (n+1)th missing number in the list of filtered indexes (missing
			// entries are visible in the view). For example, if the request
			// has asked for the model index corresponding to the 4th viewer
			// index, then we want to find the 5th missing number in the
			// filtered index sequence.

			int count = -1; // count from 0, 1, 2...
			int missingNumbers = 0; // how many numbers missing from the filtered index
			int offset = 0; // offset into the filtered index

			while (missingNumbers < (childIndex + 1)) {
				count++;
				if (offset < filteredIndexes.length) {
					if (filteredIndexes[offset] == count) {
						// not missing
						offset++;
					} else {
						// missing
						missingNumbers++;
					}
				} else {
					missingNumbers++;
				}
			}
			return count;
		}

		int modelToView(int childIndex) {
			if (filteredIndexes == null) {
				return childIndex;
			}
			int offset = 0;
			for (int i = 0; i < filteredIndexes.length; i++) {
				if (childIndex == filteredIndexes[i] ) {
					return -1;
				} else if (childIndex > filteredIndexes[i]) {
					offset++;
				} else {
					break;
				}
			}
			return childIndex - offset;
		}

		int modelToViewCount(int childCount) {
			if (filteredIndexes == null) {
				return childCount;
			}
			return childCount - filteredIndexes.length;
		}

		boolean isFiltered(int index) {
			if (filteredIndexes != null) {
				int location = Arrays.binarySearch(filteredIndexes, index);
				return location >= 0;
			}
			return false;
		}

		int indexOfFilteredElement(Object element) {
			if (filteredElements != null) {
				for (int i = 0; i < filteredElements.length; i++) {
					if (element.equals(filteredElements[i])) {
						return filteredIndexes[i];
					}
				}
			}
			return -1;
		}

		/**
		 * Sets the child count for this element, trimming any filtered elements
		 * that were above this count.
		 *
		 * @param childCount new child count
		 */
		void setModelChildCount(int childCount) {
			if (filteredIndexes != null) {
				for (int i = 0; i < filteredIndexes.length; i++) {
					if (filteredIndexes[i] >= childCount) {
						// trim
						if (i == 0) {
							filteredIndexes = null;
							// bug 200325 - filteredElements should have the same length
							// as filteredIndexes
							filteredElements = null;
							return;
						} else {
							int[] temp = new int[i + 1];
							System.arraycopy(filteredIndexes, 0, temp, 0, temp.length);
							filteredIndexes = temp;
							// bug 200325 - filteredElements should have the same length
							// as filteredIndexes
							Object[] temp2 = new Object[i + 1];
							System.arraycopy(filteredElements, 0, temp2, 0, temp2.length);
							filteredElements = temp2;
						}
					}
				}
			}
		}

		/**
		 * Updates filter index for a removed element at the given index
		 *
		 * @param index index at which an element was removed
		 */
		void removeElementFromFilters(int index) {
			if (filteredIndexes != null) {
				int location = Arrays.binarySearch(filteredIndexes, index);
				if (location >= 0) {
					// remove a filtered item
					if (filteredIndexes.length == 1) {
						// only filtered item
						filteredIndexes = null;
						filteredElements = null;
					} else {
						int[] next = new int[filteredIndexes.length - 1];
						Object[] filt = new Object[next.length];
						if (location == 0) {
							// first
							System.arraycopy(filteredIndexes, 1, next, 0, next.length);
							System.arraycopy(filteredElements, 1, filt, 0, filt.length);
						} else if (location == (filteredIndexes.length - 1)) {
							// last
							System.arraycopy(filteredIndexes, 0, next, 0, next.length);
							System.arraycopy(filteredElements, 0, filt, 0, filt.length);
						} else {
							// middle
							System.arraycopy(filteredIndexes, 0, next, 0, location);
							System.arraycopy(filteredElements, 0, filt, 0, location);
							System.arraycopy(filteredIndexes, location + 1, next, location, next.length - location);
							System.arraycopy(filteredElements, location + 1, filt, location, filt.length - location);
						}
						filteredIndexes = next;
						filteredElements = filt;
					}
				} else {
					location = 0 - (location + 1);
				}
				if (filteredIndexes != null) {
					// decrement remaining indexes
					for (int i = location; i < filteredIndexes.length; i ++) {
						filteredIndexes[i]--;
					}
				}
			}
		}
	}

	/**
	 * Filters the specified child of the given parent and returns
	 * whether the filter was added.
	 *
	 * @param parentPath path to parent element
	 * @param childIndex index of filtered child relative to parent (in model coordinates)
	 * @param element the filtered element
	 * @return whether the filter was added - returns <code>true</code> if the filter is
	 *  added, and <code>false</code> if the index was already filtered
	 */
	public boolean addFilteredIndex(TreePath parentPath, int childIndex, Object element) {
		return root.addFilter(parentPath, childIndex, 0, element);
	}

	/**
	 * Clears all filtered elements.
	 */
	public void clear() {
		root = new Node();
	}

	/**
	 * Clears all filters in the subtree of the given element.
	 *
	 * @param path element path
	 */
	public void clear(TreePath path) {
		root.clear(path, 0);
	}

	/**
	 * Clears the given filtered index of the specified parent. I.e.
	 * the child still exists, but is no longer filtered.
	 *
	 * @param parentPath parent path
	 * @param index index to clear
	 */
	public void clear(TreePath parentPath, int index) {
		root.clear(parentPath, index, 0);
	}

	public int indexOfFilteredElement(TreePath parentPath, Object element) {
        Node parentNode = root.find(parentPath, 0);
        if (parentNode == null) {
            return -1;
        }
        return parentNode.indexOfFilteredElement(element);
	}

	/**
	 * Translates and returns the given model index (raw index) into
	 * a view index (filtered index), or -1 if filtered.
	 *
	 * @param parentPath path to parent element
	 * @param childIndex index of child element in model space
	 * @return the given index in view coordinates, or -1 if filtered.
	 */
	public int modelToViewIndex(TreePath parentPath, int childIndex) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode == null) {
			return childIndex;
		}
		return parentNode.modelToView(childIndex);
	}

	/**
	 * Translates and returns the given view index (filtered) into
	 * a model index (raw index).
	 *
	 * @param parentPath path to parent element
	 * @param childIndex index of child element in view space
	 * @return the given index in model coordinates
	 */
	public int viewToModelIndex(TreePath parentPath, int childIndex) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode == null) {
			return childIndex;
		}
		return parentNode.viewToModel(childIndex);
	}

	/**
	 * Returns the number of children for the given parent, in the model.
	 *
	 * @param parentPath path to parent element
	 * @param viewCount number of children in the view
	 * @return number of children in the model
	 */
	public int viewToModelCount(TreePath parentPath, int viewCount) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode != null) {
			if (parentNode.filteredIndexes != null) {
				return viewCount + parentNode.filteredIndexes.length;
			}
		}
		return viewCount;
	}

	/**
	 * Translates and returns the given model child count (raw) into
	 * a view count (filtered).
	 *
	 * @param parentPath path to parent element
	 * @param count child count in model space
	 * @return the given count in view coordinates
	 */
	public int modelToViewCount(TreePath parentPath, int count) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode == null) {
			return count;
		}
		return parentNode.modelToViewCount(count);
	}

	/**
	 * Returns whether the given index of the specified parent is currently filtered.
	 *
	 * @param parentPath path to parent element
	 * @param index index of child element
	 * @return whether the child is currently filtered
	 */
	public boolean isFiltered(TreePath parentPath, int index) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode == null) {
			return false;
		}
		return parentNode.isFiltered(index);
	}

	/**
	 * Returns filtered children of the given parent, or <code>null</code> if none.
	 *
	 * @param parentPath Path of parent element
	 * @return filtered children or <code>null</code>
	 */
	public int[] getFilteredChildren(TreePath parentPath) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode == null) {
			return null;
		}
		return parentNode.filteredIndexes;
	}

	/**
	 * Clears any filters for the given parent above the given count.
	 *
	 * @param parentPath path to parent element
	 * @param childCount child count
	 */
	public void setModelChildCount(TreePath parentPath, int childCount) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode != null) {
			parentNode.setModelChildCount(childCount);
		}
	}

	/**
	 * The element at the given index has been removed from the parent. Update
	 * indexes.
	 *
	 * @param parentPath path to parent element
	 * @param index index of child element in model coordinates
	 */
	public void removeElementFromFilters(TreePath parentPath, int index) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode != null) {
			parentNode.removeElementFromFilters(index);
		}
	}

	/**
	 * The element has been removed from the parent. Update
	 * filtered indexes, in case it was a filtered object.
	 *
	 * @param parentPath path to parent element
	 * @param element removed element
	 * @return true if element was removed
	 */
	public boolean removeElementFromFilters(TreePath parentPath, Object element) {
		Node parentNode = root.find(parentPath, 0);
		if (parentNode != null) {
			int index = parentNode.indexOfFilteredElement(element);
			if (index >= 0) {
				parentNode.removeElementFromFilters(index);
				return true;
			}
		}
		return false;
	}
}

Back to the top