Package org.apache.calcite.util

Class Permutation

java.lang.Object
org.apache.calcite.util.Permutation
All Implemented Interfaces:
Iterable<IntPair>, Mapping, Mappings.CoreMapping, Mappings.FunctionMapping, Mappings.SourceMapping, Mappings.TargetMapping
public class Permutation extends Object implements Mapping, Mappings.TargetMapping
Represents a mapping which reorders elements in an array.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Permutation(int size)
    Creates a permutation of a given size.
    Permutation(int[] targets)
    Creates a permutation from an array.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Removes all elements in the mapping.
    Object
    clone()
     
    boolean
    equals(@Nullable Object obj)
     
    MappingType
    getMappingType()
    Returns the mapping type.
    int
    getSource(int target)
    Returns the position which maps to target.
    int
    getSourceCount()
    Returns the number of sources.
    int
    getSourceOpt(int target)
    Returns the source that a target maps to, or -1 if it is not mapped.
    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.
    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.
    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.
    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)
     
    final 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

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • Permutation

      public Permutation(int size)
      Creates a permutation of a given size.

      It is initialized 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

  • Method Details

    • 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.
      Specified by:
      size in interface Mapping
      Specified by:
      size in interface Mappings.CoreMapping

    • clear

      public void clear()
      Description copied from interface: Mapping
      Removes all elements in the mapping.
      Specified by:
      clear in interface Mapping

    • toString

      public String toString()
      Returns a string representation of this permutation.

      For example, the mapping

      Example 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

      Example 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.

      Mapping after applying insertTarget(2)
      source 0 1 2 3 4 5
      target 4 0 5 3 1 2

      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.

      Parameters:
      x - Ordinal of position to add to target

    • insertSource

      public void insertSource(int x)
      Inserts into the sources.

      Behavior is analogous to insertTarget(int).

      Parameters:
      x - Ordinal of position to add to source

    • 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
      Parameters:
      target - target
      Returns:
      source

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(@Nullable 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()
      Description copied from interface: Mappings.CoreMapping
      Returns the mapping type.
      Specified by:
      getMappingType in interface Mapping
      Specified by:
      getMappingType in interface Mappings.CoreMapping
      Specified by:
      getMappingType in interface Mappings.FunctionMapping
      Specified by:
      getMappingType in interface Mappings.SourceMapping
      Returns:
      Mapping type

    • 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)
      Description copied from interface: Mappings.SourceMapping
      Returns the source that a target maps to, or -1 if it is not mapped.
      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.