Package it.unimi.dsi.sux4j.mph.solve

Class Modulo3System.Modulo3Equation

  • Enclosing class:
    Modulo3System
    protected static class Modulo3System.Modulo3Equation
extends java.lang.Object
    An equation on F3.

    • Field Detail

      • bitVector

        protected final it.unimi.dsi.bits.LongArrayBitVector bitVector
        The vector representing the coefficients (two bits for each variable).

      • bits

        protected final long[] bits
        The bv.bits(), cached.

      • list

        protected final it.unimi.dsi.fastutil.longs.LongBigList list
        A 2-bit list view of bitVector, cached.

      • c

        protected long c
        The constant term.

      • firstVar

        protected int firstVar
        The first variable. It is Integer.MAX_VALUE if the first variable is not known. This field must be updated by updateFirstVar() to be meaningful.

      • firstCoeff

        protected int firstCoeff
        The first coefficient. This field must be updated by updateFirstVar() to be meaningful.

    • Constructor Detail

      • Modulo3Equation

        public Modulo3Equation​(long c,
                       int numVars)
        Creates a new equation.
        Parameters:
        c - the constant term.
        numVars - the number of variables.

    • Method Detail

      • add

        public Modulo3System.Modulo3Equation add​(int variable,
                                         int coefficient)
        Adds a new variable with given coefficient.
        Parameters:
        variable - a variable.
        coefficient - its coefficient.
        Returns:
        this equation.
        Throws:
        java.lang.IllegalStateException - if you try to add twice the same variable.

      • add

        public Modulo3System.Modulo3Equation add​(int variable)
        Adds a new variable with coefficient equal to one.
        Parameters:
        variable - a variable.
        Returns:
        this equation.

      • variables

        public int[] variables()
        Returns an array containing the variables in increasing order.

        Mainly for debugging purposes.

        Returns:
        an array containing the variables in increasing order.
        See Also:
        coefficients()

      • coefficients

        public int[] coefficients()
        Returns an array containing the coefficients in variable increasing order.

        Mainly for debugging purposes.

        Returns:
        an array, parallel to that returned by variables(), containing the coefficients in variable increasing order.
        See Also:
        variables()

      • eliminate

        public Modulo3System.Modulo3Equation eliminate​(int var,
                                               Modulo3System.Modulo3Equation equation)
        Eliminates the given variable from this equation, using the provided equation, by subtracting it multiplied by a suitable constant.
        Parameters:
        var - a variable.
        equation - an equation in which var appears.
        Returns:
        this equation.

      • sub

        public void sub​(Modulo3System.Modulo3Equation equation,
                int mul)
        Subtract from this equation another equation multiplied by a provided constant.
        Parameters:
        equation - the subtrahend.
        mul - a multiplier that will be applied to the subtrahend.

      • addMod3

        protected static final long addMod3​(long x,
                                    long y)
        Adds two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.
        Parameters:
        x - a 64-bit word made of modulo-3 2-bit fields.
        y - a 64-bit word made of modulo-3 2-bit fields.
        Returns:
        the field-by-field mod 3 sum of x and y.

      • subMod3

        protected static final long subMod3​(long x,
                                    long y)
        Subtracts two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.
        Parameters:
        x - a 64-bit word made of modulo-3 2-bit fields.
        y - a 64-bit word made of modulo-3 2-bit fields.
        Returns:
        the field-by-field mod 3 difference of x and y.

      • updateFirstVar

        public void updateFirstVar()
        Updates the information contained in firstVar and firstCoeff.

      • isUnsolvable

        public boolean isUnsolvable()

      • isIdentity

        public boolean isIdentity()

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • equals

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

      • normalized

        public void normalized​(long[] result)
        Writes in the provided array a normalized (all coefficients turned into ones) version of the bit vector representing the equation.
        Parameters:
        result - an array where the result will be stored; must be long at least as bits.

      • scalarProduct

        public static int scalarProduct​(long[] x,
                                long[] y)
        Returns the modulo-3 scalar product of the two provided bit vectors.

        This implementation was suggested by Djamal Belazzougui.

        Parameters:
        x - a bit vector represented as an array of longs.
        y - a bit vector represented as an array of longs.
        Returns:
        the modulo-3 scalar product of x and {code y}, unnormalized (might be larger than 2).

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object