Package org.apache.calcite.util

Class Permutation

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[] sources  
      private int[] targets  

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        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 permutation.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Removes all elements in the mapping.
      java.lang.Object clone()  
      boolean equals​(java.lang.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)  
      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.
      java.util.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.
      java.lang.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

    • 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 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:
        java.lang.IllegalArgumentException - if elements of array are not unique
        java.lang.ArrayIndexOutOfBoundsException - if elements of array are not between 0 through targets.length - 1 inclusive

      • Permutation

        private Permutation​(int[] targets,
                    int[] sources)
        Creates a permutation. Arrays are not copied, and are assumed to be valid permutations.

    • Method Detail

      • clone

        public java.lang.Object clone()
        Overrides:
        clone in class java.lang.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 java.lang.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 java.lang.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:
        java.lang.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:
        java.lang.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

      • 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)

      • 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 java.lang.Object

      • equals

        public boolean equals​(java.lang.Object obj)
        Overrides:
        equals in class java.lang.Object

      • iterator

        public java.util.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 java.lang.Iterable<IntPair>
        Specified by:
        iterator in interface Mapping

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