Pair.java
/*
* 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 org.checkerframework.checker.nullness.qual.Nullable;
import java.io.Serializable;
import java.util.AbstractList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.function.BiConsumer;
import static java.util.Objects.requireNonNull;
/**
* Pair of objects.
*
* <p>Because a pair implements {@link #equals(Object)}, {@link #hashCode()} and
* {@link #compareTo(Pair)}, it can be used in any kind of
* {@link java.util.Collection}.
*
* @param <T1> Left-hand type
* @param <T2> Right-hand type
*/
@SuppressWarnings("type.argument.type.incompatible")
public class Pair<T1, T2>
implements Comparable<Pair<T1, T2>>, Map.Entry<T1, T2>, Serializable {
@SuppressWarnings({"rawtypes", "unchecked"})
private static final Comparator NULLS_FIRST_COMPARATOR =
Comparator.nullsFirst((Comparator) Comparator.naturalOrder());
//~ Instance fields --------------------------------------------------------
public final T1 left;
public final T2 right;
//~ Constructors -----------------------------------------------------------
/**
* Creates a Pair.
*
* @param left left value
* @param right right value
*/
public Pair(T1 left, T2 right) {
this.left = left;
this.right = right;
}
/**
* Creates a Pair of appropriate type.
*
* <p>This is a shorthand that allows you to omit implicit types. For
* example, you can write:
* <blockquote>return Pair.of(s, n);</blockquote>
* instead of
* <blockquote>return new Pair<String, Integer>(s, n);</blockquote>
*
* @param left left value
* @param right right value
* @return A Pair
*/
public static <T1, T2> Pair<T1, T2> of(T1 left, T2 right) {
return new Pair<>(left, right);
}
/** Creates a {@code Pair} from a {@link java.util.Map.Entry}. */
public static <K, V> Pair<K, V> of(Map.Entry<? extends K, ? extends V> entry) {
return of(entry.getKey(), entry.getValue());
}
//~ Methods ----------------------------------------------------------------
@Override public boolean equals(@Nullable Object obj) {
return this == obj
|| (obj instanceof Map.Entry)
&& Objects.equals(this.left, ((Map.Entry) obj).getKey())
&& Objects.equals(this.right, ((Map.Entry) obj).getValue());
}
/** {@inheritDoc}
*
* <p>Computes hash code consistent with
* {@link java.util.Map.Entry#hashCode()}. */
@Override public int hashCode() {
int keyHash = left == null ? 0 : left.hashCode();
int valueHash = right == null ? 0 : right.hashCode();
return keyHash ^ valueHash;
}
@Override public int compareTo(Pair<T1, T2> that) {
//noinspection unchecked
int c = NULLS_FIRST_COMPARATOR.compare(this.left, that.left);
if (c == 0) {
//noinspection unchecked
c = NULLS_FIRST_COMPARATOR.compare(this.right, that.right);
}
return c;
}
@Override public String toString() {
return "<" + left + ", " + right + ">";
}
@Override public T1 getKey() {
return left;
}
@Override public T2 getValue() {
return right;
}
@Override public T2 setValue(T2 value) {
throw new UnsupportedOperationException();
}
/**
* Converts a collection of Pairs into a Map.
*
* <p>This is an obvious thing to do because Pair is similar in structure to
* {@link java.util.Map.Entry}.
*
* <p>The map contains a copy of the collection of Pairs; if you change the
* collection, the map does not change.
*
* @param pairs Collection of Pair objects
* @return map with the same contents as the collection
*/
public static <K, V> Map<K, V> toMap(Iterable<? extends Pair<? extends K, ? extends V>> pairs) {
final Map<K, V> map = new HashMap<>();
for (Pair<? extends K, ? extends V> pair : pairs) {
map.put(pair.left, pair.right);
}
return map;
}
/**
* Converts two lists into a list of {@link Pair}s,
* whose length is the lesser of the lengths of the
* source lists.
*
* @param ks Left list
* @param vs Right list
* @return List of pairs
* @see org.apache.calcite.linq4j.Ord#zip(java.util.List)
*/
public static <K, V> List<Pair<K, V>> zip(List<? extends K> ks, List<? extends V> vs) {
return zip(ks, vs, false);
}
/**
* Converts two lists into a list of {@link Pair}s.
*
* <p>The length of the combined list is the lesser of the lengths of the
* source lists. But typically the source lists will be the same length.
*
* @param ks Left list
* @param vs Right list
* @param strict Whether to fail if lists have different size
* @return List of pairs
* @see org.apache.calcite.linq4j.Ord#zip(java.util.List)
*/
public static <K, V> List<Pair<K, V>> zip(
final List<? extends K> ks,
final List<? extends V> vs,
boolean strict) {
final int size;
if (strict) {
if (ks.size() != vs.size()) {
throw new AssertionError();
}
size = ks.size();
} else {
size = Math.min(ks.size(), vs.size());
}
return new ZipList<>(ks, vs, size);
}
/**
* Converts two iterables into an iterable of {@link Pair}s.
*
* <p>The resulting iterator ends whenever the first of the input iterators
* ends. But typically the source iterators will be the same length.
*
* @param ks Left iterable
* @param vs Right iterable
* @return Iterable over pairs
*/
public static <K, V> Iterable<Pair<K, V>> zip(
final Iterable<? extends K> ks,
final Iterable<? extends V> vs) {
return () -> {
final Iterator<? extends K> kIterator = ks.iterator();
final Iterator<? extends V> vIterator = vs.iterator();
return new ZipIterator<>(kIterator, vIterator);
};
}
/**
* Converts two arrays into a list of {@link Pair}s.
*
* <p>The length of the combined list is the lesser of the lengths of the
* source arrays. But typically the source arrays will be the same
* length.
*
* @param ks Left array
* @param vs Right array
* @return List of pairs
*/
public static <K, V> List<Pair<K, V>> zip(
final K[] ks,
final V[] vs) {
return new AbstractList<Pair<K, V>>() {
@Override public Pair<K, V> get(int index) {
return Pair.of(ks[index], vs[index]);
}
@Override public int size() {
return Math.min(ks.length, vs.length);
}
};
}
/** Returns a mutable list of pairs backed by a pair of mutable lists.
*
* <p>Modifications to this list are reflected in the backing lists, and vice
* versa.
*
* @param <K> Key (left) value type
* @param <V> Value (right) value type */
public static <K, V> List<Pair<K, V>> zipMutable(
final List<K> ks,
final List<V> vs) {
return new MutableZipList<>(ks, vs);
}
/** Applies an action to every element of a pair of iterables.
*
* <p>Calls to the action stop whenever the first of the input iterators
* ends. But typically the source iterators will be the same length.
*
* @see Map#forEach(java.util.function.BiConsumer)
* @see org.apache.calcite.linq4j.Ord#forEach(Iterable, java.util.function.ObjIntConsumer)
*
* @param ks Left iterable
* @param vs Right iterable
* @param consumer The action to be performed for each element
*
* @param <K> Left type
* @param <V> Right type
*/
public static <K, V> void forEach(
final Iterable<? extends K> ks,
final Iterable<? extends V> vs,
BiConsumer<? super K, ? super V> consumer) {
final Iterator<? extends K> leftIterator = ks.iterator();
final Iterator<? extends V> rightIterator = vs.iterator();
while (leftIterator.hasNext() && rightIterator.hasNext()) {
consumer.accept(leftIterator.next(), rightIterator.next());
}
}
/** Calls a consumer with an ordinal for each pair of items in two
* iterables. */
public static <K, V> void forEachIndexed(Iterable<K> ks, Iterable<V> vs,
PairWithOrdinalConsumer<K, V> consumer) {
int i = 0;
final Iterator<K> ki = ks.iterator();
final Iterator<V> vi = vs.iterator();
while (ki.hasNext() && vi.hasNext()) {
consumer.accept(i++, ki.next(), vi.next());
}
}
/** Calls a consumer with an ordinal for each pair of items in an iterable
* of pairs. */
public static <K, V> void forEachIndexed(
Iterable<? extends Map.Entry<K, V>> pairs,
PairWithOrdinalConsumer<K, V> consumer) {
int i = 0;
for (Map.Entry<K, V> pair : pairs) {
consumer.accept(i++, pair.getKey(), pair.getValue());
}
}
/** Calls a consumer for each entry in a map. */
public static <K, V> void forEachIndexed(Map<K, V> map,
PairWithOrdinalConsumer<K, V> consumer) {
forEachIndexed(map.entrySet(), consumer);
}
/** Applies an action to every element of an iterable of pairs.
*
* @see Map#forEach(java.util.function.BiConsumer)
*
* @param entries Pairs
* @param consumer The action to be performed for each element
*
* @param <K> Left type
* @param <V> Right type
*/
public static <K, V> void forEach(
final Iterable<? extends Map.Entry<? extends K, ? extends V>> entries,
BiConsumer<? super K, ? super V> consumer) {
for (Map.Entry<? extends K, ? extends V> entry : entries) {
consumer.accept(entry.getKey(), entry.getValue());
}
}
/**
* Returns an iterable over the left slice of an iterable.
*
* @param iterable Iterable over pairs
* @param <L> Left type
* @param <R> Right type
* @return Iterable over the left elements
*/
public static <L, R> Iterable<L> left(
final Iterable<? extends Map.Entry<? extends L, ? extends R>> iterable) {
return Util.transform(iterable, Map.Entry::getKey);
}
/**
* Returns an iterable over the right slice of an iterable.
*
* @param iterable Iterable over pairs
* @param <L> right type
* @param <R> Right type
* @return Iterable over the right elements
*/
public static <L, R> Iterable<R> right(
final Iterable<? extends Map.Entry<? extends L, ? extends R>> iterable) {
return Util.transform(iterable, Map.Entry::getValue);
}
@SuppressWarnings("unchecked")
public static <K, V> List<K> left(
final List<? extends Map.Entry<? extends K, ? extends V>> pairs) {
if (pairs instanceof PairList) {
return ((PairList<K, V>) pairs).leftList();
}
return Util.transform(pairs, Map.Entry::getKey);
}
@SuppressWarnings("unchecked")
public static <K, V> List<V> right(
final List<? extends Map.Entry<? extends K, ? extends V>> pairs) {
if (pairs instanceof PairList) {
return ((PairList<K, V>) pairs).rightList();
}
return Util.transform(pairs, Map.Entry::getValue);
}
/**
* Returns an iterator that iterates over (i, i + 1) pairs in an iterable.
*
* <p>For example, {@code adjacents([3, 5, 7])} returns [(3, 5), (5, 7)].
*
* @param iterable Source collection
* @param <T> Element type
* @return Iterable over adjacent element pairs
*/
public static <T> Iterable<Pair<T, T>> adjacents(final Iterable<? extends T> iterable) {
return () -> {
final Iterator<? extends T> iterator = iterable.iterator();
if (!iterator.hasNext()) {
return Collections.emptyIterator();
}
return new AdjacentIterator<>(iterator);
};
}
/**
* Returns an iterator that iterates over (0, i) pairs in an iterable for
* i > 0.
*
* <p>For example, {@code firstAnd([3, 5, 7])} returns [(3, 5), (3, 7)].
*
* @param iterable Source collection
* @param <T> Element type
* @return Iterable over pairs of the first element and all other elements
*/
public static <T> Iterable<Pair<T, T>> firstAnd(final Iterable<? extends T> iterable) {
return () -> {
final Iterator<? extends T> iterator = iterable.iterator();
if (!iterator.hasNext()) {
return Collections.emptyIterator();
}
final T first = iterator.next();
return new FirstAndIterator<>(iterator, first);
};
}
/** Iterator that returns the first element of a collection paired with every
* other element.
*
* @param <E> Element type */
private static class FirstAndIterator<E> implements Iterator<Pair<E, E>> {
private final Iterator<? extends E> iterator;
private final E first;
FirstAndIterator(Iterator<? extends E> iterator, E first) {
this.iterator = requireNonNull(iterator, "iterator");
this.first = first;
}
@Override public boolean hasNext() {
return iterator.hasNext();
}
@Override public Pair<E, E> next() {
return of(first, iterator.next());
}
@Override public void remove() {
throw new UnsupportedOperationException("remove");
}
}
/** Iterator that pairs elements from two iterators.
*
* @param <L> Left-hand type
* @param <R> Right-hand type */
private static class ZipIterator<L, R> implements Iterator<Pair<L, R>> {
private final Iterator<? extends L> leftIterator;
private final Iterator<? extends R> rightIterator;
ZipIterator(Iterator<? extends L> leftIterator,
Iterator<? extends R> rightIterator) {
this.leftIterator = requireNonNull(leftIterator, "leftIterator");
this.rightIterator = requireNonNull(rightIterator, "rightIterator");
}
@Override public boolean hasNext() {
return leftIterator.hasNext() && rightIterator.hasNext();
}
@Override public Pair<L, R> next() {
return Pair.of(leftIterator.next(), rightIterator.next());
}
@Override public void remove() {
leftIterator.remove();
rightIterator.remove();
}
}
/** Iterator that returns consecutive pairs of elements from an underlying
* iterator.
*
* @param <E> Element type */
private static class AdjacentIterator<E> implements Iterator<Pair<E, E>> {
private final Iterator<? extends E> iterator;
E previous;
AdjacentIterator(Iterator<? extends E> iterator) {
this.iterator = requireNonNull(iterator, "iterator");
previous = iterator.next();
}
@Override public boolean hasNext() {
return iterator.hasNext();
}
@Override public Pair<E, E> next() {
final E current = iterator.next();
final Pair<E, E> pair = of(previous, current);
previous = current;
return pair;
}
@Override public void remove() {
throw new UnsupportedOperationException("remove");
}
}
/** Unmodifiable list of pairs, backed by a pair of lists.
*
* <p>Though it is unmodifiable, it is mutable: if the contents of one
* of the backing lists changes, the contents of this list will appear to
* change. The length, however, is fixed on creation.
*
* @param <K> Left-hand type
* @param <V> Right-hand type
*
* @see MutableZipList */
private static class ZipList<K, V> extends AbstractList<Pair<K, V>> {
private final List<? extends K> ks;
private final List<? extends V> vs;
private final int size;
ZipList(List<? extends K> ks, List<? extends V> vs, int size) {
this.ks = ks;
this.vs = vs;
this.size = size;
}
@Override public Pair<K, V> get(int index) {
return Pair.of(ks.get(index), vs.get(index));
}
@Override public int size() {
return size;
}
}
/** A mutable list of pairs backed by a pair of mutable lists.
*
* <p>Modifications to this list are reflected in the backing lists, and vice
* versa.
*
* @param <K> Key (left) value type
* @param <V> Value (right) value type */
private static class MutableZipList<K, V> extends AbstractList<Pair<K, V>> {
private final List<K> ks;
private final List<V> vs;
MutableZipList(List<K> ks, List<V> vs) {
this.ks = requireNonNull(ks, "ks");
this.vs = requireNonNull(vs, "vs");
}
@Override public Pair<K, V> get(int index) {
return Pair.of(ks.get(index), vs.get(index));
}
@Override public int size() {
return Math.min(ks.size(), vs.size());
}
@Override public void add(int index, Pair<K, V> pair) {
ks.add(index, pair.left);
vs.add(index, pair.right);
}
@Override public Pair<K, V> remove(int index) {
final K bufferedRow = ks.remove(index);
final V stateSet = vs.remove(index);
return Pair.of(bufferedRow, stateSet);
}
@Override public Pair<K, V> set(int index, Pair<K, V> pair) {
final Pair<K, V> previous = get(index);
ks.set(index, pair.left);
vs.set(index, pair.right);
return previous;
}
}
/**
* Represents an operation that accepts two input arguments and an ordinal,
* and returns no result.
*
* <p>This is a specialization of {@link java.util.function.Consumer},
* similar to {@link BiConsumer}.
*
* @param <K> Key type
* @param <V> Value type
*/
@FunctionalInterface
public interface PairWithOrdinalConsumer<K, V> {
/**
* Performs this operation on the given arguments.
*
* @param ordinal Ordinal
* @param k the first input argument
* @param v the second input argument
*/
void accept(int ordinal, K k, V v);
}
}