Mappings.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.mapping;
import org.apache.calcite.util.BitSets;
import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Permutation;
import org.apache.calcite.util.Util;
import com.google.common.collect.ImmutableList;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.CheckReturnValue;
import org.checkerframework.checker.initialization.qual.UnknownInitialization;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.function.IntFunction;
/**
* Utility functions related to mappings.
*
* @see MappingType
* @see Mapping
* @see org.apache.calcite.util.Permutation
*/
public abstract class Mappings {
//~ Constructors -----------------------------------------------------------
private Mappings() {
}
//~ Methods ----------------------------------------------------------------
/**
* Creates a mapping with required properties.
*/
public static Mapping create(
MappingType mappingType,
int sourceCount,
int targetCount) {
switch (mappingType) {
case BIJECTION:
assert sourceCount == targetCount;
return new Permutation(sourceCount);
case INVERSE_SURJECTION:
assert sourceCount >= targetCount;
return new SurjectionWithInverse(
sourceCount,
targetCount);
case PARTIAL_SURJECTION:
case SURJECTION:
return new Mappings.PartialMapping(
sourceCount,
targetCount,
mappingType);
case PARTIAL_FUNCTION:
case FUNCTION:
return new PartialFunctionImpl(
sourceCount,
targetCount,
mappingType);
case INVERSE_FUNCTION:
case INVERSE_PARTIAL_FUNCTION:
return new InverseMapping(
create(mappingType.inverse(), targetCount, sourceCount));
default:
throw Util.needToImplement(
"no known implementation for mapping type " + mappingType);
}
}
/**
* Creates the identity mapping.
*
* <p>For example, {@code createIdentity(2)} returns the mapping
* {0:0, 1:1, 2:2}.
*
* @param fieldCount Number of sources/targets
* @return Identity mapping
*/
public static IdentityMapping createIdentity(int fieldCount) {
return new Mappings.IdentityMapping(fieldCount);
}
/**
* Converts a mapping to its inverse.
*/
public static Mapping invert(Mapping mapping) {
if (mapping instanceof InverseMapping) {
return ((InverseMapping) mapping).parent;
}
return new InverseMapping(mapping);
}
/**
* Divides one mapping by another.
*
* <p>{@code divide(A, B)} returns a mapping C such that B . C (the mapping
* B followed by the mapping C) is equivalent to A.
*
* @param mapping1 First mapping
* @param mapping2 Second mapping
* @return Mapping mapping3 such that mapping1 = mapping2 . mapping3
*/
public static Mapping divide(Mapping mapping1, Mapping mapping2) {
if (mapping1.getSourceCount() != mapping2.getSourceCount()) {
throw new IllegalArgumentException();
}
Mapping remaining =
create(
MappingType.INVERSE_SURJECTION,
mapping2.getTargetCount(),
mapping1.getTargetCount());
for (int target = 0; target < mapping1.getTargetCount(); ++target) {
int source = mapping1.getSourceOpt(target);
if (source >= 0) {
int x = mapping2.getTarget(source);
remaining.set(x, target);
}
}
return remaining;
}
/**
* Multiplies one mapping by another.
*
* <p>{@code multiply(A, B)} returns a mapping C such that A . B (the mapping
* A followed by the mapping B) is equivalent to C.
*
* @param mapping1 First mapping
* @param mapping2 Second mapping
* @return Mapping mapping3 such that mapping1 = mapping2 . mapping3
*/
public static Mapping multiply(Mapping mapping1, Mapping mapping2) {
if (mapping1.getTargetCount() != mapping2.getSourceCount()) {
throw new IllegalArgumentException();
}
Mapping product =
create(
MappingType.INVERSE_SURJECTION,
mapping1.getSourceCount(),
mapping2.getTargetCount());
for (int source = 0; source < mapping1.getSourceCount(); ++source) {
int x = mapping1.getTargetOpt(source);
if (x >= 0) {
int target = mapping2.getTarget(x);
product.set(source, target);
}
}
return product;
}
/**
* Applies a mapping to a BitSet.
*
* <p>If the mapping does not affect the bit set, returns the original.
* Never changes the original.
*
* @param mapping Mapping
* @param bitSet Bit set
* @return Bit set with mapping applied
*/
public static BitSet apply(Mapping mapping, BitSet bitSet) {
final BitSet newBitSet = new BitSet();
for (int source : BitSets.toIter(bitSet)) {
final int target = mapping.getTarget(source);
newBitSet.set(target);
}
if (newBitSet.equals(bitSet)) {
return bitSet;
}
return newBitSet;
}
/**
* Applies a mapping to an {@code ImmutableBitSet}.
*
* <p>If the mapping does not affect the bit set, returns the original.
* Never changes the original.
*
* @param mapping Mapping
* @param bitSet Bit set
* @return Bit set with mapping applied
*/
public static ImmutableBitSet apply(Mapping mapping, ImmutableBitSet bitSet) {
final ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
for (int source : bitSet) {
final int target = mapping.getTarget(source);
builder.set(target);
}
return builder.build(bitSet);
}
/**
* Applies a mapping to a collection of {@code ImmutableBitSet}s.
*
* @param mapping Mapping
* @param bitSets Collection of bit sets
* @return Sorted bit sets with mapping applied
*/
public static ImmutableList<ImmutableBitSet> apply2(final Mapping mapping,
Iterable<ImmutableBitSet> bitSets) {
return ImmutableList.copyOf(
ImmutableBitSet.ORDERING.sortedCopy(
Util.transform(bitSets, input1 -> apply(mapping, input1))));
}
/**
* Applies a mapping to a list.
*
* @param mapping Mapping
* @param list List
* @param <T> Element type
* @return List with elements permuted according to mapping
*/
public static <T> List<T> apply(final Mapping mapping, final List<T> list) {
if (mapping.getSourceCount() != list.size()) {
// REVIEW: too strict?
throw new IllegalArgumentException("mapping source count "
+ mapping.getSourceCount()
+ " does not match list size " + list.size());
}
final int targetCount = mapping.getTargetCount();
final List<T> list2 = new ArrayList<>(targetCount);
for (int target = 0; target < targetCount; ++target) {
final int source = mapping.getSource(target);
list2.add(list.get(source));
}
return list2;
}
public static List<Integer> apply2(
final Mapping mapping,
final List<Integer> list) {
return new AbstractList<Integer>() {
@Override public Integer get(int index) {
final int source = list.get(index);
return mapping.getTarget(source);
}
@Override public int size() {
return list.size();
}
};
}
/**
* Creates a view of a list, permuting according to a mapping.
*
* @param mapping Mapping
* @param list List
* @param <T> Element type
* @return Permuted view of list
*/
public static <T> List<T> apply3(
final Mapping mapping,
final List<T> list) {
return new AbstractList<T>() {
@Override public T get(int index) {
return list.get(mapping.getSource(index));
}
@Override public int size() {
return mapping.getTargetCount();
}
};
}
/**
* Creates a view of a list, permuting according to a target mapping.
*
* @param mapping Mapping
* @param list List
* @param <T> Element type
* @return Permuted view of list
*/
public static <T> List<T> permute(final List<T> list,
final TargetMapping mapping) {
return new AbstractList<T>() {
@Override public T get(int index) {
return list.get(mapping.getTarget(index));
}
@Override public int size() {
return mapping.getSourceCount();
}
};
}
/**
* Returns a mapping as a list such that {@code list.get(source)} is
* {@code mapping.getTarget(source)} and {@code list.size()} is
* {@code mapping.getSourceCount()}.
*
* <p>Converse of {@link #target(List, int)}.
*
* @see #asListNonNull(TargetMapping)
*/
@CheckReturnValue
public static List<@Nullable Integer> asList(final TargetMapping mapping) {
return new AbstractList<@Nullable Integer>() {
@Override public @Nullable Integer get(int source) {
int target = mapping.getTargetOpt(source);
return target < 0 ? null : target;
}
@Override public int size() {
return mapping.getSourceCount();
}
};
}
/**
* Returns a mapping as a list such that {@code list.get(source)} is
* {@code mapping.getTarget(source)} and {@code list.size()} is
* {@code mapping.getSourceCount()}.
*
* <p>The resulting list never contains null elements.
*
* <p>Converse of {@link #target(List, int)}.
*
* @see #asList(TargetMapping)
*/
@CheckReturnValue
public static List<Integer> asListNonNull(final TargetMapping mapping) {
return new AbstractList<Integer>() {
@Override public Integer get(int source) {
int target = mapping.getTargetOpt(source);
if (target < 0) {
throw new IllegalArgumentException("Element " + source + " is not found in mapping "
+ mapping);
}
return target;
}
@Override public int size() {
return mapping.getSourceCount();
}
};
}
/**
* Converts a {@link Map} of integers to a {@link TargetMapping}.
*/
public static TargetMapping target(
Map<Integer, Integer> map,
int sourceCount,
int targetCount) {
final PartialFunctionImpl mapping =
new PartialFunctionImpl(
sourceCount, targetCount, MappingType.FUNCTION);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
mapping.set(entry.getKey(), entry.getValue());
}
return mapping;
}
public static TargetMapping target(
IntFunction<? extends @Nullable Integer> function,
int sourceCount,
int targetCount) {
final PartialFunctionImpl mapping =
new PartialFunctionImpl(sourceCount, targetCount, MappingType.FUNCTION);
for (int source = 0; source < sourceCount; source++) {
Integer target = function.apply(source);
if (target != null) {
mapping.set(source, target);
}
}
return mapping;
}
public static Mapping target(Iterable<IntPair> pairs, int sourceCount,
int targetCount) {
final PartialFunctionImpl mapping =
new PartialFunctionImpl(sourceCount, targetCount, MappingType.FUNCTION);
for (IntPair pair : pairs) {
mapping.set(pair.source, pair.target);
}
return mapping;
}
public static Mapping source(List<Integer> targets, int targetCount) {
final int sourceCount = targets.size();
final PartialFunctionImpl mapping =
new PartialFunctionImpl(sourceCount, targetCount, MappingType.FUNCTION);
for (int source = 0; source < sourceCount; source++) {
int target = targets.get(source);
mapping.set(source, target);
}
return mapping;
}
public static Mapping target(List<Integer> sources, int sourceCount) {
final int targetCount = sources.size();
final PartialFunctionImpl mapping =
new PartialFunctionImpl(sourceCount, targetCount, MappingType.FUNCTION);
for (int target = 0; target < targetCount; target++) {
int source = sources.get(target);
mapping.set(source, target);
}
return mapping;
}
/** Creates a bijection.
*
* <p>Throws if sources and targets are not one to one. */
public static Mapping bijection(List<Integer> targets) {
return new Permutation(Ints.toArray(targets));
}
/** Creates a bijection.
*
* <p>Throws if sources and targets are not one to one. */
public static Mapping bijection(Map<Integer, Integer> targets) {
int[] ints = new int[targets.size()];
for (int i = 0; i < targets.size(); i++) {
Integer value = targets.get(i);
if (value == null) {
throw new NullPointerException("Index " + i + " is not mapped in " + targets);
}
ints[i] = value;
}
return new Permutation(ints);
}
/**
* Returns whether a mapping is the identity.
*/
public static boolean isIdentity(TargetMapping mapping) {
if (mapping.getSourceCount() != mapping.getTargetCount()) {
return false;
}
for (int i = 0; i < mapping.getSourceCount(); i++) {
if (mapping.getTargetOpt(i) != i) {
return false;
}
}
return true;
}
/**
* Returns whether a mapping keeps order.
*
* <p>For example, {0:0, 1:1} and {0:1, 1:1} keeps order,
* and {0:1, 1:0} breaks the initial order.
*/
public static boolean keepsOrdering(TargetMapping mapping) {
int prevTarget = -1;
for (int i = 0; i < mapping.getSourceCount(); i++) {
int target = mapping.getTargetOpt(i);
if (target != -1) {
if (target < prevTarget) {
return false;
}
prevTarget = target;
}
}
return true;
}
/**
* Creates a mapping that consists of a set of contiguous ranges.
*
* <p>For example,
*
* <blockquote><pre>createShiftMapping(60,
* 100, 0, 3,
* 200, 50, 5);
* </pre></blockquote>
*
* <p>creates
*
* <table>
* <caption>Example mapping</caption>
* <tr><th>Source</th><th>Target</th></tr>
* <tr><td>0</td><td>100</td></tr>
* <tr><td>1</td><td>101</td></tr>
* <tr><td>2</td><td>102</td></tr>
* <tr><td>3</td><td>-1</td></tr>
* <tr><td>...</td><td>-1</td></tr>
* <tr><td>50</td><td>200</td></tr>
* <tr><td>51</td><td>201</td></tr>
* <tr><td>52</td><td>202</td></tr>
* <tr><td>53</td><td>203</td></tr>
* <tr><td>54</td><td>204</td></tr>
* <tr><td>55</td><td>-1</td></tr>
* <tr><td>...</td><td>-1</td></tr>
* <tr><td>59</td><td>-1</td></tr>
* </table>
*
* @param sourceCount Maximum value of {@code source}
* @param ints Collection of ranges, each
* {@code (target, source, count)}
* @return Mapping that maps from source ranges to target ranges
*/
public static TargetMapping createShiftMapping(
int sourceCount, int... ints) {
int targetCount = 0;
assert ints.length % 3 == 0;
for (int i = 0; i < ints.length; i += 3) {
final int target = ints[i];
final int length = ints[i + 2];
final int top = target + length;
targetCount = Math.max(targetCount, top);
}
final TargetMapping mapping =
create(
MappingType.INVERSE_SURJECTION,
sourceCount,
targetCount);
for (int i = 0; i < ints.length; i += 3) {
final int target = ints[i];
final int source = ints[i + 1];
final int length = ints[i + 2];
assert source + length <= sourceCount;
for (int j = 0; j < length; j++) {
assert mapping.getTargetOpt(source + j) == -1;
mapping.set(source + j, target + j);
}
}
return mapping;
}
/**
* Creates a mapping by appending two mappings.
*
* <p>Sources and targets of the second mapping are shifted to the right.
*
* <p>For example, <pre>append({0:0, 1:1}, {0:0, 1:1, 2:2})</pre> yields
* <pre>{0:0, 1:1, 2:2, 3:3, 4:4}</pre>.
*
* @see #merge
*/
public static TargetMapping append(
TargetMapping mapping0,
TargetMapping mapping1) {
final int s0 = mapping0.getSourceCount();
final int s1 = mapping1.getSourceCount();
final int t0 = mapping0.getTargetCount();
final int t1 = mapping1.getTargetCount();
final TargetMapping mapping =
create(MappingType.INVERSE_SURJECTION, s0 + s1, t0 + t1);
for (int s = 0; s < s0; s++) {
int t = mapping0.getTargetOpt(s);
if (t >= 0) {
mapping.set(s, t);
}
}
for (int s = 0; s < s1; s++) {
int t = mapping1.getTargetOpt(s);
if (t >= 0) {
mapping.set(s0 + s, t0 + t);
}
}
return mapping;
}
/**
* Creates a mapping by merging two mappings. There must be no clashes.
*
* <p>Unlike {@link #append}, sources and targets are not shifted.
*
* <p>For example, <code>merge({0:0, 1:1}, {2:2, 3:3, 4:4})</code> yields
* <code>{0:0, 1:1, 2:2, 3:3, 4:4}</code>.
* <code>merge({0:0, 1:1}, {1:2, 2:3})</code> throws, because there are
* two entries with source=1.
*/
public static TargetMapping merge(
TargetMapping mapping0,
TargetMapping mapping1) {
final int s0 = mapping0.getSourceCount();
final int s1 = mapping1.getSourceCount();
final int sMin = Math.min(s0, s1);
final int sMax = Math.max(s0, s1);
final int t0 = mapping0.getTargetCount();
final int t1 = mapping1.getTargetCount();
final int tMax = Math.max(t0, t1);
final TargetMapping mapping =
create(MappingType.INVERSE_SURJECTION, sMax, tMax);
for (int s = 0; s < sMin; s++) {
int t = mapping0.getTargetOpt(s);
if (t >= 0) {
mapping.set(s, t);
assert mapping1.getTargetOpt(s) < 0;
} else {
t = mapping1.getTargetOpt(s);
if (t >= 0) {
mapping.set(s, t);
}
}
}
for (int s = sMin; s < sMax; s++) {
int t = s < s0 ? mapping0.getTargetOpt(s) : -1;
if (t >= 0) {
mapping.set(s, t);
assert s >= s1 || mapping1.getTargetOpt(s) < 0;
} else {
t = s < s1 ? mapping1.getTargetOpt(s) : -1;
if (t >= 0) {
mapping.set(s, t);
}
}
}
return mapping;
}
/**
* Returns a mapping that shifts a given mapping's source by a given
* offset, incrementing the number of sources by the minimum possible.
*
* @param mapping Input mapping
* @param offset Offset to be applied to each source
* @return Shifted mapping
*/
public static TargetMapping offsetSource(
final TargetMapping mapping, final int offset) {
return offsetSource(mapping, offset, mapping.getSourceCount() + offset);
}
/**
* Returns a mapping that shifts a given mapping's source by a given
* offset.
*
* <p>For example, given {@code mapping} with sourceCount=2, targetCount=8,
* and (source, target) entries {[0: 5], [1: 7]}, offsetSource(mapping, 3)
* returns a mapping with sourceCount=5, targetCount=8,
* and (source, target) entries {[3: 5], [4: 7]}.
*
* @param mapping Input mapping
* @param offset Offset to be applied to each source
* @param sourceCount New source count; must be at least {@code mapping}'s
* source count plus {@code offset}
* @return Shifted mapping
*/
public static TargetMapping offsetSource(
final TargetMapping mapping, final int offset, final int sourceCount) {
if (sourceCount < mapping.getSourceCount() + offset) {
throw new IllegalArgumentException("new source count too low");
}
return target(
(IntFunction<@Nullable Integer>) source -> {
int source2 = source - offset;
return source2 < 0 || source2 >= mapping.getSourceCount()
? null
: mapping.getTargetOpt(source2);
},
sourceCount,
mapping.getTargetCount());
}
/**
* Returns a mapping that shifts a given mapping's target by a given
* offset, incrementing the number of targets by the minimum possible.
*
* @param mapping Input mapping
* @param offset Offset to be applied to each target
* @return Shifted mapping
*/
public static TargetMapping offsetTarget(
final TargetMapping mapping, final int offset) {
return offsetTarget(mapping, offset, mapping.getTargetCount() + offset);
}
/**
* Returns a mapping that shifts a given mapping's target by a given
* offset.
*
* <p>For example, given {@code mapping} with sourceCount=2, targetCount=8,
* and (source, target) entries {[0: 5], [1: 7]}, offsetTarget(mapping, 3)
* returns a mapping with sourceCount=2, targetCount=11,
* and (source, target) entries {[0: 8], [1: 10]}.
*
* @param mapping Input mapping
* @param offset Offset to be applied to each target
* @param targetCount New target count; must be at least {@code mapping}'s
* target count plus {@code offset}
* @return Shifted mapping
*/
public static TargetMapping offsetTarget(
final TargetMapping mapping, final int offset, final int targetCount) {
if (targetCount < mapping.getTargetCount() + offset) {
throw new IllegalArgumentException("new target count too low");
}
return target(
(IntFunction<@Nullable Integer>) source -> {
int target = mapping.getTargetOpt(source);
return target < 0 ? null : target + offset;
},
mapping.getSourceCount(), targetCount);
}
/**
* Returns a mapping that shifts a given mapping's source and target by a
* given offset.
*
* <p>For example, given {@code mapping} with sourceCount=2, targetCount=8,
* and (source, target) entries {[0: 5], [1: 7]}, offsetSource(mapping, 3)
* returns a mapping with sourceCount=5, targetCount=8,
* and (source, target) entries {[3: 8], [4: 10]}.
*
* @param mapping Input mapping
* @param offset Offset to be applied to each source
* @param sourceCount New source count; must be at least {@code mapping}'s
* source count plus {@code offset}
* @return Shifted mapping
*/
public static TargetMapping offset(
final TargetMapping mapping, final int offset, final int sourceCount) {
if (sourceCount < mapping.getSourceCount() + offset) {
throw new IllegalArgumentException("new source count too low");
}
return target(
(IntFunction<@Nullable Integer>) source -> {
final int source2 = source - offset;
if (source2 < 0 || source2 >= mapping.getSourceCount()) {
return null;
}
int target = mapping.getTargetOpt(source2);
if (target < 0) {
return null;
}
return target + offset;
},
sourceCount,
mapping.getTargetCount() + offset);
}
/** Returns whether a list of integers is the identity mapping
* [0, ..., n - 1]. */
public static boolean isIdentity(List<Integer> list, int count) {
if (list.size() != count) {
return false;
}
for (int i = 0; i < count; i++) {
final Integer o = list.get(i);
if (o == null || o != i) {
return false;
}
}
return true;
}
/** Inverts an {@link java.lang.Iterable} over
* {@link org.apache.calcite.util.mapping.IntPair}s. */
public static Iterable<IntPair> invert(final Iterable<IntPair> pairs) {
return () -> invert(pairs.iterator());
}
/** Inverts an {@link java.util.Iterator} over
* {@link org.apache.calcite.util.mapping.IntPair}s. */
public static Iterator<IntPair> invert(final Iterator<IntPair> pairs) {
return new Iterator<IntPair>() {
@Override public boolean hasNext() {
return pairs.hasNext();
}
@Override public IntPair next() {
final IntPair pair = pairs.next();
return IntPair.of(pair.target, pair.source);
}
@Override public void remove() {
throw new UnsupportedOperationException("remove");
}
};
}
/** Applies a mapping to an optional integer, returning an optional
* result. */
public static int apply(TargetMapping mapping, int i) {
return i < 0 ? i : mapping.getTarget(i);
}
//~ Inner Interfaces -------------------------------------------------------
/**
* Core interface of all mappings.
*/
public interface CoreMapping extends Iterable<IntPair> {
/**
* Returns the mapping type.
*
* @return Mapping type
*/
MappingType getMappingType();
/**
* Returns the number of elements in the mapping.
*/
int size();
}
/**
* Mapping where every source has a target. But:
*
* <ul>
* <li>A target may not have a source.
* <li>May not be finite.
* </ul>
*/
public interface FunctionMapping extends CoreMapping {
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*/
int getTargetOpt(int source);
/**
* Returns the target that a source maps to.
*
* @param source source
* @return target
* @throws NoElementException if source is not mapped
*/
int getTarget(int source);
@Override MappingType getMappingType();
int getSourceCount();
}
/**
* Mapping suitable for sourcing columns.
*
* <p>Properties:
*
* <ul>
* <li>It has a finite number of sources and targets
* <li>Each target has exactly one source
* <li>Each source has at most one target
* </ul>
*
* <p>TODO: figure out which interfaces this should extend
*/
public interface SourceMapping extends CoreMapping {
int getSourceCount();
/**
* Returns the source that a target maps to.
*
* @param target target
* @return source
* @throws NoElementException if target is not mapped
*/
int getSource(int target);
/**
* Returns the source that a target maps to, or -1 if it is not mapped.
*/
int getSourceOpt(int target);
int getTargetCount();
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*/
int getTargetOpt(int source);
@Override MappingType getMappingType();
boolean isIdentity();
Mapping inverse();
}
/**
* Mapping suitable for mapping columns to a target.
*
* <p>Properties:
*
* <ul>
* <li>It has a finite number of sources and targets
* <li>Each target has at most one source
* <li>Each source has exactly one target
* </ul>
*
* <p>TODO: figure out which interfaces this should extend
*/
public interface TargetMapping extends FunctionMapping {
@Override int getSourceCount();
/**
* Returns the source that a target maps to, or -1 if it is not mapped.
*/
int getSourceOpt(int target);
int getTargetCount();
/**
* Returns the target that a source maps to.
*
* @param source source
* @return target
* @throws NoElementException if source is not mapped
*/
@Override int getTarget(int source);
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*/
@Override int getTargetOpt(int source);
void set(int source, int target);
Mapping inverse();
}
//~ Inner Classes ----------------------------------------------------------
/** Abstract implementation of {@link Mapping}. */
public abstract static class AbstractMapping implements Mapping {
@Override public void set(int source, int target) {
throw new UnsupportedOperationException();
}
@Override public int getTargetOpt(int source) {
throw new UnsupportedOperationException();
}
@Override public int getTarget(int source) {
int target = getTargetOpt(source);
if (target == -1) {
throw new NoElementException(
"source #" + source + " has no target in mapping " + toString());
}
return target;
}
@Override public int getSourceOpt(int target) {
throw new UnsupportedOperationException();
}
@Override public int getSource(int target) {
int source = getSourceOpt(target);
if (source == -1) {
throw new NoElementException(
"target #" + target + " has no source in mapping " + toString());
}
return source;
}
@Override public int getSourceCount() {
throw new UnsupportedOperationException();
}
@Override public int getTargetCount() {
throw new UnsupportedOperationException();
}
@Override public boolean isIdentity() {
int sourceCount = getSourceCount();
int targetCount = getTargetCount();
if (sourceCount != targetCount) {
return false;
}
for (int i = 0; i < sourceCount; i++) {
if (getSource(i) != i) {
return false;
}
}
return true;
}
/**
* Returns a string representation of this mapping.
*
* <p>For example, the mapping
*
* <table border="1">
* <caption>Example</caption>
* <tr>
* <th>source</th>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* </tr>
* <tr>
* <th>target</th>
* <td>-1</td>
* <td>3</td>
* <td>2</td>
* </tr>
* </table>
*
* <table border="1">
* <caption>Example</caption>
* <tr>
* <th>target</th>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* <td>3</td>
* </tr>
* <tr>
* <th>source</th>
* <td>-1</td>
* <td>-1</td>
* <td>2</td>
* <td>1</td>
* </tr>
* </table>
*
* <p>is represented by the string "[1:3, 2:2]".
*
* <p>This method relies upon the optional method {@link #iterator()}.
*/
@Override public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("[size=").append(size())
.append(", sourceCount=").append(getSourceCount())
.append(", targetCount=").append(getTargetCount())
.append(", elements=[");
int i = 0;
for (IntPair pair : this) {
if (i++ > 0) {
buf.append(", ");
}
buf.append(pair.source).append(':').append(pair.target);
}
buf.append("]]");
return buf.toString();
}
}
/** Abstract implementation of mapping where both source and target
* domains are finite. */
public abstract static class FiniteAbstractMapping extends AbstractMapping {
@Override public Iterator<IntPair> iterator() {
return new FunctionMappingIter(this);
}
@Override public int hashCode() {
// not very efficient
return toString().hashCode();
}
@Override public boolean equals(@Nullable Object obj) {
// not very efficient
return (obj instanceof Mapping)
&& toString().equals(obj.toString());
}
}
/** Iterator that yields the (source, target) values in a
* {@link FunctionMapping}. */
static class FunctionMappingIter implements Iterator<IntPair> {
private int i = 0;
private final FunctionMapping mapping;
FunctionMappingIter(FunctionMapping mapping) {
this.mapping = mapping;
}
@Override public boolean hasNext() {
return (i < mapping.getSourceCount())
|| (mapping.getSourceCount() == -1);
}
@Override public IntPair next() {
int x = i++;
return new IntPair(
x,
mapping.getTarget(x));
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
}
/**
* Thrown when a mapping is expected to return one element but returns
* several.
*/
public static class TooManyElementsException extends RuntimeException {
}
/**
* Thrown when a mapping is expected to return one element but returns none.
*/
public static class NoElementException extends RuntimeException {
/**
* Creates a NoElementException.
*
* @param message Message
*/
public NoElementException(String message) {
super(message);
}
}
/**
* A mapping where a source has at most one target, and every target has at
* most one source.
*/
public static class PartialMapping extends FiniteAbstractMapping
implements Mapping, FunctionMapping, TargetMapping {
protected final int[] sources;
protected final int[] targets;
private final MappingType mappingType;
/**
* Creates a partial mapping.
*
* <p>Initially, no element is mapped to any other:
*
* <table border="1">
* <caption>Example</caption>
* <tr>
* <th>source</th>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* </tr>
* <tr>
* <th>target</th>
* <td>-1</td>
* <td>-1</td>
* <td>-1</td>
* </tr>
* </table>
*
* <table border="1">
* <caption>Example</caption>
* <tr>
* <th>target</th>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* <td>3</td>
* </tr>
* <tr>
* <th>source</th>
* <td>-1</td>
* <td>-1</td>
* <td>-1</td>
* <td>-1</td>
* </tr>
* </table>
*
* @param sourceCount Number of source elements
* @param targetCount Number of target elements
* @param mappingType Mapping type; must not allow multiple sources per
* target or multiple targets per source
*/
public PartialMapping(
int sourceCount,
int targetCount,
MappingType mappingType) {
this.mappingType = mappingType;
assert mappingType.isSingleSource() : mappingType;
assert mappingType.isSingleTarget() : mappingType;
this.sources = new int[targetCount];
this.targets = new int[sourceCount];
Arrays.fill(sources, -1);
Arrays.fill(targets, -1);
}
/**
* Creates a partial mapping from a list. For example, <code>
* PartialMapping({1, 2, 4}, 6)</code> creates the mapping
*
* <table border="1">
* <caption>Example</caption>
* <tr>
* <th>source</th>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* <td>3</td>
* <td>4</td>
* <td>5</td>
* </tr>
* <tr>
* <th>target</th>
* <td>-1</td>
* <td>0</td>
* <td>1</td>
* <td>-1</td>
* <td>2</td>
* <td>-1</td>
* </tr>
* </table>
*
* @param sourceList List whose i'th element is the source of target #i
* @param sourceCount Number of elements in the source domain
* @param mappingType Mapping type, must be
* {@link org.apache.calcite.util.mapping.MappingType#PARTIAL_SURJECTION}
* or stronger.
*/
public PartialMapping(
List<Integer> sourceList,
int sourceCount,
MappingType mappingType) {
this.mappingType = mappingType;
assert mappingType.isSingleSource();
assert mappingType.isSingleTarget();
int targetCount = sourceList.size();
this.targets = new int[sourceCount];
this.sources = new int[targetCount];
Arrays.fill(sources, -1);
for (int i = 0; i < sourceList.size(); ++i) {
final int source = sourceList.get(i);
sources[i] = source;
if (source >= 0) {
targets[source] = i;
} else {
assert !this.mappingType.isMandatorySource();
}
}
}
private PartialMapping(
int[] sources,
int[] targets,
MappingType mappingType) {
this.sources = sources;
this.targets = targets;
this.mappingType = mappingType;
}
@Override public MappingType getMappingType() {
return mappingType;
}
@Override public int getSourceCount() {
return targets.length;
}
@Override public int getTargetCount() {
return sources.length;
}
@Override public void clear() {
Arrays.fill(sources, -1);
Arrays.fill(targets, -1);
}
@Override public int size() {
int size = 0;
int[] a = sources.length < targets.length ? sources : targets;
for (int i1 : a) {
if (i1 >= 0) {
++size;
}
}
return size;
}
@Override public Mapping inverse() {
return new PartialMapping(
targets.clone(),
sources.clone(),
mappingType.inverse());
}
@Override public Iterator<IntPair> iterator() {
return new MappingItr();
}
protected boolean isValid() {
assertPartialValid(this.sources, this.targets);
assertPartialValid(this.targets, this.sources);
return true;
}
private static void assertPartialValid(int[] sources, int[] targets) {
for (int i = 0; i < sources.length; i++) {
final int source = sources[i];
assert source >= -1;
assert source < targets.length;
assert (source == -1) || (targets[source] == i);
}
}
@Override public void set(int source, int target) {
assert isValid();
final int prevTarget = targets[source];
targets[source] = target;
final int prevSource = sources[target];
sources[target] = source;
if (prevTarget != -1) {
sources[prevTarget] = prevSource;
}
if (prevSource != -1) {
targets[prevSource] = prevTarget;
}
assert isValid();
}
/**
* Returns the source that a target maps to, or -1 if it is not mapped.
*/
@Override public int getSourceOpt(int target) {
return sources[target];
}
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*/
@Override public int getTargetOpt(int source) {
return targets[source];
}
@Override public boolean isIdentity() {
if (sources.length != targets.length) {
return false;
}
for (int i = 0; i < sources.length; i++) {
int source = sources[i];
if (source != i) {
return false;
}
}
return true;
}
/** Mapping iterator. */
private class MappingItr implements Iterator<IntPair> {
int i = -1;
MappingItr() {
advance();
}
@Override public boolean hasNext() {
return i < targets.length;
}
private void advance(
@UnknownInitialization MappingItr this) {
do {
++i;
} while (i < targets.length && targets[i] == -1);
}
@Override public IntPair next() {
final IntPair pair = new IntPair(i, targets[i]);
advance();
return pair;
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
}
}
/**
* A surjection with inverse has precisely one source for each target.
* (Whereas a general surjection has at least one source for each target.)
* Every source has at most one target.
*
* <p>If you call {@link #set} on a target, the target's previous source
* will be lost.
*/
static class SurjectionWithInverse extends PartialMapping {
SurjectionWithInverse(int sourceCount, int targetCount) {
super(sourceCount, targetCount, MappingType.INVERSE_SURJECTION);
}
/**
* Creates a mapping between a source and a target.
*
* <p>It is an error to map a target to a source which already has a
* target.
*
* <p>If you map a source to a target which already has a source, the
* old source becomes an orphan.
*
* @param source source
* @param target target
*/
@Override public void set(int source, int target) {
assert isValid();
final int prevTarget = targets[source];
if (prevTarget != -1) {
throw new IllegalArgumentException("source #" + source
+ " is already mapped to target #" + target);
}
targets[source] = target;
sources[target] = source;
}
@Override public int getSource(int target) {
return sources[target];
}
}
/** The identity mapping, of a given size, or infinite. */
public static class IdentityMapping extends AbstractMapping
implements FunctionMapping, TargetMapping, SourceMapping {
private final int size;
/**
* Creates an identity mapping.
*
* @param size Size, or -1 if infinite.
*/
public IdentityMapping(int size) {
this.size = size;
}
@Override public void clear() {
throw new UnsupportedOperationException("Mapping is read-only");
}
@Override public int size() {
return size;
}
@Override public Mapping inverse() {
return this;
}
@Override public boolean isIdentity() {
return true;
}
@Override public void set(int source, int target) {
throw new UnsupportedOperationException();
}
@Override public MappingType getMappingType() {
return MappingType.BIJECTION;
}
@Override public int getSourceCount() {
return size;
}
@Override public int getTargetCount() {
return size;
}
/**
* Returns the target that a source maps to.
*
* @param source source
* @return target
*/
@Override public int getTarget(int source) {
if (source < 0 || (size != -1 && source >= size)) {
throw new IndexOutOfBoundsException("source #" + source
+ " has no target in identity mapping of size " + size);
}
return source;
}
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*
* @param source source
* @return target
*/
@Override public int getTargetOpt(int source) {
if (source < 0 || (size != -1 && source >= size)) {
throw new IndexOutOfBoundsException("source #" + source
+ " has no target in identity mapping of size " + size);
}
return source;
}
/**
* Returns the source that a target maps to.
*
* @param target target
* @return source
*/
@Override public int getSource(int target) {
if (target < 0 || (size != -1 && target >= size)) {
throw new IndexOutOfBoundsException("target #" + target
+ " has no source in identity mapping of size " + size);
}
return target;
}
/**
* Returns the source that a target maps to, or -1 if it is not mapped.
*
* @param target target
* @return source
*/
@Override public int getSourceOpt(int target) {
if (target < 0 || (size != -1 && target >= size)) {
throw new IndexOutOfBoundsException("target #" + target
+ " has no source in identity mapping of size " + size);
}
return target;
}
@Override public Iterator<IntPair> iterator() {
return new Iterator<IntPair>() {
int i = 0;
@Override public boolean hasNext() {
return (size < 0) || (i < size);
}
@Override public IntPair next() {
int x = i++;
return new IntPair(x, x);
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
/** Source mapping that returns the same result as a parent
* {@link SourceMapping} except for specific overriding elements. */
public static class OverridingSourceMapping extends AbstractMapping
implements SourceMapping {
private final SourceMapping parent;
private final int source;
private final int target;
public OverridingSourceMapping(
SourceMapping parent,
int source,
int target) {
this.parent = parent;
this.source = source;
this.target = target;
}
@Override public void clear() {
throw new UnsupportedOperationException("Mapping is read-only");
}
@Override public int size() {
return parent.getSourceOpt(target) >= 0
? parent.size()
: parent.size() + 1;
}
@Override public Mapping inverse() {
return new OverridingTargetMapping(
parent.inverse(),
target,
source);
}
@Override public MappingType getMappingType() {
// FIXME: Mapping type might be weaker than parent.
return parent.getMappingType();
}
@Override public int getSource(int target) {
if (target == this.target) {
return this.source;
} else {
return parent.getSource(target);
}
}
@Override public boolean isIdentity() {
// FIXME: It's possible that parent was not the identity but that
// this overriding fixed it.
return (source == target)
&& parent.isIdentity();
}
@Override public Iterator<IntPair> iterator() {
throw Util.needToImplement(this);
}
}
/** Target mapping that returns the same result as a parent
* {@link TargetMapping} except for specific overriding elements. */
public static class OverridingTargetMapping extends AbstractMapping
implements TargetMapping {
private final TargetMapping parent;
private final int target;
private final int source;
public OverridingTargetMapping(
TargetMapping parent,
int target,
int source) {
this.parent = parent;
this.target = target;
this.source = source;
}
@Override public void clear() {
throw new UnsupportedOperationException("Mapping is read-only");
}
@Override public int size() {
return parent.getTargetOpt(source) >= 0
? parent.size()
: parent.size() + 1;
}
@Override public void set(int source, int target) {
parent.set(source, target);
}
@Override public Mapping inverse() {
return new OverridingSourceMapping(
parent.inverse(),
source,
target);
}
@Override public MappingType getMappingType() {
// FIXME: Mapping type might be weaker than parent.
return parent.getMappingType();
}
@Override public boolean isIdentity() {
// FIXME: Possible that parent is not identity but this overriding
// fixes it.
return (source == target)
&& ((Mapping) parent).isIdentity();
}
@Override public int getTarget(int source) {
if (source == this.source) {
return this.target;
} else {
return parent.getTarget(source);
}
}
@Override public Iterator<IntPair> iterator() {
throw Util.needToImplement(this);
}
}
/**
* Implementation of {@link Mapping} where a source can have at most one
* target, and a target can have any number of sources. The source count
* must be finite, but the target count may be infinite.
*
* <p>The implementation uses an array for the forward-mapping, but does not
* store the backward mapping.
*/
private static class PartialFunctionImpl extends AbstractMapping
implements TargetMapping {
private final int sourceCount;
private final int targetCount;
private final MappingType mappingType;
private final int[] targets;
PartialFunctionImpl(
int sourceCount,
int targetCount,
MappingType mappingType) {
super();
if (sourceCount < 0) {
throw new IllegalArgumentException("Sources must be finite");
}
this.sourceCount = sourceCount;
this.targetCount = targetCount;
this.mappingType = mappingType;
if (!mappingType.isSingleTarget()) {
throw new IllegalArgumentException(
"Must have at most one target");
}
this.targets = new int[sourceCount];
Arrays.fill(targets, -1);
}
@Override public int getSourceCount() {
return sourceCount;
}
@Override public int getTargetCount() {
return targetCount;
}
@Override public void clear() {
Arrays.fill(targets, -1);
}
@Override public int size() {
int size = 0;
for (int target : targets) {
if (target >= 0) {
++size;
}
}
return size;
}
@SuppressWarnings("method.invocation.invalid")
@Override public Iterator<IntPair> iterator() {
return new Iterator<IntPair>() {
int i = -1;
{
advance();
}
private void advance() {
while (true) {
++i;
if (i >= sourceCount) {
break; // end
}
if (targets[i] >= 0) {
break; // found one
}
}
}
@Override public boolean hasNext() {
return i < sourceCount;
}
@Override public IntPair next() {
final IntPair pair = new IntPair(i, targets[i]);
advance();
return pair;
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override public MappingType getMappingType() {
return mappingType;
}
@Override public Mapping inverse() {
return target(invert(this), targetCount, sourceCount);
}
@Override public void set(int source, int target) {
if ((target < 0) && mappingType.isMandatorySource()) {
throw new IllegalArgumentException("Target is required");
}
if ((target >= targetCount) && (targetCount >= 0)) {
throw new IllegalArgumentException(
"Target must be less than target count, " + targetCount);
}
targets[source] = target;
}
public void setAll(Mapping mapping) {
for (IntPair pair : mapping) {
set(pair.source, pair.target);
}
}
/**
* Returns the target that a source maps to, or -1 if it is not mapped.
*
* @return target
*/
@Override public int getTargetOpt(int source) {
return targets[source];
}
}
/**
* Decorator which converts any {@link Mapping} into the inverse of itself.
*
* <p>If the mapping does not have an inverse -- for example, if a given
* source can have more than one target -- then the corresponding method
* call of the underlying mapping will raise a runtime exception.
*/
private static class InverseMapping implements Mapping {
private final Mapping parent;
InverseMapping(Mapping parent) {
this.parent = parent;
}
@Override public Iterator<IntPair> iterator() {
final Iterator<IntPair> parentIter = parent.iterator();
return new Iterator<IntPair>() {
@Override public boolean hasNext() {
return parentIter.hasNext();
}
@Override public IntPair next() {
IntPair parentPair = parentIter.next();
return new IntPair(parentPair.target, parentPair.source);
}
@Override public void remove() {
parentIter.remove();
}
};
}
@Override public void clear() {
parent.clear();
}
@Override public int size() {
return parent.size();
}
@Override public int getSourceCount() {
return parent.getTargetCount();
}
@Override public int getTargetCount() {
return parent.getSourceCount();
}
@Override public MappingType getMappingType() {
return parent.getMappingType().inverse();
}
@Override public boolean isIdentity() {
return parent.isIdentity();
}
@Override public int getTargetOpt(int source) {
return parent.getSourceOpt(source);
}
@Override public int getTarget(int source) {
return parent.getSource(source);
}
@Override public int getSource(int target) {
return parent.getTarget(target);
}
@Override public int getSourceOpt(int target) {
return parent.getTargetOpt(target);
}
@Override public Mapping inverse() {
return parent;
}
@Override public void set(int source, int target) {
parent.set(target, source);
}
}
/**
* Concatenates multiple mappings.
*
* <pre>
* [ 1:0, 2:1] // sourceCount:100
* [ 1:0, 2:1] // sourceCount:100
* output:
* [ 1:0, 2:1, 101:2, 102:3 ] ; sourceCount:200
* </pre>
*/
public static Mapping concatenateMappings(List<Mapping> inputMappings) {
int fieldCount = 0;
int newFieldCount = 0;
for (Mapping inputMapping : inputMappings) {
fieldCount += inputMapping.getSourceCount();
newFieldCount += inputMapping.getTargetCount();
}
Mapping mapping =
create(MappingType.INVERSE_SURJECTION, fieldCount, newFieldCount);
int offset = 0;
int newOffset = 0;
for (Mapping inputMapping : inputMappings) {
for (IntPair pair : inputMapping) {
mapping.set(pair.source + offset, pair.target + newOffset);
}
offset += inputMapping.getSourceCount();
newOffset += inputMapping.getTargetCount();
}
return mapping;
}
}