scale.score.dependence.omega.omegaLib
Class Equation

java.lang.Object
  scale.score.dependence.omega.omegaLib.Equation

public final class Equation
extends java.lang.Object

A representation of a linear equation.

$Id: Equation.java,v 1.15 2005-02-07 21:28:39 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

This version of the Omega Libray is a translation from C++ to Java of the Omega Library developed at the University of Maryland.

Copyright (C) 1994-1996 by the Omega Project

All rights reserved.

NOTICE: This software is provided ``as is'', without any warranty, including any implied warranty for merchantability or fitness for a particular purpose. Under no circumstances shall the Omega Project or its agents be liable for any use of, misuse of, or inability to use this software, including incidental and consequential damages.

License is hereby given to use, modify, and redistribute this software, in whole or in part, for any purpose, commercial or non-commercial, provided that the user agrees to the terms of this copyright notice, including disclaimer of warranty, and provided that this copyright notice, including disclaimer of warranty, is preserved in the source code and documentation of anything derived from this software. Any redistributor of this software or anything derived from this software assumes responsibility for ensuring that any parties to whom such a redistribution is made are fully aware of the terms of this license and disclaimer.

The Omega project can be contacted at omega@cs.umd.edu or http://www.cs.umd.edu/projects/omega

An equation represents a linear equation of the form
C + a₁V₁ + ... + a_nV_n
An Equation has three other pices of information associated with it:

color

the color - BLACK or red

key

an integer value used in various algorithms

varCount

????

An equation has two boolean flags associated with it:

touched

???

essential

???

Field Summary

int	v1
int	v2

Constructor Summary

Equation(int key, int color, int nVars, int constant)
Create a new Equation.

Method Summary

