fix
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/StateMachine.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/StateMachine.java
index bcaa4bb..86e9c66 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/StateMachine.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/StateMachine.java
@@ -19,7 +19,6 @@
package org.apache.iotdb.db.queryengine.execution;
-import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.util.concurrent.ListenableFuture;
@@ -298,12 +297,10 @@
safeExecute(() -> stateChangeListener.stateChanged(currentState));
}
- @VisibleForTesting
boolean isTerminalState(T state) {
return terminalStates.contains(state);
}
- @VisibleForTesting
List<StateChangeListener<T>> getStateChangeListeners() {
synchronized (lock) {
return ImmutableList.copyOf(stateChangeListeners);
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/rowpattern/matcher/ArrayView.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/rowpattern/matcher/ArrayView.java
index 63197a2..c38eb23 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/rowpattern/matcher/ArrayView.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/rowpattern/matcher/ArrayView.java
@@ -19,8 +19,6 @@
package org.apache.iotdb.db.queryengine.execution.operator.process.rowpattern.matcher;
-import com.google.common.annotations.VisibleForTesting;
-
import java.util.Arrays;
import static com.google.common.base.Preconditions.checkArgument;
@@ -48,7 +46,6 @@
return length;
}
- @VisibleForTesting
public int[] toArray() {
return Arrays.copyOf(array, length);
}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/array/ShortBigArray.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/array/ShortBigArray.java
index 38bdb76..c2013dd 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/array/ShortBigArray.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/array/ShortBigArray.java
@@ -19,10 +19,9 @@
package org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.array;
-import com.google.common.primitives.Shorts;
-
import java.util.Arrays;
+import static com.google.common.base.Preconditions.checkArgument;
import static org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.array.BigArrays.INITIAL_SEGMENTS;
import static org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.array.BigArrays.SEGMENT_SIZE;
import static org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.array.BigArrays.offset;
@@ -97,7 +96,21 @@
* @param value the value
*/
public void add(long index, long value) {
- array[segment(index)][offset(index)] += Shorts.checkedCast(value);
+ array[segment(index)][offset(index)] += checkedCast(value);
+ }
+
+ /**
+ * Returns the {@code short} value that is equal to {@code value}, if possible.
+ *
+ * @param value any value in the range of the {@code short} type
+ * @return the {@code short} value that equals {@code value}
+ * @throws IllegalArgumentException if {@code value} is greater than {@link Short#MAX_VALUE} or
+ * less than {@link Short#MIN_VALUE}
+ */
+ public static short checkedCast(long value) {
+ short result = (short) value;
+ checkArgument(result == value, "Out of range: %s", value);
+ return result;
}
/**
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/GroupByHash.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/GroupByHash.java
index 60059ae..524dee9 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/GroupByHash.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/GroupByHash.java
@@ -21,7 +21,6 @@
import org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.UpdateMemory;
-import com.google.common.annotations.VisibleForTesting;
import org.apache.tsfile.block.column.Column;
import org.apache.tsfile.read.common.block.TsBlockBuilder;
import org.apache.tsfile.read.common.type.Type;
@@ -56,6 +55,5 @@
long getRawHash(int groupId);
- @VisibleForTesting
int getCapacity();
}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/MarkDistinctHash.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/MarkDistinctHash.java
index 7001bdf..c866dc0 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/MarkDistinctHash.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/source/relational/aggregation/grouped/hash/MarkDistinctHash.java
@@ -21,7 +21,6 @@
import org.apache.iotdb.db.queryengine.execution.operator.source.relational.aggregation.grouped.UpdateMemory;
-import com.google.common.annotations.VisibleForTesting;
import org.apache.tsfile.block.column.Column;
import org.apache.tsfile.read.common.block.column.BooleanColumn;
import org.apache.tsfile.read.common.block.column.RunLengthEncodedColumn;
@@ -55,7 +54,6 @@
groupByHash.getGroupCount(), groupIds, columns[0].getPositionCount());
}
- @VisibleForTesting
public int getCapacity() {
return groupByHash.getCapacity();
}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/EqualityInference.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/EqualityInference.java
index f5ecd7d..d31d1f0 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/EqualityInference.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/EqualityInference.java
@@ -25,7 +25,6 @@
import org.apache.iotdb.db.queryengine.plan.relational.sql.ast.SymbolReference;
import org.apache.iotdb.db.queryengine.plan.relational.utils.DisjointSet;
-import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
@@ -354,7 +353,6 @@
* Returns a canonical expression that is fully contained by the symbolScope and that is
* equivalent to the specified expression. Returns null if unable to find a canonical.
*/
- @VisibleForTesting
Expression getScopedCanonical(Expression expression, Predicate<Symbol> symbolScope) {
Expression canonicalIndex = canonicalMap.get(expression);
if (canonicalIndex == null) {
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/base/Functions.java b/iotdb-core/node-commons/src/main/java/com/google/common/base/Functions.java
new file mode 100644
index 0000000..53c6457
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/base/Functions.java
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2007 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.base;
+
+import javax.annotation.CheckForNull;
+
+/**
+ * Static utility methods pertaining to {@code com.google.common.base.Function} instances; see that
+ * class for information about migrating to {@code java.util.function}.
+ *
+ * <p>All methods return serializable functions as long as they're given serializable parameters.
+ *
+ * <p>See the Guava User Guide article on <a
+ * href="https://github.com/google/guava/wiki/FunctionalExplained">the use of {@code Function}</a>.
+ *
+ * @author Mike Bostock
+ * @author Jared Levy
+ * @since 2.0
+ */
+public final class Functions {
+ private Functions() {}
+
+ /**
+ * Returns the identity function.
+ *
+ * <p><b>Discouraged:</b> Prefer using a lambda like {@code v -> v}, which is shorter and often
+ * more readable.
+ */
+ // implementation is "fully variant"; E has become a "pass-through" type
+ @SuppressWarnings("unchecked")
+ public static <E extends Object> Function<E, E> identity() {
+ return (Function<E, E>) IdentityFunction.INSTANCE;
+ }
+
+ // enum singleton pattern
+ private enum IdentityFunction implements Function<Object, Object> {
+ INSTANCE;
+
+ @Override
+ @CheckForNull
+ public Object apply(@CheckForNull Object o) {
+ return o;
+ }
+
+ @Override
+ public String toString() {
+ return "Functions.identity()";
+ }
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/base/Splitter.java b/iotdb-core/node-commons/src/main/java/com/google/common/base/Splitter.java
index d850ede..7d626a3 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/base/Splitter.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/base/Splitter.java
@@ -16,15 +16,9 @@
import javax.annotation.CheckForNull;
-import java.util.ArrayList;
-import java.util.Collections;
import java.util.Iterator;
-import java.util.LinkedHashMap;
import java.util.List;
-import java.util.Map;
import java.util.regex.Pattern;
-import java.util.stream.Stream;
-import java.util.stream.StreamSupport;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
@@ -241,83 +235,6 @@
}
/**
- * Returns a splitter that considers any subsequence matching a given pattern (regular expression)
- * to be a separator. For example, {@code Splitter.onPattern("\r?\n").split(entireFile)} splits a
- * string into lines whether it uses DOS-style or UNIX-style line terminators. This is equivalent
- * to {@code Splitter.on(Pattern.compile(pattern))}.
- *
- * @param separatorPattern the pattern that determines whether a subsequence is a separator. This
- * pattern may not match the empty string.
- * @return a splitter, with default settings, that uses this pattern
- * @throws IllegalArgumentException if {@code separatorPattern} matches the empty string or is a
- * malformed expression
- */
- public static Splitter onPattern(String separatorPattern) {
- return on(Platform.compilePattern(separatorPattern));
- }
-
- /**
- * Returns a splitter that divides strings into pieces of the given length. For example, {@code
- * Splitter.fixedLength(2).split("abcde")} returns an iterable containing {@code ["ab", "cd",
- * "e"]}. The last piece can be smaller than {@code length} but will never be empty.
- *
- * <p><b>Note:</b> if {@link #fixedLength} is used in conjunction with {@link #limit}, the final
- * split piece <i>may be longer than the specified fixed length</i>. This is because the splitter
- * will <i>stop splitting when the limit is reached</i>, and just return the final piece as-is.
- *
- * <p><b>Exception:</b> for consistency with separator-based splitters, {@code split("")} does not
- * yield an empty iterable, but an iterable containing {@code ""}. This is the only case in which
- * {@code Iterables.size(split(input))} does not equal {@code IntMath.divide(input.length(),
- * length, CEILING)}. To avoid this behavior, use {@code omitEmptyStrings}.
- *
- * @param length the desired length of pieces after splitting, a positive integer
- * @return a splitter, with default settings, that can split into fixed sized pieces
- * @throws IllegalArgumentException if {@code length} is zero or negative
- */
- public static Splitter fixedLength(final int length) {
- checkArgument(length > 0, "The length may not be less than 1");
-
- return new Splitter(
- new Strategy() {
- @Override
- public SplittingIterator iterator(final Splitter splitter, CharSequence toSplit) {
- return new SplittingIterator(splitter, toSplit) {
- @Override
- public int separatorStart(int start) {
- int nextChunkStart = start + length;
- return (nextChunkStart < toSplit.length() ? nextChunkStart : -1);
- }
-
- @Override
- public int separatorEnd(int separatorPosition) {
- return separatorPosition;
- }
- };
- }
- });
- }
-
- /**
- * Returns a splitter that behaves equivalently to {@code this} splitter, but automatically omits
- * empty strings from the results. For example, {@code
- * Splitter.on(',').omitEmptyStrings().split(",a,,,b,c,,")} returns an iterable containing only
- * {@code ["a", "b", "c"]}.
- *
- * <p>If either {@code trimResults} option is also specified when creating a splitter, that
- * splitter always trims results first before checking for emptiness. So, for example, {@code
- * Splitter.on(':').omitEmptyStrings().trimResults().split(": : : ")} returns an empty iterable.
- *
- * <p>Note that it is ordinarily not possible for {@link #split(CharSequence)} to return an empty
- * iterable, but when using this option, it can (if the input sequence consists of nothing but
- * separators).
- *
- * @return a splitter with the desired configuration
- */
- public Splitter omitEmptyStrings() {
- return new Splitter(strategy, true, trimmer, limit);
- }
-
- /**
* Returns a splitter that behaves equivalently to {@code this} splitter but stops splitting after
* it reaches the limit. The limit defines the maximum number of items returned by the iterator,
* or the maximum size of the list returned by {@link #splitToList}.
@@ -398,132 +315,6 @@
return strategy.iterator(this, sequence);
}
- /**
- * Splits {@code sequence} into string components and returns them as an immutable list. If you
- * want an {@link Iterable} which may be lazily evaluated, use {@link #split(CharSequence)}.
- *
- * @param sequence the sequence of characters to split
- * @return an immutable list of the segments split from the parameter
- * @since 15.0
- */
- public List<String> splitToList(CharSequence sequence) {
- checkNotNull(sequence);
-
- Iterator<String> iterator = splittingIterator(sequence);
- List<String> result = new ArrayList<>();
-
- while (iterator.hasNext()) {
- result.add(iterator.next());
- }
-
- return Collections.unmodifiableList(result);
- }
-
- /**
- * Splits {@code sequence} into string components and makes them available through an {@link
- * Stream}, which may be lazily evaluated. If you want an eagerly computed {@link List}, use
- * {@link #splitToList(CharSequence)}.
- *
- * @param sequence the sequence of characters to split
- * @return a stream over the segments split from the parameter
- * @since 28.2
- */
- public Stream<String> splitToStream(CharSequence sequence) {
- // Can't use Streams.stream() from base
- return StreamSupport.stream(split(sequence).spliterator(), false);
- }
-
- /**
- * Returns a {@code MapSplitter} which splits entries based on this splitter, and splits entries
- * into keys and values using the specified separator.
- *
- * @since 10.0
- */
- public MapSplitter withKeyValueSeparator(String separator) {
- return withKeyValueSeparator(on(separator));
- }
-
- /**
- * Returns a {@code MapSplitter} which splits entries based on this splitter, and splits entries
- * into keys and values using the specified separator.
- *
- * @since 14.0
- */
- public MapSplitter withKeyValueSeparator(char separator) {
- return withKeyValueSeparator(on(separator));
- }
-
- /**
- * Returns a {@code MapSplitter} which splits entries based on this splitter, and splits entries
- * into keys and values using the specified key-value splitter.
- *
- * <p>Note: Any configuration option configured on this splitter, such as {@link #trimResults},
- * does not change the behavior of the {@code keyValueSplitter}.
- *
- * <p>Example:
- *
- * <pre>{@code
- * String toSplit = " x -> y, z-> a ";
- * Splitter outerSplitter = Splitter.on(',').trimResults();
- * MapSplitter mapSplitter = outerSplitter.withKeyValueSeparator(Splitter.on("->"));
- * Map<String, String> result = mapSplitter.split(toSplit);
- * assertThat(result).isEqualTo(ImmutableMap.of("x ", " y", "z", " a"));
- * }</pre>
- *
- * @since 10.0
- */
- public MapSplitter withKeyValueSeparator(Splitter keyValueSplitter) {
- return new MapSplitter(this, keyValueSplitter);
- }
-
- /**
- * An object that splits strings into maps as {@code Splitter} splits iterables and lists. Like
- * {@code Splitter}, it is thread-safe and immutable. The common way to build instances is by
- * providing an additional {@linkplain Splitter#withKeyValueSeparator key-value separator} to
- * {@link Splitter}.
- *
- * @since 10.0
- */
- public static final class MapSplitter {
- private static final String INVALID_ENTRY_MESSAGE = "Chunk [%s] is not a valid entry";
- private final Splitter outerSplitter;
- private final Splitter entrySplitter;
-
- private MapSplitter(Splitter outerSplitter, Splitter entrySplitter) {
- this.outerSplitter = outerSplitter; // only "this" is passed
- this.entrySplitter = checkNotNull(entrySplitter);
- }
-
- /**
- * Splits {@code sequence} into substrings, splits each substring into an entry, and returns an
- * unmodifiable map with each of the entries. For example, {@code
- * Splitter.on(';').trimResults().withKeyValueSeparator("=>").split("a=>b ; c=>b")} will return
- * a mapping from {@code "a"} to {@code "b"} and {@code "c"} to {@code "b"}.
- *
- * <p>The returned map preserves the order of the entries from {@code sequence}.
- *
- * @throws IllegalArgumentException if the specified sequence does not split into valid map
- * entries, or if there are duplicate keys
- */
- public Map<String, String> split(CharSequence sequence) {
- Map<String, String> map = new LinkedHashMap<>();
- for (String entry : outerSplitter.split(sequence)) {
- Iterator<String> entryFields = entrySplitter.splittingIterator(entry);
-
- checkArgument(entryFields.hasNext(), INVALID_ENTRY_MESSAGE, entry);
- String key = entryFields.next();
- checkArgument(!map.containsKey(key), "Duplicate key [%s] found.", key);
-
- checkArgument(entryFields.hasNext(), INVALID_ENTRY_MESSAGE, entry);
- String value = entryFields.next();
- map.put(key, value);
-
- checkArgument(!entryFields.hasNext(), INVALID_ENTRY_MESSAGE, entry);
- }
- return Collections.unmodifiableMap(map);
- }
- }
-
private interface Strategy {
Iterator<String> iterator(Splitter splitter, CharSequence toSplit);
}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/base/Strings.java b/iotdb-core/node-commons/src/main/java/com/google/common/base/Strings.java
index eab6202..c75da4d 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/base/Strings.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/base/Strings.java
@@ -32,16 +32,6 @@
private Strings() {}
/**
- * Returns the given string if it is non-null; the empty string otherwise.
- *
- * @param string the string to test and possibly return
- * @return {@code string} itself if it is non-null; {@code ""} if it is null
- */
- public static String nullToEmpty(@CheckForNull String string) {
- return Platform.nullToEmpty(string);
- }
-
- /**
* Returns the given string if it is nonempty; {@code null} otherwise.
*
* @param string the string to test and possibly return
@@ -68,68 +58,6 @@
}
/**
- * Returns a string, of length at least {@code minLength}, consisting of {@code string} prepended
- * with as many copies of {@code padChar} as are necessary to reach that length. For example,
- *
- * <ul>
- * <li>{@code padStart("7", 3, '0')} returns {@code "007"}
- * <li>{@code padStart("2010", 3, '0')} returns {@code "2010"}
- * </ul>
- *
- * <p>See {@link java.util.Formatter} for a richer set of formatting capabilities.
- *
- * @param string the string which should appear at the end of the result
- * @param minLength the minimum length the resulting string must have. Can be zero or negative, in
- * which case the input string is always returned.
- * @param padChar the character to insert at the beginning of the result until the minimum length
- * is reached
- * @return the padded string
- */
- public static String padStart(String string, int minLength, char padChar) {
- checkNotNull(string); // eager for GWT.
- if (string.length() >= minLength) {
- return string;
- }
- StringBuilder sb = new StringBuilder(minLength);
- for (int i = string.length(); i < minLength; i++) {
- sb.append(padChar);
- }
- sb.append(string);
- return sb.toString();
- }
-
- /**
- * Returns a string, of length at least {@code minLength}, consisting of {@code string} appended
- * with as many copies of {@code padChar} as are necessary to reach that length. For example,
- *
- * <ul>
- * <li>{@code padEnd("4.", 5, '0')} returns {@code "4.000"}
- * <li>{@code padEnd("2010", 3, '!')} returns {@code "2010"}
- * </ul>
- *
- * <p>See {@link java.util.Formatter} for a richer set of formatting capabilities.
- *
- * @param string the string which should appear at the beginning of the result
- * @param minLength the minimum length the resulting string must have. Can be zero or negative, in
- * which case the input string is always returned.
- * @param padChar the character to append to the end of the result until the minimum length is
- * reached
- * @return the padded string
- */
- public static String padEnd(String string, int minLength, char padChar) {
- checkNotNull(string); // eager for GWT.
- if (string.length() >= minLength) {
- return string;
- }
- StringBuilder sb = new StringBuilder(minLength);
- sb.append(string);
- for (int i = string.length(); i < minLength; i++) {
- sb.append(padChar);
- }
- return sb.toString();
- }
-
- /**
* Returns a string consisting of a specific number of concatenated copies of an input string. For
* example, {@code repeat("hey", 3)} returns the string {@code "heyheyhey"}.
*
@@ -168,62 +96,6 @@
}
/**
- * Returns the longest string {@code prefix} such that {@code a.toString().startsWith(prefix) &&
- * b.toString().startsWith(prefix)}, taking care not to split surrogate pairs. If {@code a} and
- * {@code b} have no common prefix, returns the empty string.
- *
- * @since 11.0
- */
- public static String commonPrefix(CharSequence a, CharSequence b) {
- checkNotNull(a);
- checkNotNull(b);
-
- int maxPrefixLength = Math.min(a.length(), b.length());
- int p = 0;
- while (p < maxPrefixLength && a.charAt(p) == b.charAt(p)) {
- p++;
- }
- if (validSurrogatePairAt(a, p - 1) || validSurrogatePairAt(b, p - 1)) {
- p--;
- }
- return a.subSequence(0, p).toString();
- }
-
- /**
- * Returns the longest string {@code suffix} such that {@code a.toString().endsWith(suffix) &&
- * b.toString().endsWith(suffix)}, taking care not to split surrogate pairs. If {@code a} and
- * {@code b} have no common suffix, returns the empty string.
- *
- * @since 11.0
- */
- public static String commonSuffix(CharSequence a, CharSequence b) {
- checkNotNull(a);
- checkNotNull(b);
-
- int maxSuffixLength = Math.min(a.length(), b.length());
- int s = 0;
- while (s < maxSuffixLength && a.charAt(a.length() - s - 1) == b.charAt(b.length() - s - 1)) {
- s++;
- }
- if (validSurrogatePairAt(a, a.length() - s - 1)
- || validSurrogatePairAt(b, b.length() - s - 1)) {
- s--;
- }
- return a.subSequence(a.length() - s, a.length()).toString();
- }
-
- /**
- * True when a valid surrogate pair starts at the given {@code index} in the given {@code string}.
- * Out-of-range indexes return false.
- */
- static boolean validSurrogatePairAt(CharSequence string, int index) {
- return index >= 0
- && index <= (string.length() - 2)
- && Character.isHighSurrogate(string.charAt(index))
- && Character.isLowSurrogate(string.charAt(index + 1));
- }
-
- /**
* Returns the given {@code template} string with each occurrence of {@code "%s"} replaced with
* the corresponding argument value from {@code args}; or, if the placeholder and argument counts
* do not match, returns a best-effort form of that string. Will not throw an exception under
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimap.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimap.java
new file mode 100644
index 0000000..4a5252b
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimap.java
@@ -0,0 +1,165 @@
+/*
+ * Copyright (C) 2007 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import static com.google.common.collect.CollectPreconditions.checkNonnegative;
+
+/**
+ * Implementation of {@code Multimap} that uses an {@code ArrayList} to store the values for a given
+ * key. A {@link HashMap} associates each key with an {@link ArrayList} of values.
+ *
+ * <p>When iterating through the collections supplied by this class, the ordering of values for a
+ * given key agrees with the order in which the values were added.
+ *
+ * <p>This multimap allows duplicate key-value pairs. After adding a new key-value pair equal to an
+ * existing key-value pair, the {@code ArrayListMultimap} will contain entries for both the new
+ * value and the old value.
+ *
+ * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
+ * views are modifiable.
+ *
+ * <p>The lists returned by {@link #get}, {@link #removeAll}, and {@link #replaceValues} all
+ * implement {@link java.util.RandomAccess}.
+ *
+ * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
+ * read operations will work correctly. To allow concurrent update operations, wrap your multimap
+ * with a call to {@link Multimaps#synchronizedListMultimap}.
+ *
+ * <p>See the Guava User Guide article on <a href=
+ * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>.
+ *
+ * @author Jared Levy
+ * @since 2.0
+ */
+public final class ArrayListMultimap<K extends Object, V extends Object>
+ extends ArrayListMultimapGwtSerializationDependencies<K, V> {
+ // Default from ArrayList
+ private static final int DEFAULT_VALUES_PER_KEY = 3;
+
+ transient int expectedValuesPerKey;
+
+ /**
+ * Creates a new, empty {@code ArrayListMultimap} with the default initial capacities.
+ *
+ * <p>This method will soon be deprecated in favor of {@code
+ * MultimapBuilder.hashKeys().arrayListValues().build()}.
+ */
+ public static <K extends Object, V extends Object> ArrayListMultimap<K, V> create() {
+ return new ArrayListMultimap<>();
+ }
+
+ /**
+ * Constructs an empty {@code ArrayListMultimap} with enough capacity to hold the specified
+ * numbers of keys and values without resizing.
+ *
+ * <p>This method will soon be deprecated in favor of {@code
+ * MultimapBuilder.hashKeys(expectedKeys).arrayListValues(expectedValuesPerKey).build()}.
+ *
+ * @param expectedKeys the expected number of distinct keys
+ * @param expectedValuesPerKey the expected average number of values per key
+ * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
+ * negative
+ */
+ public static <K extends Object, V extends Object> ArrayListMultimap<K, V> create(
+ int expectedKeys, int expectedValuesPerKey) {
+ return new ArrayListMultimap<>(expectedKeys, expectedValuesPerKey);
+ }
+
+ /**
+ * Constructs an {@code ArrayListMultimap} with the same mappings as the specified multimap.
+ *
+ * <p>This method will soon be deprecated in favor of {@code
+ * MultimapBuilder.hashKeys().arrayListValues().build(multimap)}.
+ *
+ * @param multimap the multimap whose contents are copied to this multimap
+ */
+ public static <K extends Object, V extends Object> ArrayListMultimap<K, V> create(
+ Multimap<? extends K, ? extends V> multimap) {
+ return new ArrayListMultimap<>(multimap);
+ }
+
+ private ArrayListMultimap() {
+ this(12, DEFAULT_VALUES_PER_KEY);
+ }
+
+ private ArrayListMultimap(int expectedKeys, int expectedValuesPerKey) {
+ super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys));
+ checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
+ this.expectedValuesPerKey = expectedValuesPerKey;
+ }
+
+ private ArrayListMultimap(Multimap<? extends K, ? extends V> multimap) {
+ this(
+ multimap.keySet().size(),
+ (multimap instanceof ArrayListMultimap)
+ ? ((ArrayListMultimap<?, ?>) multimap).expectedValuesPerKey
+ : DEFAULT_VALUES_PER_KEY);
+ putAll(multimap);
+ }
+
+ /**
+ * Creates a new, empty {@code ArrayList} to hold the collection of values for an arbitrary key.
+ */
+ @Override
+ List<V> createCollection() {
+ return new ArrayList<V>(expectedValuesPerKey);
+ }
+
+ /**
+ * Reduces the memory used by this {@code ArrayListMultimap}, if feasible.
+ *
+ * @deprecated For a {@link ListMultimap} that automatically trims to size, use {@link
+ * ImmutableListMultimap}. If you need a mutable collection, remove the {@code trimToSize}
+ * call, or switch to a {@code HashMap<K, ArrayList<V>>}.
+ */
+ @Deprecated
+ public void trimToSize() {
+ for (Collection<V> collection : backingMap().values()) {
+ ArrayList<V> arrayList = (ArrayList<V>) collection;
+ arrayList.trimToSize();
+ }
+ }
+
+ /**
+ * @serialData expectedValuesPerKey, number of distinct keys, and then for each distinct key: the
+ * key, number of values for that key, and the key's values
+ */
+ private void writeObject(ObjectOutputStream stream) throws IOException {
+ stream.defaultWriteObject();
+ Serialization.writeMultimap(this, stream);
+ }
+
+ private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
+ stream.defaultReadObject();
+ expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
+ int distinctKeys = Serialization.readCount(stream);
+ Map<K, Collection<V>> map = Maps.newHashMap();
+ setMap(map);
+ Serialization.populateMultimap(this, stream, distinctKeys);
+ }
+
+ private static final long serialVersionUID = 0;
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimapGwtSerializationDependencies.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimapGwtSerializationDependencies.java
new file mode 100644
index 0000000..15220cf
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/ArrayListMultimapGwtSerializationDependencies.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import java.util.Collection;
+import java.util.Map;
+
+/**
+ * A dummy superclass to support GWT serialization of the element types of an {@link
+ * ArrayListMultimap}. The GWT supersource for this class contains a field for each type.
+ *
+ * <p>For details about this hack, see {@code GwtSerializationDependencies}, which takes the same
+ * approach but with a subclass rather than a superclass.
+ *
+ * <p>TODO(cpovirk): Consider applying this subclass approach to our other types.
+ */
+abstract class ArrayListMultimapGwtSerializationDependencies<K, V>
+ extends AbstractListMultimap<K, V> {
+ ArrayListMultimapGwtSerializationDependencies(Map<K, Collection<V>> map) {
+ super(map);
+ }
+ // TODO(cpovirk): Maybe I should have just one shared superclass for AbstractMultimap itself?
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimap.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimap.java
new file mode 100644
index 0000000..b3a361d
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimap.java
@@ -0,0 +1,642 @@
+/*
+ * Copyright (C) 2007 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import com.google.common.base.Objects;
+
+import javax.annotation.CheckForNull;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.function.Consumer;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+import static com.google.common.collect.CollectPreconditions.checkNonnegative;
+import static java.util.Objects.requireNonNull;
+
+/**
+ * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that
+ * returns collections whose iterators follow the ordering in which the data was added to the
+ * multimap.
+ *
+ * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through
+ * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code
+ * removeAll}, and {@code replaceValues} return collections that iterate through the values in the
+ * order they were added. The collections generated by {@code entries} and {@code values} iterate
+ * across the key-value mappings in the order they were added to the multimap.
+ *
+ * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and
+ * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or
+ * removing mappings does not affect the key iteration order. However, if you remove all values
+ * associated with a key and then add the key back to the multimap, that key will come last in the
+ * key iteration order.
+ *
+ * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
+ * existing key-value pair has no effect.
+ *
+ * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
+ * views are modifiable.
+ *
+ * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
+ * read operations will work correctly. To allow concurrent update operations, wrap your multimap
+ * with a call to {@link Multimaps#synchronizedSetMultimap}.
+ *
+ * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap}
+ * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will
+ * result.
+ *
+ * <p>See the Guava User Guide article on <a href=
+ * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>.
+ *
+ * @author Jared Levy
+ * @author Louis Wasserman
+ * @since 2.0
+ */
+public final class LinkedHashMultimap<K extends Object, V extends Object>
+ extends LinkedHashMultimapGwtSerializationDependencies<K, V> {
+
+ /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */
+ public static <K extends Object, V extends Object> LinkedHashMultimap<K, V> create() {
+ return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
+ }
+
+ /**
+ * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
+ * numbers of keys and values without rehashing.
+ *
+ * @param expectedKeys the expected number of distinct keys
+ * @param expectedValuesPerKey the expected average number of values per key
+ * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
+ * negative
+ */
+ public static <K extends Object, V extends Object> LinkedHashMultimap<K, V> create(
+ int expectedKeys, int expectedValuesPerKey) {
+ return new LinkedHashMultimap<>(
+ Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey));
+ }
+
+ /**
+ * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
+ * key-value mapping appears multiple times in the input multimap, it only appears once in the
+ * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
+ * as the input multimap, except for excluding duplicate mappings.
+ *
+ * @param multimap the multimap whose contents are copied to this multimap
+ */
+ public static <K extends Object, V extends Object> LinkedHashMultimap<K, V> create(
+ Multimap<? extends K, ? extends V> multimap) {
+ LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
+ result.putAll(multimap);
+ return result;
+ }
+
+ private interface ValueSetLink<K extends Object, V extends Object> {
+ ValueSetLink<K, V> getPredecessorInValueSet();
+
+ ValueSetLink<K, V> getSuccessorInValueSet();
+
+ void setPredecessorInValueSet(ValueSetLink<K, V> entry);
+
+ void setSuccessorInValueSet(ValueSetLink<K, V> entry);
+ }
+
+ private static <K extends Object, V extends Object> void succeedsInValueSet(
+ ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
+ pred.setSuccessorInValueSet(succ);
+ succ.setPredecessorInValueSet(pred);
+ }
+
+ private static <K extends Object, V extends Object> void succeedsInMultimap(
+ ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
+ pred.setSuccessorInMultimap(succ);
+ succ.setPredecessorInMultimap(pred);
+ }
+
+ private static <K extends Object, V extends Object> void deleteFromValueSet(
+ ValueSetLink<K, V> entry) {
+ succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
+ }
+
+ private static <K extends Object, V extends Object> void deleteFromMultimap(
+ ValueEntry<K, V> entry) {
+ succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
+ }
+
+ /**
+ * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
+ * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
+ * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
+ * whole.
+ */
+ static final class ValueEntry<K extends Object, V extends Object> extends ImmutableEntry<K, V>
+ implements ValueSetLink<K, V> {
+ final int smearedValueHash;
+
+ @CheckForNull ValueEntry<K, V> nextInValueBucket;
+ /*
+ * The *InValueSet and *InMultimap fields below are null after construction, but we almost
+ * always call succeedsIn*() to initialize them immediately thereafter.
+ *
+ * The exception is the *InValueSet fields of multimapHeaderEntry, which are never set. (That
+ * works out fine as long as we continue to be careful not to try to delete them or iterate
+ * past them.)
+ *
+ * We could consider "lying" and omitting @CheckNotNull from all these fields. Normally, I'm not
+ * a fan of that: What if we someday implement (presumably to be enabled during tests only)
+ * bytecode rewriting that checks for any null value that passes through an API with a
+ * known-non-null type? But that particular problem might not arise here, since we're not
+ * actually reading from the fields in any case in which they might be null (as proven by the
+ * requireNonNull checks below). Plus, we're *already* lying here, since newHeader passes a null
+ * key and value, which we pass to the superconstructor, even though the key and value type for
+ * a given entry might not include null. The right fix for the header problems is probably to
+ * define a separate MultimapLink interface with a separate "header" implementation, which
+ * hopefully could avoid implementing Entry or ValueSetLink at all. (But note that that approach
+ * requires us to define extra classes -- unfortunate under Android.) *Then* we could consider
+ * lying about the fields below on the grounds that we always initialize them just after the
+ * constructor -- an example of the kind of lying that our hypothetical bytecode rewriter would
+ * already have to deal with, thanks to DI frameworks that perform field and method injection,
+ * frameworks like Android that define post-construct hooks like Activity.onCreate, etc.
+ */
+
+ @CheckForNull ValueSetLink<K, V> predecessorInValueSet;
+ @CheckForNull ValueSetLink<K, V> successorInValueSet;
+
+ @CheckForNull ValueEntry<K, V> predecessorInMultimap;
+ @CheckForNull ValueEntry<K, V> successorInMultimap;
+
+ ValueEntry(
+ K key, V value, int smearedValueHash, @CheckForNull ValueEntry<K, V> nextInValueBucket) {
+ super(key, value);
+ this.smearedValueHash = smearedValueHash;
+ this.nextInValueBucket = nextInValueBucket;
+ }
+
+ @SuppressWarnings("nullness") // see the comment on the class fields, especially about newHeader
+ static <K extends Object, V extends Object> ValueEntry<K, V> newHeader() {
+ return new ValueEntry<>(null, null, 0, null);
+ }
+
+ boolean matchesValue(@CheckForNull Object v, int smearedVHash) {
+ return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
+ }
+
+ @Override
+ public ValueSetLink<K, V> getPredecessorInValueSet() {
+ return requireNonNull(predecessorInValueSet); // see the comment on the class fields
+ }
+
+ @Override
+ public ValueSetLink<K, V> getSuccessorInValueSet() {
+ return requireNonNull(successorInValueSet); // see the comment on the class fields
+ }
+
+ @Override
+ public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
+ predecessorInValueSet = entry;
+ }
+
+ @Override
+ public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
+ successorInValueSet = entry;
+ }
+
+ public ValueEntry<K, V> getPredecessorInMultimap() {
+ return requireNonNull(predecessorInMultimap); // see the comment on the class fields
+ }
+
+ public ValueEntry<K, V> getSuccessorInMultimap() {
+ return requireNonNull(successorInMultimap); // see the comment on the class fields
+ }
+
+ public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
+ this.successorInMultimap = multimapSuccessor;
+ }
+
+ public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
+ this.predecessorInMultimap = multimapPredecessor;
+ }
+ }
+
+ private static final int DEFAULT_KEY_CAPACITY = 16;
+ private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
+ static final double VALUE_SET_LOAD_FACTOR = 1.0;
+
+ transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
+ private transient ValueEntry<K, V> multimapHeaderEntry;
+
+ private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
+ super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity));
+ checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
+
+ this.valueSetCapacity = valueSetCapacity;
+ this.multimapHeaderEntry = ValueEntry.newHeader();
+ succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
+ *
+ * @return a new {@code LinkedHashSet} containing a collection of values for one key
+ */
+ @Override
+ Set<V> createCollection() {
+ return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
+ * key-value pairs are added to the multimap.
+ *
+ * @param key key to associate with values in the collection
+ * @return a new decorated set containing a collection of values for one key
+ */
+ @Override
+ Collection<V> createCollection(K key) {
+ return new ValueSet(key, valueSetCapacity);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
+ * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
+ * the {@link #entries()} and {@link #values()} iteration orderings.
+ */
+ @Override
+ public Set<V> replaceValues(K key, Iterable<? extends V> values) {
+ return super.replaceValues(key, values);
+ }
+
+ /**
+ * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
+ * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
+ * operations.
+ *
+ * <p>The iterator generated by the returned set traverses the entries in the order they were
+ * added to the multimap.
+ *
+ * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the
+ * time the entry is returned by a method call to the collection or its iterator.
+ */
+ @Override
+ public Set<Entry<K, V>> entries() {
+ return super.entries();
+ }
+
+ /**
+ * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
+ * key set contains a key if and only if this multimap maps that key to at least one value.
+ *
+ * <p>The iterator generated by the returned set traverses the keys in the order they were first
+ * added to the multimap.
+ *
+ * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
+ * <i>adding</i> to the returned set is not possible.
+ */
+ @Override
+ public Set<K> keySet() {
+ return super.keySet();
+ }
+
+ /**
+ * Returns a collection of all values in the multimap. Changes to the returned collection will
+ * update the underlying multimap, and vice versa.
+ *
+ * <p>The iterator generated by the returned collection traverses the values in the order they
+ * were added to the multimap.
+ */
+ @Override
+ public Collection<V> values() {
+ return super.values();
+ }
+
+ final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
+ /*
+ * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
+ * consumption.
+ */
+
+ private final K key;
+ ValueEntry<K, V>[] hashTable;
+ private int size = 0;
+ private int modCount = 0;
+
+ // We use the set object itself as the end of the linked list, avoiding an unnecessary
+ // entry object per key.
+ private ValueSetLink<K, V> firstEntry;
+ private ValueSetLink<K, V> lastEntry;
+
+ ValueSet(K key, int expectedValues) {
+ this.key = key;
+ this.firstEntry = this;
+ this.lastEntry = this;
+ // Round expected values up to a power of 2 to get the table size.
+ int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
+
+ @SuppressWarnings({"rawtypes", "unchecked"})
+ ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
+ this.hashTable = hashTable;
+ }
+
+ private int mask() {
+ return hashTable.length - 1;
+ }
+
+ @Override
+ public ValueSetLink<K, V> getPredecessorInValueSet() {
+ return lastEntry;
+ }
+
+ @Override
+ public ValueSetLink<K, V> getSuccessorInValueSet() {
+ return firstEntry;
+ }
+
+ @Override
+ public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
+ lastEntry = entry;
+ }
+
+ @Override
+ public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
+ firstEntry = entry;
+ }
+
+ @Override
+ public Iterator<V> iterator() {
+ return new Iterator<V>() {
+ ValueSetLink<K, V> nextEntry = firstEntry;
+ @CheckForNull ValueEntry<K, V> toRemove;
+ int expectedModCount = modCount;
+
+ private void checkForComodification() {
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ checkForComodification();
+ return nextEntry != ValueSet.this;
+ }
+
+ @Override
+ public V next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
+ V result = entry.getValue();
+ toRemove = entry;
+ nextEntry = entry.getSuccessorInValueSet();
+ return result;
+ }
+
+ @Override
+ public void remove() {
+ checkForComodification();
+ checkState(toRemove != null, "no calls to next() since the last call to remove()");
+ ValueSet.this.remove(toRemove.getValue());
+ expectedModCount = modCount;
+ toRemove = null;
+ }
+ };
+ }
+
+ @Override
+ public void forEach(Consumer<? super V> action) {
+ checkNotNull(action);
+ for (ValueSetLink<K, V> entry = firstEntry;
+ entry != ValueSet.this;
+ entry = entry.getSuccessorInValueSet()) {
+ action.accept(((ValueEntry<K, V>) entry).getValue());
+ }
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public boolean contains(@CheckForNull Object o) {
+ int smearedHash = Hashing.smearedHash(o);
+ for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
+ entry != null;
+ entry = entry.nextInValueBucket) {
+ if (entry.matchesValue(o, smearedHash)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public boolean add(V value) {
+ int smearedHash = Hashing.smearedHash(value);
+ int bucket = smearedHash & mask();
+ ValueEntry<K, V> rowHead = hashTable[bucket];
+ for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
+ if (entry.matchesValue(value, smearedHash)) {
+ return false;
+ }
+ }
+
+ ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead);
+ succeedsInValueSet(lastEntry, newEntry);
+ succeedsInValueSet(newEntry, this);
+ succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
+ succeedsInMultimap(newEntry, multimapHeaderEntry);
+ hashTable[bucket] = newEntry;
+ size++;
+ modCount++;
+ rehashIfNecessary();
+ return true;
+ }
+
+ private void rehashIfNecessary() {
+ if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
+ @SuppressWarnings("unchecked")
+ ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
+ this.hashTable = hashTable;
+ int mask = hashTable.length - 1;
+ for (ValueSetLink<K, V> entry = firstEntry;
+ entry != this;
+ entry = entry.getSuccessorInValueSet()) {
+ ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
+ int bucket = valueEntry.smearedValueHash & mask;
+ valueEntry.nextInValueBucket = hashTable[bucket];
+ hashTable[bucket] = valueEntry;
+ }
+ }
+ }
+
+ @Override
+ public boolean remove(@CheckForNull Object o) {
+ int smearedHash = Hashing.smearedHash(o);
+ int bucket = smearedHash & mask();
+ ValueEntry<K, V> prev = null;
+ for (ValueEntry<K, V> entry = hashTable[bucket];
+ entry != null;
+ prev = entry, entry = entry.nextInValueBucket) {
+ if (entry.matchesValue(o, smearedHash)) {
+ if (prev == null) {
+ // first entry in the bucket
+ hashTable[bucket] = entry.nextInValueBucket;
+ } else {
+ prev.nextInValueBucket = entry.nextInValueBucket;
+ }
+ deleteFromValueSet(entry);
+ deleteFromMultimap(entry);
+ size--;
+ modCount++;
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public void clear() {
+ Arrays.fill(hashTable, null);
+ size = 0;
+ for (ValueSetLink<K, V> entry = firstEntry;
+ entry != this;
+ entry = entry.getSuccessorInValueSet()) {
+ ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
+ deleteFromMultimap(valueEntry);
+ }
+ succeedsInValueSet(this, this);
+ modCount++;
+ }
+ }
+
+ @Override
+ Iterator<Entry<K, V>> entryIterator() {
+ return new Iterator<Entry<K, V>>() {
+ ValueEntry<K, V> nextEntry = multimapHeaderEntry.getSuccessorInMultimap();
+ @CheckForNull ValueEntry<K, V> toRemove;
+
+ @Override
+ public boolean hasNext() {
+ return nextEntry != multimapHeaderEntry;
+ }
+
+ @Override
+ public Entry<K, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ ValueEntry<K, V> result = nextEntry;
+ toRemove = result;
+ nextEntry = nextEntry.getSuccessorInMultimap();
+ return result;
+ }
+
+ @Override
+ public void remove() {
+ checkState(toRemove != null, "no calls to next() since the last call to remove()");
+ LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
+ toRemove = null;
+ }
+ };
+ }
+
+ @Override
+ Spliterator<Entry<K, V>> entrySpliterator() {
+ return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED);
+ }
+
+ @Override
+ Iterator<V> valueIterator() {
+ return Maps.valueIterator(entryIterator());
+ }
+
+ @Override
+ Spliterator<V> valueSpliterator() {
+ return CollectSpliterators.map(entrySpliterator(), Entry::getValue);
+ }
+
+ @Override
+ public void clear() {
+ super.clear();
+ succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
+ }
+
+ /**
+ * @serialData the expected values per key, the number of distinct keys, the number of entries,
+ * and the entries in order
+ */
+ private void writeObject(ObjectOutputStream stream) throws IOException {
+ stream.defaultWriteObject();
+ stream.writeInt(keySet().size());
+ for (K key : keySet()) {
+ stream.writeObject(key);
+ }
+ stream.writeInt(size());
+ for (Entry<K, V> entry : entries()) {
+ stream.writeObject(entry.getKey());
+ stream.writeObject(entry.getValue());
+ }
+ }
+
+ private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
+ stream.defaultReadObject();
+ multimapHeaderEntry = ValueEntry.newHeader();
+ succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
+ valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
+ int distinctKeys = stream.readInt();
+ Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
+ for (int i = 0; i < distinctKeys; i++) {
+ @SuppressWarnings("unchecked")
+ K key = (K) stream.readObject();
+ map.put(key, createCollection(key));
+ }
+ int entries = stream.readInt();
+ for (int i = 0; i < entries; i++) {
+ @SuppressWarnings("unchecked")
+ K key = (K) stream.readObject();
+ @SuppressWarnings("unchecked")
+ V value = (V) stream.readObject();
+ /*
+ * requireNonNull is safe for a properly serialized multimap: We've already inserted a
+ * collection for each key that we expect.
+ */
+ requireNonNull(map.get(key)).add(value);
+ }
+ setMap(map);
+ }
+
+ private static final long serialVersionUID = 1;
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimapGwtSerializationDependencies.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimapGwtSerializationDependencies.java
new file mode 100644
index 0000000..994ff54
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/LinkedHashMultimapGwtSerializationDependencies.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import java.util.Collection;
+import java.util.Map;
+
+/**
+ * A dummy superclass to support GWT serialization of the element types of a {@link
+ * LinkedHashMultimap}. The GWT supersource for this class contains a field for each type.
+ *
+ * <p>For details about this hack, see {@code GwtSerializationDependencies}, which takes the same
+ * approach but with a subclass rather than a superclass.
+ *
+ * <p>TODO(cpovirk): Consider applying this subclass approach to our other types.
+ */
+abstract class LinkedHashMultimapGwtSerializationDependencies<K, V>
+ extends AbstractSetMultimap<K, V> {
+ LinkedHashMultimapGwtSerializationDependencies(Map<K, Collection<V>> map) {
+ super(map);
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Lists.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Lists.java
index 982fbfd..f8355c1 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Lists.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Lists.java
@@ -32,12 +32,10 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;
-import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.Predicate;
import static com.google.common.base.Preconditions.checkArgument;
@@ -165,96 +163,6 @@
}
/**
- * Creates an {@code ArrayList} instance to hold {@code estimatedSize} elements, <i>plus</i> an
- * unspecified amount of padding; you almost certainly mean to call {@link
- * #newArrayListWithCapacity} (see that method for further advice on usage).
- *
- * <p><b>Note:</b> This method will soon be deprecated. Even in the rare case that you do want
- * some amount of padding, it's best if you choose your desired amount explicitly.
- *
- * @param estimatedSize an estimate of the eventual {@link List#size()} of the new list
- * @return a new, empty {@code ArrayList}, sized appropriately to hold the estimated number of
- * elements
- * @throws IllegalArgumentException if {@code estimatedSize} is negative
- */
- public static <E extends Object> ArrayList<E> newArrayListWithExpectedSize(int estimatedSize) {
- return new ArrayList<>(computeArrayListCapacity(estimatedSize));
- }
-
- // LinkedList
-
- /**
- * Creates a <i>mutable</i>, empty {@code LinkedList} instance (for Java 6 and earlier).
- *
- * <p><b>Note:</b> if you won't be adding any elements to the list, use {@link ImmutableList#of()}
- * instead.
- *
- * <p><b>Performance note:</b> {@link ArrayList} and {@link java.util.ArrayDeque} consistently
- * outperform {@code LinkedList} except in certain rare and specific situations. Unless you have
- * spent a lot of time benchmarking your specific needs, use one of those instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code LinkedList} {@linkplain LinkedList#LinkedList() constructor} directly, taking
- * advantage of <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- */
- public static <E extends Object> LinkedList<E> newLinkedList() {
- return new LinkedList<>();
- }
-
- /**
- * Creates a <i>mutable</i> {@code LinkedList} instance containing the given elements; a very thin
- * shortcut for creating an empty list then calling {@link Iterables#addAll}.
- *
- * <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link
- * ImmutableList#copyOf(Iterable)} instead. (Or, change {@code elements} to be a {@link
- * FluentIterable} and call {@code elements.toList()}.)
- *
- * <p><b>Performance note:</b> {@link ArrayList} and {@link java.util.ArrayDeque} consistently
- * outperform {@code LinkedList} except in certain rare and specific situations. Unless you have
- * spent a lot of time benchmarking your specific needs, use one of those instead.
- *
- * <p><b>Note:</b> if {@code elements} is a {@link Collection}, you don't need this method. Use
- * the {@code LinkedList} {@linkplain LinkedList#LinkedList(Collection) constructor} directly,
- * taking advantage of <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- */
- public static <E extends Object> LinkedList<E> newLinkedList(Iterable<? extends E> elements) {
- LinkedList<E> list = newLinkedList();
- Iterables.addAll(list, elements);
- return list;
- }
-
- /**
- * Creates an empty {@code CopyOnWriteArrayList} instance.
- *
- * <p><b>Note:</b> if you need an immutable empty {@link List}, use {@link Collections#emptyList}
- * instead.
- *
- * @return a new, empty {@code CopyOnWriteArrayList}
- * @since 12.0
- */
- public static <E extends Object> CopyOnWriteArrayList<E> newCopyOnWriteArrayList() {
- return new CopyOnWriteArrayList<>();
- }
-
- /**
- * Creates a {@code CopyOnWriteArrayList} instance containing the given elements.
- *
- * @param elements the elements that the list should contain, in order
- * @return a new {@code CopyOnWriteArrayList} containing those elements
- * @since 12.0
- */
- public static <E extends Object> CopyOnWriteArrayList<E> newCopyOnWriteArrayList(
- Iterable<? extends E> elements) {
- // We copy elements to an ArrayList first, rather than incurring the
- // quadratic cost of adding them to the COWAL directly.
- Collection<? extends E> elementsCollection =
- (elements instanceof Collection)
- ? (Collection<? extends E>) elements
- : newArrayList(elements);
- return new CopyOnWriteArrayList<>(elementsCollection);
- }
-
- /**
* Returns an unmodifiable list containing the specified first element and backed by the specified
* array of additional elements. Changes to the {@code rest} array will be reflected in the
* returned list. Unlike {@link Arrays#asList}, the returned list is unmodifiable.
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Maps.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Maps.java
index 7b034e6..bb836bb 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Maps.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Maps.java
@@ -34,7 +34,6 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
-import java.util.EnumMap;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.IdentityHashMap;
@@ -62,10 +61,8 @@
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Predicates.compose;
-import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;
import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
-import static java.util.Collections.singletonMap;
import static java.util.Objects.requireNonNull;
/**
@@ -133,65 +130,6 @@
}
/**
- * Returns an immutable map instance containing the given entries. Internally, the returned map
- * will be backed by an {@link EnumMap}.
- *
- * <p>The iteration order of the returned map follows the enum's iteration order, not the order in
- * which the elements appear in the given map.
- *
- * @param map the map to make an immutable copy of
- * @return an immutable map containing those entries
- * @since 14.0
- */
- public static <K extends Enum<K>, V> ImmutableMap<K, V> immutableEnumMap(
- Map<K, ? extends V> map) {
- if (map instanceof ImmutableEnumMap) {
- @SuppressWarnings("unchecked") // safe covariant cast
- ImmutableEnumMap<K, V> result = (ImmutableEnumMap<K, V>) map;
- return result;
- }
- Iterator<? extends Entry<K, ? extends V>> entryItr = map.entrySet().iterator();
- if (!entryItr.hasNext()) {
- return ImmutableMap.of();
- }
- Entry<K, ? extends V> entry1 = entryItr.next();
- K key1 = entry1.getKey();
- V value1 = entry1.getValue();
- checkEntryNotNull(key1, value1);
- // Do something that works for j2cl, where we can't call getDeclaredClass():
- EnumMap<K, V> enumMap = new EnumMap<>(singletonMap(key1, value1));
- while (entryItr.hasNext()) {
- Entry<K, ? extends V> entry = entryItr.next();
- K key = entry.getKey();
- V value = entry.getValue();
- checkEntryNotNull(key, value);
- enumMap.put(key, value);
- }
- return ImmutableEnumMap.asImmutable(enumMap);
- }
-
- /**
- * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
- * and values are the result of applying the provided mapping functions to the input elements. The
- * resulting implementation is specialized for enum key types. The returned map and its views will
- * iterate over keys in their enum definition order, not encounter order.
- *
- * <p>If the mapped keys contain duplicates, an {@code IllegalArgumentException} is thrown when
- * the collection operation is performed. (This differs from the {@code Collector} returned by
- * {@link java.util.stream.Collectors#toMap(java.util.function.Function,
- * java.util.function.Function) Collectors.toMap(Function, Function)}, which throws an {@code
- * IllegalStateException}.)
- *
- * @since 21.0
- */
- public static <T extends Object, K extends Enum<K>, V>
- Collector<T, ?, ImmutableMap<K, V>> toImmutableEnumMap(
- java.util.function.Function<? super T, ? extends K> keyFunction,
- java.util.function.Function<? super T, ? extends V> valueFunction) {
- return CollectCollectors.toImmutableEnumMap(keyFunction, valueFunction);
- }
-
- /**
* Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
* and values are the result of applying the provided mapping functions to the input elements. The
* resulting implementation is specialized for enum key types. The returned map and its views will
@@ -228,25 +166,6 @@
}
/**
- * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as the specified map.
- *
- * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#copyOf(Map)} instead.
- *
- * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link #newEnumMap} instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code HashMap} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- *
- * @param map the mappings to be placed in the new map
- * @return a new {@code HashMap} initialized with the mappings from {@code map}
- */
- public static <K extends Object, V extends Object> HashMap<K, V> newHashMap(
- Map<? extends K, ? extends V> map) {
- return new HashMap<>(map);
- }
-
- /**
* Creates a {@code HashMap} instance, with a high enough "initial capacity" that it <i>should</i>
* hold {@code expectedSize} elements without growth. This behavior cannot be broadly guaranteed,
* but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed that the method
@@ -305,24 +224,6 @@
}
/**
- * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance with the same
- * mappings as the specified map.
- *
- * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#copyOf(Map)} instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code LinkedHashMap} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- *
- * @param map the mappings to be placed in the new map
- * @return a new, {@code LinkedHashMap} initialized with the mappings from {@code map}
- */
- public static <K extends Object, V extends Object> LinkedHashMap<K, V> newLinkedHashMap(
- Map<? extends K, ? extends V> map) {
- return new LinkedHashMap<>(map);
- }
-
- /**
* Creates a {@code LinkedHashMap} instance, with a high enough "initial capacity" that it
* <i>should</i> hold {@code expectedSize} elements without growth. This behavior cannot be
* broadly guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed
@@ -349,43 +250,6 @@
}
/**
- * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural ordering of its
- * elements.
- *
- * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedMap#of()} instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code TreeMap} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- *
- * @return a new, empty {@code TreeMap}
- */
- public static <K extends Comparable, V extends Object> TreeMap<K, V> newTreeMap() {
- return new TreeMap<>();
- }
-
- /**
- * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as the specified map
- * and using the same ordering as the specified map.
- *
- * <p><b>Note:</b> if mutability is not required, use {@link
- * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code TreeMap} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- *
- * @param map the sorted map whose mappings are to be placed in the new map and whose comparator
- * is to be used to sort the new map
- * @return a new {@code TreeMap} initialized with the mappings from {@code map} and using the
- * comparator of {@code map}
- */
- public static <K extends Object, V extends Object> TreeMap<K, V> newTreeMap(
- SortedMap<K, ? extends V> map) {
- return new TreeMap<>(map);
- }
-
- /**
* Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given comparator.
*
* <p><b>Note:</b> if mutability is not required, use {@code
@@ -409,33 +273,6 @@
}
/**
- * Creates an {@code EnumMap} instance.
- *
- * @param type the key type for this map
- * @return a new, empty {@code EnumMap}
- */
- public static <K extends Enum<K>, V extends Object> EnumMap<K, V> newEnumMap(Class<K> type) {
- return new EnumMap<>(checkNotNull(type));
- }
-
- /**
- * Creates an {@code EnumMap} with the same mappings as the specified map.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code EnumMap} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
- *
- * @param map the map from which to initialize this {@code EnumMap}
- * @return a new {@code EnumMap} initialized with the mappings from {@code map}
- * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap} instance and contains
- * no mappings
- */
- public static <K extends Enum<K>, V extends Object> EnumMap<K, V> newEnumMap(
- Map<K, ? extends V> map) {
- return new EnumMap<>(map);
- }
-
- /**
* Creates an {@code IdentityHashMap} instance.
*
* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/MoreCollectors.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/MoreCollectors.java
new file mode 100644
index 0000000..6a78296
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/MoreCollectors.java
@@ -0,0 +1,170 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import javax.annotation.CheckForNull;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Optional;
+import java.util.stream.Collector;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static java.util.Collections.emptyList;
+
+/**
+ * Collectors not present in {@code java.util.stream.Collectors} that are not otherwise associated
+ * with a {@code com.google.common} type.
+ *
+ * @author Louis Wasserman
+ * @since 21.0
+ */
+public final class MoreCollectors {
+
+ /*
+ * TODO(lowasser): figure out if we can convert this to a concurrent AtomicReference-based
+ * collector without breaking j2cl?
+ */
+ private static final Collector<Object, ?, Optional<Object>> TO_OPTIONAL =
+ Collector.of(
+ ToOptionalState::new,
+ ToOptionalState::add,
+ ToOptionalState::combine,
+ ToOptionalState::getOptional,
+ Collector.Characteristics.UNORDERED);
+
+ /**
+ * A collector that converts a stream of zero or one elements to an {@code Optional}.
+ *
+ * @throws IllegalArgumentException if the stream consists of two or more elements.
+ * @throws NullPointerException if any element in the stream is {@code null}.
+ * @return {@code Optional.of(onlyElement)} if the stream has exactly one element (must not be
+ * {@code null}) and returns {@code Optional.empty()} if it has none.
+ */
+ @SuppressWarnings("unchecked")
+ public static <T> Collector<T, ?, Optional<T>> toOptional() {
+ return (Collector) TO_OPTIONAL;
+ }
+
+ private static final Object NULL_PLACEHOLDER = new Object();
+
+ private static final Collector<Object, ?, Object> ONLY_ELEMENT =
+ Collector.<Object, ToOptionalState, Object>of(
+ ToOptionalState::new,
+ (state, o) -> state.add((o == null) ? NULL_PLACEHOLDER : o),
+ ToOptionalState::combine,
+ state -> {
+ Object result = state.getElement();
+ return (result == NULL_PLACEHOLDER) ? null : result;
+ },
+ Collector.Characteristics.UNORDERED);
+
+ /**
+ * A collector that takes a stream containing exactly one element and returns that element. The
+ * returned collector throws an {@code IllegalArgumentException} if the stream consists of two or
+ * more elements, and a {@code NoSuchElementException} if the stream is empty.
+ */
+ @SuppressWarnings("unchecked")
+ public static <T extends Object> Collector<T, ?, T> onlyElement() {
+ return (Collector) ONLY_ELEMENT;
+ }
+
+ /**
+ * This atrocity is here to let us report several of the elements in the stream if there were more
+ * than one, not just two.
+ */
+ private static final class ToOptionalState {
+ static final int MAX_EXTRAS = 4;
+
+ @CheckForNull Object element;
+ List<Object> extras;
+
+ ToOptionalState() {
+ element = null;
+ extras = emptyList();
+ }
+
+ IllegalArgumentException multiples(boolean overflow) {
+ StringBuilder sb =
+ new StringBuilder().append("expected one element but was: <").append(element);
+ for (Object o : extras) {
+ sb.append(", ").append(o);
+ }
+ if (overflow) {
+ sb.append(", ...");
+ }
+ sb.append('>');
+ throw new IllegalArgumentException(sb.toString());
+ }
+
+ void add(Object o) {
+ checkNotNull(o);
+ if (element == null) {
+ this.element = o;
+ } else if (extras.isEmpty()) {
+ // Replace immutable empty list with mutable list.
+ extras = new ArrayList<>(MAX_EXTRAS);
+ extras.add(o);
+ } else if (extras.size() < MAX_EXTRAS) {
+ extras.add(o);
+ } else {
+ throw multiples(true);
+ }
+ }
+
+ ToOptionalState combine(ToOptionalState other) {
+ if (element == null) {
+ return other;
+ } else if (other.element == null) {
+ return this;
+ } else {
+ if (extras.isEmpty()) {
+ // Replace immutable empty list with mutable list.
+ extras = new ArrayList<>();
+ }
+ extras.add(other.element);
+ extras.addAll(other.extras);
+ if (extras.size() > MAX_EXTRAS) {
+ extras.subList(MAX_EXTRAS, extras.size()).clear();
+ throw multiples(true);
+ }
+ return this;
+ }
+ }
+
+ Optional<Object> getOptional() {
+ if (extras.isEmpty()) {
+ return Optional.ofNullable(element);
+ } else {
+ throw multiples(false);
+ }
+ }
+
+ Object getElement() {
+ if (element == null) {
+ throw new NoSuchElementException();
+ } else if (extras.isEmpty()) {
+ return element;
+ } else {
+ throw multiples(false);
+ }
+ }
+ }
+
+ private MoreCollectors() {}
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Queues.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Queues.java
index 384e42d..8f17611 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Queues.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Queues.java
@@ -14,21 +14,11 @@
package com.google.common.collect;
-import com.google.common.base.Preconditions;
-
import java.util.ArrayDeque;
-import java.util.Collection;
import java.util.Deque;
-import java.util.PriorityQueue;
import java.util.Queue;
-import java.util.concurrent.ArrayBlockingQueue;
-import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;
-import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
-import java.util.concurrent.PriorityBlockingQueue;
-import java.util.concurrent.SynchronousQueue;
-import java.util.concurrent.TimeUnit;
/**
* Static utility methods pertaining to {@link Queue} and {@link Deque} instances. Also see this
@@ -40,16 +30,6 @@
public final class Queues {
private Queues() {}
- // ArrayBlockingQueue
-
- /**
- * Creates an empty {@code ArrayBlockingQueue} with the given (fixed) capacity and nonfair access
- * policy.
- */
- public static <E> ArrayBlockingQueue<E> newArrayBlockingQueue(int capacity) {
- return new ArrayBlockingQueue<E>(capacity);
- }
-
// ArrayDeque
/**
@@ -61,21 +41,6 @@
return new ArrayDeque<E>();
}
- /**
- * Creates an {@code ArrayDeque} containing the elements of the specified iterable, in the order
- * they are returned by the iterable's iterator.
- *
- * @since 12.0
- */
- public static <E> ArrayDeque<E> newArrayDeque(Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new ArrayDeque<E>((Collection<? extends E>) elements);
- }
- ArrayDeque<E> deque = new ArrayDeque<E>();
- Iterables.addAll(deque, elements);
- return deque;
- }
-
// ConcurrentLinkedQueue
/** Creates an empty {@code ConcurrentLinkedQueue}. */
@@ -83,365 +48,10 @@
return new ConcurrentLinkedQueue<E>();
}
- /**
- * Creates a {@code ConcurrentLinkedQueue} containing the elements of the specified iterable, in
- * the order they are returned by the iterable's iterator.
- */
- public static <E> ConcurrentLinkedQueue<E> newConcurrentLinkedQueue(
- Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new ConcurrentLinkedQueue<E>((Collection<? extends E>) elements);
- }
- ConcurrentLinkedQueue<E> queue = new ConcurrentLinkedQueue<E>();
- Iterables.addAll(queue, elements);
- return queue;
- }
-
- // LinkedBlockingDeque
-
- /**
- * Creates an empty {@code LinkedBlockingDeque} with a capacity of {@link Integer#MAX_VALUE}.
- *
- * @since 12.0
- */
- public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque() {
- return new LinkedBlockingDeque<E>();
- }
-
- /**
- * Creates an empty {@code LinkedBlockingDeque} with the given (fixed) capacity.
- *
- * @throws IllegalArgumentException if {@code capacity} is less than 1
- * @since 12.0
- */
- public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque(int capacity) {
- return new LinkedBlockingDeque<E>(capacity);
- }
-
- /**
- * Creates a {@code LinkedBlockingDeque} with a capacity of {@link Integer#MAX_VALUE}, containing
- * the elements of the specified iterable, in the order they are returned by the iterable's
- * iterator.
- *
- * @since 12.0
- */
- public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque(Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new LinkedBlockingDeque<E>((Collection<? extends E>) elements);
- }
- LinkedBlockingDeque<E> deque = new LinkedBlockingDeque<E>();
- Iterables.addAll(deque, elements);
- return deque;
- }
-
// LinkedBlockingQueue
/** Creates an empty {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}. */
public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue() {
return new LinkedBlockingQueue<E>();
}
-
- /**
- * Creates an empty {@code LinkedBlockingQueue} with the given (fixed) capacity.
- *
- * @throws IllegalArgumentException if {@code capacity} is less than 1
- */
- public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue(int capacity) {
- return new LinkedBlockingQueue<E>(capacity);
- }
-
- /**
- * Creates a {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}, containing
- * the elements of the specified iterable, in the order they are returned by the iterable's
- * iterator.
- *
- * @param elements the elements that the queue should contain, in order
- * @return a new {@code LinkedBlockingQueue} containing those elements
- */
- public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue(Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new LinkedBlockingQueue<E>((Collection<? extends E>) elements);
- }
- LinkedBlockingQueue<E> queue = new LinkedBlockingQueue<E>();
- Iterables.addAll(queue, elements);
- return queue;
- }
-
- // LinkedList: see {@link com.google.common.collect.Lists}
-
- // PriorityBlockingQueue
-
- /**
- * Creates an empty {@code PriorityBlockingQueue} with the ordering given by its elements' natural
- * ordering.
- *
- * @since 11.0 (but the bound of {@code E} was changed from {@code Object} to {@code Comparable}
- * in 15.0)
- */
- public static <E extends Comparable> PriorityBlockingQueue<E> newPriorityBlockingQueue() {
- return new PriorityBlockingQueue<E>();
- }
-
- /**
- * Creates a {@code PriorityBlockingQueue} containing the given elements.
- *
- * <p><b>Note:</b> If the specified iterable is a {@code SortedSet} or a {@code PriorityQueue},
- * this priority queue will be ordered according to the same ordering.
- *
- * @since 11.0 (but the bound of {@code E} was changed from {@code Object} to {@code Comparable}
- * in 15.0)
- */
- public static <E extends Comparable> PriorityBlockingQueue<E> newPriorityBlockingQueue(
- Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new PriorityBlockingQueue<E>((Collection<? extends E>) elements);
- }
- PriorityBlockingQueue<E> queue = new PriorityBlockingQueue<E>();
- Iterables.addAll(queue, elements);
- return queue;
- }
-
- // PriorityQueue
-
- /**
- * Creates an empty {@code PriorityQueue} with the ordering given by its elements' natural
- * ordering.
- *
- * @since 11.0 (but the bound of {@code E} was changed from {@code Object} to {@code Comparable}
- * in 15.0)
- */
- public static <E extends Comparable> PriorityQueue<E> newPriorityQueue() {
- return new PriorityQueue<E>();
- }
-
- /**
- * Creates a {@code PriorityQueue} containing the given elements.
- *
- * <p><b>Note:</b> If the specified iterable is a {@code SortedSet} or a {@code PriorityQueue},
- * this priority queue will be ordered according to the same ordering.
- *
- * @since 11.0 (but the bound of {@code E} was changed from {@code Object} to {@code Comparable}
- * in 15.0)
- */
- public static <E extends Comparable> PriorityQueue<E> newPriorityQueue(
- Iterable<? extends E> elements) {
- if (elements instanceof Collection) {
- return new PriorityQueue<E>((Collection<? extends E>) elements);
- }
- PriorityQueue<E> queue = new PriorityQueue<E>();
- Iterables.addAll(queue, elements);
- return queue;
- }
-
- // SynchronousQueue
-
- /** Creates an empty {@code SynchronousQueue} with nonfair access policy. */
- public static <E> SynchronousQueue<E> newSynchronousQueue() {
- return new SynchronousQueue<E>();
- }
-
- /**
- * Drains the queue as {@link BlockingQueue#drainTo(Collection, int)}, but if the requested {@code
- * numElements} elements are not available, it will wait for them up to the specified timeout.
- *
- * @param q the blocking queue to be drained
- * @param buffer where to add the transferred elements
- * @param numElements the number of elements to be waited for
- * @param timeout how long to wait before giving up
- * @return the number of elements transferred
- * @throws InterruptedException if interrupted while waiting
- * @since 28.0
- */
- public static <E> int drain(
- BlockingQueue<E> q, Collection<? super E> buffer, int numElements, java.time.Duration timeout)
- throws InterruptedException {
- // TODO(b/126049426): Consider using saturateToNanos(timeout) instead.
- return drain(q, buffer, numElements, timeout.toNanos(), TimeUnit.NANOSECONDS);
- }
-
- /**
- * Drains the queue as {@link BlockingQueue#drainTo(Collection, int)}, but if the requested {@code
- * numElements} elements are not available, it will wait for them up to the specified timeout.
- *
- * @param q the blocking queue to be drained
- * @param buffer where to add the transferred elements
- * @param numElements the number of elements to be waited for
- * @param timeout how long to wait before giving up, in units of {@code unit}
- * @param unit a {@code TimeUnit} determining how to interpret the timeout parameter
- * @return the number of elements transferred
- * @throws InterruptedException if interrupted while waiting
- */
- @SuppressWarnings("GoodTime") // should accept a java.time.Duration
- public static <E> int drain(
- BlockingQueue<E> q,
- Collection<? super E> buffer,
- int numElements,
- long timeout,
- TimeUnit unit)
- throws InterruptedException {
- Preconditions.checkNotNull(buffer);
- /*
- * This code performs one System.nanoTime() more than necessary, and in return, the time to
- * execute Queue#drainTo is not added *on top* of waiting for the timeout (which could make
- * the timeout arbitrarily inaccurate, given a queue that is slow to drain).
- */
- long deadline = System.nanoTime() + unit.toNanos(timeout);
- int added = 0;
- while (added < numElements) {
- // we could rely solely on #poll, but #drainTo might be more efficient when there are multiple
- // elements already available (e.g. LinkedBlockingQueue#drainTo locks only once)
- added += q.drainTo(buffer, numElements - added);
- if (added < numElements) { // not enough elements immediately available; will have to poll
- E e = q.poll(deadline - System.nanoTime(), TimeUnit.NANOSECONDS);
- if (e == null) {
- break; // we already waited enough, and there are no more elements in sight
- }
- buffer.add(e);
- added++;
- }
- }
- return added;
- }
-
- /**
- * Drains the queue as {@linkplain #drain(BlockingQueue, Collection, int, Duration)}, but with a
- * different behavior in case it is interrupted while waiting. In that case, the operation will
- * continue as usual, and in the end the thread's interruption status will be set (no {@code
- * InterruptedException} is thrown).
- *
- * @param q the blocking queue to be drained
- * @param buffer where to add the transferred elements
- * @param numElements the number of elements to be waited for
- * @param timeout how long to wait before giving up
- * @return the number of elements transferred
- * @since 28.0
- */
- public static <E> int drainUninterruptibly(
- BlockingQueue<E> q,
- Collection<? super E> buffer,
- int numElements,
- java.time.Duration timeout) {
- // TODO(b/126049426): Consider using saturateToNanos(timeout) instead.
- return drainUninterruptibly(q, buffer, numElements, timeout.toNanos(), TimeUnit.NANOSECONDS);
- }
-
- /**
- * Drains the queue as {@linkplain #drain(BlockingQueue, Collection, int, long, TimeUnit)}, but
- * with a different behavior in case it is interrupted while waiting. In that case, the operation
- * will continue as usual, and in the end the thread's interruption status will be set (no {@code
- * InterruptedException} is thrown).
- *
- * @param q the blocking queue to be drained
- * @param buffer where to add the transferred elements
- * @param numElements the number of elements to be waited for
- * @param timeout how long to wait before giving up, in units of {@code unit}
- * @param unit a {@code TimeUnit} determining how to interpret the timeout parameter
- * @return the number of elements transferred
- */
- @SuppressWarnings("GoodTime") // should accept a java.time.Duration
- public static <E> int drainUninterruptibly(
- BlockingQueue<E> q,
- Collection<? super E> buffer,
- int numElements,
- long timeout,
- TimeUnit unit) {
- Preconditions.checkNotNull(buffer);
- long deadline = System.nanoTime() + unit.toNanos(timeout);
- int added = 0;
- boolean interrupted = false;
- try {
- while (added < numElements) {
- // we could rely solely on #poll, but #drainTo might be more efficient when there are
- // multiple elements already available (e.g. LinkedBlockingQueue#drainTo locks only once)
- added += q.drainTo(buffer, numElements - added);
- if (added < numElements) { // not enough elements immediately available; will have to poll
- E e; // written exactly once, by a successful (uninterrupted) invocation of #poll
- while (true) {
- try {
- e = q.poll(deadline - System.nanoTime(), TimeUnit.NANOSECONDS);
- break;
- } catch (InterruptedException ex) {
- interrupted = true; // note interruption and retry
- }
- }
- if (e == null) {
- break; // we already waited enough, and there are no more elements in sight
- }
- buffer.add(e);
- added++;
- }
- }
- } finally {
- if (interrupted) {
- Thread.currentThread().interrupt();
- }
- }
- return added;
- }
-
- /**
- * Returns a synchronized (thread-safe) queue backed by the specified queue. In order to guarantee
- * serial access, it is critical that <b>all</b> access to the backing queue is accomplished
- * through the returned queue.
- *
- * <p>It is imperative that the user manually synchronize on the returned queue when accessing the
- * queue's iterator:
- *
- * <pre>{@code
- * Queue<E> queue = Queues.synchronizedQueue(MinMaxPriorityQueue.<E>create());
- * ...
- * queue.add(element); // Needn't be in synchronized block
- * ...
- * synchronized (queue) { // Must synchronize on queue!
- * Iterator<E> i = queue.iterator(); // Must be in synchronized block
- * while (i.hasNext()) {
- * foo(i.next());
- * }
- * }
- * }</pre>
- *
- * <p>Failure to follow this advice may result in non-deterministic behavior.
- *
- * <p>The returned queue will be serializable if the specified queue is serializable.
- *
- * @param queue the queue to be wrapped in a synchronized view
- * @return a synchronized view of the specified queue
- * @since 14.0
- */
- public static <E extends Object> Queue<E> synchronizedQueue(Queue<E> queue) {
- return Synchronized.queue(queue, null);
- }
-
- /**
- * Returns a synchronized (thread-safe) deque backed by the specified deque. In order to guarantee
- * serial access, it is critical that <b>all</b> access to the backing deque is accomplished
- * through the returned deque.
- *
- * <p>It is imperative that the user manually synchronize on the returned deque when accessing any
- * of the deque's iterators:
- *
- * <pre>{@code
- * Deque<E> deque = Queues.synchronizedDeque(Queues.<E>newArrayDeque());
- * ...
- * deque.add(element); // Needn't be in synchronized block
- * ...
- * synchronized (deque) { // Must synchronize on deque!
- * Iterator<E> i = deque.iterator(); // Must be in synchronized block
- * while (i.hasNext()) {
- * foo(i.next());
- * }
- * }
- * }</pre>
- *
- * <p>Failure to follow this advice may result in non-deterministic behavior.
- *
- * <p>The returned deque will be serializable if the specified deque is serializable.
- *
- * @param deque the deque to be wrapped in a synchronized view
- * @return a synchronized view of the specified deque
- * @since 15.0
- */
- public static <E extends Object> Deque<E> synchronizedDeque(Deque<E> deque) {
- return Synchronized.deque(deque, null);
- }
}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Sets.java b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Sets.java
index 4678eed..894a46d 100644
--- a/iotdb-core/node-commons/src/main/java/com/google/common/collect/Sets.java
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/collect/Sets.java
@@ -42,9 +42,7 @@
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.CopyOnWriteArraySet;
import java.util.function.Consumer;
-import java.util.stream.Collector;
import java.util.stream.Stream;
import static com.google.common.base.Preconditions.checkArgument;
@@ -82,79 +80,6 @@
}
}
- /**
- * Returns an immutable set instance containing the given enum elements. Internally, the returned
- * set will be backed by an {@link EnumSet}.
- *
- * <p>The iteration order of the returned set follows the enum's iteration order, not the order in
- * which the elements are provided to the method.
- *
- * @param anElement one of the elements the set should contain
- * @param otherElements the rest of the elements the set should contain
- * @return an immutable set containing those elements, minus duplicates
- */
- // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
- public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(
- E anElement, E... otherElements) {
- return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements));
- }
-
- /**
- * Returns an immutable set instance containing the given enum elements. Internally, the returned
- * set will be backed by an {@link EnumSet}.
- *
- * <p>The iteration order of the returned set follows the enum's iteration order, not the order in
- * which the elements appear in the given collection.
- *
- * @param elements the elements, all of the same {@code enum} type, that the set should contain
- * @return an immutable set containing those elements, minus duplicates
- */
- // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
- public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(Iterable<E> elements) {
- if (elements instanceof ImmutableEnumSet) {
- return (ImmutableEnumSet<E>) elements;
- } else if (elements instanceof Collection) {
- Collection<E> collection = (Collection<E>) elements;
- if (collection.isEmpty()) {
- return ImmutableSet.of();
- } else {
- return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection));
- }
- } else {
- Iterator<E> itr = elements.iterator();
- if (itr.hasNext()) {
- EnumSet<E> enumSet = EnumSet.of(itr.next());
- Iterators.addAll(enumSet, itr);
- return ImmutableEnumSet.asImmutable(enumSet);
- } else {
- return ImmutableSet.of();
- }
- }
- }
-
- /**
- * Returns a {@code Collector} that accumulates the input elements into a new {@code ImmutableSet}
- * with an implementation specialized for enums. Unlike {@link ImmutableSet#toImmutableSet}, the
- * resulting set will iterate over elements in their enum definition order, not encounter order.
- *
- * @since 21.0
- */
- public static <E extends Enum<E>> Collector<E, ?, ImmutableSet<E>> toImmutableEnumSet() {
- return CollectCollectors.toImmutableEnumSet();
- }
-
- /**
- * Returns a new, <i>mutable</i> {@code EnumSet} instance containing the given elements in their
- * natural order. This method behaves identically to {@link EnumSet#copyOf(Collection)}, but also
- * accepts non-{@code Collection} iterables and empty iterables.
- */
- public static <E extends Enum<E>> EnumSet<E> newEnumSet(
- Iterable<E> iterable, Class<E> elementType) {
- EnumSet<E> set = EnumSet.noneOf(elementType);
- Iterables.addAll(set, iterable);
- return set;
- }
-
// HashSet
/**
@@ -387,111 +312,6 @@
return set;
}
- /**
- * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given comparator.
- *
- * <p><b>Note:</b> if mutability is not required, use {@code
- * ImmutableSortedSet.orderedBy(comparator).build()} instead.
- *
- * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
- * use the {@code TreeSet} constructor directly, taking advantage of <a
- * href="http://goo.gl/iz2Wi">"diamond" syntax</a>. One caveat to this is that the {@code TreeSet}
- * constructor uses a null {@code Comparator} to mean "natural ordering," whereas this factory
- * rejects null. Clean your code accordingly.
- *
- * @param comparator the comparator to use to sort the set
- * @return a new, empty {@code TreeSet}
- * @throws NullPointerException if {@code comparator} is null
- */
- public static <E extends Object> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
- return new TreeSet<E>(checkNotNull(comparator));
- }
-
- /**
- * Creates an empty {@code Set} that uses identity to determine equality. It compares object
- * references, instead of calling {@code equals}, to determine whether a provided object matches
- * an element in the set. For example, {@code contains} returns {@code false} when passed an
- * object that equals a set member, but isn't the same instance. This behavior is similar to the
- * way {@code IdentityHashMap} handles key lookups.
- *
- * @since 8.0
- */
- public static <E extends Object> Set<E> newIdentityHashSet() {
- return Collections.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
- }
-
- /**
- * Creates an empty {@code CopyOnWriteArraySet} instance.
- *
- * <p><b>Note:</b> if you need an immutable empty {@link Set}, use {@link Collections#emptySet}
- * instead.
- *
- * @return a new, empty {@code CopyOnWriteArraySet}
- * @since 12.0
- */
- public static <E extends Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() {
- return new CopyOnWriteArraySet<E>();
- }
-
- /**
- * Creates a {@code CopyOnWriteArraySet} instance containing the given elements.
- *
- * @param elements the elements that the set should contain, in order
- * @return a new {@code CopyOnWriteArraySet} containing those elements
- * @since 12.0
- */
- public static <E extends Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet(
- Iterable<? extends E> elements) {
- // We copy elements to an ArrayList first, rather than incurring the
- // quadratic cost of adding them to the COWAS directly.
- Collection<? extends E> elementsCollection =
- (elements instanceof Collection)
- ? (Collection<? extends E>) elements
- : Lists.newArrayList(elements);
- return new CopyOnWriteArraySet<E>(elementsCollection);
- }
-
- /**
- * Creates an {@code EnumSet} consisting of all enum values that are not in the specified
- * collection. If the collection is an {@link EnumSet}, this method has the same behavior as
- * {@link EnumSet#complementOf}. Otherwise, the specified collection must contain at least one
- * element, in order to determine the element type. If the collection could be empty, use {@link
- * #complementOf(Collection, Class)} instead of this method.
- *
- * @param collection the collection whose complement should be stored in the enum set
- * @return a new, modifiable {@code EnumSet} containing all values of the enum that aren't present
- * in the given collection
- * @throws IllegalArgumentException if {@code collection} is not an {@code EnumSet} instance and
- * contains no elements
- */
- public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection) {
- if (collection instanceof EnumSet) {
- return EnumSet.complementOf((EnumSet<E>) collection);
- }
- checkArgument(
- !collection.isEmpty(), "collection is empty; use the other version of this method");
- Class<E> type = collection.iterator().next().getDeclaringClass();
- return makeComplementByHand(collection, type);
- }
-
- /**
- * Creates an {@code EnumSet} consisting of all enum values that are not in the specified
- * collection. This is equivalent to {@link EnumSet#complementOf}, but can act on any input
- * collection, as long as the elements are of enum type.
- *
- * @param collection the collection whose complement should be stored in the {@code EnumSet}
- * @param type the type of the elements in the set
- * @return a new, modifiable {@code EnumSet} initially containing all the values of the enum not
- * present in the given collection
- */
- public static <E extends Enum<E>> EnumSet<E> complementOf(
- Collection<E> collection, Class<E> type) {
- checkNotNull(collection);
- return (collection instanceof EnumSet)
- ? EnumSet.complementOf((EnumSet<E>) collection)
- : makeComplementByHand(collection, type);
- }
-
private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(
Collection<E> collection, Class<E> type) {
EnumSet<E> result = EnumSet.allOf(type);
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/BaseGraph.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/BaseGraph.java
new file mode 100644
index 0000000..1df5de7
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/BaseGraph.java
@@ -0,0 +1,175 @@
+/*
+ * Copyright (C) 2017 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import java.util.Set;
+
+/**
+ * A non-public interface for the methods shared between {@link Graph} and {@link ValueGraph}.
+ *
+ * @author James Sexton
+ * @param <N> Node parameter type
+ */
+interface BaseGraph<N> extends SuccessorsFunction<N>, PredecessorsFunction<N> {
+ //
+ // Graph-level accessors
+ //
+
+ /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */
+ Set<N> nodes();
+
+ /** Returns all edges in this graph. */
+ Set<EndpointPair<N>> edges();
+
+ //
+ // Graph properties
+ //
+
+ /**
+ * Returns true if the edges in this graph are directed. Directed edges connect a {@link
+ * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
+ * undirected edges connect a pair of nodes to each other.
+ */
+ boolean isDirected();
+
+ /**
+ * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting
+ * to add a self-loop to a graph that does not allow them will throw an {@link
+ * IllegalArgumentException}.
+ */
+ boolean allowsSelfLoops();
+
+ /** Returns the order of iteration for the elements of {@link #nodes()}. */
+ ElementOrder<N> nodeOrder();
+
+ /**
+ * Returns an {@link ElementOrder} that specifies the order of iteration for the elements of
+ * {@link #edges()}, {@link #adjacentNodes(Object)}, {@link #predecessors(Object)}, {@link
+ * #successors(Object)} and {@link #incidentEdges(Object)}.
+ *
+ * @since 29.0
+ */
+ ElementOrder<N> incidentEdgeOrder();
+
+ //
+ // Element-level accessors
+ //
+
+ /**
+ * Returns the nodes which have an incident edge in common with {@code node} in this graph.
+ *
+ * <p>This is equal to the union of {@link #predecessors(Object)} and {@link #successors(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ Set<N> adjacentNodes(N node);
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
+ *
+ * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ Set<N> predecessors(N node);
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s outgoing edges in the direction (if any) of the edge.
+ *
+ * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
+ * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ Set<N> successors(N node);
+
+ /**
+ * Returns the edges in this graph whose endpoints include {@code node}.
+ *
+ * <p>This is equal to the union of incoming and outgoing edges.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ * @since 24.0
+ */
+ Set<EndpointPair<N>> incidentEdges(N node);
+
+ /**
+ * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently,
+ * the number of times an edge touches {@code node}).
+ *
+ * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}.
+ *
+ * <p>For undirected graphs, this is equal to {@code incidentEdges(node).size()} + (number of
+ * self-loops incident to {@code node}).
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ int degree(N node);
+
+ /**
+ * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()})
+ * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ int inDegree(N node);
+
+ /**
+ * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()})
+ * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ int outDegree(N node);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code nodeU} to {@code nodeV}. This is
+ * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}.
+ *
+ * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
+ *
+ * @since 23.0
+ */
+ boolean hasEdgeConnecting(N nodeU, N nodeV);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code endpoints} (in the order, if
+ * any, specified by {@code endpoints}). This is equivalent to {@code
+ * edges().contains(endpoints)}.
+ *
+ * <p>Unlike the other {@code EndpointPair}-accepting methods, this method does not throw if the
+ * endpoints are unordered; it simply returns false. This is for consistency with the behavior of
+ * {@link Collection#contains(Object)} (which does not generally throw if the object cannot be
+ * present in the collection), and the desire to have this method's behavior be compatible with
+ * {@code edges().contains(endpoints)}.
+ *
+ * @since 27.1
+ */
+ boolean hasEdgeConnecting(EndpointPair<N> endpoints);
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/ElementOrder.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/ElementOrder.java
new file mode 100644
index 0000000..370b060
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/ElementOrder.java
@@ -0,0 +1,206 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.base.MoreObjects.ToStringHelper;
+import com.google.common.base.Objects;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Ordering;
+
+import javax.annotation.CheckForNull;
+
+import java.util.Comparator;
+import java.util.Map;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
+/**
+ * Used to represent the order of elements in a data structure that supports different options for
+ * iteration order guarantees.
+ *
+ * <p>Example usage:
+ *
+ * <pre>{@code
+ * MutableGraph<Integer> graph =
+ * GraphBuilder.directed().nodeOrder(ElementOrder.<Integer>natural()).build();
+ * }</pre>
+ *
+ * @author Joshua O'Madadhain
+ * @since 20.0
+ */
+public final class ElementOrder<T> {
+ private final Type type;
+
+ @SuppressWarnings("Immutable") // Hopefully the comparator provided is immutable!
+ @CheckForNull
+ private final Comparator<T> comparator;
+
+ /**
+ * The type of ordering that this object specifies.
+ *
+ * <ul>
+ * <li>UNORDERED: no order is guaranteed.
+ * <li>STABLE: ordering is guaranteed to follow a pattern that won't change between releases.
+ * Some methods may have stronger guarantees.
+ * <li>INSERTION: insertion ordering is guaranteed.
+ * <li>SORTED: ordering according to a supplied comparator is guaranteed.
+ * </ul>
+ */
+ public enum Type {
+ UNORDERED,
+ STABLE,
+ INSERTION,
+ SORTED
+ }
+
+ private ElementOrder(Type type, @CheckForNull Comparator<T> comparator) {
+ this.type = checkNotNull(type);
+ this.comparator = comparator;
+ checkState((type == Type.SORTED) == (comparator != null));
+ }
+
+ /** Returns an instance which specifies that no ordering is guaranteed. */
+ public static <S> ElementOrder<S> unordered() {
+ return new ElementOrder<>(Type.UNORDERED, null);
+ }
+
+ /**
+ * Returns an instance which specifies that ordering is guaranteed to be always be the same across
+ * iterations, and across releases. Some methods may have stronger guarantees.
+ *
+ * <p>This instance is only useful in combination with {@code incidentEdgeOrder}, e.g. {@code
+ * graphBuilder.incidentEdgeOrder(ElementOrder.stable())}.
+ *
+ * <h3>In combination with {@code incidentEdgeOrder}</h3>
+ *
+ * <p>{@code incidentEdgeOrder(ElementOrder.stable())} guarantees the ordering of the returned
+ * collections of the following methods:
+ *
+ * <ul>
+ * <li>For {@link Graph} and {@link ValueGraph}:
+ * <ul>
+ * <li>{@code edges()}: Stable order
+ * <li>{@code adjacentNodes(node)}: Connecting edge insertion order
+ * <li>{@code predecessors(node)}: Connecting edge insertion order
+ * <li>{@code successors(node)}: Connecting edge insertion order
+ * <li>{@code incidentEdges(node)}: Edge insertion order
+ * </ul>
+ * <li>For {@link Network}:
+ * <ul>
+ * <li>{@code adjacentNodes(node)}: Stable order
+ * <li>{@code predecessors(node)}: Connecting edge insertion order
+ * <li>{@code successors(node)}: Connecting edge insertion order
+ * <li>{@code incidentEdges(node)}: Stable order
+ * <li>{@code inEdges(node)}: Edge insertion order
+ * <li>{@code outEdges(node)}: Edge insertion order
+ * <li>{@code adjacentEdges(edge)}: Stable order
+ * <li>{@code edgesConnecting(nodeU, nodeV)}: Edge insertion order
+ * </ul>
+ * </ul>
+ *
+ * @since 29.0
+ */
+ public static <S> ElementOrder<S> stable() {
+ return new ElementOrder<>(Type.STABLE, null);
+ }
+
+ /** Returns an instance which specifies that insertion ordering is guaranteed. */
+ public static <S> ElementOrder<S> insertion() {
+ return new ElementOrder<>(Type.INSERTION, null);
+ }
+
+ /**
+ * Returns an instance which specifies that the natural ordering of the elements is guaranteed.
+ */
+ public static <S extends Comparable<? super S>> ElementOrder<S> natural() {
+ return new ElementOrder<>(Type.SORTED, Ordering.<S>natural());
+ }
+
+ /**
+ * Returns an instance which specifies that the ordering of the elements is guaranteed to be
+ * determined by {@code comparator}.
+ */
+ public static <S> ElementOrder<S> sorted(Comparator<S> comparator) {
+ return new ElementOrder<>(Type.SORTED, checkNotNull(comparator));
+ }
+
+ /** Returns the type of ordering used. */
+ public Type type() {
+ return type;
+ }
+
+ /**
+ * Returns the {@link Comparator} used.
+ *
+ * @throws UnsupportedOperationException if comparator is not defined
+ */
+ public Comparator<T> comparator() {
+ if (comparator != null) {
+ return comparator;
+ }
+ throw new UnsupportedOperationException("This ordering does not define a comparator.");
+ }
+
+ @Override
+ public boolean equals(@CheckForNull Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (!(obj instanceof ElementOrder)) {
+ return false;
+ }
+
+ ElementOrder<?> other = (ElementOrder<?>) obj;
+ return (type == other.type) && Objects.equal(comparator, other.comparator);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(type, comparator);
+ }
+
+ @Override
+ public String toString() {
+ ToStringHelper helper = MoreObjects.toStringHelper(this).add("type", type);
+ if (comparator != null) {
+ helper.add("comparator", comparator);
+ }
+ return helper.toString();
+ }
+
+ /** Returns an empty mutable map whose keys will respect this {@link ElementOrder}. */
+ <K extends T, V> Map<K, V> createMap(int expectedSize) {
+ switch (type) {
+ case UNORDERED:
+ return Maps.newHashMapWithExpectedSize(expectedSize);
+ case INSERTION:
+ case STABLE:
+ return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
+ case SORTED:
+ return Maps.newTreeMap(comparator());
+ default:
+ throw new AssertionError();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ <T1 extends T> ElementOrder<T1> cast() {
+ return (ElementOrder<T1>) this;
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/EndpointPair.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/EndpointPair.java
new file mode 100644
index 0000000..04543be
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/EndpointPair.java
@@ -0,0 +1,250 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import com.google.common.base.Objects;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.UnmodifiableIterator;
+
+import javax.annotation.CheckForNull;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.graph.GraphConstants.NOT_AVAILABLE_ON_UNDIRECTED;
+
+/**
+ * An immutable pair representing the two endpoints of an edge in a graph. The {@link EndpointPair}
+ * of a directed edge is an ordered pair of nodes ({@link #source()} and {@link #target()}). The
+ * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and
+ * {@link #nodeV()}).
+ *
+ * <p>The edge is a self-loop if, and only if, the two endpoints are equal.
+ *
+ * @author James Sexton
+ * @since 20.0
+ */
+public abstract class EndpointPair<N> implements Iterable<N> {
+ private final N nodeU;
+ private final N nodeV;
+
+ private EndpointPair(N nodeU, N nodeV) {
+ this.nodeU = checkNotNull(nodeU);
+ this.nodeV = checkNotNull(nodeV);
+ }
+
+ /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */
+ public static <N> EndpointPair<N> ordered(N source, N target) {
+ return new Ordered<>(source, target);
+ }
+
+ /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */
+ public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) {
+ // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair.
+ return new Unordered<>(nodeV, nodeU);
+ }
+
+ /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */
+ static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) {
+ return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
+ }
+
+ /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */
+ static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) {
+ return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
+ }
+
+ /**
+ * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source.
+ *
+ * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
+ */
+ public abstract N source();
+
+ /**
+ * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target.
+ *
+ * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
+ */
+ public abstract N target();
+
+ /**
+ * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise,
+ * returns an arbitrary (but consistent) endpoint of the origin edge.
+ */
+ public final N nodeU() {
+ return nodeU;
+ }
+
+ /**
+ * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin
+ * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}.
+ */
+ public final N nodeV() {
+ return nodeV;
+ }
+
+ /**
+ * Returns the node that is adjacent to {@code node} along the origin edge.
+ *
+ * @throws IllegalArgumentException if this {@link EndpointPair} does not contain {@code node}
+ * @since 20.0 (but the argument type was changed from {@code Object} to {@code N} in 31.0)
+ */
+ public final N adjacentNode(N node) {
+ if (node.equals(nodeU)) {
+ return nodeV;
+ } else if (node.equals(nodeV)) {
+ return nodeU;
+ } else {
+ throw new IllegalArgumentException("EndpointPair " + this + " does not contain node " + node);
+ }
+ }
+
+ /**
+ * Returns {@code true} if this {@link EndpointPair} is an ordered pair (i.e. represents the
+ * endpoints of a directed edge).
+ */
+ public abstract boolean isOrdered();
+
+ /** Iterates in the order {@link #nodeU()}, {@link #nodeV()}. */
+ @Override
+ public final UnmodifiableIterator<N> iterator() {
+ return Iterators.forArray(nodeU, nodeV);
+ }
+
+ /**
+ * Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()}
+ * are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An
+ * ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}.
+ */
+ @Override
+ public abstract boolean equals(@CheckForNull Object obj);
+
+ /**
+ * The hashcode of an ordered {@link EndpointPair} is equal to {@code Objects.hashCode(source(),
+ * target())}. The hashcode of an unordered {@link EndpointPair} is equal to {@code
+ * nodeU().hashCode() + nodeV().hashCode()}.
+ */
+ @Override
+ public abstract int hashCode();
+
+ private static final class Ordered<N> extends EndpointPair<N> {
+ private Ordered(N source, N target) {
+ super(source, target);
+ }
+
+ @Override
+ public N source() {
+ return nodeU();
+ }
+
+ @Override
+ public N target() {
+ return nodeV();
+ }
+
+ @Override
+ public boolean isOrdered() {
+ return true;
+ }
+
+ @Override
+ public boolean equals(@CheckForNull Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (!(obj instanceof EndpointPair)) {
+ return false;
+ }
+
+ EndpointPair<?> other = (EndpointPair<?>) obj;
+ if (isOrdered() != other.isOrdered()) {
+ return false;
+ }
+
+ return source().equals(other.source()) && target().equals(other.target());
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(source(), target());
+ }
+
+ @Override
+ public String toString() {
+ return "<" + source() + " -> " + target() + ">";
+ }
+ }
+
+ private static final class Unordered<N> extends EndpointPair<N> {
+ private Unordered(N nodeU, N nodeV) {
+ super(nodeU, nodeV);
+ }
+
+ @Override
+ public N source() {
+ throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
+ }
+
+ @Override
+ public N target() {
+ throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
+ }
+
+ @Override
+ public boolean isOrdered() {
+ return false;
+ }
+
+ @Override
+ public boolean equals(@CheckForNull Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (!(obj instanceof EndpointPair)) {
+ return false;
+ }
+
+ EndpointPair<?> other = (EndpointPair<?>) obj;
+ if (isOrdered() != other.isOrdered()) {
+ return false;
+ }
+
+ // Equivalent to the following simple implementation:
+ // boolean condition1 = nodeU().equals(other.nodeU()) && nodeV().equals(other.nodeV());
+ // boolean condition2 = nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU());
+ // return condition1 || condition2;
+ if (nodeU().equals(other.nodeU())) { // check condition1
+ // Here's the tricky bit. We don't have to explicitly check for condition2 in this case.
+ // Why? The second half of condition2 requires that nodeV equals other.nodeU.
+ // We already know that nodeU equals other.nodeU. Combined with the earlier statement,
+ // and the transitive property of equality, this implies that nodeU equals nodeV.
+ // If nodeU equals nodeV, condition1 == condition2, so checking condition1 is sufficient.
+ return nodeV().equals(other.nodeV());
+ }
+ return nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); // check condition2
+ }
+
+ @Override
+ public int hashCode() {
+ return nodeU().hashCode() + nodeV().hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return "[" + nodeU() + ", " + nodeV() + "]";
+ }
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/Graph.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Graph.java
new file mode 100644
index 0000000..50b32e3
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Graph.java
@@ -0,0 +1,299 @@
+/*
+ * Copyright (C) 2014 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import javax.annotation.CheckForNull;
+
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * An interface for <a
+ * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data,
+ * whose edges are anonymous entities with no identity or information of their own.
+ *
+ * <p>A graph is composed of a set of nodes and a set of edges connecting pairs of nodes.
+ *
+ * <p>There are three primary interfaces provided to represent graphs. In order of increasing
+ * complexity they are: {@link Graph}, {@link ValueGraph}, and {@link Network}. You should generally
+ * prefer the simplest interface that satisfies your use case. See the <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#choosing-the-right-graph-type">
+ * "Choosing the right graph type"</a> section of the Guava User Guide for more details.
+ *
+ * <h3>Capabilities</h3>
+ *
+ * <p>{@code Graph} supports the following use cases (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#definitions">definitions of
+ * terms</a>):
+ *
+ * <ul>
+ * <li>directed graphs
+ * <li>undirected graphs
+ * <li>graphs that do/don't allow self-loops
+ * <li>graphs whose nodes/edges are insertion-ordered, sorted, or unordered
+ * </ul>
+ *
+ * <p>{@code Graph} explicitly does not support parallel edges, and forbids implementations or
+ * extensions with parallel edges. If you need parallel edges, use {@link Network}.
+ *
+ * <h3>Building a {@code Graph}</h3>
+ *
+ * <p>The implementation classes that {@code common.graph} provides are not public, by design. To
+ * create an instance of one of the built-in implementations of {@code Graph}, use the {@link
+ * GraphBuilder} class:
+ *
+ * <pre>{@code
+ * MutableGraph<Integer> graph = GraphBuilder.undirected().build();
+ * }</pre>
+ *
+ * <p>{@link GraphBuilder#build()} returns an instance of {@link MutableGraph}, which is a subtype
+ * of {@code Graph} that provides methods for adding and removing nodes and edges. If you do not
+ * need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph),
+ * you should use the non-mutating {@link Graph} interface, or an {@link ImmutableGraph}.
+ *
+ * <p>You can create an immutable copy of an existing {@code Graph} using {@link
+ * ImmutableGraph#copyOf(Graph)}:
+ *
+ * <pre>{@code
+ * ImmutableGraph<Integer> immutableGraph = ImmutableGraph.copyOf(graph);
+ * }</pre>
+ *
+ * <p>Instances of {@link ImmutableGraph} do not implement {@link MutableGraph} (obviously!) and are
+ * contractually guaranteed to be unmodifiable and thread-safe.
+ *
+ * <p>The Guava User Guide has <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances">more
+ * information on (and examples of) building graphs</a>.
+ *
+ * <h3>Additional documentation</h3>
+ *
+ * <p>See the Guava User Guide for the {@code common.graph} package (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
+ * additional documentation, including:
+ *
+ * <ul>
+ * <li><a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#equals-hashcode-and-graph-equivalence">
+ * {@code equals()}, {@code hashCode()}, and graph equivalence</a>
+ * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#synchronization">
+ * Synchronization policy</a>
+ * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">Notes
+ * for implementors</a>
+ * </ul>
+ *
+ * @author James Sexton
+ * @author Joshua O'Madadhain
+ * @param <N> Node parameter type
+ * @since 20.0
+ */
+public interface Graph<N> extends BaseGraph<N> {
+ //
+ // Graph-level accessors
+ //
+
+ /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */
+ @Override
+ Set<N> nodes();
+
+ /** Returns all edges in this graph. */
+ @Override
+ Set<EndpointPair<N>> edges();
+
+ //
+ // Graph properties
+ //
+
+ /**
+ * Returns true if the edges in this graph are directed. Directed edges connect a {@link
+ * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
+ * undirected edges connect a pair of nodes to each other.
+ */
+ @Override
+ boolean isDirected();
+
+ /**
+ * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting
+ * to add a self-loop to a graph that does not allow them will throw an {@link
+ * IllegalArgumentException}.
+ */
+ @Override
+ boolean allowsSelfLoops();
+
+ /** Returns the order of iteration for the elements of {@link #nodes()}. */
+ @Override
+ ElementOrder<N> nodeOrder();
+
+ /**
+ * Returns an {@link ElementOrder} that specifies the order of iteration for the elements of
+ * {@link #edges()}, {@link #adjacentNodes(Object)}, {@link #predecessors(Object)}, {@link
+ * #successors(Object)} and {@link #incidentEdges(Object)}.
+ *
+ * @since 29.0
+ */
+ @Override
+ ElementOrder<N> incidentEdgeOrder();
+
+ //
+ // Element-level accessors
+ //
+
+ /**
+ * Returns the nodes which have an incident edge in common with {@code node} in this graph.
+ *
+ * <p>This is equal to the union of {@link #predecessors(Object)} and {@link #successors(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ Set<N> adjacentNodes(N node);
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
+ *
+ * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ Set<N> predecessors(N node);
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s outgoing edges in the direction (if any) of the edge.
+ *
+ * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
+ * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ Set<N> successors(N node);
+
+ /**
+ * Returns the edges in this graph whose endpoints include {@code node}.
+ *
+ * <p>This is equal to the union of incoming and outgoing edges.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ * @since 24.0
+ */
+ @Override
+ Set<EndpointPair<N>> incidentEdges(N node);
+
+ /**
+ * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently,
+ * the number of times an edge touches {@code node}).
+ *
+ * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}.
+ *
+ * <p>For undirected graphs, this is equal to {@code incidentEdges(node).size()} + (number of
+ * self-loops incident to {@code node}).
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ int degree(N node);
+
+ /**
+ * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()})
+ * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ int inDegree(N node);
+
+ /**
+ * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()})
+ * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ @Override
+ int outDegree(N node);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code nodeU} to {@code nodeV}. This is
+ * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}.
+ *
+ * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
+ *
+ * @since 23.0
+ */
+ @Override
+ boolean hasEdgeConnecting(N nodeU, N nodeV);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code endpoints} (in the order, if
+ * any, specified by {@code endpoints}). This is equivalent to {@code
+ * edges().contains(endpoints)}.
+ *
+ * <p>Unlike the other {@code EndpointPair}-accepting methods, this method does not throw if the
+ * endpoints are unordered and the graph is directed; it simply returns {@code false}. This is for
+ * consistency with the behavior of {@link Collection#contains(Object)} (which does not generally
+ * throw if the object cannot be present in the collection), and the desire to have this method's
+ * behavior be compatible with {@code edges().contains(endpoints)}.
+ *
+ * @since 27.1
+ */
+ @Override
+ boolean hasEdgeConnecting(EndpointPair<N> endpoints);
+
+ //
+ // Graph identity
+ //
+
+ /**
+ * Returns {@code true} iff {@code object} is a {@link Graph} that has the same elements and the
+ * same structural relationships as those in this graph.
+ *
+ * <p>Thus, two graphs A and B are equal if <b>all</b> of the following are true:
+ *
+ * <ul>
+ * <li>A and B have equal {@link #isDirected() directedness}.
+ * <li>A and B have equal {@link #nodes() node sets}.
+ * <li>A and B have equal {@link #edges() edge sets}.
+ * </ul>
+ *
+ * <p>Graph properties besides {@link #isDirected() directedness} do <b>not</b> affect equality.
+ * For example, two graphs may be considered equal even if one allows self-loops and the other
+ * doesn't. Additionally, the order in which nodes or edges are added to the graph, and the order
+ * in which they are iterated over, are irrelevant.
+ *
+ * <p>A reference implementation of this is provided by {@link AbstractGraph#equals(Object)}.
+ */
+ @Override
+ boolean equals(@CheckForNull Object object);
+
+ /**
+ * Returns the hash code for this graph. The hash code of a graph is defined as the hash code of
+ * the set returned by {@link #edges()}.
+ *
+ * <p>A reference implementation of this is provided by {@link AbstractGraph#hashCode()}.
+ */
+ @Override
+ int hashCode();
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/GraphConstants.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/GraphConstants.java
new file mode 100644
index 0000000..3c58f00
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/GraphConstants.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2016 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+/** A utility class to hold various constants used by the Guava Graph library. */
+final class GraphConstants {
+
+ private GraphConstants() {}
+
+ static final int EXPECTED_DEGREE = 2;
+
+ static final int DEFAULT_NODE_COUNT = 10;
+ static final int DEFAULT_EDGE_COUNT = DEFAULT_NODE_COUNT * EXPECTED_DEGREE;
+
+ // Load factor and capacity for "inner" (i.e. per node/edge element) hash sets or maps
+ static final float INNER_LOAD_FACTOR = 1.0f;
+ static final int INNER_CAPACITY = 2; // ceiling(EXPECTED_DEGREE / INNER_LOAD_FACTOR)
+
+ // Error messages
+ static final String NODE_NOT_IN_GRAPH = "Node %s is not an element of this graph.";
+ static final String EDGE_NOT_IN_GRAPH = "Edge %s is not an element of this graph.";
+ static final String REUSING_EDGE =
+ "Edge %s already exists between the following nodes: %s, "
+ + "so it cannot be reused to connect the following nodes: %s.";
+ static final String MULTIPLE_EDGES_CONNECTING =
+ "Cannot call edgeConnecting() when parallel edges exist between %s and %s. Consider calling "
+ + "edgesConnecting() instead.";
+ static final String PARALLEL_EDGES_NOT_ALLOWED =
+ "Nodes %s and %s are already connected by a different edge. To construct a graph "
+ + "that allows parallel edges, call allowsParallelEdges(true) on the Builder.";
+ static final String SELF_LOOPS_NOT_ALLOWED =
+ "Cannot add self-loop edge on node %s, as self-loops are not allowed. To construct a graph "
+ + "that allows self-loops, call allowsSelfLoops(true) on the Builder.";
+ static final String NOT_AVAILABLE_ON_UNDIRECTED =
+ "Cannot call source()/target() on a EndpointPair from an undirected graph. Consider calling "
+ + "adjacentNode(node) if you already have a node, or nodeU()/nodeV() if you don't.";
+ static final String EDGE_ALREADY_EXISTS = "Edge %s already exists in the graph.";
+ static final String ENDPOINTS_MISMATCH =
+ "Mismatch: endpoints' ordering is not compatible with directionality of the graph";
+
+ /** Singleton edge value for {@link Graph} implementations backed by {@link ValueGraph}s. */
+ enum Presence {
+ EDGE_EXISTS
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/Network.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Network.java
new file mode 100644
index 0000000..05707d1
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Network.java
@@ -0,0 +1,428 @@
+/*
+ * Copyright (C) 2014 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import javax.annotation.CheckForNull;
+
+import java.util.Optional;
+import java.util.Set;
+
+/**
+ * An interface for <a
+ * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data,
+ * whose edges are unique objects.
+ *
+ * <p>A graph is composed of a set of nodes and a set of edges connecting pairs of nodes.
+ *
+ * <p>There are three primary interfaces provided to represent graphs. In order of increasing
+ * complexity they are: {@link Graph}, {@link ValueGraph}, and {@link Network}. You should generally
+ * prefer the simplest interface that satisfies your use case. See the <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#choosing-the-right-graph-type">
+ * "Choosing the right graph type"</a> section of the Guava User Guide for more details.
+ *
+ * <h3>Capabilities</h3>
+ *
+ * <p>{@code Network} supports the following use cases (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#definitions">definitions of
+ * terms</a>):
+ *
+ * <ul>
+ * <li>directed graphs
+ * <li>undirected graphs
+ * <li>graphs that do/don't allow parallel edges
+ * <li>graphs that do/don't allow self-loops
+ * <li>graphs whose nodes/edges are insertion-ordered, sorted, or unordered
+ * <li>graphs whose edges are unique objects
+ * </ul>
+ *
+ * <h3>Building a {@code Network}</h3>
+ *
+ * <p>The implementation classes that {@code common.graph} provides are not public, by design. To
+ * create an instance of one of the built-in implementations of {@code Network}, use the {@link
+ * NetworkBuilder} class:
+ *
+ * <pre>{@code
+ * MutableNetwork<Integer, MyEdge> graph = NetworkBuilder.directed().build();
+ * }</pre>
+ *
+ * <p>{@link NetworkBuilder#build()} returns an instance of {@link MutableNetwork}, which is a
+ * subtype of {@code Network} that provides methods for adding and removing nodes and edges. If you
+ * do not need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the
+ * graph), you should use the non-mutating {@link Network} interface, or an {@link
+ * ImmutableNetwork}.
+ *
+ * <p>You can create an immutable copy of an existing {@code Network} using {@link
+ * ImmutableNetwork#copyOf(Network)}:
+ *
+ * <pre>{@code
+ * ImmutableNetwork<Integer, MyEdge> immutableGraph = ImmutableNetwork.copyOf(graph);
+ * }</pre>
+ *
+ * <p>Instances of {@link ImmutableNetwork} do not implement {@link MutableNetwork} (obviously!) and
+ * are contractually guaranteed to be unmodifiable and thread-safe.
+ *
+ * <p>The Guava User Guide has <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances">more
+ * information on (and examples of) building graphs</a>.
+ *
+ * <h3>Additional documentation</h3>
+ *
+ * <p>See the Guava User Guide for the {@code common.graph} package (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
+ * additional documentation, including:
+ *
+ * <ul>
+ * <li><a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#equals-hashcode-and-graph-equivalence">
+ * {@code equals()}, {@code hashCode()}, and graph equivalence</a>
+ * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#synchronization">
+ * Synchronization policy</a>
+ * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">Notes
+ * for implementors</a>
+ * </ul>
+ *
+ * @author James Sexton
+ * @author Joshua O'Madadhain
+ * @param <N> Node parameter type
+ * @param <E> Edge parameter type
+ * @since 20.0
+ */
+public interface Network<N, E> extends SuccessorsFunction<N>, PredecessorsFunction<N> {
+ //
+ // Network-level accessors
+ //
+
+ /** Returns all nodes in this network, in the order specified by {@link #nodeOrder()}. */
+ Set<N> nodes();
+
+ /** Returns all edges in this network, in the order specified by {@link #edgeOrder()}. */
+ Set<E> edges();
+
+ /**
+ * Returns a live view of this network as a {@link Graph}. The resulting {@link Graph} will have
+ * an edge connecting node A to node B if this {@link Network} has an edge connecting A to B.
+ *
+ * <p>If this network {@link #allowsParallelEdges() allows parallel edges}, parallel edges will be
+ * treated as if collapsed into a single edge. For example, the {@link #degree(Object)} of a node
+ * in the {@link Graph} view may be less than the degree of the same node in this {@link Network}.
+ */
+ Graph<N> asGraph();
+
+ //
+ // Network properties
+ //
+
+ /**
+ * Returns true if the edges in this network are directed. Directed edges connect a {@link
+ * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
+ * undirected edges connect a pair of nodes to each other.
+ */
+ boolean isDirected();
+
+ /**
+ * Returns true if this network allows parallel edges. Attempting to add a parallel edge to a
+ * network that does not allow them will throw an {@link IllegalArgumentException}.
+ */
+ boolean allowsParallelEdges();
+
+ /**
+ * Returns true if this network allows self-loops (edges that connect a node to itself).
+ * Attempting to add a self-loop to a network that does not allow them will throw an {@link
+ * IllegalArgumentException}.
+ */
+ boolean allowsSelfLoops();
+
+ /** Returns the order of iteration for the elements of {@link #nodes()}. */
+ ElementOrder<N> nodeOrder();
+
+ /** Returns the order of iteration for the elements of {@link #edges()}. */
+ ElementOrder<E> edgeOrder();
+
+ //
+ // Element-level accessors
+ //
+
+ /**
+ * Returns the nodes which have an incident edge in common with {@code node} in this network.
+ *
+ * <p>This is equal to the union of {@link #predecessors(Object)} and {@link #successors(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ Set<N> adjacentNodes(N node);
+
+ /**
+ * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
+ *
+ * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ @Override
+ Set<N> predecessors(N node);
+
+ /**
+ * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s outgoing edges in the direction (if any) of the edge.
+ *
+ * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}.
+ *
+ * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
+ * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ @Override
+ Set<N> successors(N node);
+
+ /**
+ * Returns the edges whose {@link #incidentNodes(Object) incident nodes} in this network include
+ * {@code node}.
+ *
+ * <p>This is equal to the union of {@link #inEdges(Object)} and {@link #outEdges(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ Set<E> incidentEdges(N node);
+
+ /**
+ * Returns all edges in this network which can be traversed in the direction (if any) of the edge
+ * to end at {@code node}.
+ *
+ * <p>In a directed network, an incoming edge's {@link EndpointPair#target()} equals {@code node}.
+ *
+ * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ Set<E> inEdges(N node);
+
+ /**
+ * Returns all edges in this network which can be traversed in the direction (if any) of the edge
+ * starting from {@code node}.
+ *
+ * <p>In a directed network, an outgoing edge's {@link EndpointPair#source()} equals {@code node}.
+ *
+ * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ Set<E> outEdges(N node);
+
+ /**
+ * Returns the count of {@code node}'s {@link #incidentEdges(Object) incident edges}, counting
+ * self-loops twice (equivalently, the number of times an edge touches {@code node}).
+ *
+ * <p>For directed networks, this is equal to {@code inDegree(node) + outDegree(node)}.
+ *
+ * <p>For undirected networks, this is equal to {@code incidentEdges(node).size()} + (number of
+ * self-loops incident to {@code node}).
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ int degree(N node);
+
+ /**
+ * Returns the count of {@code node}'s {@link #inEdges(Object) incoming edges} in a directed
+ * network. In an undirected network, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ int inDegree(N node);
+
+ /**
+ * Returns the count of {@code node}'s {@link #outEdges(Object) outgoing edges} in a directed
+ * network. In an undirected network, returns the {@link #degree(Object)}.
+ *
+ * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this network
+ */
+ int outDegree(N node);
+
+ /**
+ * Returns the nodes which are the endpoints of {@code edge} in this network.
+ *
+ * @throws IllegalArgumentException if {@code edge} is not an element of this network
+ */
+ EndpointPair<N> incidentNodes(E edge);
+
+ /**
+ * Returns the edges which have an {@link #incidentNodes(Object) incident node} in common with
+ * {@code edge}. An edge is not considered adjacent to itself.
+ *
+ * @throws IllegalArgumentException if {@code edge} is not an element of this network
+ */
+ Set<E> adjacentEdges(E edge);
+
+ /**
+ * Returns the set of edges that each directly connect {@code nodeU} to {@code nodeV}.
+ *
+ * <p>In an undirected network, this is equal to {@code edgesConnecting(nodeV, nodeU)}.
+ *
+ * <p>The resulting set of edges will be parallel (i.e. have equal {@link
+ * #incidentNodes(Object)}). If this network does not {@link #allowsParallelEdges() allow parallel
+ * edges}, the resulting set will contain at most one edge (equivalent to {@code
+ * edgeConnecting(nodeU, nodeV).asSet()}).
+ *
+ * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
+ * network
+ */
+ Set<E> edgesConnecting(N nodeU, N nodeV);
+
+ /**
+ * Returns the set of edges that each directly connect {@code endpoints} (in the order, if any,
+ * specified by {@code endpoints}).
+ *
+ * <p>The resulting set of edges will be parallel (i.e. have equal {@link
+ * #incidentNodes(Object)}). If this network does not {@link #allowsParallelEdges() allow parallel
+ * edges}, the resulting set will contain at most one edge (equivalent to {@code
+ * edgeConnecting(endpoints).asSet()}).
+ *
+ * <p>If this network is directed, {@code endpoints} must be ordered.
+ *
+ * @throws IllegalArgumentException if either endpoint is not an element of this network
+ * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed
+ * @since 27.1
+ */
+ Set<E> edgesConnecting(EndpointPair<N> endpoints);
+
+ /**
+ * Returns the single edge that directly connects {@code nodeU} to {@code nodeV}, if one is
+ * present, or {@code Optional.empty()} if no such edge exists.
+ *
+ * <p>In an undirected network, this is equal to {@code edgeConnecting(nodeV, nodeU)}.
+ *
+ * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
+ * to {@code nodeV}
+ * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
+ * network
+ * @since 23.0
+ */
+ Optional<E> edgeConnecting(N nodeU, N nodeV);
+
+ /**
+ * Returns the single edge that directly connects {@code endpoints} (in the order, if any,
+ * specified by {@code endpoints}), if one is present, or {@code Optional.empty()} if no such edge
+ * exists.
+ *
+ * <p>If this graph is directed, the endpoints must be ordered.
+ *
+ * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
+ * to {@code nodeV}
+ * @throws IllegalArgumentException if either endpoint is not an element of this network
+ * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed
+ * @since 27.1
+ */
+ Optional<E> edgeConnecting(EndpointPair<N> endpoints);
+
+ /**
+ * Returns the single edge that directly connects {@code nodeU} to {@code nodeV}, if one is
+ * present, or {@code null} if no such edge exists.
+ *
+ * <p>In an undirected network, this is equal to {@code edgeConnectingOrNull(nodeV, nodeU)}.
+ *
+ * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
+ * to {@code nodeV}
+ * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
+ * network
+ * @since 23.0
+ */
+ @CheckForNull
+ E edgeConnectingOrNull(N nodeU, N nodeV);
+
+ /**
+ * Returns the single edge that directly connects {@code endpoints} (in the order, if any,
+ * specified by {@code endpoints}), if one is present, or {@code null} if no such edge exists.
+ *
+ * <p>If this graph is directed, the endpoints must be ordered.
+ *
+ * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
+ * to {@code nodeV}
+ * @throws IllegalArgumentException if either endpoint is not an element of this network
+ * @throws IllegalArgumentException if the endpoints are unordered and the graph is directed
+ * @since 27.1
+ */
+ @CheckForNull
+ E edgeConnectingOrNull(EndpointPair<N> endpoints);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code nodeU} to {@code nodeV}. This is
+ * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}, and to
+ * {@code edgeConnectingOrNull(nodeU, nodeV) != null}.
+ *
+ * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
+ *
+ * @since 23.0
+ */
+ boolean hasEdgeConnecting(N nodeU, N nodeV);
+
+ /**
+ * Returns true if there is an edge that directly connects {@code endpoints} (in the order, if
+ * any, specified by {@code endpoints}).
+ *
+ * <p>Unlike the other {@code EndpointPair}-accepting methods, this method does not throw if the
+ * endpoints are unordered and the graph is directed; it simply returns {@code false}. This is for
+ * consistency with {@link Graph#hasEdgeConnecting(EndpointPair)} and {@link
+ * ValueGraph#hasEdgeConnecting(EndpointPair)}.
+ *
+ * @since 27.1
+ */
+ boolean hasEdgeConnecting(EndpointPair<N> endpoints);
+
+ //
+ // Network identity
+ //
+
+ /**
+ * Returns {@code true} iff {@code object} is a {@link Network} that has the same elements and the
+ * same structural relationships as those in this network.
+ *
+ * <p>Thus, two networks A and B are equal if <b>all</b> of the following are true:
+ *
+ * <ul>
+ * <li>A and B have equal {@link #isDirected() directedness}.
+ * <li>A and B have equal {@link #nodes() node sets}.
+ * <li>A and B have equal {@link #edges() edge sets}.
+ * <li>Every edge in A and B connects the same nodes in the same direction (if any).
+ * </ul>
+ *
+ * <p>Network properties besides {@link #isDirected() directedness} do <b>not</b> affect equality.
+ * For example, two networks may be considered equal even if one allows parallel edges and the
+ * other doesn't. Additionally, the order in which nodes or edges are added to the network, and
+ * the order in which they are iterated over, are irrelevant.
+ *
+ * <p>A reference implementation of this is provided by {@link AbstractNetwork#equals(Object)}.
+ */
+ @Override
+ boolean equals(@CheckForNull Object object);
+
+ /**
+ * Returns the hash code for this network. The hash code of a network is defined as the hash code
+ * of a map from each of its {@link #edges() edges} to their {@link #incidentNodes(Object)
+ * incident nodes}.
+ *
+ * <p>A reference implementation of this is provided by {@link AbstractNetwork#hashCode()}.
+ */
+ @Override
+ int hashCode();
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/PredecessorsFunction.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/PredecessorsFunction.java
new file mode 100644
index 0000000..c5fdb81
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/PredecessorsFunction.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2014 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+/**
+ * A functional interface for <a
+ * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data.
+ *
+ * <p>This interface is meant to be used as the type of a parameter to graph algorithms (such as
+ * topological sort) that only need a way of accessing the predecessors of a node in a graph.
+ *
+ * <h3>Usage</h3>
+ *
+ * Given an algorithm, for example:
+ *
+ * <pre>{@code
+ * public <N> someGraphAlgorithm(N startNode, PredecessorsFunction<N> predecessorsFunction);
+ * }</pre>
+ *
+ * you will invoke it depending on the graph representation you're using.
+ *
+ * <p>If you have an instance of one of the primary {@code common.graph} types ({@link Graph},
+ * {@link ValueGraph}, and {@link Network}):
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, graph);
+ * }</pre>
+ *
+ * This works because those types each implement {@code PredecessorsFunction}. It will also work
+ * with any other implementation of this interface.
+ *
+ * <p>If you have your own graph implementation based around a custom node type {@code MyNode},
+ * which has a method {@code getParents()} that retrieves its predecessors in a graph:
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, MyNode::getParents);
+ * }</pre>
+ *
+ * <p>If you have some other mechanism for returning the predecessors of a node, or one that doesn't
+ * return a {@code Iterable<? extends N>}, then you can use a lambda to perform a more general
+ * transformation:
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, node -> ImmutableList.of(node.mother(), node.father()));
+ * }</pre>
+ *
+ * <p>Graph algorithms that need additional capabilities (accessing both predecessors and
+ * successors, iterating over the edges, etc.) should declare their input to be of a type that
+ * provides those capabilities, such as {@link Graph}, {@link ValueGraph}, or {@link Network}.
+ *
+ * <h3>Additional documentation</h3>
+ *
+ * <p>See the Guava User Guide for the {@code common.graph} package (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
+ * additional documentation, including <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">notes for
+ * implementors</a>
+ *
+ * @author Joshua O'Madadhain
+ * @author Jens Nyman
+ * @param <N> Node parameter type
+ * @since 23.0
+ */
+public interface PredecessorsFunction<N> {
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
+ *
+ * <p>Some algorithms that operate on a {@code PredecessorsFunction} may produce undesired results
+ * if the returned {@link Iterable} contains duplicate elements. Implementations of such
+ * algorithms should document their behavior in the presence of duplicates.
+ *
+ * <p>The elements of the returned {@code Iterable} must each be:
+ *
+ * <ul>
+ * <li>Non-null
+ * <li>Usable as {@code Map} keys (see the Guava User Guide's section on <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#graph-elements-nodes-and-edges">
+ * graph elements</a> for details)
+ * </ul>
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ Iterable<? extends N> predecessors(N node);
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/SuccessorsFunction.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/SuccessorsFunction.java
new file mode 100644
index 0000000..1481310
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/SuccessorsFunction.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2014 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+/**
+ * A functional interface for <a
+ * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data.
+ *
+ * <p>This interface is meant to be used as the type of a parameter to graph algorithms (such as
+ * breadth first traversal) that only need a way of accessing the successors of a node in a graph.
+ *
+ * <h3>Usage</h3>
+ *
+ * Given an algorithm, for example:
+ *
+ * <pre>{@code
+ * public <N> someGraphAlgorithm(N startNode, SuccessorsFunction<N> successorsFunction);
+ * }</pre>
+ *
+ * you will invoke it depending on the graph representation you're using.
+ *
+ * <p>If you have an instance of one of the primary {@code common.graph} types ({@link Graph},
+ * {@link ValueGraph}, and {@link Network}):
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, graph);
+ * }</pre>
+ *
+ * This works because those types each implement {@code SuccessorsFunction}. It will also work with
+ * any other implementation of this interface.
+ *
+ * <p>If you have your own graph implementation based around a custom node type {@code MyNode},
+ * which has a method {@code getChildren()} that retrieves its successors in a graph:
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, MyNode::getChildren);
+ * }</pre>
+ *
+ * <p>If you have some other mechanism for returning the successors of a node, or one that doesn't
+ * return an {@code Iterable<? extends N>}, then you can use a lambda to perform a more general
+ * transformation:
+ *
+ * <pre>{@code
+ * someGraphAlgorithm(startNode, node -> ImmutableList.of(node.leftChild(), node.rightChild()));
+ * }</pre>
+ *
+ * <p>Graph algorithms that need additional capabilities (accessing both predecessors and
+ * successors, iterating over the edges, etc.) should declare their input to be of a type that
+ * provides those capabilities, such as {@link Graph}, {@link ValueGraph}, or {@link Network}.
+ *
+ * <h3>Additional documentation</h3>
+ *
+ * <p>See the Guava User Guide for the {@code common.graph} package (<a
+ * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
+ * additional documentation, including <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">notes for
+ * implementors</a>
+ *
+ * @author Joshua O'Madadhain
+ * @author Jens Nyman
+ * @param <N> Node parameter type
+ * @since 23.0
+ */
+public interface SuccessorsFunction<N> {
+
+ /**
+ * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
+ * {@code node}'s outgoing edges in the direction (if any) of the edge.
+ *
+ * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
+ * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
+ *
+ * <p>Some algorithms that operate on a {@code SuccessorsFunction} may produce undesired results
+ * if the returned {@link Iterable} contains duplicate elements. Implementations of such
+ * algorithms should document their behavior in the presence of duplicates.
+ *
+ * <p>The elements of the returned {@code Iterable} must each be:
+ *
+ * <ul>
+ * <li>Non-null
+ * <li>Usable as {@code Map} keys (see the Guava User Guide's section on <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#graph-elements-nodes-and-edges">
+ * graph elements</a> for details)
+ * </ul>
+ *
+ * @throws IllegalArgumentException if {@code node} is not an element of this graph
+ */
+ Iterable<? extends N> successors(N node);
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/graph/Traverser.java b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Traverser.java
new file mode 100644
index 0000000..c4d20eb
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/graph/Traverser.java
@@ -0,0 +1,516 @@
+/*
+ * Copyright (C) 2017 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.graph;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.ImmutableSet;
+
+import javax.annotation.CheckForNull;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static java.util.Objects.requireNonNull;
+
+/**
+ * An object that can traverse the nodes that are reachable from a specified (set of) start node(s)
+ * using a specified {@link SuccessorsFunction}.
+ *
+ * <p>There are two entry points for creating a {@code Traverser}: {@link
+ * #forTree(SuccessorsFunction)} and {@link #forGraph(SuccessorsFunction)}. You should choose one
+ * based on your answers to the following questions:
+ *
+ * <ol>
+ * <li>Is there only one path to any node that's reachable from any start node? (If so, the graph
+ * to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
+ * <li>Are the node objects' implementations of {@code equals()}/{@code hashCode()} <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursive</a>?
+ * </ol>
+ *
+ * <p>If your answers are:
+ *
+ * <ul>
+ * <li>(1) "no" and (2) "no", use {@link #forGraph(SuccessorsFunction)}.
+ * <li>(1) "yes" and (2) "yes", use {@link #forTree(SuccessorsFunction)}.
+ * <li>(1) "yes" and (2) "no", you can use either, but {@code forTree()} will be more efficient.
+ * <li>(1) "no" and (2) "yes", <b><i>neither will work</i></b>, but if you transform your node
+ * objects into a non-recursive form, you can use {@code forGraph()}.
+ * </ul>
+ *
+ * @author Jens Nyman
+ * @param <N> Node parameter type
+ * @since 23.1
+ */
+public abstract class Traverser<N> {
+ private final SuccessorsFunction<N> successorFunction;
+
+ private Traverser(SuccessorsFunction<N> successorFunction) {
+ this.successorFunction = checkNotNull(successorFunction);
+ }
+
+ /**
+ * Creates a new traverser for the given general {@code graph}.
+ *
+ * <p>Traversers created using this method are guaranteed to visit each node reachable from the
+ * start node(s) at most once.
+ *
+ * <p>If you know that no node in {@code graph} is reachable by more than one path from the start
+ * node(s), consider using {@link #forTree(SuccessorsFunction)} instead.
+ *
+ * <p><b>Performance notes</b>
+ *
+ * <ul>
+ * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
+ * the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
+ * {@code hashCode()} implementations. (See the <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#elements-must-be-useable-as-map-keys">
+ * notes on element objects</a> for more information.)
+ * <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
+ * of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
+ * number of nodes that have been seen but not yet visited, that is, the "horizon").
+ * </ul>
+ *
+ * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
+ */
+ public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) {
+ return new Traverser<N>(graph) {
+ @Override
+ Traversal<N> newTraversal() {
+ return Traversal.inGraph(graph);
+ }
+ };
+ }
+
+ /**
+ * Creates a new traverser for a directed acyclic graph that has at most one path from the start
+ * node(s) to any node reachable from the start node(s), and has no paths from any start node to
+ * any other start node, such as a tree or forest.
+ *
+ * <p>{@code forTree()} is especially useful (versus {@code forGraph()}) in cases where the data
+ * structure being traversed is, in addition to being a tree/forest, also defined <a
+ * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursively</a>.
+ * This is because the {@code forTree()}-based implementations don't keep track of visited nodes,
+ * and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves
+ * both time and space versus traversing the same graph using {@code forGraph()}.
+ *
+ * <p>Providing a graph to be traversed for which there is more than one path from the start
+ * node(s) to any node may lead to:
+ *
+ * <ul>
+ * <li>Traversal not terminating (if the graph has cycles)
+ * <li>Nodes being visited multiple times (if multiple paths exist from any start node to any
+ * node reachable from any start node)
+ * </ul>
+ *
+ * <p><b>Performance notes</b>
+ *
+ * <ul>
+ * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
+ * the start node).
+ * <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
+ * of nodes that have been seen but not yet visited, that is, the "horizon").
+ * </ul>
+ *
+ * <p><b>Examples</b> (all edges are directed facing downwards)
+ *
+ * <p>The graph below would be valid input with start nodes of {@code a, f, c}. However, if {@code
+ * b} were <i>also</i> a start node, then there would be multiple paths to reach {@code e} and
+ * {@code h}.
+ *
+ * <pre>{@code
+ * a b c
+ * / \ / \ |
+ * / \ / \ |
+ * d e f g
+ * |
+ * |
+ * h
+ * }</pre>
+ *
+ * <p>.
+ *
+ * <p>The graph below would be a valid input with start nodes of {@code a, f}. However, if {@code
+ * b} were a start node, there would be multiple paths to {@code f}.
+ *
+ * <pre>{@code
+ * a b
+ * / \ / \
+ * / \ / \
+ * c d e
+ * \ /
+ * \ /
+ * f
+ * }</pre>
+ *
+ * <p><b>Note on binary trees</b>
+ *
+ * <p>This method can be used to traverse over a binary tree. Given methods {@code
+ * leftChild(node)} and {@code rightChild(node)}, this method can be called as
+ *
+ * <pre>{@code
+ * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
+ * }</pre>
+ *
+ * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
+ * one path between any two nodes
+ */
+ public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree) {
+ if (tree instanceof BaseGraph) {
+ checkArgument(((BaseGraph<?>) tree).isDirected(), "Undirected graphs can never be trees.");
+ }
+ if (tree instanceof Network) {
+ checkArgument(((Network<?, ?>) tree).isDirected(), "Undirected networks can never be trees.");
+ }
+ return new Traverser<N>(tree) {
+ @Override
+ Traversal<N> newTraversal() {
+ return Traversal.inTree(tree);
+ }
+ };
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
+ * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then
+ * depth 1, then 2, and so on.
+ *
+ * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
+ * the order {@code abcdef} (assuming successors are returned in alphabetical order).
+ *
+ * <pre>{@code
+ * b ---- a ---- d
+ * | |
+ * | |
+ * e ---- c ---- f
+ * }</pre>
+ *
+ * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
+ * while iteration is in progress.
+ *
+ * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
+ * compute its next element on the fly. It is thus possible to limit the traversal to a certain
+ * number of nodes as follows:
+ *
+ * <pre>{@code
+ * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
+ * }</pre>
+ *
+ * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
+ * info.
+ *
+ * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
+ */
+ public final Iterable<N> breadthFirst(N startNode) {
+ return breadthFirst(ImmutableSet.of(startNode));
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
+ * startNodes}, in the order of a breadth-first traversal. This is equivalent to a breadth-first
+ * traversal of a graph with an additional root node whose successors are the listed {@code
+ * startNodes}.
+ *
+ * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
+ * @see #breadthFirst(Object)
+ * @since 24.1
+ */
+ public final Iterable<N> breadthFirst(Iterable<? extends N> startNodes) {
+ ImmutableSet<N> validated = validate(startNodes);
+ return new Iterable<N>() {
+ @Override
+ public Iterator<N> iterator() {
+ return newTraversal().breadthFirst(validated.iterator());
+ }
+ };
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
+ * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the
+ * {@code Iterable} in the order in which they are first visited.
+ *
+ * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
+ * the order {@code abecfd} (assuming successors are returned in alphabetical order).
+ *
+ * <pre>{@code
+ * b ---- a ---- d
+ * | |
+ * | |
+ * e ---- c ---- f
+ * }</pre>
+ *
+ * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
+ * while iteration is in progress.
+ *
+ * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
+ * compute its next element on the fly. It is thus possible to limit the traversal to a certain
+ * number of nodes as follows:
+ *
+ * <pre>{@code
+ * Iterables.limit(
+ * Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
+ * }</pre>
+ *
+ * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
+ *
+ * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
+ */
+ public final Iterable<N> depthFirstPreOrder(N startNode) {
+ return depthFirstPreOrder(ImmutableSet.of(startNode));
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
+ * startNodes}, in the order of a depth-first pre-order traversal. This is equivalent to a
+ * depth-first pre-order traversal of a graph with an additional root node whose successors are
+ * the listed {@code startNodes}.
+ *
+ * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
+ * @see #depthFirstPreOrder(Object)
+ * @since 24.1
+ */
+ public final Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes) {
+ ImmutableSet<N> validated = validate(startNodes);
+ return new Iterable<N>() {
+ @Override
+ public Iterator<N> iterator() {
+ return newTraversal().preOrder(validated.iterator());
+ }
+ };
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
+ * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the
+ * {@code Iterable} in the order in which they are visited for the last time.
+ *
+ * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
+ * the order {@code fcebda} (assuming successors are returned in alphabetical order).
+ *
+ * <pre>{@code
+ * b ---- a ---- d
+ * | |
+ * | |
+ * e ---- c ---- f
+ * }</pre>
+ *
+ * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
+ * while iteration is in progress.
+ *
+ * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
+ * compute its next element on the fly. It is thus possible to limit the traversal to a certain
+ * number of nodes as follows:
+ *
+ * <pre>{@code
+ * Iterables.limit(
+ * Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
+ * }</pre>
+ *
+ * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
+ *
+ * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
+ */
+ public final Iterable<N> depthFirstPostOrder(N startNode) {
+ return depthFirstPostOrder(ImmutableSet.of(startNode));
+ }
+
+ /**
+ * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
+ * startNodes}, in the order of a depth-first post-order traversal. This is equivalent to a
+ * depth-first post-order traversal of a graph with an additional root node whose successors are
+ * the listed {@code startNodes}.
+ *
+ * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
+ * @see #depthFirstPostOrder(Object)
+ * @since 24.1
+ */
+ public final Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes) {
+ ImmutableSet<N> validated = validate(startNodes);
+ return new Iterable<N>() {
+ @Override
+ public Iterator<N> iterator() {
+ return newTraversal().postOrder(validated.iterator());
+ }
+ };
+ }
+
+ abstract Traversal<N> newTraversal();
+
+ @SuppressWarnings("CheckReturnValue")
+ private ImmutableSet<N> validate(Iterable<? extends N> startNodes) {
+ ImmutableSet<N> copy = ImmutableSet.copyOf(startNodes);
+ for (N node : copy) {
+ successorFunction.successors(node); // Will throw if node doesn't exist
+ }
+ return copy;
+ }
+
+ /**
+ * Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take
+ * the next element from the next non-empty iterator; for graph, we need to loop through the next
+ * non-empty iterator to find first unvisited node.
+ */
+ private abstract static class Traversal<N> {
+ final SuccessorsFunction<N> successorFunction;
+
+ Traversal(SuccessorsFunction<N> successorFunction) {
+ this.successorFunction = successorFunction;
+ }
+
+ static <N> Traversal<N> inGraph(SuccessorsFunction<N> graph) {
+ Set<N> visited = new HashSet<>();
+ return new Traversal<N>(graph) {
+ @Override
+ @CheckForNull
+ N visitNext(Deque<Iterator<? extends N>> horizon) {
+ Iterator<? extends N> top = horizon.getFirst();
+ while (top.hasNext()) {
+ N element = top.next();
+ // requireNonNull is safe because horizon contains only graph nodes.
+ /*
+ * TODO(cpovirk): Replace these two statements with one (`N element =
+ * requireNonNull(top.next())`) once our checker supports it.
+ *
+ * (The problem is likely
+ * https://github.com/jspecify/jspecify-reference-checker/blob/61aafa4ae52594830cfc2d61c8b113009dbdb045/src/main/java/com/google/jspecify/nullness/NullSpecAnnotatedTypeFactory.java#L896)
+ */
+ requireNonNull(element);
+ if (visited.add(element)) {
+ return element;
+ }
+ }
+ horizon.removeFirst();
+ return null;
+ }
+ };
+ }
+
+ static <N> Traversal<N> inTree(SuccessorsFunction<N> tree) {
+ return new Traversal<N>(tree) {
+ @CheckForNull
+ @Override
+ N visitNext(Deque<Iterator<? extends N>> horizon) {
+ Iterator<? extends N> top = horizon.getFirst();
+ if (top.hasNext()) {
+ return checkNotNull(top.next());
+ }
+ horizon.removeFirst();
+ return null;
+ }
+ };
+ }
+
+ final Iterator<N> breadthFirst(Iterator<? extends N> startNodes) {
+ return topDown(startNodes, InsertionOrder.BACK);
+ }
+
+ final Iterator<N> preOrder(Iterator<? extends N> startNodes) {
+ return topDown(startNodes, InsertionOrder.FRONT);
+ }
+
+ /**
+ * In top-down traversal, an ancestor node is always traversed before any of its descendant
+ * nodes. The traversal order among descendant nodes (particularly aunts and nieces) are
+ * determined by the {@code InsertionOrder} parameter: nieces are placed at the FRONT before
+ * aunts for pre-order; while in BFS they are placed at the BACK after aunts.
+ */
+ private Iterator<N> topDown(Iterator<? extends N> startNodes, InsertionOrder order) {
+ Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
+ horizon.add(startNodes);
+ return new AbstractIterator<N>() {
+ @Override
+ @CheckForNull
+ protected N computeNext() {
+ do {
+ N next = visitNext(horizon);
+ if (next != null) {
+ Iterator<? extends N> successors = successorFunction.successors(next).iterator();
+ if (successors.hasNext()) {
+ // BFS: horizon.addLast(successors)
+ // Pre-order: horizon.addFirst(successors)
+ order.insertInto(horizon, successors);
+ }
+ return next;
+ }
+ } while (!horizon.isEmpty());
+ return endOfData();
+ }
+ };
+ }
+
+ final Iterator<N> postOrder(Iterator<? extends N> startNodes) {
+ Deque<N> ancestorStack = new ArrayDeque<>();
+ Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
+ horizon.add(startNodes);
+ return new AbstractIterator<N>() {
+ @Override
+ @CheckForNull
+ protected N computeNext() {
+ for (N next = visitNext(horizon); next != null; next = visitNext(horizon)) {
+ Iterator<? extends N> successors = successorFunction.successors(next).iterator();
+ if (!successors.hasNext()) {
+ return next;
+ }
+ horizon.addFirst(successors);
+ ancestorStack.push(next);
+ }
+ // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker.
+ if (!ancestorStack.isEmpty()) {
+ return ancestorStack.pop();
+ }
+ return endOfData();
+ }
+ };
+ }
+
+ /**
+ * Visits the next node from the top iterator of {@code horizon} and returns the visited node.
+ * Null is returned to indicate reaching the end of the top iterator.
+ *
+ * <p>For example, if horizon is {@code [[a, b], [c, d], [e]]}, {@code visitNext()} will return
+ * {@code [a, b, null, c, d, null, e, null]} sequentially, encoding the topological structure.
+ * (Note, however, that the callers of {@code visitNext()} often insert additional iterators
+ * into {@code horizon} between calls to {@code visitNext()}. This causes them to receive
+ * additional values interleaved with those shown above.)
+ */
+ @CheckForNull
+ abstract N visitNext(Deque<Iterator<? extends N>> horizon);
+ }
+
+ /** Poor man's method reference for {@code Deque::addFirst} and {@code Deque::addLast}. */
+ private enum InsertionOrder {
+ FRONT {
+ @Override
+ <T> void insertInto(Deque<T> deque, T value) {
+ deque.addFirst(value);
+ }
+ },
+ BACK {
+ @Override
+ <T> void insertInto(Deque<T> deque, T value) {
+ deque.addLast(value);
+ }
+ };
+
+ abstract <T> void insertInto(Deque<T> deque, T value);
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHashFunction.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHashFunction.java
new file mode 100644
index 0000000..4c84d13
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHashFunction.java
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2017 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkPositionIndexes;
+
+/**
+ * Skeleton implementation of {@link HashFunction} in terms of {@link #newHasher()}.
+ *
+ * <p>TODO(lowasser): make public
+ */
+abstract class AbstractHashFunction implements HashFunction {
+ @Override
+ public <T extends Object> HashCode hashObject(T instance, Funnel<? super T> funnel) {
+ return newHasher().putObject(instance, funnel).hash();
+ }
+
+ @Override
+ public HashCode hashUnencodedChars(CharSequence input) {
+ int len = input.length();
+ return newHasher(len * 2).putUnencodedChars(input).hash();
+ }
+
+ @Override
+ public HashCode hashString(CharSequence input, Charset charset) {
+ return newHasher().putString(input, charset).hash();
+ }
+
+ @Override
+ public HashCode hashInt(int input) {
+ return newHasher(4).putInt(input).hash();
+ }
+
+ @Override
+ public HashCode hashLong(long input) {
+ return newHasher(8).putLong(input).hash();
+ }
+
+ @Override
+ public HashCode hashBytes(byte[] input) {
+ return hashBytes(input, 0, input.length);
+ }
+
+ @Override
+ public HashCode hashBytes(byte[] input, int off, int len) {
+ checkPositionIndexes(off, off + len, input.length);
+ return newHasher(len).putBytes(input, off, len).hash();
+ }
+
+ @Override
+ public HashCode hashBytes(ByteBuffer input) {
+ return newHasher(input.remaining()).putBytes(input).hash();
+ }
+
+ @Override
+ public Hasher newHasher(int expectedInputSize) {
+ checkArgument(
+ expectedInputSize >= 0, "expectedInputSize must be >= 0 but was %s", expectedInputSize);
+ return newHasher();
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHasher.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHasher.java
new file mode 100644
index 0000000..eb49f37
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractHasher.java
@@ -0,0 +1,120 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import com.google.common.base.Preconditions;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+
+/**
+ * An abstract implementation of {@link Hasher}, which only requires subtypes to implement {@link
+ * #putByte}. Subtypes may provide more efficient implementations, however.
+ *
+ * @author Dimitris Andreou
+ */
+abstract class AbstractHasher implements Hasher {
+ @Override
+ public final Hasher putBoolean(boolean b) {
+ return putByte(b ? (byte) 1 : (byte) 0);
+ }
+
+ @Override
+ public final Hasher putDouble(double d) {
+ return putLong(Double.doubleToRawLongBits(d));
+ }
+
+ @Override
+ public final Hasher putFloat(float f) {
+ return putInt(Float.floatToRawIntBits(f));
+ }
+
+ @Override
+ public Hasher putUnencodedChars(CharSequence charSequence) {
+ for (int i = 0, len = charSequence.length(); i < len; i++) {
+ putChar(charSequence.charAt(i));
+ }
+ return this;
+ }
+
+ @Override
+ public Hasher putString(CharSequence charSequence, Charset charset) {
+ return putBytes(charSequence.toString().getBytes(charset));
+ }
+
+ @Override
+ public Hasher putBytes(byte[] bytes) {
+ return putBytes(bytes, 0, bytes.length);
+ }
+
+ @Override
+ public Hasher putBytes(byte[] bytes, int off, int len) {
+ Preconditions.checkPositionIndexes(off, off + len, bytes.length);
+ for (int i = 0; i < len; i++) {
+ putByte(bytes[off + i]);
+ }
+ return this;
+ }
+
+ @Override
+ public Hasher putBytes(ByteBuffer b) {
+ if (b.hasArray()) {
+ putBytes(b.array(), b.arrayOffset() + b.position(), b.remaining());
+ Java8Compatibility.position(b, b.limit());
+ } else {
+ for (int remaining = b.remaining(); remaining > 0; remaining--) {
+ putByte(b.get());
+ }
+ }
+ return this;
+ }
+
+ @Override
+ public Hasher putShort(short s) {
+ putByte((byte) s);
+ putByte((byte) (s >>> 8));
+ return this;
+ }
+
+ @Override
+ public Hasher putInt(int i) {
+ putByte((byte) i);
+ putByte((byte) (i >>> 8));
+ putByte((byte) (i >>> 16));
+ putByte((byte) (i >>> 24));
+ return this;
+ }
+
+ @Override
+ public Hasher putLong(long l) {
+ for (int i = 0; i < 64; i += 8) {
+ putByte((byte) (l >>> i));
+ }
+ return this;
+ }
+
+ @Override
+ public Hasher putChar(char c) {
+ putByte((byte) c);
+ putByte((byte) (c >>> 8));
+ return this;
+ }
+
+ @Override
+ public <T extends Object> Hasher putObject(T instance, Funnel<? super T> funnel) {
+ funnel.funnel(instance, this);
+ return this;
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractStreamingHasher.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractStreamingHasher.java
new file mode 100644
index 0000000..718fb36
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/AbstractStreamingHasher.java
@@ -0,0 +1,212 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * A convenience base class for implementors of {@code Hasher}; handles accumulating data until an
+ * entire "chunk" (of implementation-dependent length) is ready to be hashed.
+ *
+ * @author Kevin Bourrillion
+ * @author Dimitris Andreou
+ */
+// TODO(kevinb): this class still needs some design-and-document-for-inheritance love
+abstract class AbstractStreamingHasher extends AbstractHasher {
+ /** Buffer via which we pass data to the hash algorithm (the implementor) */
+ private final ByteBuffer buffer;
+
+ /** Number of bytes to be filled before process() invocation(s). */
+ private final int bufferSize;
+
+ /** Number of bytes processed per process() invocation. */
+ private final int chunkSize;
+
+ /**
+ * Constructor for use by subclasses. This hasher instance will process chunks of the specified
+ * size.
+ *
+ * @param chunkSize the number of bytes available per {@link #process(ByteBuffer)} invocation;
+ * must be at least 4
+ */
+ protected AbstractStreamingHasher(int chunkSize) {
+ this(chunkSize, chunkSize);
+ }
+
+ /**
+ * Constructor for use by subclasses. This hasher instance will process chunks of the specified
+ * size, using an internal buffer of {@code bufferSize} size, which must be a multiple of {@code
+ * chunkSize}.
+ *
+ * @param chunkSize the number of bytes available per {@link #process(ByteBuffer)} invocation;
+ * must be at least 4
+ * @param bufferSize the size of the internal buffer. Must be a multiple of chunkSize
+ */
+ protected AbstractStreamingHasher(int chunkSize, int bufferSize) {
+ // TODO(kevinb): check more preconditions (as bufferSize >= chunkSize) if this is ever public
+ checkArgument(bufferSize % chunkSize == 0);
+
+ // TODO(user): benchmark performance difference with longer buffer
+ // always space for a single primitive
+ this.buffer = ByteBuffer.allocate(bufferSize + 7).order(ByteOrder.LITTLE_ENDIAN);
+ this.bufferSize = bufferSize;
+ this.chunkSize = chunkSize;
+ }
+
+ /** Processes the available bytes of the buffer (at most {@code chunk} bytes). */
+ protected abstract void process(ByteBuffer bb);
+
+ /**
+ * This is invoked for the last bytes of the input, which are not enough to fill a whole chunk.
+ * The passed {@code ByteBuffer} is guaranteed to be non-empty.
+ *
+ * <p>This implementation simply pads with zeros and delegates to {@link #process(ByteBuffer)}.
+ */
+ protected void processRemaining(ByteBuffer bb) {
+ Java8Compatibility.position(bb, bb.limit()); // move at the end
+ Java8Compatibility.limit(bb, chunkSize + 7); // get ready to pad with longs
+ while (bb.position() < chunkSize) {
+ bb.putLong(0);
+ }
+ Java8Compatibility.limit(bb, chunkSize);
+ Java8Compatibility.flip(bb);
+ process(bb);
+ }
+
+ @Override
+ public final Hasher putBytes(byte[] bytes, int off, int len) {
+ return putBytesInternal(ByteBuffer.wrap(bytes, off, len).order(ByteOrder.LITTLE_ENDIAN));
+ }
+
+ @Override
+ public final Hasher putBytes(ByteBuffer readBuffer) {
+ ByteOrder order = readBuffer.order();
+ try {
+ readBuffer.order(ByteOrder.LITTLE_ENDIAN);
+ return putBytesInternal(readBuffer);
+ } finally {
+ readBuffer.order(order);
+ }
+ }
+
+ private Hasher putBytesInternal(ByteBuffer readBuffer) {
+ // If we have room for all of it, this is easy
+ if (readBuffer.remaining() <= buffer.remaining()) {
+ buffer.put(readBuffer);
+ munchIfFull();
+ return this;
+ }
+
+ // First add just enough to fill buffer size, and munch that
+ int bytesToCopy = bufferSize - buffer.position();
+ for (int i = 0; i < bytesToCopy; i++) {
+ buffer.put(readBuffer.get());
+ }
+ munch(); // buffer becomes empty here, since chunkSize divides bufferSize
+
+ // Now process directly from the rest of the input buffer
+ while (readBuffer.remaining() >= chunkSize) {
+ process(readBuffer);
+ }
+
+ // Finally stick the remainder back in our usual buffer
+ buffer.put(readBuffer);
+ return this;
+ }
+
+ /*
+ * Note: hashString(CharSequence, Charset) is intentionally not overridden.
+ *
+ * While intuitively, using CharsetEncoder to encode the CharSequence directly to the buffer (or
+ * even to an intermediate buffer) should be considerably more efficient than potentially
+ * copying the CharSequence to a String and then calling getBytes(Charset) on that String, in
+ * reality there are optimizations that make the getBytes(Charset) approach considerably faster,
+ * at least for commonly used charsets like UTF-8.
+ */
+
+ @Override
+ public final Hasher putByte(byte b) {
+ buffer.put(b);
+ munchIfFull();
+ return this;
+ }
+
+ @Override
+ public final Hasher putShort(short s) {
+ buffer.putShort(s);
+ munchIfFull();
+ return this;
+ }
+
+ @Override
+ public final Hasher putChar(char c) {
+ buffer.putChar(c);
+ munchIfFull();
+ return this;
+ }
+
+ @Override
+ public final Hasher putInt(int i) {
+ buffer.putInt(i);
+ munchIfFull();
+ return this;
+ }
+
+ @Override
+ public final Hasher putLong(long l) {
+ buffer.putLong(l);
+ munchIfFull();
+ return this;
+ }
+
+ @Override
+ public final HashCode hash() {
+ munch();
+ Java8Compatibility.flip(buffer);
+ if (buffer.remaining() > 0) {
+ processRemaining(buffer);
+ Java8Compatibility.position(buffer, buffer.limit());
+ }
+ return makeHash();
+ }
+
+ /**
+ * Computes a hash code based on the data that have been provided to this hasher. This is called
+ * after all chunks are handled with {@link #process} and any leftover bytes that did not make a
+ * complete chunk are handled with {@link #processRemaining}.
+ */
+ protected abstract HashCode makeHash();
+
+ // Process pent-up data in chunks
+ private void munchIfFull() {
+ if (buffer.remaining() < 8) {
+ // buffer is full; not enough room for a primitive. We have at least one full chunk.
+ munch();
+ }
+ }
+
+ private void munch() {
+ Java8Compatibility.flip(buffer);
+ while (buffer.remaining() >= chunkSize) {
+ // we could limit the buffer to ensure process() does not read more than
+ // chunkSize number of bytes, but we trust the implementations
+ process(buffer);
+ }
+ buffer.compact(); // preserve any remaining data that do not make a full chunk
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/Funnel.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Funnel.java
new file mode 100644
index 0000000..a0bbd91
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Funnel.java
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.io.Serializable;
+
+/**
+ * An object which can send data from an object of type {@code T} into a {@code PrimitiveSink}.
+ * Implementations for common types can be found in {@link Funnels}.
+ *
+ * <p>Note that serialization of {@linkplain BloomFilter bloom filters} requires the proper
+ * serialization of funnels. When possible, it is recommended that funnels be implemented as a
+ * single-element enum to maintain serialization guarantees. See Effective Java (2nd Edition), Item
+ * 3: "Enforce the singleton property with a private constructor or an enum type". For example:
+ *
+ * <pre>{@code
+ * public enum PersonFunnel implements Funnel<Person> {
+ * INSTANCE;
+ * public void funnel(Person person, PrimitiveSink into) {
+ * into.putUnencodedChars(person.getFirstName())
+ * .putUnencodedChars(person.getLastName())
+ * .putInt(person.getAge());
+ * }
+ * }
+ * }</pre>
+ *
+ * @author Dimitris Andreou
+ * @since 11.0
+ */
+public interface Funnel<T extends Object> extends Serializable {
+
+ /**
+ * Sends a stream of data from the {@code from} object into the sink {@code into}. There is no
+ * requirement that this data be complete enough to fully reconstitute the object later.
+ *
+ * @since 12.0 (in Guava 11.0, {@code PrimitiveSink} was named {@code Sink})
+ */
+ void funnel(T from, PrimitiveSink into);
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashCode.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashCode.java
new file mode 100644
index 0000000..69eae71
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashCode.java
@@ -0,0 +1,430 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import com.google.common.base.Preconditions;
+import com.google.common.primitives.Ints;
+
+import javax.annotation.CheckForNull;
+
+import java.io.Serializable;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
+/**
+ * An immutable hash code of arbitrary bit length.
+ *
+ * @author Dimitris Andreou
+ * @author Kurt Alfred Kluever
+ * @since 11.0
+ */
+public abstract class HashCode {
+ HashCode() {}
+
+ /** Returns the number of bits in this hash code; a positive multiple of 8. */
+ public abstract int bits();
+
+ /**
+ * Returns the first four bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to an
+ * {@code int} value in little-endian order.
+ *
+ * @throws IllegalStateException if {@code bits() < 32}
+ */
+ public abstract int asInt();
+
+ /**
+ * Returns the first eight bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to a
+ * {@code long} value in little-endian order.
+ *
+ * @throws IllegalStateException if {@code bits() < 64}
+ */
+ public abstract long asLong();
+
+ /**
+ * If this hashcode has enough bits, returns {@code asLong()}, otherwise returns a {@code long}
+ * value with {@code asBytes()} as the least-significant bytes and {@code 0x00} as the remaining
+ * most-significant bytes.
+ *
+ * @since 14.0 (since 11.0 as {@code Hashing.padToLong(HashCode)})
+ */
+ public abstract long padToLong();
+
+ /**
+ * Returns the value of this hash code as a byte array. The caller may modify the byte array;
+ * changes to it will <i>not</i> be reflected in this {@code HashCode} object or any other arrays
+ * returned by this method.
+ */
+ // TODO(user): consider ByteString here, when that is available
+ public abstract byte[] asBytes();
+
+ /**
+ * Copies bytes from this hash code into {@code dest}.
+ *
+ * @param dest the byte array into which the hash code will be written
+ * @param offset the start offset in the data
+ * @param maxLength the maximum number of bytes to write
+ * @return the number of bytes written to {@code dest}
+ * @throws IndexOutOfBoundsException if there is not enough room in {@code dest}
+ */
+ public int writeBytesTo(byte[] dest, int offset, int maxLength) {
+ maxLength = Ints.min(maxLength, bits() / 8);
+ Preconditions.checkPositionIndexes(offset, offset + maxLength, dest.length);
+ writeBytesToImpl(dest, offset, maxLength);
+ return maxLength;
+ }
+
+ abstract void writeBytesToImpl(byte[] dest, int offset, int maxLength);
+
+ /**
+ * Returns a mutable view of the underlying bytes for the given {@code HashCode} if it is a
+ * byte-based hashcode. Otherwise it returns {@link HashCode#asBytes}. Do <i>not</i> mutate this
+ * array or else you will break the immutability contract of {@code HashCode}.
+ */
+ byte[] getBytesInternal() {
+ return asBytes();
+ }
+
+ /**
+ * Returns whether this {@code HashCode} and that {@code HashCode} have the same value, given that
+ * they have the same number of bits.
+ */
+ abstract boolean equalsSameBits(HashCode that);
+
+ /**
+ * Creates a 32-bit {@code HashCode} representation of the given int value. The underlying bytes
+ * are interpreted in little endian order.
+ *
+ * @since 15.0 (since 12.0 in HashCodes)
+ */
+ public static HashCode fromInt(int hash) {
+ return new IntHashCode(hash);
+ }
+
+ private static final class IntHashCode extends HashCode implements Serializable {
+ static final long INT_MASK = 0xffffffffL;
+ final int hash;
+
+ IntHashCode(int hash) {
+ this.hash = hash;
+ }
+
+ @Override
+ public int bits() {
+ return 32;
+ }
+
+ @Override
+ public byte[] asBytes() {
+ return new byte[] {(byte) hash, (byte) (hash >> 8), (byte) (hash >> 16), (byte) (hash >> 24)};
+ }
+
+ @Override
+ public int asInt() {
+ return hash;
+ }
+
+ @Override
+ public long asLong() {
+ throw new IllegalStateException("this HashCode only has 32 bits; cannot create a long");
+ }
+
+ @Override
+ public long padToLong() {
+ return toLong(hash);
+ }
+
+ /**
+ * Returns the value of the given {@code int} as a {@code long}, when treated as unsigned.
+ *
+ * <p><b>Java 8 users:</b> use {@link Integer#toUnsignedLong(int)} instead.
+ */
+ public static long toLong(int value) {
+ return value & INT_MASK;
+ }
+
+ @Override
+ void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
+ for (int i = 0; i < maxLength; i++) {
+ dest[offset + i] = (byte) (hash >> (i * 8));
+ }
+ }
+
+ @Override
+ boolean equalsSameBits(HashCode that) {
+ return hash == that.asInt();
+ }
+
+ private static final long serialVersionUID = 0;
+ }
+
+ /**
+ * Creates a 64-bit {@code HashCode} representation of the given long value. The underlying bytes
+ * are interpreted in little endian order.
+ *
+ * @since 15.0 (since 12.0 in HashCodes)
+ */
+ public static HashCode fromLong(long hash) {
+ return new LongHashCode(hash);
+ }
+
+ private static final class LongHashCode extends HashCode implements Serializable {
+ final long hash;
+
+ LongHashCode(long hash) {
+ this.hash = hash;
+ }
+
+ @Override
+ public int bits() {
+ return 64;
+ }
+
+ @Override
+ public byte[] asBytes() {
+ return new byte[] {
+ (byte) hash,
+ (byte) (hash >> 8),
+ (byte) (hash >> 16),
+ (byte) (hash >> 24),
+ (byte) (hash >> 32),
+ (byte) (hash >> 40),
+ (byte) (hash >> 48),
+ (byte) (hash >> 56)
+ };
+ }
+
+ @Override
+ public int asInt() {
+ return (int) hash;
+ }
+
+ @Override
+ public long asLong() {
+ return hash;
+ }
+
+ @Override
+ public long padToLong() {
+ return hash;
+ }
+
+ @Override
+ void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
+ for (int i = 0; i < maxLength; i++) {
+ dest[offset + i] = (byte) (hash >> (i * 8));
+ }
+ }
+
+ @Override
+ boolean equalsSameBits(HashCode that) {
+ return hash == that.asLong();
+ }
+
+ private static final long serialVersionUID = 0;
+ }
+
+ /**
+ * Creates a {@code HashCode} from a byte array. The array is defensively copied to preserve the
+ * immutability contract of {@code HashCode}. The array cannot be empty.
+ *
+ * @since 15.0 (since 12.0 in HashCodes)
+ */
+ public static HashCode fromBytes(byte[] bytes) {
+ checkArgument(bytes.length >= 1, "A HashCode must contain at least 1 byte.");
+ return fromBytesNoCopy(bytes.clone());
+ }
+
+ /**
+ * Creates a {@code HashCode} from a byte array. The array is <i>not</i> copied defensively, so it
+ * must be handed-off so as to preserve the immutability contract of {@code HashCode}.
+ */
+ static HashCode fromBytesNoCopy(byte[] bytes) {
+ return new BytesHashCode(bytes);
+ }
+
+ private static final class BytesHashCode extends HashCode implements Serializable {
+ final byte[] bytes;
+
+ BytesHashCode(byte[] bytes) {
+ this.bytes = checkNotNull(bytes);
+ }
+
+ @Override
+ public int bits() {
+ return bytes.length * 8;
+ }
+
+ @Override
+ public byte[] asBytes() {
+ return bytes.clone();
+ }
+
+ @Override
+ public int asInt() {
+ checkState(
+ bytes.length >= 4,
+ "HashCode#asInt() requires >= 4 bytes (it only has %s bytes).",
+ bytes.length);
+ return (bytes[0] & 0xFF)
+ | ((bytes[1] & 0xFF) << 8)
+ | ((bytes[2] & 0xFF) << 16)
+ | ((bytes[3] & 0xFF) << 24);
+ }
+
+ @Override
+ public long asLong() {
+ checkState(
+ bytes.length >= 8,
+ "HashCode#asLong() requires >= 8 bytes (it only has %s bytes).",
+ bytes.length);
+ return padToLong();
+ }
+
+ @Override
+ public long padToLong() {
+ long retVal = (bytes[0] & 0xFF);
+ for (int i = 1; i < Math.min(bytes.length, 8); i++) {
+ retVal |= (bytes[i] & 0xFFL) << (i * 8);
+ }
+ return retVal;
+ }
+
+ @Override
+ void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
+ System.arraycopy(bytes, 0, dest, offset, maxLength);
+ }
+
+ @Override
+ byte[] getBytesInternal() {
+ return bytes;
+ }
+
+ @Override
+ boolean equalsSameBits(HashCode that) {
+ // We don't use MessageDigest.isEqual() here because its contract does not guarantee
+ // constant-time evaluation (no short-circuiting).
+ if (this.bytes.length != that.getBytesInternal().length) {
+ return false;
+ }
+
+ boolean areEqual = true;
+ for (int i = 0; i < this.bytes.length; i++) {
+ areEqual &= (this.bytes[i] == that.getBytesInternal()[i]);
+ }
+ return areEqual;
+ }
+
+ private static final long serialVersionUID = 0;
+ }
+
+ /**
+ * Creates a {@code HashCode} from a hexadecimal ({@code base 16}) encoded string. The string must
+ * be at least 2 characters long, and contain only valid, lower-cased hexadecimal characters.
+ *
+ * <p>This method accepts the exact format generated by {@link #toString}. If you require more
+ * lenient {@code base 16} decoding, please use {@link com.google.common.io.BaseEncoding#decode}
+ * (and pass the result to {@link #fromBytes}).
+ *
+ * @since 15.0
+ */
+ public static HashCode fromString(String string) {
+ checkArgument(
+ string.length() >= 2, "input string (%s) must have at least 2 characters", string);
+ checkArgument(
+ string.length() % 2 == 0,
+ "input string (%s) must have an even number of characters",
+ string);
+
+ byte[] bytes = new byte[string.length() / 2];
+ for (int i = 0; i < string.length(); i += 2) {
+ int ch1 = decode(string.charAt(i)) << 4;
+ int ch2 = decode(string.charAt(i + 1));
+ bytes[i / 2] = (byte) (ch1 + ch2);
+ }
+ return fromBytesNoCopy(bytes);
+ }
+
+ private static int decode(char ch) {
+ if (ch >= '0' && ch <= '9') {
+ return ch - '0';
+ }
+ if (ch >= 'a' && ch <= 'f') {
+ return ch - 'a' + 10;
+ }
+ throw new IllegalArgumentException("Illegal hexadecimal character: " + ch);
+ }
+
+ /**
+ * Returns {@code true} if {@code object} is a {@link HashCode} instance with the identical byte
+ * representation to this hash code.
+ *
+ * <p><b>Security note:</b> this method uses a constant-time (not short-circuiting) implementation
+ * to protect against <a href="http://en.wikipedia.org/wiki/Timing_attack">timing attacks</a>.
+ */
+ @Override
+ public final boolean equals(@CheckForNull Object object) {
+ if (object instanceof HashCode) {
+ HashCode that = (HashCode) object;
+ return bits() == that.bits() && equalsSameBits(that);
+ }
+ return false;
+ }
+
+ /**
+ * Returns a "Java hash code" for this {@code HashCode} instance; this is well-defined (so, for
+ * example, you can safely put {@code HashCode} instances into a {@code HashSet}) but is otherwise
+ * probably not what you want to use.
+ */
+ @Override
+ public final int hashCode() {
+ // If we have at least 4 bytes (32 bits), just take the first 4 bytes. Since this is
+ // already a (presumably) high-quality hash code, any four bytes of it will do.
+ if (bits() >= 32) {
+ return asInt();
+ }
+ // If we have less than 4 bytes, use them all.
+ byte[] bytes = getBytesInternal();
+ int val = (bytes[0] & 0xFF);
+ for (int i = 1; i < bytes.length; i++) {
+ val |= ((bytes[i] & 0xFF) << (i * 8));
+ }
+ return val;
+ }
+
+ /**
+ * Returns a string containing each byte of {@link #asBytes}, in order, as a two-digit unsigned
+ * hexadecimal number in lower case.
+ *
+ * <p>Note that if the output is considered to be a single hexadecimal number, whether this string
+ * is big-endian or little-endian depends on the byte order of {@link #asBytes}. This may be
+ * surprising for implementations of {@code HashCode} that represent the number in big-endian
+ * since everything else in the hashing API uniformly treats multibyte values as little-endian.
+ *
+ * <p>To create a {@code HashCode} from its string representation, see {@link #fromString}.
+ */
+ @Override
+ public final String toString() {
+ byte[] bytes = getBytesInternal();
+ StringBuilder sb = new StringBuilder(2 * bytes.length);
+ for (byte b : bytes) {
+ sb.append(hexDigits[(b >> 4) & 0xf]).append(hexDigits[b & 0xf]);
+ }
+ return sb.toString();
+ }
+
+ private static final char[] hexDigits = "0123456789abcdef".toCharArray();
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashFunction.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashFunction.java
new file mode 100644
index 0000000..a6ed525
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/HashFunction.java
@@ -0,0 +1,218 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import com.google.common.primitives.Ints;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+
+/**
+ * A hash function is a collision-averse pure function that maps an arbitrary block of data to a
+ * number called a <i>hash code</i>.
+ *
+ * <h3>Definition</h3>
+ *
+ * <p>Unpacking this definition:
+ *
+ * <ul>
+ * <li><b>block of data:</b> the input for a hash function is always, in concept, an ordered byte
+ * array. This hashing API accepts an arbitrary sequence of byte and multibyte values (via
+ * {@link Hasher}), but this is merely a convenience; these are always translated into raw
+ * byte sequences under the covers.
+ * <li><b>hash code:</b> each hash function always yields hash codes of the same fixed bit length
+ * (given by {@link #bits}). For example, {@link Hashing#sha1} produces a 160-bit number,
+ * while {@link Hashing#murmur3_32()} yields only 32 bits. Because a {@code long} value is
+ * clearly insufficient to hold all hash code values, this API represents a hash code as an
+ * instance of {@link HashCode}.
+ * <li><b>pure function:</b> the value produced must depend only on the input bytes, in the order
+ * they appear. Input data is never modified. {@link HashFunction} instances should always be
+ * stateless, and therefore thread-safe.
+ * <li><b>collision-averse:</b> while it can't be helped that a hash function will sometimes
+ * produce the same hash code for distinct inputs (a "collision"), every hash function strives
+ * to <i>some</i> degree to make this unlikely. (Without this condition, a function that
+ * always returns zero could be called a hash function. It is not.)
+ * </ul>
+ *
+ * <p>Summarizing the last two points: "equal yield equal <i>always</i>; unequal yield unequal
+ * <i>often</i>." This is the most important characteristic of all hash functions.
+ *
+ * <h3>Desirable properties</h3>
+ *
+ * <p>A high-quality hash function strives for some subset of the following virtues:
+ *
+ * <ul>
+ * <li><b>collision-resistant:</b> while the definition above requires making at least <i>some</i>
+ * token attempt, one measure of the quality of a hash function is <i>how well</i> it succeeds
+ * at this goal. Important note: it may be easy to achieve the theoretical minimum collision
+ * rate when using completely <i>random</i> sample input. The true test of a hash function is
+ * how it performs on representative real-world data, which tends to contain many hidden
+ * patterns and clumps. The goal of a good hash function is to stamp these patterns out as
+ * thoroughly as possible.
+ * <li><b>bit-dispersing:</b> masking out any <i>single bit</i> from a hash code should yield only
+ * the expected <i>twofold</i> increase to all collision rates. Informally, the "information"
+ * in the hash code should be as evenly "spread out" through the hash code's bits as possible.
+ * The result is that, for example, when choosing a bucket in a hash table of size 2^8,
+ * <i>any</i> eight bits could be consistently used.
+ * <li><b>cryptographic:</b> certain hash functions such as {@link Hashing#sha512} are designed to
+ * make it as infeasible as possible to reverse-engineer the input that produced a given hash
+ * code, or even to discover <i>any</i> two distinct inputs that yield the same result. These
+ * are called <i>cryptographic hash functions</i>. But, whenever it is learned that either of
+ * these feats has become computationally feasible, the function is deemed "broken" and should
+ * no longer be used for secure purposes. (This is the likely eventual fate of <i>all</i>
+ * cryptographic hashes.)
+ * <li><b>fast:</b> perhaps self-explanatory, but often the most important consideration.
+ * </ul>
+ *
+ * <h3>Providing input to a hash function</h3>
+ *
+ * <p>The primary way to provide the data that your hash function should act on is via a {@link
+ * Hasher}. Obtain a new hasher from the hash function using {@link #newHasher}, "push" the relevant
+ * data into it using methods like {@link Hasher#putBytes(byte[])}, and finally ask for the {@code
+ * HashCode} when finished using {@link Hasher#hash}. (See an {@linkplain #newHasher example} of
+ * this.)
+ *
+ * <p>If all you want to hash is a single byte array, string or {@code long} value, there are
+ * convenient shortcut methods defined directly on {@link HashFunction} to make this easier.
+ *
+ * <p>Hasher accepts primitive data types, but can also accept any Object of type {@code T} provided
+ * that you implement a {@link Funnel}{@code <T>} to specify how to "feed" data from that object
+ * into the function. (See {@linkplain Hasher#putObject an example} of this.)
+ *
+ * <p><b>Compatibility note:</b> Throughout this API, multibyte values are always interpreted in
+ * <i>little-endian</i> order. That is, hashing the byte array {@code {0x01, 0x02, 0x03, 0x04}} is
+ * equivalent to hashing the {@code int} value {@code 0x04030201}. If this isn't what you need,
+ * methods such as {@link Integer#reverseBytes} and {@link Ints#toByteArray} will help.
+ *
+ * <h3>Relationship to {@link Object#hashCode}</h3>
+ *
+ * <p>Java's baked-in concept of hash codes is constrained to 32 bits, and provides no separation
+ * between hash algorithms and the data they act on, so alternate hash algorithms can't be easily
+ * substituted. Also, implementations of {@code hashCode} tend to be poor-quality, in part because
+ * they end up depending on <i>other</i> existing poor-quality {@code hashCode} implementations,
+ * including those in many JDK classes.
+ *
+ * <p>{@code Object.hashCode} implementations tend to be very fast, but have weak collision
+ * prevention and <i>no</i> expectation of bit dispersion. This leaves them perfectly suitable for
+ * use in hash tables, because extra collisions cause only a slight performance hit, while poor bit
+ * dispersion is easily corrected using a secondary hash function (which all reasonable hash table
+ * implementations in Java use). For the many uses of hash functions beyond data structures,
+ * however, {@code Object.hashCode} almost always falls short -- hence this library.
+ *
+ * @author Kevin Bourrillion
+ * @since 11.0
+ */
+public interface HashFunction {
+ /**
+ * Begins a new hash code computation by returning an initialized, stateful {@code Hasher}
+ * instance that is ready to receive data. Example:
+ *
+ * <pre>{@code
+ * HashFunction hf = Hashing.md5();
+ * HashCode hc = hf.newHasher()
+ * .putLong(id)
+ * .putBoolean(isActive)
+ * .hash();
+ * }</pre>
+ */
+ Hasher newHasher();
+
+ /**
+ * Begins a new hash code computation as {@link #newHasher()}, but provides a hint of the expected
+ * size of the input (in bytes). This is only important for non-streaming hash functions (hash
+ * functions that need to buffer their whole input before processing any of it).
+ */
+ Hasher newHasher(int expectedInputSize);
+
+ /**
+ * Shortcut for {@code newHasher().putInt(input).hash()}; returns the hash code for the given
+ * {@code int} value, interpreted in little-endian byte order. The implementation <i>might</i>
+ * perform better than its longhand equivalent, but should not perform worse.
+ *
+ * @since 12.0
+ */
+ HashCode hashInt(int input);
+
+ /**
+ * Shortcut for {@code newHasher().putLong(input).hash()}; returns the hash code for the given
+ * {@code long} value, interpreted in little-endian byte order. The implementation <i>might</i>
+ * perform better than its longhand equivalent, but should not perform worse.
+ */
+ HashCode hashLong(long input);
+
+ /**
+ * Shortcut for {@code newHasher().putBytes(input).hash()}. The implementation <i>might</i>
+ * perform better than its longhand equivalent, but should not perform worse.
+ */
+ HashCode hashBytes(byte[] input);
+
+ /**
+ * Shortcut for {@code newHasher().putBytes(input, off, len).hash()}. The implementation
+ * <i>might</i> perform better than its longhand equivalent, but should not perform worse.
+ *
+ * @throws IndexOutOfBoundsException if {@code off < 0} or {@code off + len > bytes.length} or
+ * {@code len < 0}
+ */
+ HashCode hashBytes(byte[] input, int off, int len);
+
+ /**
+ * Shortcut for {@code newHasher().putBytes(input).hash()}. The implementation <i>might</i>
+ * perform better than its longhand equivalent, but should not perform worse.
+ *
+ * @since 23.0
+ */
+ HashCode hashBytes(ByteBuffer input);
+
+ /**
+ * Shortcut for {@code newHasher().putUnencodedChars(input).hash()}. The implementation
+ * <i>might</i> perform better than its longhand equivalent, but should not perform worse. Note
+ * that no character encoding is performed; the low byte and high byte of each {@code char} are
+ * hashed directly (in that order).
+ *
+ * <p><b>Warning:</b> This method will produce different output than most other languages do when
+ * running the same hash function on the equivalent input. For cross-language compatibility, use
+ * {@link #hashString}, usually with a charset of UTF-8. For other use cases, use {@code
+ * hashUnencodedChars}.
+ *
+ * @since 15.0 (since 11.0 as hashString(CharSequence)).
+ */
+ HashCode hashUnencodedChars(CharSequence input);
+
+ /**
+ * Shortcut for {@code newHasher().putString(input, charset).hash()}. Characters are encoded using
+ * the given {@link Charset}. The implementation <i>might</i> perform better than its longhand
+ * equivalent, but should not perform worse.
+ *
+ * <p><b>Warning:</b> This method, which reencodes the input before hashing it, is useful only for
+ * cross-language compatibility. For other use cases, prefer {@link #hashUnencodedChars}, which is
+ * faster, produces the same output across Java releases, and hashes every {@code char} in the
+ * input, even if some are invalid.
+ */
+ HashCode hashString(CharSequence input, Charset charset);
+
+ /**
+ * Shortcut for {@code newHasher().putObject(instance, funnel).hash()}. The implementation
+ * <i>might</i> perform better than its longhand equivalent, but should not perform worse.
+ *
+ * @since 14.0
+ */
+ <T extends Object> HashCode hashObject(T instance, Funnel<? super T> funnel);
+
+ /**
+ * Returns the number of bits (a multiple of 32) that each hash code produced by this hash
+ * function has.
+ */
+ int bits();
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hasher.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hasher.java
new file mode 100644
index 0000000..034753df
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hasher.java
@@ -0,0 +1,135 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+
+/**
+ * A {@link PrimitiveSink} that can compute a hash code after reading the input. Each hasher should
+ * translate all multibyte values ({@link #putInt(int)}, {@link #putLong(long)}, etc) to bytes in
+ * little-endian order.
+ *
+ * <p><b>Warning:</b> The result of calling any methods after calling {@link #hash} is undefined.
+ *
+ * <p><b>Warning:</b> Using a specific character encoding when hashing a {@link CharSequence} with
+ * {@link #putString(CharSequence, Charset)} is generally only useful for cross-language
+ * compatibility (otherwise prefer {@link #putUnencodedChars}). However, the character encodings
+ * must be identical across languages. Also beware that {@link Charset} definitions may occasionally
+ * change between Java releases.
+ *
+ * <p><b>Warning:</b> Chunks of data that are put into the {@link Hasher} are not delimited. The
+ * resulting {@link HashCode} is dependent only on the bytes inserted, and the order in which they
+ * were inserted, not how those bytes were chunked into discrete put() operations. For example, the
+ * following three expressions all generate colliding hash codes:
+ *
+ * <pre>{@code
+ * newHasher().putByte(b1).putByte(b2).putByte(b3).hash()
+ * newHasher().putByte(b1).putBytes(new byte[] { b2, b3 }).hash()
+ * newHasher().putBytes(new byte[] { b1, b2, b3 }).hash()
+ * }</pre>
+ *
+ * <p>If you wish to avoid this, you should either prepend or append the size of each chunk. Keep in
+ * mind that when dealing with char sequences, the encoded form of two concatenated char sequences
+ * is not equivalent to the concatenation of their encoded form. Therefore, {@link
+ * #putString(CharSequence, Charset)} should only be used consistently with <i>complete</i>
+ * sequences and not broken into chunks.
+ *
+ * @author Kevin Bourrillion
+ * @since 11.0
+ */
+public interface Hasher extends PrimitiveSink {
+ @Override
+ Hasher putByte(byte b);
+
+ @Override
+ Hasher putBytes(byte[] bytes);
+
+ @Override
+ Hasher putBytes(byte[] bytes, int off, int len);
+
+ @Override
+ Hasher putBytes(ByteBuffer bytes);
+
+ @Override
+ Hasher putShort(short s);
+
+ @Override
+ Hasher putInt(int i);
+
+ @Override
+ Hasher putLong(long l);
+
+ /** Equivalent to {@code putInt(Float.floatToRawIntBits(f))}. */
+ @Override
+ Hasher putFloat(float f);
+
+ /** Equivalent to {@code putLong(Double.doubleToRawLongBits(d))}. */
+ @Override
+ Hasher putDouble(double d);
+
+ /** Equivalent to {@code putByte(b ? (byte) 1 : (byte) 0)}. */
+ @Override
+ Hasher putBoolean(boolean b);
+
+ @Override
+ Hasher putChar(char c);
+
+ /**
+ * Equivalent to processing each {@code char} value in the {@code CharSequence}, in order. In
+ * other words, no character encoding is performed; the low byte and high byte of each {@code
+ * char} are hashed directly (in that order). The input must not be updated while this method is
+ * in progress.
+ *
+ * <p><b>Warning:</b> This method will produce different output than most other languages do when
+ * running the same hash function on the equivalent input. For cross-language compatibility, use
+ * {@link #putString}, usually with a charset of UTF-8. For other use cases, use {@code
+ * putUnencodedChars}.
+ *
+ * @since 15.0 (since 11.0 as putString(CharSequence)).
+ */
+ @Override
+ Hasher putUnencodedChars(CharSequence charSequence);
+
+ /**
+ * Equivalent to {@code putBytes(charSequence.toString().getBytes(charset))}.
+ *
+ * <p><b>Warning:</b> This method, which reencodes the input before hashing it, is useful only for
+ * cross-language compatibility. For other use cases, prefer {@link #putUnencodedChars}, which is
+ * faster, produces the same output across Java releases, and hashes every {@code char} in the
+ * input, even if some are invalid.
+ */
+ @Override
+ Hasher putString(CharSequence charSequence, Charset charset);
+
+ /** A simple convenience for {@code funnel.funnel(object, this)}. */
+ <T extends Object> Hasher putObject(T instance, Funnel<? super T> funnel);
+
+ /**
+ * Computes a hash code based on the data that have been provided to this hasher. The result is
+ * unspecified if this method is called more than once on the same instance.
+ */
+ HashCode hash();
+
+ /**
+ * {@inheritDoc}
+ *
+ * @deprecated This returns {@link Object#hashCode()}; you almost certainly mean to call {@code
+ * hash().asInt()}.
+ */
+ @Override
+ @Deprecated
+ int hashCode();
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hashing.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hashing.java
new file mode 100644
index 0000000..6a350dd
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Hashing.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+/**
+ * Static methods to obtain {@link HashFunction} instances, and other static hashing-related
+ * utilities.
+ *
+ * <p>A comparison of the various hash functions can be found <a
+ * href="http://goo.gl/jS7HH">here</a>.
+ *
+ * @author Kevin Bourrillion
+ * @author Dimitris Andreou
+ * @author Kurt Alfred Kluever
+ * @since 11.0
+ */
+public final class Hashing {
+ /**
+ * Used to randomize {@link #goodFastHash} instances, so that programs which persist anything
+ * dependent on the hash codes they produce will fail sooner.
+ */
+ @SuppressWarnings("GoodTime") // reading system time without TimeSource
+ static final int GOOD_FAST_HASH_SEED = (int) System.currentTimeMillis();
+
+ /**
+ * Returns a hash function implementing the <a
+ * href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">128-bit murmur3
+ * algorithm, x64 variant</a> (little-endian variant), using a seed value of zero.
+ *
+ * <p>The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).
+ */
+ public static HashFunction murmur3_128() {
+ return Murmur3_128HashFunction.MURMUR3_128;
+ }
+
+ private Hashing() {}
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/Java8Compatibility.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Java8Compatibility.java
new file mode 100644
index 0000000..ee8e9e8
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Java8Compatibility.java
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2020 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.nio.Buffer;
+
+/**
+ * Wrappers around {@link Buffer} methods that are covariantly overridden in Java 9+. See
+ * https://github.com/google/guava/issues/3990
+ */
+final class Java8Compatibility {
+ static void clear(Buffer b) {
+ b.clear();
+ }
+
+ static void flip(Buffer b) {
+ b.flip();
+ }
+
+ static void limit(Buffer b, int limit) {
+ b.limit(limit);
+ }
+
+ static void position(Buffer b, int position) {
+ b.position(position);
+ }
+
+ private Java8Compatibility() {}
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/Murmur3_128HashFunction.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Murmur3_128HashFunction.java
new file mode 100644
index 0000000..fddb59a
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/Murmur3_128HashFunction.java
@@ -0,0 +1,225 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+/*
+ * MurmurHash3 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code.
+ */
+
+/*
+ * Source:
+ * https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ * (Modified to adapt to Guava coding conventions and to use the HashFunction interface)
+ */
+
+package com.google.common.hash;
+
+import javax.annotation.CheckForNull;
+
+import java.io.Serializable;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+
+/**
+ * See MurmurHash3_x64_128 in <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">the
+ * C++ implementation</a>.
+ *
+ * @author Austin Appleby
+ * @author Dimitris Andreou
+ */
+final class Murmur3_128HashFunction extends AbstractHashFunction implements Serializable {
+ static final HashFunction MURMUR3_128 = new Murmur3_128HashFunction(0);
+
+ static final HashFunction GOOD_FAST_HASH_128 =
+ new Murmur3_128HashFunction(Hashing.GOOD_FAST_HASH_SEED);
+
+ // TODO(user): when the shortcuts are implemented, update BloomFilterStrategies
+ private final int seed;
+
+ Murmur3_128HashFunction(int seed) {
+ this.seed = seed;
+ }
+
+ @Override
+ public int bits() {
+ return 128;
+ }
+
+ @Override
+ public Hasher newHasher() {
+ return new Murmur3_128Hasher(seed);
+ }
+
+ @Override
+ public String toString() {
+ return "Hashing.murmur3_128(" + seed + ")";
+ }
+
+ @Override
+ public boolean equals(@CheckForNull Object object) {
+ if (object instanceof Murmur3_128HashFunction) {
+ Murmur3_128HashFunction other = (Murmur3_128HashFunction) object;
+ return seed == other.seed;
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return getClass().hashCode() ^ seed;
+ }
+
+ private static final class Murmur3_128Hasher extends AbstractStreamingHasher {
+ private static final int CHUNK_SIZE = 16;
+ private static final long C1 = 0x87c37b91114253d5L;
+ private static final long C2 = 0x4cf5ad432745937fL;
+ private long h1;
+ private long h2;
+ private int length;
+
+ Murmur3_128Hasher(int seed) {
+ super(CHUNK_SIZE);
+ this.h1 = seed;
+ this.h2 = seed;
+ this.length = 0;
+ }
+
+ @Override
+ protected void process(ByteBuffer bb) {
+ long k1 = bb.getLong();
+ long k2 = bb.getLong();
+ bmix64(k1, k2);
+ length += CHUNK_SIZE;
+ }
+
+ private void bmix64(long k1, long k2) {
+ h1 ^= mixK1(k1);
+
+ h1 = Long.rotateLeft(h1, 27);
+ h1 += h2;
+ h1 = h1 * 5 + 0x52dce729;
+
+ h2 ^= mixK2(k2);
+
+ h2 = Long.rotateLeft(h2, 31);
+ h2 += h1;
+ h2 = h2 * 5 + 0x38495ab5;
+ }
+
+ @Override
+ protected void processRemaining(ByteBuffer bb) {
+ long k1 = 0;
+ long k2 = 0;
+ length += bb.remaining();
+ switch (bb.remaining()) {
+ case 15:
+ k2 ^= (long) toInt(bb.get(14)) << 48; // fall through
+ case 14:
+ k2 ^= (long) toInt(bb.get(13)) << 40; // fall through
+ case 13:
+ k2 ^= (long) toInt(bb.get(12)) << 32; // fall through
+ case 12:
+ k2 ^= (long) toInt(bb.get(11)) << 24; // fall through
+ case 11:
+ k2 ^= (long) toInt(bb.get(10)) << 16; // fall through
+ case 10:
+ k2 ^= (long) toInt(bb.get(9)) << 8; // fall through
+ case 9:
+ k2 ^= (long) toInt(bb.get(8)); // fall through
+ case 8:
+ k1 ^= bb.getLong();
+ break;
+ case 7:
+ k1 ^= (long) toInt(bb.get(6)) << 48; // fall through
+ case 6:
+ k1 ^= (long) toInt(bb.get(5)) << 40; // fall through
+ case 5:
+ k1 ^= (long) toInt(bb.get(4)) << 32; // fall through
+ case 4:
+ k1 ^= (long) toInt(bb.get(3)) << 24; // fall through
+ case 3:
+ k1 ^= (long) toInt(bb.get(2)) << 16; // fall through
+ case 2:
+ k1 ^= (long) toInt(bb.get(1)) << 8; // fall through
+ case 1:
+ k1 ^= (long) toInt(bb.get(0));
+ break;
+ default:
+ throw new AssertionError("Should never get here.");
+ }
+ h1 ^= mixK1(k1);
+ h2 ^= mixK2(k2);
+ }
+
+ @Override
+ protected HashCode makeHash() {
+ h1 ^= length;
+ h2 ^= length;
+
+ h1 += h2;
+ h2 += h1;
+
+ h1 = fmix64(h1);
+ h2 = fmix64(h2);
+
+ h1 += h2;
+ h2 += h1;
+
+ return HashCode.fromBytesNoCopy(
+ ByteBuffer.wrap(new byte[CHUNK_SIZE])
+ .order(ByteOrder.LITTLE_ENDIAN)
+ .putLong(h1)
+ .putLong(h2)
+ .array());
+ }
+
+ private static long fmix64(long k) {
+ k ^= k >>> 33;
+ k *= 0xff51afd7ed558ccdL;
+ k ^= k >>> 33;
+ k *= 0xc4ceb9fe1a85ec53L;
+ k ^= k >>> 33;
+ return k;
+ }
+
+ private static long mixK1(long k1) {
+ k1 *= C1;
+ k1 = Long.rotateLeft(k1, 31);
+ k1 *= C2;
+ return k1;
+ }
+
+ private static long mixK2(long k2) {
+ k2 *= C2;
+ k2 = Long.rotateLeft(k2, 33);
+ k2 *= C1;
+ return k2;
+ }
+ }
+
+ private static final long serialVersionUID = 0L;
+ private static final int UNSIGNED_MASK = 0xFF;
+
+ /**
+ * Returns the value of the given byte as an integer, when treated as unsigned. That is, returns
+ * {@code value + 256} if {@code value} is negative; {@code value} itself otherwise.
+ *
+ * <p><b>Java 8 users:</b> use {@link Byte#toUnsignedInt(byte)} instead.
+ *
+ * @since 6.0
+ */
+ public static int toInt(byte value) {
+ return value & UNSIGNED_MASK;
+ }
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/hash/PrimitiveSink.java b/iotdb-core/node-commons/src/main/java/com/google/common/hash/PrimitiveSink.java
new file mode 100644
index 0000000..cc08217
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/hash/PrimitiveSink.java
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.hash;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+
+/**
+ * An object which can receive a stream of primitive values.
+ *
+ * @author Kevin Bourrillion
+ * @since 12.0 (in 11.0 as {@code Sink})
+ */
+public interface PrimitiveSink {
+ /**
+ * Puts a byte into this sink.
+ *
+ * @param b a byte
+ * @return this instance
+ */
+ PrimitiveSink putByte(byte b);
+
+ /**
+ * Puts an array of bytes into this sink.
+ *
+ * @param bytes a byte array
+ * @return this instance
+ */
+ PrimitiveSink putBytes(byte[] bytes);
+
+ /**
+ * Puts a chunk of an array of bytes into this sink. {@code bytes[off]} is the first byte written,
+ * {@code bytes[off + len - 1]} is the last.
+ *
+ * @param bytes a byte array
+ * @param off the start offset in the array
+ * @param len the number of bytes to write
+ * @return this instance
+ * @throws IndexOutOfBoundsException if {@code off < 0} or {@code off + len > bytes.length} or
+ * {@code len < 0}
+ */
+ PrimitiveSink putBytes(byte[] bytes, int off, int len);
+
+ /**
+ * Puts the remaining bytes of a byte buffer into this sink. {@code bytes.position()} is the first
+ * byte written, {@code bytes.limit() - 1} is the last. The position of the buffer will be equal
+ * to the limit when this method returns.
+ *
+ * @param bytes a byte buffer
+ * @return this instance
+ * @since 23.0
+ */
+ PrimitiveSink putBytes(ByteBuffer bytes);
+
+ /** Puts a short into this sink. */
+ PrimitiveSink putShort(short s);
+
+ /** Puts an int into this sink. */
+ PrimitiveSink putInt(int i);
+
+ /** Puts a long into this sink. */
+ PrimitiveSink putLong(long l);
+
+ /** Puts a float into this sink. */
+ PrimitiveSink putFloat(float f);
+
+ /** Puts a double into this sink. */
+ PrimitiveSink putDouble(double d);
+
+ /** Puts a boolean into this sink. */
+ PrimitiveSink putBoolean(boolean b);
+
+ /** Puts a character into this sink. */
+ PrimitiveSink putChar(char c);
+
+ /**
+ * Puts each 16-bit code unit from the {@link CharSequence} into this sink.
+ *
+ * <p><b>Warning:</b> This method will produce different output than most other languages do when
+ * running on the equivalent input. For cross-language compatibility, use {@link #putString},
+ * usually with a charset of UTF-8. For other use cases, use {@code putUnencodedChars}.
+ *
+ * @since 15.0 (since 11.0 as putString(CharSequence))
+ */
+ PrimitiveSink putUnencodedChars(CharSequence charSequence);
+
+ /**
+ * Puts a string into this sink using the given charset.
+ *
+ * <p><b>Warning:</b> This method, which reencodes the input before processing it, is useful only
+ * for cross-language compatibility. For other use cases, prefer {@link #putUnencodedChars}, which
+ * is faster, produces the same output across Java releases, and processes every {@code char} in
+ * the input, even if some are invalid.
+ */
+ PrimitiveSink putString(CharSequence charSequence, Charset charset);
+}
diff --git a/iotdb-core/node-commons/src/main/java/com/google/common/primitives/Bytes.java b/iotdb-core/node-commons/src/main/java/com/google/common/primitives/Bytes.java
new file mode 100644
index 0000000..f512365
--- /dev/null
+++ b/iotdb-core/node-commons/src/main/java/com/google/common/primitives/Bytes.java
@@ -0,0 +1,448 @@
+/*
+ * Copyright (C) 2008 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.primitives;
+
+import javax.annotation.CheckForNull;
+
+import java.io.Serializable;
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.RandomAccess;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkElementIndex;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkPositionIndexes;
+
+/**
+ * Static utility methods pertaining to {@code byte} primitives, that are not already found in
+ * either {@link Byte} or {@link Arrays}, <i>and interpret bytes as neither signed nor unsigned</i>.
+ * The methods which specifically treat bytes as signed or unsigned are found in {@link SignedBytes}
+ * and {@link UnsignedBytes}.
+ *
+ * <p>See the Guava User Guide article on <a
+ * href="https://github.com/google/guava/wiki/PrimitivesExplained">primitive utilities</a>.
+ *
+ * @author Kevin Bourrillion
+ * @since 1.0
+ */
+// TODO(kevinb): how to prevent warning on UnsignedBytes when building GWT
+// javadoc?
+public final class Bytes {
+ private Bytes() {}
+
+ /**
+ * Returns a hash code for {@code value}; equal to the result of invoking {@code ((Byte)
+ * value).hashCode()}.
+ *
+ * <p><b>Java 8 users:</b> use {@link Byte#hashCode(byte)} instead.
+ *
+ * @param value a primitive {@code byte} value
+ * @return a hash code for the value
+ */
+ public static int hashCode(byte value) {
+ return value;
+ }
+
+ /**
+ * Returns {@code true} if {@code target} is present as an element anywhere in {@code array}.
+ *
+ * @param array an array of {@code byte} values, possibly empty
+ * @param target a primitive {@code byte} value
+ * @return {@code true} if {@code array[i] == target} for some value of {@code i}
+ */
+ public static boolean contains(byte[] array, byte target) {
+ for (byte value : array) {
+ if (value == target) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns the index of the first appearance of the value {@code target} in {@code array}.
+ *
+ * @param array an array of {@code byte} values, possibly empty
+ * @param target a primitive {@code byte} value
+ * @return the least index {@code i} for which {@code array[i] == target}, or {@code -1} if no
+ * such index exists.
+ */
+ public static int indexOf(byte[] array, byte target) {
+ return indexOf(array, target, 0, array.length);
+ }
+
+ // TODO(kevinb): consider making this public
+ private static int indexOf(byte[] array, byte target, int start, int end) {
+ for (int i = start; i < end; i++) {
+ if (array[i] == target) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ /**
+ * Returns the start position of the first occurrence of the specified {@code target} within
+ * {@code array}, or {@code -1} if there is no such occurrence.
+ *
+ * <p>More formally, returns the lowest index {@code i} such that {@code Arrays.copyOfRange(array,
+ * i, i + target.length)} contains exactly the same elements as {@code target}.
+ *
+ * @param array the array to search for the sequence {@code target}
+ * @param target the array to search for as a sub-sequence of {@code array}
+ */
+ public static int indexOf(byte[] array, byte[] target) {
+ checkNotNull(array, "array");
+ checkNotNull(target, "target");
+ if (target.length == 0) {
+ return 0;
+ }
+
+ outer:
+ for (int i = 0; i < array.length - target.length + 1; i++) {
+ for (int j = 0; j < target.length; j++) {
+ if (array[i + j] != target[j]) {
+ continue outer;
+ }
+ }
+ return i;
+ }
+ return -1;
+ }
+
+ /**
+ * Returns the index of the last appearance of the value {@code target} in {@code array}.
+ *
+ * @param array an array of {@code byte} values, possibly empty
+ * @param target a primitive {@code byte} value
+ * @return the greatest index {@code i} for which {@code array[i] == target}, or {@code -1} if no
+ * such index exists.
+ */
+ public static int lastIndexOf(byte[] array, byte target) {
+ return lastIndexOf(array, target, 0, array.length);
+ }
+
+ // TODO(kevinb): consider making this public
+ private static int lastIndexOf(byte[] array, byte target, int start, int end) {
+ for (int i = end - 1; i >= start; i--) {
+ if (array[i] == target) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ /**
+ * Returns the values from each provided array combined into a single array. For example, {@code
+ * concat(new byte[] {a, b}, new byte[] {}, new byte[] {c}} returns the array {@code {a, b, c}}.
+ *
+ * @param arrays zero or more {@code byte} arrays
+ * @return a single array containing all the values from the source arrays, in order
+ */
+ public static byte[] concat(byte[]... arrays) {
+ int length = 0;
+ for (byte[] array : arrays) {
+ length += array.length;
+ }
+ byte[] result = new byte[length];
+ int pos = 0;
+ for (byte[] array : arrays) {
+ System.arraycopy(array, 0, result, pos, array.length);
+ pos += array.length;
+ }
+ return result;
+ }
+
+ /**
+ * Returns an array containing the same values as {@code array}, but guaranteed to be of a
+ * specified minimum length. If {@code array} already has a length of at least {@code minLength},
+ * it is returned directly. Otherwise, a new array of size {@code minLength + padding} is
+ * returned, containing the values of {@code array}, and zeroes in the remaining places.
+ *
+ * @param array the source array
+ * @param minLength the minimum length the returned array must guarantee
+ * @param padding an extra amount to "grow" the array by if growth is necessary
+ * @throws IllegalArgumentException if {@code minLength} or {@code padding} is negative
+ * @return an array containing the values of {@code array}, with guaranteed minimum length {@code
+ * minLength}
+ */
+ public static byte[] ensureCapacity(byte[] array, int minLength, int padding) {
+ checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
+ checkArgument(padding >= 0, "Invalid padding: %s", padding);
+ return (array.length < minLength) ? Arrays.copyOf(array, minLength + padding) : array;
+ }
+
+ /**
+ * Returns an array containing each value of {@code collection}, converted to a {@code byte} value
+ * in the manner of {@link Number#byteValue}.
+ *
+ * <p>Elements are copied from the argument collection as if by {@code collection.toArray()}.
+ * Calling this method is as thread-safe as calling that method.
+ *
+ * @param collection a collection of {@code Number} instances
+ * @return an array containing the same values as {@code collection}, in the same order, converted
+ * to primitives
+ * @throws NullPointerException if {@code collection} or any of its elements is null
+ * @since 1.0 (parameter was {@code Collection<Byte>} before 12.0)
+ */
+ public static byte[] toArray(Collection<? extends Number> collection) {
+ if (collection instanceof ByteArrayAsList) {
+ return ((ByteArrayAsList) collection).toByteArray();
+ }
+
+ Object[] boxedArray = collection.toArray();
+ int len = boxedArray.length;
+ byte[] array = new byte[len];
+ for (int i = 0; i < len; i++) {
+ // checkNotNull for GWT (do not optimize)
+ array[i] = ((Number) checkNotNull(boxedArray[i])).byteValue();
+ }
+ return array;
+ }
+
+ /**
+ * Returns a fixed-size list backed by the specified array, similar to {@link
+ * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)}, but any attempt to
+ * set a value to {@code null} will result in a {@link NullPointerException}.
+ *
+ * <p>The returned list maintains the values, but not the identities, of {@code Byte} objects
+ * written to or read from it. For example, whether {@code list.get(0) == list.get(0)} is true for
+ * the returned list is unspecified.
+ *
+ * <p>The returned list is serializable.
+ *
+ * @param backingArray the array to back the list
+ * @return a list view of the array
+ */
+ public static List<Byte> asList(byte... backingArray) {
+ if (backingArray.length == 0) {
+ return Collections.emptyList();
+ }
+ return new ByteArrayAsList(backingArray);
+ }
+
+ private static class ByteArrayAsList extends AbstractList<Byte>
+ implements RandomAccess, Serializable {
+ final byte[] array;
+ final int start;
+ final int end;
+
+ ByteArrayAsList(byte[] array) {
+ this(array, 0, array.length);
+ }
+
+ ByteArrayAsList(byte[] array, int start, int end) {
+ this.array = array;
+ this.start = start;
+ this.end = end;
+ }
+
+ @Override
+ public int size() {
+ return end - start;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return false;
+ }
+
+ @Override
+ public Byte get(int index) {
+ checkElementIndex(index, size());
+ return array[start + index];
+ }
+
+ @Override
+ public boolean contains(@CheckForNull Object target) {
+ // Overridden to prevent a ton of boxing
+ return (target instanceof Byte) && Bytes.indexOf(array, (Byte) target, start, end) != -1;
+ }
+
+ @Override
+ public int indexOf(@CheckForNull Object target) {
+ // Overridden to prevent a ton of boxing
+ if (target instanceof Byte) {
+ int i = Bytes.indexOf(array, (Byte) target, start, end);
+ if (i >= 0) {
+ return i - start;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public int lastIndexOf(@CheckForNull Object target) {
+ // Overridden to prevent a ton of boxing
+ if (target instanceof Byte) {
+ int i = Bytes.lastIndexOf(array, (Byte) target, start, end);
+ if (i >= 0) {
+ return i - start;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public Byte set(int index, Byte element) {
+ checkElementIndex(index, size());
+ byte oldValue = array[start + index];
+ // checkNotNull for GWT (do not optimize)
+ array[start + index] = checkNotNull(element);
+ return oldValue;
+ }
+
+ @Override
+ public List<Byte> subList(int fromIndex, int toIndex) {
+ int size = size();
+ checkPositionIndexes(fromIndex, toIndex, size);
+ if (fromIndex == toIndex) {
+ return Collections.emptyList();
+ }
+ return new ByteArrayAsList(array, start + fromIndex, start + toIndex);
+ }
+
+ @Override
+ public boolean equals(@CheckForNull Object object) {
+ if (object == this) {
+ return true;
+ }
+ if (object instanceof ByteArrayAsList) {
+ ByteArrayAsList that = (ByteArrayAsList) object;
+ int size = size();
+ if (that.size() != size) {
+ return false;
+ }
+ for (int i = 0; i < size; i++) {
+ if (array[start + i] != that.array[that.start + i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return super.equals(object);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = 1;
+ for (int i = start; i < end; i++) {
+ result = 31 * result + Bytes.hashCode(array[i]);
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder(size() * 5);
+ builder.append('[').append(array[start]);
+ for (int i = start + 1; i < end; i++) {
+ builder.append(", ").append(array[i]);
+ }
+ return builder.append(']').toString();
+ }
+
+ byte[] toByteArray() {
+ return Arrays.copyOfRange(array, start, end);
+ }
+
+ private static final long serialVersionUID = 0;
+ }
+
+ /**
+ * Reverses the elements of {@code array}. This is equivalent to {@code
+ * Collections.reverse(Bytes.asList(array))}, but is likely to be more efficient.
+ *
+ * @since 23.1
+ */
+ public static void reverse(byte[] array) {
+ checkNotNull(array);
+ reverse(array, 0, array.length);
+ }
+
+ /**
+ * Reverses the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex}
+ * exclusive. This is equivalent to {@code
+ * Collections.reverse(Bytes.asList(array).subList(fromIndex, toIndex))}, but is likely to be more
+ * efficient.
+ *
+ * @throws IndexOutOfBoundsException if {@code fromIndex < 0}, {@code toIndex > array.length}, or
+ * {@code toIndex > fromIndex}
+ * @since 23.1
+ */
+ public static void reverse(byte[] array, int fromIndex, int toIndex) {
+ checkNotNull(array);
+ checkPositionIndexes(fromIndex, toIndex, array.length);
+ for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
+ byte tmp = array[i];
+ array[i] = array[j];
+ array[j] = tmp;
+ }
+ }
+
+ /**
+ * Performs a right rotation of {@code array} of "distance" places, so that the first element is
+ * moved to index "distance", and the element at index {@code i} ends up at index {@code (distance
+ * + i) mod array.length}. This is equivalent to {@code Collections.rotate(Bytes.asList(array),
+ * distance)}, but is somewhat faster.
+ *
+ * <p>The provided "distance" may be negative, which will rotate left.
+ *
+ * @since 32.0.0
+ */
+ public static void rotate(byte[] array, int distance) {
+ rotate(array, distance, 0, array.length);
+ }
+
+ /**
+ * Performs a right rotation of {@code array} between {@code fromIndex} inclusive and {@code
+ * toIndex} exclusive. This is equivalent to {@code
+ * Collections.rotate(Bytes.asList(array).subList(fromIndex, toIndex), distance)}, but is somewhat
+ * faster.
+ *
+ * <p>The provided "distance" may be negative, which will rotate left.
+ *
+ * @throws IndexOutOfBoundsException if {@code fromIndex < 0}, {@code toIndex > array.length}, or
+ * {@code toIndex > fromIndex}
+ * @since 32.0.0
+ */
+ public static void rotate(byte[] array, int distance, int fromIndex, int toIndex) {
+ // See Ints.rotate for more details about possible algorithms here.
+ checkNotNull(array);
+ checkPositionIndexes(fromIndex, toIndex, array.length);
+ if (array.length <= 1) {
+ return;
+ }
+
+ int length = toIndex - fromIndex;
+ // Obtain m = (-distance mod length), a non-negative value less than "length". This is how many
+ // places left to rotate.
+ int m = -distance % length;
+ m = (m < 0) ? m + length : m;
+ // The current index of what will become the first element of the rotated section.
+ int newFirstIndex = m + fromIndex;
+ if (newFirstIndex == fromIndex) {
+ return;
+ }
+
+ reverse(array, fromIndex, newFirstIndex);
+ reverse(array, newFirstIndex, toIndex);
+ reverse(array, fromIndex, toIndex);
+ }
+}
