Permutation.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.util.mapping.IntPair;
import org.apache.calcite.util.mapping.Mapping;
import org.apache.calcite.util.mapping.MappingType;
import org.apache.calcite.util.mapping.Mappings;
import org.checkerframework.checker.initialization.qual.UnknownInitialization;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.checkerframework.checker.nullness.qual.RequiresNonNull;
import java.util.Arrays;
import java.util.Iterator;
/**
* Represents a mapping which reorders elements in an array.
*/
public class Permutation implements Mapping, Mappings.TargetMapping {
//~ Instance fields --------------------------------------------------------
private int[] targets;
private int[] sources;
//~ Constructors -----------------------------------------------------------
/**
* Creates a permutation of a given size.
*
* <p>It is initialized to the identity permutation, such as "[0, 1, 2, 3]".
*
* @param size Number of elements in the permutation
*/
@SuppressWarnings("method.invocation.invalid")
public Permutation(int size) {
targets = new int[size];
sources = new int[size];
// Initialize to identity.
identity();
}
/**
* Creates a permutation from an array.
*
* @param targets Array of targets
* @throws IllegalArgumentException if elements of array are not unique
* @throws ArrayIndexOutOfBoundsException if elements of array are not
* between 0 through targets.length - 1
* inclusive
*/
public Permutation(int[] targets) {
this.targets = targets.clone();
this.sources = new int[targets.length];
Arrays.fill(sources, -1);
for (int i = 0; i < targets.length; i++) {
int target = targets[i];
if (target < 0 || target >= sources.length) {
throw new IllegalArgumentException("target out of range");
}
if (sources[target] != -1) {
throw new IllegalArgumentException(
"more than one permutation element maps to position " + target);
}
sources[target] = i;
}
assert isValid(true);
}
/**
* Creates a permutation. Arrays are not copied, and are assumed to be valid
* permutations.
*/
private Permutation(int[] targets, int[] sources) {
this.targets = targets;
this.sources = sources;
assert isValid(true);
}
//~ Methods ----------------------------------------------------------------
@Override public Object clone() {
return new Permutation(
targets.clone(),
sources.clone());
}
/**
* Initializes this permutation to the identity permutation.
*/
public void identity() {
for (int i = 0; i < targets.length; i++) {
targets[i] = sources[i] = i;
}
}
/**
* Returns the number of elements in this permutation.
*/
@Override public final int size() {
return targets.length;
}
@Override public void clear() {
throw new UnsupportedOperationException(
"Cannot clear: permutation must always contain one mapping per element");
}
/**
* Returns a string representation of this permutation.
*
* <p>For example, the mapping
*
* <table>
* <caption>Example mapping</caption>
* <tr>
* <th>source</th>
* <th>target</th>
* </tr>
* <tr>
* <td>0</td>
* <td>2</td>
* </tr>
* <tr>
* <td>1</td>
* <td>0</td>
* </tr>
* <tr>
* <td>2</td>
* <td>1</td>
* </tr>
* <tr>
* <td>3</td>
* <td>3</td>
* </tr>
* </table>
*
* <p>is represented by the string "[2, 0, 1, 3]".
*/
@Override public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("[");
for (int i = 0; i < targets.length; i++) {
if (i > 0) {
buf.append(", ");
}
buf.append(targets[i]);
}
buf.append("]");
return buf.toString();
}
/**
* Maps source position to target position.
*
* <p>To preserve the 1:1 nature of the permutation, the previous target of
* source becomes the new target of the previous source.
*
* <p>For example, given the permutation
*
* <blockquote><pre>[3, 2, 0, 1]</pre></blockquote>
*
* <p>suppose we map position 2 to target 1. Position 2 currently has target
* 0, and the source of position 1 is position 3. We preserve the permutation
* property by mapping the previous source 3 to the previous target 0. The new
* permutation is
*
* <blockquote><pre>[3, 2, 1, 0].</pre></blockquote>
*
* <p>Another example. Again starting from
*
* <blockquote><pre>[3, 2, 0, 1]</pre></blockquote>
*
* <p>suppose we map position 2 to target 3. We map the previous source 0 to
* the previous target 0, which gives
*
* <blockquote><pre>[0, 2, 3, 1].</pre></blockquote>
*
* @param source Source position
* @param target Target position
* @throws ArrayIndexOutOfBoundsException if source or target is negative or
* greater than or equal to the size of
* the permuation
*/
@Override public void set(int source, int target) {
set(source, target, false);
}
/**
* Maps source position to target position, automatically resizing if source
* or target is out of bounds.
*
* <p>To preserve the 1:1 nature of the permutation, the previous target of
* source becomes the new target of the previous source.
*
* <p>For example, given the permutation
*
* <blockquote><pre>[3, 2, 0, 1]</pre></blockquote>
*
* <p>suppose we map position 2 to target 1. Position 2 currently has target
* 0, and the source of position 1 is position 3. We preserve the permutation
* property by mapping the previous source 3 to the previous target 0. The new
* permutation is
*
* <blockquote><pre>[3, 2, 1, 0].</pre></blockquote>
*
* <p>Another example. Again starting from
*
* <blockquote><pre>[3, 2, 0, 1]</pre></blockquote>
*
* <p>suppose we map position 2 to target 3. We map the previous source 0 to
* the previous target 0, which gives
*
* <blockquote><pre>[0, 2, 3, 1].</pre></blockquote>
*
* @param source Source position
* @param target Target position
* @param allowResize Whether to resize the permutation if the source or
* target is greater than the current capacity
* @throws ArrayIndexOutOfBoundsException if source or target is negative,
* or greater than or equal to the size
* of the permutation, and
* <code>allowResize</code> is false
*/
public void set(int source, int target, boolean allowResize) {
final int maxSourceTarget = Math.max(source, target);
if (maxSourceTarget >= sources.length) {
if (allowResize) {
resize(maxSourceTarget + 1);
} else {
throw new ArrayIndexOutOfBoundsException(maxSourceTarget);
}
}
int prevTarget = targets[source];
assert sources[prevTarget] == source;
int prevSource = sources[target];
assert targets[prevSource] == target;
setInternal(source, target);
// To balance things up, make the previous source reference the
// previous target. This ensures that each ordinal occurs precisely
// once in the sources array and the targets array.
setInternal(prevSource, prevTarget);
// For example:
// Before: [2, 1, 0, 3]
// Now we set(source=1, target=0)
// previous target of source (1) was 1, is now 0
// previous source of target (0) was 2, is now 1
// something now has to have target 1 -- use previous source
// After: [2, 0, 1, 3]
}
/**
* Inserts into the targets.
*
* <p>For example, consider the permutation
*
* <table border="1">
* <caption>Example permutation</caption>
* <tr>
* <td>source</td>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* <td>3</td>
* <td>4</td>
* </tr>
* <tr>
* <td>target</td>
* <td>3</td>
* <td>0</td>
* <td>4</td>
* <td>2</td>
* <td>1</td>
* </tr>
* </table>
*
* <p>After applying <code>insertTarget(2)</code> every target 2 or higher is
* shifted up one.
*
* <table border="1">
* <caption>Mapping after applying insertTarget(2)</caption>
* <tr>
* <td>source</td>
* <td>0</td>
* <td>1</td>
* <td>2</td>
* <td>3</td>
* <td>4</td>
* <td>5</td>
* </tr>
* <tr>
* <td>target</td>
* <td>4</td>
* <td>0</td>
* <td>5</td>
* <td>3</td>
* <td>1</td>
* <td>2</td>
* </tr>
* </table>
*
* <p>Note that the array has been extended to accommodate the new target, and
* the previously unmapped source 5 is mapped to the unused target slot 2.
*
* @param x Ordinal of position to add to target
*/
public void insertTarget(int x) {
assert isValid(true);
resize(sources.length + 1);
// Shuffle sources up.
shuffleUp(sources, x);
// Shuffle targets.
increment(x, targets);
assert isValid(true);
}
/**
* Inserts into the sources.
*
* <p>Behavior is analogous to {@link #insertTarget(int)}.
*
* @param x Ordinal of position to add to source
*/
public void insertSource(int x) {
assert isValid(true);
resize(targets.length + 1);
// Shuffle targets up.
shuffleUp(targets, x);
// Increment sources.
increment(x, sources);
assert isValid(true);
}
private void increment(int x, int[] zzz) {
final int size = zzz.length;
for (int i = 0; i < size; i++) {
if (targets[i] == (size - 1)) {
targets[i] = x;
} else if (targets[i] >= x) {
++targets[i];
}
}
}
private static void shuffleUp(final int[] zz, int x) {
final int size = zz.length;
int t = zz[size - 1];
System.arraycopy(zz, x, zz, x + 1, size - 1 - x);
zz[x] = t;
}
private void resize(int newSize) {
assert isValid(true);
final int size = targets.length;
int[] newTargets = new int[newSize];
System.arraycopy(targets, 0, newTargets, 0, size);
int[] newSources = new int[newSize];
System.arraycopy(sources, 0, newSources, 0, size);
// Initialize the new elements to the identity mapping.
for (int i = size; i < newSize; i++) {
newSources[i] = i;
newTargets[i] = i;
}
targets = newTargets;
sources = newSources;
assert isValid(true);
}
private void setInternal(int source, int target) {
targets[source] = target;
sources[target] = source;
}
/**
* Returns the inverse permutation.
*/
@Override public Permutation inverse() {
return new Permutation(
sources.clone(),
targets.clone());
}
/**
* Returns whether this is the identity permutation.
*/
@Override public boolean isIdentity() {
for (int i = 0; i < targets.length; i++) {
if (targets[i] != i) {
return false;
}
}
return true;
}
/**
* Returns the position that <code>source</code> is mapped to.
*/
@Override public int getTarget(int source) {
return targets[source];
}
/**
* Returns the position which maps to <code>target</code>.
*/
@Override public int getSource(int target) {
return sources[target];
}
/**
* Checks whether this permutation is valid.
*
* @param fail Whether to assert if invalid
* @return Whether valid
*/
@RequiresNonNull({"sources", "targets"})
private boolean isValid(@UnknownInitialization Permutation this, boolean fail) {
final int size = targets.length;
if (sources.length != size) {
assert !fail : "different lengths";
return false;
}
// Every element in sources has corresponding element in targets.
int[] occurCount = new int[size];
for (int i = 0; i < size; i++) {
int target = targets[i];
if (sources[target] != i) {
assert !fail
: "source[" + target + "] = " + sources[target]
+ ", should be " + i;
return false;
}
int source = sources[i];
if (targets[source] != i) {
assert !fail
: "target[" + source + "] = " + targets[source]
+ ", should be " + i;
return false;
}
// Every member should occur once.
if (occurCount[target] != 0) {
assert !fail : "target " + target + " occurs more than once";
return false;
}
occurCount[target]++;
}
return true;
}
@Override public int hashCode() {
// not very efficient
return toString().hashCode();
}
@Override public boolean equals(@Nullable Object obj) {
// not very efficient
return (obj instanceof Permutation)
&& toString().equals(obj.toString());
}
// implement Mapping
@Override public Iterator<IntPair> iterator() {
return new Iterator<IntPair>() {
private int i = 0;
@Override public boolean hasNext() {
return i < targets.length;
}
@Override public IntPair next() {
final IntPair pair = new IntPair(i, targets[i]);
++i;
return pair;
}
@Override public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override public int getSourceCount() {
return targets.length;
}
@Override public int getTargetCount() {
return targets.length;
}
@Override public MappingType getMappingType() {
return MappingType.BIJECTION;
}
@Override public int getTargetOpt(int source) {
return getTarget(source);
}
@Override public int getSourceOpt(int target) {
return getSource(target);
}
public void setAll(Mapping mapping) {
for (IntPair pair : mapping) {
set(pair.source, pair.target);
}
}
/**
* Returns the product of this Permutation with a given Permutation. Does
* not modify this Permutation or <code>permutation</code>.
*
* <p>For example, perm.product(perm.inverse()) yields the identity.
*/
public Permutation product(Permutation permutation) {
Permutation product = new Permutation(sources.length);
for (int i = 0; i < targets.length; ++i) {
product.set(i, permutation.getTarget(targets[i]));
}
return product;
}
}