void	addToCoef(int var, int value) Add the value to the specified coefficient.
boolean	anyNZCoef(int last, int first) Return true if any coefficient's value is 1 or -1.
void	checkMultCoefs(Equation f1, int nVars, int mult) Set the coefficients to the product of a scalar and the coefficients of another Equation.
void	checkMultCoefs(int nVars, int mult) Multiply the coefficients by a scalar value.
java.lang.String	coefsToString(int last, int first) Return a String representing the coefficients.
void	combineColumns(int src, int dest) Add the sorce column coefficient to the destination column coefficient.
int	computeHashcode(int topVar, int[] packing)
Equation	copy() Create a new Equation that is a duplicate of this Equation.
void	copyCoef(Equation from, int src, int dest) Set the destination coefficient to the same value as the soure coefficient.
void	copyCoef(int src, int dest) Set the destination coefficient to the same value as the soure coefficient.
void	copyCoef(int src, int dest, int number) Set the destination coefficients to the same value as the soure coefficients.
void	copyCoefs(Equation from, int num) Copy the coefficients from one Equation to another.
void	copyCoefs(Equation from, int last, int first) Copy the coefficients from one Equation to another.
void	copyCoefsIndexed(Equation from, int nVars, int[] index) Copy the coefficients from the specified Equation to this Equation.
void	copyColumn(Equation fp, int src, int dest)
static int	created()
int	crossProduct(int last, int first)
void	divideCoef(int var, int value) Divide the specified coefficient by the value.
void	divideCoefs(int nVars, int value) Divide the coefficients by the value.
void	divideCoefsEven(int nVars, int value) Divide the coefficients by the value.
void	eqncpy(Equation eq) Make this Equation the duplicate of the specified Equation.
boolean	findDifference(int nVars) Return true if equation is of form (v1 - coef >= v2).
int	findLargestNZ(int last, int first) Return the index of the last coefficient with the largest non-zero value.
int	findSmallestNZ(int last, int first) Return the index of the last coefficient with the smallest non-zero value.
int	gcdCoefs(int last, int first) Return the greates common denominator of the specified coefficients.
int	gcdSumOfProd(Equation eq2, int mult1, int mult2, int last, int first)
int	getCoefficient(int i) Return the specified coefficient.
int	getColor() Return the color of the Equation.
int	getConstant() Return the coefficient of the constant term.
int	getKey() Return the key.
int	getVarCount() Return the varCount.
void	incVarCount() Increment the varCount value by 1.
void	intModHat(int var, int b)
boolean	intModHat(int first, int last, int b)
void	intModHatI(int i, int nVars)
boolean	isBlack() Return true if the Equation is BLACK.
boolean	isEssential() Return true if this Equation is essential.
boolean	isGoodEquation(Equation eq2, int mult, int last, int first)
boolean	isNotBlack() Return true if the Equation is not BLACK.
boolean	isNotRed() Return true if the Equation is not red.
boolean	isNotZero(int var) Return true if specified coefficient is not zero.
boolean	isTouched() Return true if this Equation is touched.
boolean	isZero(int var) Return true if specified coefficient is zero.
int	lastCoefGt1(int last, int first) Return the index of the last coefficient whose absolute value is greater than 1.
int	lastDiffModZero(Equation eq2, int g, int i, int last, int first)
int	lastNZCoef(int last, int first) Return the index of the last non-zero coefficient.
int	lastNZCoef(int v1, int v2, int last, int first) Return the index of the last non-zero coefficient whose index is not specified.
int	lastOneCoef(int last, int first) Return the index of the last coefficient whose value is 1 or -1.
void	multAndSub(Equation f1, int mult, int nVars) Subtract the product of a scalar and the coefficients of another Equation from these coefficients.
void	multCoefs(Equation f1, int nVars, int mult) Set the coefficients to the product of a scalar and the coefficients of another Equation.
void	multCoefs(int nVars, int mult) Multiply all of the coefficients by the scalar specified.
void	negate(int nVars) Negate all of the coefficients.
void	negateCoefficients(int nVars) Negate all of the coefficients and set touched to true.
void	negateCoefs(Equation from, int last, int first) Negate the of the specified Equation to get this Equation's coefficients.
void	negateCoefs(int last, int first) Negate the specified coefficients.
int	numNZCoefs(int last, int first) Return count of coefficients that are not zero.
int	numOneCoefs(int last, int first) Return count of coefficients whose value is 1 or -1.
int	numVars() Return the number of variable slots that exist.
int	packNZIndexes(int[] indexes, int last, int first)
void	reset(int color, int nVars, int constant) Reset the Equation for resuse.
void	set(int color, int key, boolean touched) Set the color, key, and touched values.
void	setCoef(int i, int value) Set the value of the specified coefficient.
void	setColor(Equation f1) Set the color of the Equation.
void	setColor(Equation f1, Equation f2) Set the color of this Equation to the union of the colors of the two Equations.
void	setColor(Equation f1, Equation f2, Equation f3) Set the color of this Equation to the union of the colors of the three Equations.
void	setColor(int color) Set the color of the Equation.
void	setConstant(int value) Set the value of the constant term.
void	setEssential(boolean flg) Set the essential flag.
void	setKey(int key) Set the key value.
void	setTouched(boolean flg) Set the touched flag.
void	setTrueIfNotZero(boolean[] res, int last, int first) Set the array element true if the corresponding coefficient is not zero.
void	setVarCount(int varCount) Set the varCount value.
void	sumAndDivide(Equation f1, Equation f2, int divisor, int nVars) Set the coefficients to the (c1 + c2) / divisor where n1 and n2 are the coressponding coefficients from two Equations.
void	sumOfCoefs(Equation f1, Equation f2, int nVars) Set the coefficients to the sum of the coefficients from two Equations.
void	sumOfMult(Equation f1, int mult1, Equation f2, int mult2, int nVars) Set the coefficients to (coef[i] = mult1 * f1.coef[i] + mult2 * f2.coef[i];).
void	swapVars(int v1, int v2) Swap the values of the specified coefficients and set touched true.
java.lang.String	toString() Return a String representation of this Equation.
void	turnBlack() Turn the Equation BLACK.
void	turnRed() Turn the Equation red.
void	weirdCopyCoefs(Equation from, int last, int first, int g) Copy the coefficients from the specified Equation to this Equation.
void	zeroColumn(int col) Set the specified coefficient to zero.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

v1

public int v1

v2

public int v2

Constructor Detail

Equation

public Equation(int key,
                int color,
                int nVars,
                int constant)

Create a new Equation.

Parameters:

key - is the key value

color - is the color of the Equation

nVars - is the number of variables

constant - is the value of the constant term coefficient

Method Detail

created

public static int created()

copy

public Equation copy()

Create a new Equation that is a duplicate of this Equation.

reset

public void reset(int color,
                  int nVars,
                  int constant)

Reset the Equation for resuse.

Parameters:

nVars - is the number of variables in the equation.

set

public void set(int color,
                int key,
                boolean touched)

Set the color, key, and touched values.

eqncpy

public void eqncpy(Equation eq)

Make this Equation the duplicate of the specified Equation.

toString

public java.lang.String toString()

Return a String representation of this Equation.

Overrides:

toString in class java.lang.Object

coefsToString

public java.lang.String coefsToString(int last,
                                      int first)

Return a String representing the coefficients.

Parameters:

last - is the index of the last coefficient copied

first - is the index of the first coefficient copied

getVarCount

public int getVarCount()

Return the varCount.

setVarCount

public void setVarCount(int varCount)

Set the varCount value.

incVarCount

