This is an automated email from the ASF dual-hosted git repository. jhyde pushed a commit to branch main in repository https://gitbox.apache.org/repos/asf/calcite.git
commit 4219c993b642f7ba66f7b9a28a66f4616eb1168a Author: Julian Hyde <[email protected]> AuthorDate: Tue Feb 7 11:16:34 2023 -0800 [CALCITE-5706] Add class PairList `PairList` is a list whose entries are pairs (`interface Map.Entry`). Its implementation is efficient (backed by a single list, where the left and right parts of each pair are stored in even, odd positions). In addition to the usual `List` methods, there are additional methods for pairs: `add(K, V)`, `leftList()`, `rightList()`, `toImmutableMap()`, `forEach(BiConsumer<K, V>)`, `forEach(IndexedBiConsumer<K, V>)`, By default `PairList` is immutable, but using the method `PairList.immutable()` you can override the backing list and create an immutable `PairList`. --- .../java/org/apache/calcite/runtime/PairList.java | 178 +++++++++++++++++++++ .../java/org/apache/calcite/util/PairListTest.java | 126 +++++++++++++++ 2 files changed, 304 insertions(+) diff --git a/core/src/main/java/org/apache/calcite/runtime/PairList.java b/core/src/main/java/org/apache/calcite/runtime/PairList.java new file mode 100644 index 0000000000..c3cfaf14e2 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/runtime/PairList.java @@ -0,0 +1,178 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you 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 org.apache.calcite.runtime; + +import org.apache.calcite.util.Pair; +import org.apache.calcite.util.Util; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableMap; + +import org.checkerframework.checker.nullness.qual.Nullable; + +import java.util.AbstractList; +import java.util.ArrayList; +import java.util.List; +import java.util.Map; +import java.util.function.BiConsumer; + +import static java.util.Objects.requireNonNull; + +/** A list of pairs, stored as a quotient list. + * + * @param <T> First type + * @param <U> Second type + */ +public class PairList<T, U> extends AbstractList<Map.Entry<T, U>> { + final List<@Nullable Object> list; + + private PairList(List<@Nullable Object> list) { + this.list = list; + } + + /** Creates an empty PairList. */ + public static <T, U> PairList<T, U> of() { + return new PairList<>(new ArrayList<>()); + } + + /** Creates a PairList backed by a given list. + * + * <p>Changes to the backing list will be reflected in the PairList. + * If the backing list is immutable, this PairList will be also. */ + public static <T, U> PairList<T, U> backedBy(List<@Nullable Object> list) { + return new PairList<>(list); + } + + /** Creates a PairList from a Map. */ + @SuppressWarnings("RedundantCast") + public static <T, U> PairList<T, U> of(Map<T, U> map) { + final List<@Nullable Object> list = new ArrayList<>(map.size() * 2); + map.forEach((t, u) -> { + list.add((Object) t); + list.add((Object) u); + }); + return new PairList<>(list); + } + + @SuppressWarnings("unchecked") + @Override public Map.Entry<T, U> get(int index) { + int x = index * 2; + return Pair.of((T) list.get(x), (U) list.get(x + 1)); + } + + @Override public int size() { + return list.size() / 2; + } + + @SuppressWarnings("RedundantCast") + @Override public boolean add(Map.Entry<T, U> entry) { + list.add((Object) entry.getKey()); + list.add((Object) entry.getValue()); + return true; + } + + @SuppressWarnings("RedundantCast") + @Override public void add(int index, Map.Entry<T, U> entry) { + int x = index * 2; + list.add(x, (Object) entry.getKey()); + list.add(x + 1, (Object) entry.getValue()); + } + + /** Adds a pair to this list. */ + @SuppressWarnings("RedundantCast") + public void add(T t, U u) { + list.add((Object) t); + list.add((Object) u); + } + + @SuppressWarnings("unchecked") + @Override public Map.Entry<T, U> remove(int index) { + final int x = index * 2; + T t = (T) list.remove(x); + U u = (U) list.remove(x); + return Pair.of(t, u); + } + + /** Returns an unmodifiable list view consisting of the left entry of each + * pair. */ + @SuppressWarnings("unchecked") + public List<T> leftList() { + return Util.quotientList((List<T>) list, 2, 0); + } + + /** Returns an unmodifiable list view consisting of the right entry of each + * pair. */ + @SuppressWarnings("unchecked") + public List<U> rightList() { + return Util.quotientList((List<U>) list, 2, 1); + } + + /** Calls a BiConsumer with each pair in this list. */ + @SuppressWarnings("unchecked") + public void forEach(BiConsumer<T, U> consumer) { + requireNonNull(consumer, "consumer"); + for (int i = 0; i < list.size();) { + T t = (T) list.get(i++); + U u = (U) list.get(i++); + consumer.accept(t, u); + } + } + + /** Calls a BiConsumer with each pair in this list. */ + @SuppressWarnings("unchecked") + public void forEachIndexed(IndexedBiConsumer<T, U> consumer) { + requireNonNull(consumer, "consumer"); + for (int i = 0, j = 0; i < list.size();) { + T t = (T) list.get(i++); + U u = (U) list.get(i++); + consumer.accept(j++, t, u); + } + } + + /** Creates an {@link ImmutableMap} whose entries are the pairs in this list. + * Throws if keys are not unique. */ + public ImmutableMap<T, U> toImmutableMap() { + final ImmutableMap.Builder<T, U> b = ImmutableMap.builder(); + forEach((t, u) -> b.put(t, u)); + return b.build(); + } + + /** Returns an immutable PairList whose contents are the same as this + * PairList. */ + public PairList<T, U> immutable() { + final List<@Nullable Object> immutableList = ImmutableList.copyOf(list); + return backedBy(immutableList); + } + + /** Action to be taken each step of an indexed iteration over a PairList. + * + * @param <T> First type + * @param <U> Second type + * + * @see PairList#forEachIndexed(IndexedBiConsumer) + */ + public interface IndexedBiConsumer<T, U> { + /** + * Performs this operation on the given arguments. + * + * @param index Index + * @param t First input argument + * @param u Second input argument + */ + void accept(int index, T t, U u); + } +} diff --git a/core/src/test/java/org/apache/calcite/util/PairListTest.java b/core/src/test/java/org/apache/calcite/util/PairListTest.java new file mode 100644 index 0000000000..3029475a89 --- /dev/null +++ b/core/src/test/java/org/apache/calcite/util/PairListTest.java @@ -0,0 +1,126 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you 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 org.apache.calcite.util; + +import org.apache.calcite.runtime.PairList; + +import com.google.common.collect.ImmutableMap; + +import org.junit.jupiter.api.Test; + +import java.util.ArrayList; +import java.util.List; +import java.util.Map; + +import static org.hamcrest.CoreMatchers.is; +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.hasSize; +import static org.junit.jupiter.api.Assertions.assertThrows; + +/** Unit test for {@code PairList}. */ +class PairListTest { + /** Basic test for {@link PairList}. */ + @Test void testPairList() { + final PairList<Integer, String> pairList = PairList.of(); + final List<Pair<Integer, String>> list = new ArrayList<>(); + + final Runnable validator = () -> { + assertThat(pairList.isEmpty(), is(list.isEmpty())); + assertThat(pairList, hasSize(list.size())); + assertThat(pairList.leftList(), hasSize(list.size())); + assertThat(pairList.rightList(), hasSize(list.size())); + assertThat(pairList.leftList(), is(Pair.left(list))); + assertThat(pairList.rightList(), is(Pair.right(list))); + + final List<Map.Entry<Integer, String>> list2 = new ArrayList<>(pairList); + assertThat(list2, is(list)); + + // Check PairList.forEach(Consumer) + list2.clear(); + //noinspection UseBulkOperation + pairList.forEach(p -> list2.add(p)); + assertThat(list2, is(list)); + + // Check PairList.forEach(BiConsumer) + list2.clear(); + pairList.forEach((k, v) -> list2.add(Pair.of(k, v))); + assertThat(list2, is(list)); + + // Check PairList.forEachIndexed + list2.clear(); + pairList.forEachIndexed((i, k, v) -> { + assertThat(i, is(list2.size())); + list2.add(Pair.of(k, v)); + }); + assertThat(list2, is(list)); + + final PairList<Integer, String> immutablePairList = pairList.immutable(); + assertThat(immutablePairList, hasSize(list.size())); + assertThat(immutablePairList, is(list)); + assertThrows(UnsupportedOperationException.class, () -> + immutablePairList.add(0, "")); + list2.clear(); + immutablePairList.forEach((k, v) -> list2.add(Pair.of(k, v))); + assertThat(list2, is(list)); + }; + + validator.run(); + + pairList.add(1, "a"); + list.add(Pair.of(1, "a")); + validator.run(); + + pairList.add(Pair.of(2, "b")); + list.add(Pair.of(2, "b")); + validator.run(); + + pairList.add(0, Pair.of(3, "c")); + list.add(0, Pair.of(3, "c")); + validator.run(); + + Map.Entry<Integer, String> x = pairList.remove(1); + Pair<Integer, String> y = list.remove(1); + assertThat(x, is(y)); + validator.run(); + + pairList.clear(); + list.clear(); + validator.run(); + } + + /** Tests {@link PairList#of(Map)} and {@link PairList#toImmutableMap()}. */ + @Test void testPairListOfMap() { + final ImmutableMap<String, Integer> map = ImmutableMap.of("a", 1, "b", 2); + final PairList<String, Integer> list = PairList.of(map); + assertThat(list, hasSize(2)); + assertThat(list.toString(), is("[<a, 1>, <b, 2>]")); + + final ImmutableMap<String, Integer> map2 = list.toImmutableMap(); + assertThat(map2, is(map)); + + // After calling toImmutableMap, you can modify the list and call + // toImmutableMap again. + list.add("c", 3); + assertThat(list.toString(), is("[<a, 1>, <b, 2>, <c, 3>]")); + final ImmutableMap<String, Integer> map3 = list.toImmutableMap(); + assertThat(map3.toString(), is("{a=1, b=2, c=3}")); + + final Map<String, Integer> emptyMap = ImmutableMap.of(); + final PairList<String, Integer> emptyList = PairList.of(emptyMap); + assertThat(emptyList.isEmpty(), is(true)); + } +}
