diff options
Diffstat (limited to 'org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util')
3 files changed, 1059 insertions, 0 deletions
diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayMap.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayMap.java new file mode 100644 index 000000000..eed0a5a74 --- /dev/null +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayMap.java @@ -0,0 +1,312 @@ +/******************************************************************************* + * Copyright (c) 2007, 2016 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.jdt.internal.core.nd.util; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import java.util.Set; +import java.util.TreeMap; + + +/** + * Provides functionality similar to a Map, with the feature that char arrays + * and sections of char arrays (known as slices) may be used as keys. + * + * This class is useful because small pieces of an existing large char[] buffer + * can be directly used as map keys. This avoids the need to create many String + * objects as would normally be needed as keys in a standard java.util.Map. + * Thus performance is improved in the CDT core. + * + * Most methods are overloaded with two versions, one that uses a + * section of a char[] as the key (a slice), and one that uses + * the entire char[] as the key. + * + * This class is intended as a replacement for CharArrayObjectMap. + * + * ex: + * char[] key = "one two three".toCharArray(); + * map.put(key, 4, 3, new Integer(99)); + * map.get(key, 4, 3); // returns 99 + * map.get("two".toCharArray()); // returns 99 + * + * @author Mike Kucera + * + * @param <V> + */ +public final class CharArrayMap<V> { + + /** + * Wrapper class used as keys in the map. The purpose + * of this class is to provide implementations of + * equals() and hashCode() that operate on array slices. + * + * This class is private so it is assumed that the arguments + * passed to the constructor are legal. + */ + private static final class Key implements Comparable<Key>{ + final char[] buffer; + final int start; + final int length; + + public Key(char[] buffer, int start, int length) { + this.buffer = buffer; + this.length = length; + this.start = start; + } + + /** + * @throws NullPointerException if buffer is null + */ + public Key(char[] buffer) { + this.buffer = buffer; + this.length = buffer.length; // throws NPE + this.start = 0; + } + + @Override + public boolean equals(Object x) { + if(this == x) + return true; + if(!(x instanceof Key)) + return false; + + Key k = (Key) x; + if(this.length != k.length) + return false; + + for(int i = this.start, j = k.start; i < this.length; i++, j++) { + if(this.buffer[i] != k.buffer[j]) { + return false; + } + } + return true; + } + + @Override + public int hashCode() { + int result = 17; + for(int i = this.start; i < this.start+this.length; i++) { + result = 37 * result + this.buffer[i]; + } + return result; + } + + @SuppressWarnings("nls") + @Override + public String toString() { + String slice = new String(this.buffer, this.start, this.length); + return "'" + slice + "'@(" + this.start + "," + this.length + ")"; + } + + + @Override + public int compareTo(Key other) { + char[] b1 = this.buffer, b2 = other.buffer; + + for(int i = this.start, j = other.start; i < b1.length && j < b2.length; i++, j++) { + if(b1[i] != b2[j]) + return b1[i] < b2[j] ? -1 : 1; + } + return b1.length - b2.length; + } + } + + + /** + * Used to enforce preconditions. + * Note that the NPE thrown by mutator methods is thrown from the Key constructor. + * + * @throws IndexOutOfBoundsException if boundaries are wrong in any way + */ + private static void checkBoundaries(char[] chars, int start, int length) { + if(start < 0 || length < 0 || start >= chars.length || start + length > chars.length) + throw new IndexOutOfBoundsException("Buffer length: " + chars.length + //$NON-NLS-1$ + ", Start index: " + start + //$NON-NLS-1$ + ", Length: " + length); //$NON-NLS-1$ + } + + + private final Map<Key,V> map; + + + /** + * Constructs an empty CharArrayMap with default initial capacity. + */ + public CharArrayMap() { + this.map = new HashMap<Key,V>(); + } + + + /** + * Static factory method that constructs an empty CharArrayMap with default initial capacity, + * and the map will be kept in ascending key order. + * + * Characters are compared using a strictly numerical comparison; it is not locale-dependent. + */ + public static <V> CharArrayMap<V> createOrderedMap() { + // TreeMap does not have a constructor that takes an initial capacity + return new CharArrayMap<V>(new TreeMap<Key, V>()); + } + + + private CharArrayMap(Map<Key, V> map) { + assert map != null; + this.map = map; + } + + + /** + * Constructs an empty CharArrayMap with the given initial capacity. + * @throws IllegalArgumentException if the initial capacity is negative + */ + public CharArrayMap(int initialCapacity) { + this.map = new HashMap<Key,V>(initialCapacity); + } + + /** + * Creates a new mapping in this map, uses the given array slice as the key. + * If the map previously contained a mapping for this key, the old value is replaced. + * @throws NullPointerException if chars is null + * @throws IndexOutOfBoundsException if the boundaries specified by start and length are out of range + */ + public void put(char[] chars, int start, int length, V value) { + checkBoundaries(chars, start, length); + this.map.put(new Key(chars, start, length), value); + } + + /** + * Creates a new mapping in this map, uses all of the given array as the key. + * If the map previously contained a mapping for this key, the old value is replaced. + * @throws NullPointerException if chars is null + */ + public void put(char[] chars, V value) { + this.map.put(new Key(chars), value); + } + + /** + * Returns the value to which the specified array slice is mapped in this map, + * or null if the map contains no mapping for this key. + * @throws NullPointerException if chars is null + * @throws IndexOutOfBoundsException if the boundaries specified by start and length are out of range + */ + public V get(char[] chars, int start, int length) { + checkBoundaries(chars, start, length); + return this.map.get(new Key(chars, start, length)); + } + + /** + * Returns the value to which the specified array is mapped in this map, + * or null if the map contains no mapping for this key. + * @throws NullPointerException if chars is null + */ + public V get(char[] chars) { + return this.map.get(new Key(chars)); + } + + /** + * Removes the mapping for the given array slice if present. + * Returns the value object that corresponded to the key + * or null if the key was not in the map. + * @throws NullPointerException if chars is null + * @throws IndexOutOfBoundsException if the boundaries specified by start and length are out of range + */ + public V remove(char[] chars, int start, int length) { + checkBoundaries(chars, start, length); + return this.map.remove(new Key(chars, start, length)); + } + + /** + * Removes the mapping for the given array if present. + * Returns the value object that corresponded to the key + * or null if the key was not in the map. + * @throws NullPointerException if chars is null + */ + public V remove(char[] chars) { + return this.map.remove(new Key(chars)); + } + + /** + * Returns true if the given key has a value associated with it in the map. + * @throws NullPointerException if chars is null + * @throws IndexOutOfBoundsException if the boundaries specified by start and length are out of range + */ + public boolean containsKey(char[] chars, int start, int length) { + checkBoundaries(chars, start, length); + return this.map.containsKey(new Key(chars, start, length)); + } + + /** + * Returns true if the given key has a value associated with it in the map. + * @throws NullPointerException if chars is null + */ + public boolean containsKey(char[] chars) { + return this.map.containsKey(new Key(chars)); + } + + /** + * Returns true if the given value is contained in the map. + */ + public boolean containsValue(V value) { + return this.map.containsValue(value); + } + + /** + * Use this in a foreach loop. + */ + public Collection<V> values() { + return this.map.values(); + } + + /** + * Returns the keys stored in the map. + */ + public Collection<char[]> keys() { + Set<Key> keys= this.map.keySet(); + ArrayList<char[]> r= new ArrayList<char[]>(keys.size()); + for (Key key : keys) { + r.add(CharArrayUtils.extract(key.buffer, key.start, key.length)); + } + return r; + } + + /** + * Removes all mappings from the map. + */ + public void clear() { + this.map.clear(); + } + + /** + * Returns the number of mappings. + */ + public int size() { + return this.map.size(); + } + + /** + * Returns true if the map is empty. + */ + public boolean isEmpty() { + return this.map.isEmpty(); + } + + + /** + * Returns a String representation of the map. + */ + @Override + public String toString() { + return this.map.toString(); + } + +} diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayUtils.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayUtils.java new file mode 100644 index 000000000..1a5791eef --- /dev/null +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/CharArrayUtils.java @@ -0,0 +1,522 @@ +/******************************************************************************* + * Copyright (c) 2004, 2016 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 + * Andrew Ferguson (Symbian) + * Markus Schorn (Wind River Systems) + * Sergey Prigogin (Google) + *******************************************************************************/ +package org.eclipse.jdt.internal.core.nd.util; + +import java.util.Arrays; + +/** + * A static utility class for char arrays. + */ +public class CharArrayUtils { + /** @since 5.4 */ + public static final char[] EMPTY_CHAR_ARRAY = {}; + public static final char[] EMPTY = EMPTY_CHAR_ARRAY; + /** @since 5.7 */ + public static final char[][] EMPTY_ARRAY_OF_CHAR_ARRAYS = {}; + + private CharArrayUtils() {} + + public static final int hash(char[] str, int start, int length) { + int h = 0; + int end = start + length; + + for (int curr = start; curr < end; ++curr) { + h = 31 * h + str[curr]; + } + + return h; + } + + public static final int hash(char[] str) { + return hash(str, 0, str.length); + } + + public static final boolean equals(char[] str1, char[] str2) { + return Arrays.equals(str1, str2); + } + + public static final boolean equals(char[][] strarr1, char[][] strarr2) { + if (strarr1 == strarr2) { + return true; + } + if (strarr1 == null || strarr2 == null) { + return false; + } + if (strarr1.length != strarr2.length) { + return false; + } + for (int i = 0; i < strarr2.length; i++) { + if (!Arrays.equals(strarr1[i], strarr2[i])) { + return false; + } + } + return true; + } + + /** + * Returns {@code true} if the contents of a character array are the same as contents + * of a string. + * @since 5.4 + */ + public static final boolean equals(char[] str1, String str2) { + int length = str1.length; + if (str2.length() != length) + return false; + + for (int i = 0; i < length; i++) { + if (str1[i] != str2.charAt(i)) + return false; + } + return true; + } + + /** + * Returns true iff the given array contains the given char at the given position + */ + public static final boolean hasCharAt(char toLookFor, int position, char[] toSearch) { + if (toSearch.length <= position) { + return false; + } + + return toSearch[position] == toLookFor; + } + + /** + * Returns {@code true} if the contents of a section of a character array are the same as contents of a string. + * + * @since 5.5 + */ + public static final boolean equals(char[] str1, int start1, int length1, String str2) { + if (length1 != str2.length() || str1.length < length1 + start1) + return false; + for (int i = 0; i < length1; ++i) { + if (str1[start1++] != str2.charAt(i)) + return false; + } + return true; + } + + /** + * Returns {@code true} if a prefix of the character array is the same as contents + * of a string. + * @since 5.4 + */ + public static final boolean startsWith(char[] str1, String str2) { + int len = str2.length(); + if (str1.length < len) + return false; + for (int i = 0; i < len; i++) { + if (str1[i] != str2.charAt(i)) { + return false; + } + } + return true; + } + + /** + * Implements a lexicographical comparator for char arrays. Comparison is done + * on a per char basis, not a code-point basis. + * + * @param str1 the first of the two char arrays to compare + * @param str2 the second of the two char arrays to compare + * @return 0 if str1==str2, -1 if str1 < str2 and 1 if str1 > str2 + */ + /* + * aftodo - we should think about using the Character codepoint static methods + * if we move to Java 5 + */ + public static final int compare(char[] str1, char[] str2) { + if (str1 == str2) + return 0; + + int end= Math.min(str1.length, str2.length); + for (int i = 0; i < end; ++i) { + int diff= str1[i] - str2[i]; + if (diff != 0) + return diff; + } + + return str1.length - str2.length; + } + + /** + * Returns {@code true} if the contents of a section of a character array are the same as + * contents of another character array. + */ + public static final boolean equals(char[] str1, int start1, int length1, char[] str2) { + if (length1 != str2.length || str1.length < length1 + start1) + return false; + if (str1 == str2 && start1 == 0) + return true; + for (int i = 0; i < length1; ++i) { + if (str1[start1++] != str2[i]) + return false; + } + + return true; + } + + public static final boolean equals(char[] str1, int start1, int length1, char[] str2, boolean ignoreCase) { + if (!ignoreCase) + return equals(str1, start1, length1, str2); + + if (length1 != str2.length || str1.length < start1 + length1) + return false; + + for (int i = 0; i < length1; ++i) { + if (Character.toLowerCase(str1[start1++]) != Character.toLowerCase(str2[i])) + return false; + } + return true; + } + + public static final char[] extract(char[] str, int start, int length) { + if (start == 0 && length == str.length) + return str; + + char[] copy = new char[length]; + System.arraycopy(str, start, copy, 0, length); + return copy; + } + + public static final char[] concat(char[] first, char[] second) { + if (first == null) + return second; + if (second == null) + return first; + + int length1 = first.length; + int length2 = second.length; + char[] result = new char[length1 + length2]; + System.arraycopy(first, 0, result, 0, length1); + System.arraycopy(second, 0, result, length1, length2); + return result; + } + + public static final char[] concat(char[] first, char[] second, char[] third) { + if (first == null) + return concat(second, third); + if (second == null) + return concat(first, third); + if (third == null) + return concat(first, second); + + int length1 = first.length; + int length2 = second.length; + int length3 = third.length; + char[] result = new char[length1 + length2 + length3]; + System.arraycopy(first, 0, result, 0, length1); + System.arraycopy(second, 0, result, length1, length2); + System.arraycopy(third, 0, result, length1 + length2, length3); + return result; + } + + public static final char[] concat(char[] first, char[] second, char[] third, char[] fourth) { + if (first == null) + return concat(second, third, fourth); + if (second == null) + return concat(first, third, fourth); + if (third == null) + return concat(first, second, fourth); + if (fourth == null) + return concat(first, second, third); + + int length1 = first.length; + int length2 = second.length; + int length3 = third.length; + int length4 = fourth.length; + char[] result = new char[length1 + length2 + length3 + length4]; + System.arraycopy(first, 0, result, 0, length1); + System.arraycopy(second, 0, result, length1, length2); + System.arraycopy(third, 0, result, length1 + length2, length3); + System.arraycopy(fourth, 0, result, length1 + length2 + length3, length4); + return result; + } + + /** + * Answers a new array which is the concatenation of all the given arrays. + * + * @param toCatenate + * @since 3.12 + */ + public static char[] concat(char[]... toCatenate) { + int totalSize = 0; + for (char[] next: toCatenate) { + totalSize += next.length; + } + + char[] result = new char[totalSize]; + int writeIndex = 0; + for (char[] next: toCatenate) { + if (next == null) { + continue; + } + System.arraycopy(next, 0, result, writeIndex, next.length); + writeIndex += next.length; + } + return result; + } + + public static final char[] replace(char[] array, char[] toBeReplaced, char[] replacementChars) { + int max = array.length; + int replacedLength = toBeReplaced.length; + int replacementLength = replacementChars.length; + + int[] starts = new int[5]; + int occurrenceCount = 0; + + if (!equals(toBeReplaced, replacementChars)) { + next: for (int i = 0; i < max; i++) { + int j = 0; + while (j < replacedLength) { + if (i + j == max) + continue next; + if (array[i + j] != toBeReplaced[j++]) + continue next; + } + if (occurrenceCount == starts.length) { + System.arraycopy(starts, 0, starts = new int[occurrenceCount * 2], 0, + occurrenceCount); + } + starts[occurrenceCount++] = i; + } + } + if (occurrenceCount == 0) + return array; + char[] result = new char[max + occurrenceCount * (replacementLength - replacedLength)]; + int inStart = 0, outStart = 0; + for (int i = 0; i < occurrenceCount; i++) { + int offset = starts[i] - inStart; + System.arraycopy(array, inStart, result, outStart, offset); + inStart += offset; + outStart += offset; + System.arraycopy( + replacementChars, + 0, + result, + outStart, + replacementLength); + inStart += replacedLength; + outStart += replacementLength; + } + System.arraycopy(array, inStart, result, outStart, max - inStart); + return result; + } + + public static final char[][] subarray(char[][] array, int start, int end) { + if (end == -1) + end = array.length; + if (start > end) + return null; + if (start < 0) + return null; + if (end > array.length) + return null; + + char[][] result = new char[end - start][]; + System.arraycopy(array, start, result, 0, end - start); + return result; + } + + public static final char[] subarray(char[] array, int start, int end) { + if (end == -1) + end = array.length; + if (start > end) + return null; + if (start < 0) + return null; + if (end > array.length) + return null; + + char[] result = new char[end - start]; + System.arraycopy(array, start, result, 0, end - start); + return result; + } + + public static final int indexOf(char toBeFound, char[] array) { + for (int i = 0; i < array.length; i++) { + if (toBeFound == array[i]) + return i; + } + return -1; + } + + public static int indexOf(char toBeFound, char[] buffer, int start, int end) { + if (start < 0 || start > buffer.length || end > buffer.length) + return -1; + + for (int i = start; i < end; i++) { + if (toBeFound == buffer[i]) + return i; + } + return -1; + } + + public static final int indexOf(char[] toBeFound, char[] array) { + if (toBeFound.length > array.length) + return -1; + + int j = 0; + for (int i = 0; i < array.length; i++) { + if (toBeFound[j] == array[i]) { + if (++j == toBeFound.length) + return i - j + 1; + } else { + j = 0; + } + } + return -1; + } + + public static final int lastIndexOf(char[] toBeFound, char[] array) { + return lastIndexOf(toBeFound, array, 0); + } + + /** + * @since 5.11 + */ + public static int lastIndexOf(char toBeFound, char[] array) { + return lastIndexOf(toBeFound, array, 0); + } + + /** + * @since 5.11 + */ + public static int lastIndexOf(char toBeFound, char[] array, int fromIndex) { + for (int i = array.length; --i >= fromIndex;) { + if (array[i] == toBeFound) { + return i; + } + } + return -1; + } + + /** + * @since 5.11 + */ + public static int lastIndexOf(char[] toBeFound, char[] array, int fromIndex) { + int i = array.length; + int j = toBeFound.length; + while (true) { + if (--j < 0) + return i; + if (--i < fromIndex) + return -1; + if (toBeFound[j] != array[i]) { + i += toBeFound.length - j - 1; + j = toBeFound.length; + } + } + } + + static final public char[] trim(char[] chars) { + if (chars == null) + return null; + + int length = chars.length; + int start = 0; + while (start < length && chars[start] == ' ') { + start++; + } + if (start == length) + return EMPTY_CHAR_ARRAY; + + int end = length; + while (--end > start && chars[end] == ' ') { + // Nothing to do + } + end++; + if (start == 0 && end == length) + return chars; + return subarray(chars, start, end); + } + + static final public char[] lastSegment(char[] array, char[] separator) { + int pos = lastIndexOf(separator, array); + if (pos < 0) + return array; + return subarray(array, pos + separator.length, array.length); + } + + /** + * @param buff + * @param i + * @param charImage + */ + public static void overWrite(char[] buff, int i, char[] charImage) { + if (buff.length < i + charImage.length) + return; + for (int j = 0; j < charImage.length; j++) { + buff[i + j] = charImage[j]; + } + } + + /** + * Finds an array of chars in an array of arrays of chars. + * + * @return offset where the array was found or {@code -1} + */ + public static int indexOf(final char[] searchFor, final char[][] searchIn) { + for (int i = 0; i < searchIn.length; i++) { + if (equals(searchIn[i], searchFor)) { + return i; + } + } + return -1; + } + + /** + * Converts a {@link StringBuilder} to a character array. + * @since 5.5 + */ + public static char[] extractChars(StringBuilder buf) { + final int len = buf.length(); + if (len == 0) + return EMPTY_CHAR_ARRAY; + char[] result= new char[len]; + buf.getChars(0, len, result, 0); + return result; + } + + public static char[] subarray(char[] inputString, int index) { + if (inputString.length <= index) { + return EMPTY_CHAR_ARRAY; + } + + char[] result = new char[inputString.length - index]; + System.arraycopy(inputString, index, result, 0, result.length); + return result; + } + + public static boolean startsWith(char[] fieldDescriptor, char c) { + return fieldDescriptor.length > 0 && fieldDescriptor[0] == c; + } + + /** + * If the given array is null, returns the empty array. Otherwise, returns the argument. + */ + public static char[] notNull(char[] contents) { + if (contents == null) { + return EMPTY_CHAR_ARRAY; + } + return contents; + } + + public static boolean endsWith(char[] fieldDescriptor, char c) { + if (fieldDescriptor.length == 0) { + return false; + } + return fieldDescriptor[fieldDescriptor.length - 1] == c; + } +} diff --git a/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/PathMap.java b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/PathMap.java new file mode 100644 index 000000000..f328fe041 --- /dev/null +++ b/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/util/PathMap.java @@ -0,0 +1,225 @@ +/******************************************************************************* + * Copyright (c) 2015, 2016 Google, Inc 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: + * Stefan Xenos (Google) - Initial implementation + *******************************************************************************/ +package org.eclipse.jdt.internal.core.nd.util; + +import org.eclipse.core.runtime.IPath; +import org.eclipse.core.runtime.Path; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +/** + * Maps IPath keys onto values. + */ +public class PathMap<T> { + private static class Node<T> { + int depth; + boolean exists; + T value; + Map<String, Node<T>> children; + + Node(int depth) { + this.depth = depth; + } + + String getSegment(IPath key) { + return key.segment(this.depth); + } + + Node<T> createNode(IPath key) { + if (this.depth == key.segmentCount()) { + this.exists = true; + return this; + } + + String nextSegment = getSegment(key); + Node<T> next = createChild(nextSegment); + return next.createNode(key); + } + + public Node<T> createChild(String nextSegment) { + if (this.children == null) { + this.children = new HashMap<>(); + } + Node<T> next = this.children.get(nextSegment); + if (next == null) { + next = new Node<>(this.depth + 1); + this.children.put(nextSegment, next); + } + return next; + } + + public Node<T> getMostSpecificNode(IPath key) { + if (this.depth == key.segmentCount()) { + return this; + } + String nextSegment = getSegment(key); + + Node<T> child = getChild(nextSegment); + if (child == null) { + return this; + } + Node<T> result = child.getMostSpecificNode(key); + if (result.exists) { + return result; + } else { + return this; + } + } + + Node<T> getChild(String nextSegment) { + if (this.children == null) { + return null; + } + return this.children.get(nextSegment); + } + + public void addAllKeys(Set<IPath> result, IPath parent) { + if (this.exists) { + result.add(parent); + } + + if (this.children == null) { + return; + } + + for (Entry<String, Node<T>> next : this.children.entrySet()) { + String key = next.getKey(); + IPath nextPath = buildChildPath(parent, key); + next.getValue().addAllKeys(result, nextPath); + } + } + + IPath buildChildPath(IPath parent, String key) { + IPath nextPath = parent.append(key); + return nextPath; + } + + public void toString(StringBuilder builder, IPath parentPath) { + if (this.exists) { + builder.append("["); //$NON-NLS-1$ + builder.append(parentPath); + builder.append("] = "); //$NON-NLS-1$ + builder.append(this.value); + builder.append("\n"); //$NON-NLS-1$ + } + if (this.children != null) { + for (Entry<String, Node<T>> next : this.children.entrySet()) { + String key = next.getKey(); + IPath nextPath = buildChildPath(parentPath, key); + next.getValue().toString(builder, nextPath); + } + } + } + } + + private static class DeviceNode<T> extends Node<T> { + Node<T> noDevice = new Node<>(0); + + DeviceNode() { + super(-1); + } + + @Override + String getSegment(IPath key) { + return key.getDevice(); + } + + @Override + public Node<T> createChild(String nextSegment) { + if (nextSegment == null) { + return this.noDevice; + } + return super.createChild(nextSegment); + } + + Node<T> getChild(String nextSegment) { + if (nextSegment == null) { + return this.noDevice; + } + return super.getChild(nextSegment); + } + + @Override + IPath buildChildPath(IPath parent, String key) { + IPath nextPath = Path.EMPTY.append(parent); + nextPath.setDevice(key); + return nextPath; + } + + @Override + public void toString(StringBuilder builder, IPath parentPath) { + this.noDevice.toString(builder, parentPath); + super.toString(builder,parentPath); + } + } + + private Node<T> root = new DeviceNode<T>(); + + /** + * Inserts the given key into the map. + */ + public T put(IPath key, T value) { + Node<T> node = this.root.createNode(key); + T result = node.value; + node.value = value; + return result; + } + + /** + * Returns the value associated with the given key + */ + public T get(IPath key) { + Node<T> node = this.root.getMostSpecificNode(key); + if (!node.exists || node.depth < key.segmentCount()) { + return null; + } + return node.value; + } + + /** + * Returns the value associated with the longest prefix of the given key + * that can be found in the map. + */ + public T getMostSpecific(IPath key) { + Node<T> node = this.root.getMostSpecificNode(key); + if (!node.exists) { + return null; + } + return node.value; + } + + /** + * Returns true iff any key in this map is a prefix of the given path. + */ + public boolean containsPrefixOf(IPath path) { + Node<T> node = this.root.getMostSpecificNode(path); + return node.exists; + } + + public Set<IPath> keySet() { + Set<IPath> result = new HashSet<>(); + + this.root.addAllKeys(result, Path.EMPTY); + return result; + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + this.root.toString(builder, Path.EMPTY); + return builder.toString(); + } +} |