public void incVarCount()

Increment the varCount value by 1.

getKey

public int getKey()

Return the key.

setKey

public void setKey(int key)

Set the key value.

isTouched

public boolean isTouched()

Return true if this Equation is touched.

setTouched

public void setTouched(boolean flg)

Set the touched flag.

isEssential

public boolean isEssential()

Return true if this Equation is essential.

setEssential

public void setEssential(boolean flg)

Set the essential flag.

isZero

public boolean isZero(int var)

Return true if specified coefficient is zero.

isNotZero

public boolean isNotZero(int var)

Return true if specified coefficient is not zero.

turnBlack

public void turnBlack()

Turn the Equation BLACK.

turnRed

public void turnRed()

Turn the Equation red.

getColor

public int getColor()

Return the color of the Equation.

setColor

public void setColor(int color)

Set the color of the Equation.

setColor

public void setColor(Equation f1)

Set the color of the Equation.

setColor

public void setColor(Equation f1,
                     Equation f2)

Set the color of this Equation to the union of the colors of the two Equations.

setColor

public void setColor(Equation f1,
                     Equation f2,
                     Equation f3)

Set the color of this Equation to the union of the colors of the three Equations.

isBlack

public boolean isBlack()

Return true if the Equation is BLACK.

isNotBlack

public boolean isNotBlack()

Return true if the Equation is not BLACK.

isNotRed

public boolean isNotRed()

Return true if the Equation is not red.

numVars

public int numVars()

Return the number of variable slots that exist.

getCoefficient

public int getCoefficient(int i)

Return the specified coefficient.

getConstant

public int getConstant()

Return the coefficient of the constant term.

setCoef

public void setCoef(int i,
                    int value)

Set the value of the specified coefficient.

setConstant

public void setConstant(int value)

Set the value of the constant term.

addToCoef

public void addToCoef(int var,
                      int value)

Add the value to the specified coefficient.

sumOfCoefs

public void sumOfCoefs(Equation f1,
                       Equation f2,
                       int nVars)

Set the coefficients to the sum of the coefficients from two Equations.

divideCoef

public void divideCoef(int var,
                       int value)

Divide the specified coefficient by the value.

divideCoefs

public void divideCoefs(int nVars,
                        int value)

Divide the coefficients by the value.

divideCoefsEven

public void divideCoefsEven(int nVars,
                            int value)

Divide the coefficients by the value. Abort if they are not evenly divided.

sumAndDivide

public void sumAndDivide(Equation f1,
                         Equation f2,
                         int divisor,
                         int nVars)

Set the coefficients to the (c1 + c2) / divisor where n1 and n2 are the coressponding coefficients from two Equations.

copyCoef

public void copyCoef(int src,
                     int dest)

Set the destination coefficient to the same value as the soure coefficient.

copyCoef

public void copyCoef(Equation from,
                     int src,
                     int dest)

Set the destination coefficient to the same value as the soure coefficient.

copyCoef

public void copyCoef(int src,
                     int dest,
                     int number)

Set the destination coefficients to the same value as the soure coefficients.

copyCoefs

public void copyCoefs(Equation from,
                      int num)

Copy the coefficients from one Equation to another.

Parameters:

from - is the source of the coefficients

copyCoefs

public void copyCoefs(Equation from,
                      int last,
                      int first)

Copy the coefficients from one Equation to another.

Parameters:

from - is the source of the coefficients

last - is the index of the last coefficient copied

first - is the index of the first coefficient copied

copyCoefsIndexed

public void copyCoefsIndexed(Equation from,
                             int nVars,
                             int[] index)

Copy the coefficients from the specified Equation to this Equation. The coefficients are re-ordered as specified.

 coef[index[i]] = from.coef[i]
 

Parameters:

from - is the source of the coefficients

index - specifies the mapping

weirdCopyCoefs

public void weirdCopyCoefs(Equation from,
                           int last,
                           int first,
                           int g)

Copy the coefficients from the specified Equation to this Equation.

 coef[i] = (6 * from.coef[i] + g / 2) / g;
 

Parameters:

from - is the source of the coefficients

last - is the index of the last coefficient copied

first - is the index of the first coefficient copied

g - is the weird value

copyColumn

public void copyColumn(Equation fp,
                       int src,
                       int dest)

zeroColumn

public void zeroColumn(int col)

Set the specified coefficient to zero.

negateCoefs

public void negateCoefs(int last,
                        int first)

Negate the specified coefficients.

Parameters:

last - is the index of the last coefficient negated

first - is the index of the first coefficient negated

negateCoefs

public void negateCoefs(Equation from,
                        int last,
                        int first)

Negate the of the specified Equation to get this Equation's coefficients.

