Package it.unimi.dsi.sux4j.mph.solve
Class Modulo3System.Modulo3Equation
- java.lang.Object
-
- it.unimi.dsi.sux4j.mph.solve.Modulo3System.Modulo3Equation
-
- Enclosing class:
- Modulo3System
protected static class Modulo3System.Modulo3Equation extends java.lang.Object
An equation on F3.
-
-
Field Summary
Fields Modifier and Type Field Description protected long[]
bits
Thebv.bits()
, cached.protected it.unimi.dsi.bits.LongArrayBitVector
bitVector
The vector representing the coefficients (two bits for each variable).protected long
c
The constant term.protected int
firstCoeff
The first coefficient.protected int
firstVar
The first variable.protected it.unimi.dsi.fastutil.longs.LongBigList
list
A 2-bit list view ofbitVector
, cached.
-
Constructor Summary
Constructors Modifier Constructor Description Modulo3Equation(long c, int numVars)
Creates a new equation.protected
Modulo3Equation(Modulo3System.Modulo3Equation equation)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Modulo3System.Modulo3Equation
add(int variable)
Adds a new variable with coefficient equal to one.Modulo3System.Modulo3Equation
add(int variable, int coefficient)
Adds a new variable with given coefficient.protected static 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.int[]
coefficients()
Returns an array containing the coefficients in variable increasing order.Modulo3System.Modulo3Equation
copy()
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.boolean
equals(java.lang.Object o)
int
hashCode()
boolean
isIdentity()
boolean
isUnsolvable()
void
normalized(long[] result)
Writes in the provided array a normalized (all coefficients turned into ones) version of the bit vector representing the equation.static int
scalarProduct(long[] x, long[] y)
Returns the modulo-3 scalar product of the two provided bit vectors.void
sub(Modulo3System.Modulo3Equation equation, int mul)
Subtract from this equation another equation multiplied by a provided constant.protected static 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.java.lang.String
toString()
void
updateFirstVar()
Updates the information contained infirstVar
andfirstCoeff
.int[]
variables()
Returns an array containing the variables in increasing order.
-
-
-
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
Thebv.bits()
, cached.
-
list
protected final it.unimi.dsi.fastutil.longs.LongBigList list
A 2-bit list view ofbitVector
, cached.
-
c
protected long c
The constant term.
-
firstVar
protected int firstVar
The first variable. It isInteger.MAX_VALUE
if the first variable is not known. This field must be updated byupdateFirstVar()
to be meaningful.
-
firstCoeff
protected int firstCoeff
The first coefficient. This field must be updated byupdateFirstVar()
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.
-
Modulo3Equation
protected Modulo3Equation(Modulo3System.Modulo3Equation equation)
-
-
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 whichvar
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
andy
.
-
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
andy
.
-
updateFirstVar
public void updateFirstVar()
Updates the information contained infirstVar
andfirstCoeff
.
-
isUnsolvable
public boolean isUnsolvable()
-
isIdentity
public boolean isIdentity()
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
equals
public boolean equals(java.lang.Object o)
- Overrides:
equals
in classjava.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 asbits
.
-
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 classjava.lang.Object
-
copy
public Modulo3System.Modulo3Equation copy()
-
-