org.eigenbase.util
Class Permutation

java.lang.Object
  org.eigenbase.util.Permutation

All Implemented Interfaces:

Iterable<IntPair>, Mapping, Mappings.FunctionMapping, Mappings.SourceMapping, Mappings.TargetMapping

public class Permutation
extends Object
implements Mapping, Mappings.TargetMapping

Represents a mapping which reorders elements in an array.

Version:

$Id: //open/dev/farrago/src/org/eigenbase/util/Permutation.java#10 $

Author:

Julian Hyde

Field Summary

private int[]	sources
private int[]	targets

Constructor Summary

	Permutation(int size) Creates a permutation of a given size.
	Permutation(int[] targets) Creates a permutation from an array.
private	Permutation(int[] targets, int[] sources) Creates a permuation.

Method Summary

Object	clone()
boolean	equals(Object obj)
MappingType	getMappingType()
int	getSource(int target) Returns the position which maps to target.
int	getSourceCount() Returns the number of sources.
int	getSourceOpt(int target)
int	getTarget(int source) Returns the position that source is mapped to.
int	getTargetCount() Returns the number of targets.
int	getTargetOpt(int source) Returns the target that a source maps to, or -1 if it is not mapped.
int	hashCode()
void	identity() Initializes this permutation to the identity permutation.
private void	increment(int x, int[] zzz)
void	insertSource(int x) Inserts into the sources.
void	insertTarget(int x) Inserts into the targets.
Permutation	inverse() Returns the inverse permutation.
boolean	isIdentity() Returns whether this is the identity permutation.
private boolean	isValid(boolean fail) Checks whether this permutation is valid.
Iterator<IntPair>	iterator() Returns an iterator over the elements in this mapping.
Permutation	product(Permutation permutation) Returns the product of this Permutation with a given Permutation.
private void	resize(int newSize)
void	set(int source, int target) Maps source position to target position.
void	set(int source, int target, boolean allowResize) Maps source position to target position, automatically resizing if source or target is out of bounds.
void	setAll(Mapping mapping)
private void	setInternal(int source, int target)
private void	shuffleUp(int[] zz, int x)
int	size() Returns the number of elements in this permutation.
String	toString() Returns a string representation of this permutation.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

targets

private int[] targets

sources

private int[] sources

Constructor Detail

Permutation

public Permutation(int size)

Creates a permutation of a given size.

It is intialized to the identity permutation, such as "[0, 1, 2, 3]".

Parameters:

size - Number of elements in the permutation

Permutation

public Permutation(int[] targets)

Creates a permutation from an array.

Parameters:

targets - Array of targets

Throws:

IllegalArgumentException - if elements of array are not unique

ArrayIndexOutOfBoundsException - if elements of array are not between 0 through targets.length - 1 inclusive

Permutation

private Permutation(int[] targets,
                    int[] sources)

Creates a permuation. Arrays are not copied, and are assumed to be valid permutations.

Method Detail

clone

public Object clone()

Overrides:

clone in class Object

identity

public void identity()

Initializes this permutation to the identity permutation.

size

public final int size()

Returns the number of elements in this permutation.

toString

public String toString()

Returns a string representation of this permutation.

For example, the mapping

source	target
0	2
1	0
2	1
3	3

is represented by the string "[2, 0, 1, 3]".

Overrides:

toString in class Object

set

public void set(int source,
                int target)

Maps source position to target position.

To preserve the 1:1 nature of the permutation, the previous target of source becomes the new target of the previous source.

For example, given the permutation

[3, 2, 0, 1]

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

[3, 2, 1, 0].

Another example. Again starting from

[3, 2, 0, 1]

suppose we map position 2 to target 3. We map the previous source 0 to the previous target 0, which gives

[0, 2, 3, 1].

Specified by:

set in interface Mappings.TargetMapping

Parameters:

source - Source position

target - Target position

Throws:

ArrayIndexOutOfBoundsException - if source or target is negative or greater than or equal to the size of the permuation

set

public void set(int source,
                int target,
                boolean allowResize)

Maps source position to target position, automatically resizing if source or target is out of bounds.

To preserve the 1:1 nature of the permutation, the previous target of source becomes the new target of the previous source.