Parameters:

last - is the index of the last coefficient negated

first - is the index of the first coefficient negated

negate

public void negate(int nVars)

Negate all of the coefficients. The constant term coefficient is set to -C - 1.

negateCoefficients

public void negateCoefficients(int nVars)

Negate all of the coefficients and set touched to true.

multCoefs

public void multCoefs(int nVars,
                      int mult)

Multiply all of the coefficients by the scalar specified.

multCoefs

public void multCoefs(Equation f1,
                      int nVars,
                      int mult)

Set the coefficients to the product of a scalar and the coefficients of another Equation. The constant term is not multiplied.

Parameters:

mult - is the scalar used

checkMultCoefs

public void checkMultCoefs(int nVars,
                           int mult)

Multiply the coefficients by a scalar value.

Parameters:

mult - is the scalar used

checkMultCoefs

public void checkMultCoefs(Equation f1,
                           int nVars,
                           int mult)

Set the coefficients to the product of a scalar and the coefficients of another Equation.

Parameters:

mult - is the scalar used

multAndSub

public void multAndSub(Equation f1,
                       int mult,
                       int nVars)

Subtract the product of a scalar and the coefficients of another Equation from these coefficients.

Parameters:

mult - is the scalar used

sumOfMult

public void sumOfMult(Equation f1,
                      int mult1,
                      Equation f2,
                      int mult2,
                      int nVars)

Set the coefficients to (coef[i] = mult1 * f1.coef[i] + mult2 * f2.coef[i];).

combineColumns

public void combineColumns(int src,
                           int dest)

Add the sorce column coefficient to the destination column coefficient. Set the source coefficient to zero.

swapVars

public void swapVars(int v1,
                     int v2)

Swap the values of the specified coefficients and set touched true.

findDifference

public boolean findDifference(int nVars)

Return true if equation is of form (v1 - coef >= v2).

intModHat

public void intModHat(int var,
                      int b)

intModHatI

public void intModHatI(int i,
                       int nVars)

intModHat

public boolean intModHat(int first,
                         int last,
                         int b)

gcdCoefs

public int gcdCoefs(int last,
                    int first)

Return the greates common denominator of the specified coefficients.

Parameters:

last - is index of the last coefficient

first - is index of the first coefficient

gcdSumOfProd

public int gcdSumOfProd(Equation eq2,
                        int mult1,
                        int mult2,
                        int last,
                        int first)

computeHashcode

public int computeHashcode(int topVar,
                           int[] packing)

anyNZCoef

public boolean anyNZCoef(int last,
                         int first)

Return true if any coefficient's value is 1 or -1. Start at the coefficient specified by last and stop at the coefficient specified by first.

numNZCoefs

public int numNZCoefs(int last,
                      int first)

Return count of coefficients that are not zero. Start at the coefficient specified by last and stop at the coefficient specified by first.

numOneCoefs

public int numOneCoefs(int last,
                       int first)

Return count of coefficients whose value is 1 or -1. Start at the coefficient specified by last and stop at the coefficient specified by first.

lastOneCoef

public int lastOneCoef(int last,
                       int first)

Return the index of the last coefficient whose value is 1 or -1. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

lastNZCoef

public int lastNZCoef(int last,
                      int first)

Return the index of the last non-zero coefficient. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

lastNZCoef

public int lastNZCoef(int v1,
                      int v2,
                      int last,
                      int first)

Return the index of the last non-zero coefficient whose index is not specified. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

Parameters:

v1 - specifies the first index to be skipped

v2 - specifies the second index to be skipped

lastCoefGt1

public int lastCoefGt1(int last,
                       int first)

Return the index of the last coefficient whose absolute value is greater than 1. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

findSmallestNZ

public int findSmallestNZ(int last,
                          int first)

Return the index of the last coefficient with the smallest non-zero value. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

findLargestNZ

public int findLargestNZ(int last,
                         int first)

Return the index of the last coefficient with the largest non-zero value. Start at the coefficient specified by last and stop at the coefficient specified by first. If none qualifiy, return first - 1.

lastDiffModZero

public int lastDiffModZero(Equation eq2,
                           int g,
                           int i,
                           int last,
                           int first)

crossProduct

public int crossProduct(int last,
                        int first)

setTrueIfNotZero

public void setTrueIfNotZero(boolean[] res,
                             int last,
                             int first)

Set the array element true if the corresponding coefficient is not zero.

packNZIndexes

public int packNZIndexes(int[] indexes,
                         int last,
                         int first)

Returns:

the number of non-zero indexes

isGoodEquation

public boolean isGoodEquation(Equation eq2,
                              int mult,
                              int last,
                              int first)