Class Modulo3System.Modulo3Equation

java.lang.Object
it.unimi.dsi.sux4j.mph.solve.Modulo3System.Modulo3Equation
Enclosing class:
Modulo3System
protected static class Modulo3System.Modulo3Equation extends Object
An equation on F3.
Author:
Sebastiano Vigna

  • Field Details

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

    • Modulo3Equation

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

    • Modulo3Equation

      protected Modulo3Equation(Modulo3System.Modulo3Equation equation)

  • Method Details

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

      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:

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

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class 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 String toString()
      Overrides:
      toString in class Object

    • copy

      public Modulo3System.Modulo3Equation copy()