For example, given the permutation

[3, 2, 0, 1]

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

[3, 2, 1, 0].

Another example. Again starting from

[3, 2, 0, 1]

suppose we map position 2 to target 3. We map the previous source 0 to the previous target 0, which gives

[0, 2, 3, 1].

Parameters:

source - Source position

target - Target position

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 allowResize is false

insertTarget

public void insertTarget(int x)

Inserts into the targets.

For example, consider the permutation

source	0	1	2	3	4
target	3	0	4	2	1

After applying insertTarget(2) every target 2 or higher is shifted up one.

source	0	1	2	3	4	5
target	4	0	5	3	1	2

Note that the array has been extended to accomodate the new target, and the previously unmapped source 5 is mapped to the unused target slot 2.

Parameters:

x -

insertSource

public void insertSource(int x)

Inserts into the sources.

Behavior is analogous to insertTarget(int).

Parameters:

x -

increment

private void increment(int x,
                       int[] zzz)

shuffleUp

private void shuffleUp(int[] zz,
                       int x)

resize

private void resize(int newSize)

setInternal

private void setInternal(int source,
                         int target)

inverse

public Permutation inverse()

Returns the inverse permutation.

Specified by:

inverse in interface Mappings.SourceMapping

Specified by:

inverse in interface Mappings.TargetMapping

isIdentity

public boolean isIdentity()

Returns whether this is the identity permutation.

Specified by:

isIdentity in interface Mapping

Specified by:

isIdentity in interface Mappings.SourceMapping

getTarget

public int getTarget(int source)

Returns the position that source is mapped to.

Specified by:

getTarget in interface Mappings.FunctionMapping

Specified by:

getTarget in interface Mappings.TargetMapping

Parameters:

source - source

Returns:

target

getSource

public int getSource(int target)

Returns the position which maps to target.

Specified by:

getSource in interface Mappings.SourceMapping

isValid

private boolean isValid(boolean fail)

Checks whether this permutation is valid.

Parameters:

fail - Whether to assert if invalid

Returns:

Whether valid

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

iterator

public Iterator<IntPair> iterator()

Description copied from interface: Mapping

Returns an iterator over the elements in this mapping.

This method is optional; implementations may throw UnsupportedOperationException.

Specified by:

iterator in interface Iterable<IntPair>

Specified by:

iterator in interface Mapping

getSourceCount

public int getSourceCount()

Description copied from interface: Mapping

Returns the number of sources. Valid sources will be in the range 0 .. sourceCount.

Specified by:

getSourceCount in interface Mapping

Specified by:

getSourceCount in interface Mappings.FunctionMapping

Specified by:

getSourceCount in interface Mappings.SourceMapping

Specified by:

getSourceCount in interface Mappings.TargetMapping

getTargetCount

public int getTargetCount()

Description copied from interface: Mapping

Returns the number of targets. Valid targets will be in the range 0 .. targetCount.

Specified by:

getTargetCount in interface Mapping

Specified by:

getTargetCount in interface Mappings.SourceMapping

Specified by:

getTargetCount in interface Mappings.TargetMapping

getMappingType

public MappingType getMappingType()

Specified by:

getMappingType in interface Mapping

Specified by:

getMappingType in interface Mappings.FunctionMapping

Specified by:

getMappingType in interface Mappings.SourceMapping

Specified by:

getMappingType in interface Mappings.TargetMapping

getTargetOpt

public int getTargetOpt(int source)

Description copied from interface: Mappings.FunctionMapping

Returns the target that a source maps to, or -1 if it is not mapped.

Specified by:

getTargetOpt in interface Mappings.FunctionMapping

Specified by:

getTargetOpt in interface Mappings.SourceMapping

Specified by:

getTargetOpt in interface Mappings.TargetMapping

getSourceOpt

public int getSourceOpt(int target)

Specified by:

getSourceOpt in interface Mappings.SourceMapping

Specified by:

getSourceOpt in interface Mappings.TargetMapping

setAll

public void setAll(Mapping mapping)

product

public Permutation product(Permutation permutation)

Returns the product of this Permutation with a given Permutation. Does not modify this Permutation or permutation.

For example, perm.product(perm.inverse()) yields the identity.