scale.score.dependence.omega.omegaLib
Class Relation

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

public final class Relation
extends java.lang.Object

Relation.

$Id: Relation.java,v 1.15 2005-02-07 21:28:41 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

Constructor Summary

Relation(OmegaLib omegaLib)

Relation(OmegaLib omegaLib, int nci)

Relation(OmegaLib omegaLib, int numberInput, int numberOutput)
Create a relation.

Relation(OmegaLib omegaLib, Relation r)

Relation(OmegaLib omegaLib, RelBody r)

Relation(Relation r, Conjunct c)

Relation(RelBody r)

Relation(RelBody r, Conjunct c)

Method Summary

FAnd	addAnd()
FExists	addExists()
FForall	addForall()
FNot	addNot()
FOr	addOr()
Relation	affineHull()
Relation	after(int carried_by, int new_output, int dir)
FAnd	andWith()
FAnd	andWithAnd()
Relation	approximate()
Relation	approximate(boolean strides_allowed)
void	calculateDimensions(Conjunct c, int[] dims)
Relation	checkForConvexPairs()
Relation	checkForConvexRepresentation()
Relation	complement() complement.
Relation	composition(Relation r2) Composition(F, G) = F o G, where F o G (x) = F(G(x)) That is, if F = { [i] .
Relation	conicClosure()
Relation	conicHull()
Relation	convexHull()
static int	created()
Relation	crossProduct(Relation input_B) Cross Product.
Relation	decoupledConvexHull()
void	delete()
Relation	deltas() Deltas(F) Return a set such that the ith variable is old Out_i - In_i Delta variables are created as input variables.
Relation	deltas(int eq_no)
Relation	deltasToRelation(int numberInputs, int numberOutputs)
Relation	difference(Relation input_r2) F minus G.
Relation	domain() Domain and Range.
boolean	equal(Relation r2)
Relation	extractDNFByCarriedLevel(int level, int direction)
protected void	finalize() Keep the count of instances up-to-date.
VarDecl	getLocal(GlobalVarDecl G)
VarDecl	getLocal(GlobalVarDecl G, int of)
VarDecl	getLocal(VarDecl v)
RelBody	getRelBody()
Conjunct	getSingleConjunct()
java.lang.Object	getVar(java.lang.String name)
HashMap<java.lang.String,java.lang.Object>	getVars()
Relation	gist(Relation r2, int effort) Compute gist(r1) given r2.
Relation	gistSingleConjunct(Relation input_R2, int effort) Compute (gist r1 given r2).
boolean	hasSingleConjunct()
Relation	hull(boolean stridesAllowed, int effort, Relation knownHull)
VarDecl	inputVar(int nth)
Relation	intersection(Relation input_r2) F intersection G.
Relation	inverse() inverse F -reverse the input and output tuples.
boolean	isDOK(Relation D, Relation AxA) Check if we can use D instead of R.
boolean	isLowerBoundSatisfiable()
boolean	isNotSatisfiable()
boolean	isObviousTautology()
boolean	isSatisfiable()
boolean	isSet()
boolean	isUpperBoundDefinitelyNotSatisfiable()
boolean	isUpperBoundSatisfiable()
Relation	linearHull()
Relation	makeLevelCarriedTo(int level)
void	nameInputVar(int nth, java.lang.String S)
void	nameOutputVar(int nth, java.lang.String S)
void	nameSetVar(int nth, java.lang.String S)
int	numberInput()
int	numberOfConjuncts()
int	numberOutput()
int	numberSet()
VarDecl	outputVar(int nth)
void	prefixPrint()
void	prefixPrint(boolean debug)
void	printWithSubs()
Relation	project(GlobalVarDecl g) Project out global variable g from relation r.
Relation	project(int pos, int vkind) Project an input, output or set variable, leaving a variable in that position with no constraints.
Relation	project(Vector<VarDecl> s)
Relation	projectOnSym(Relation input_context) Project away all input and output variables.
Relation	projectOntoJust(VarDecl v)
Relation	projectSym() Project all symbolic variables from relation r.
void	putVar(java.lang.String name, java.lang.Object var)
boolean	queryDifference(VarDecl v1, VarDecl v2, int[] bounds)
void	queryVariableBounds(VarDecl v, int[] bounds)
Relation	range()
Conjunct	removeFirstConjunct()
Relation	restrictDomain(Relation input_r2) F \ G (the relation F restricted to domain G).
Relation	restrictRange(Relation input_r2) F / G (the relation F restricted to range G) align the output tuples for F and G match named variables in F and G formula is f & g
void	setFinalized()
VarDecl	setVar(int nth)
void	simplify()
java.lang.String	toString()
Relation	transitiveClosure0(int maxExpansion, Relation iterationSpace) Transitive closure of the relation containing multiple conjuncts.
Relation	tryConjunctTransitiveClosure(Relation IterationSpace, Relation rPlus) Try to get conjunct transitive closure.
Relation	union(Relation input_r2) r1 Union r2.
Relation	vennDiagramForm(Relation Context_In)

Methods inherited from class java.lang.Object

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

Constructor Detail

Relation

public Relation(OmegaLib omegaLib)

Relation

public Relation(OmegaLib omegaLib,
                int numberInput,
                int numberOutput)

Create a relation. Its will be built later.

Relation

public Relation(OmegaLib omegaLib,
                int nci)

Relation

public Relation(OmegaLib omegaLib,
                Relation r)

Relation

public Relation(OmegaLib omegaLib,
                RelBody r)

Relation

public Relation(Relation r,
                Conjunct c)

Relation

public Relation(RelBody r,
                Conjunct c)

Relation

public Relation(RelBody r)

Method Detail

created

public static int created()

finalize

protected void finalize()
                 throws java.lang.Throwable

Keep the count of instances up-to-date.

Overrides:

finalize in class java.lang.Object

Throws:

java.lang.Throwable - [needs description]

delete

public void delete()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

setFinalized

public void setFinalized()

putVar

public void putVar(java.lang.String name,
                   java.lang.Object var)

getVar

public java.lang.Object getVar(java.lang.String name)

getVars

public HashMap<java.lang.String,java.lang.Object> getVars()

getRelBody

public RelBody getRelBody()

addForall

public FForall addForall()

addExists

public FExists addExists()

addAnd

public FAnd addAnd()

andWith

public FAnd andWith()

addOr

public FOr addOr()

addNot

public FNot addNot()

isSet

public boolean isSet()

numberInput

public int numberInput()

numberOutput

public int numberOutput()

numberSet

public int numberSet()

inputVar

public VarDecl inputVar(int nth)

outputVar

public VarDecl outputVar(int nth)

setVar

public VarDecl setVar(int nth)

getLocal

public VarDecl getLocal(VarDecl v)

getLocal

public VarDecl getLocal(GlobalVarDecl G)

getLocal

public VarDecl getLocal(GlobalVarDecl G,
                        int of)

nameInputVar

public void nameInputVar(int nth,
                         java.lang.String S)

nameOutputVar

public void nameOutputVar(int nth,
                          java.lang.String S)

nameSetVar

public void nameSetVar(int nth,
                       java.lang.String S)

andWithAnd

public FAnd andWithAnd()

prefixPrint

public void prefixPrint()

prefixPrint

public void prefixPrint(boolean debug)

printWithSubs

public void printWithSubs()

isLowerBoundSatisfiable

public boolean isLowerBoundSatisfiable()

isUpperBoundDefinitelyNotSatisfiable

public boolean isUpperBoundDefinitelyNotSatisfiable()

isUpperBoundSatisfiable

public boolean isUpperBoundSatisfiable()

isSatisfiable

public boolean isSatisfiable()

isNotSatisfiable

public boolean isNotSatisfiable()

isObviousTautology

public boolean isObviousTautology()

numberOfConjuncts

public int numberOfConjuncts()

simplify

public void simplify()

removeFirstConjunct

public Conjunct removeFirstConjunct()

getSingleConjunct

public Conjunct getSingleConjunct()

hasSingleConjunct

public boolean hasSingleConjunct()

queryDifference

public boolean queryDifference(VarDecl v1,
                               VarDecl v2,
                               int[] bounds)

queryVariableBounds

public void queryVariableBounds(VarDecl v,
                                int[] bounds)

makeLevelCarriedTo

public Relation makeLevelCarriedTo(int level)

extractDNFByCarriedLevel

public Relation extractDNFByCarriedLevel(int level,
                                         int direction)

calculateDimensions

public void calculateDimensions(Conjunct c,
                                int[] dims)

approximate

public Relation approximate()

approximate

public Relation approximate(boolean strides_allowed)

projectOnSym

public Relation projectOnSym(Relation input_context)

Project away all input and output variables.

project

public Relation project(GlobalVarDecl g)

Project out global variable g from relation r.

projectSym

public Relation projectSym()

Project all symbolic variables from relation r.

project

public Relation project(int pos,
                        int vkind)

Project an input, output or set variable, leaving a variable in that position with no constraints.

project

public Relation project(Vector<VarDecl> s)

union

public Relation union(Relation input_r2)

r1 Union r2. align the input tuples (if any) for F and G align the output tuples (if any) for F and G match named variables in F and G formula is f | g

intersection

public Relation intersection(Relation input_r2)

F intersection G. align the input tuples (if any) for F and G align the output tuples (if any) for F and G match named variables in F and G formula is f & g

restrictDomain

public Relation restrictDomain(Relation input_r2)

F \ G (the relation F restricted to domain G). align the input tuples for F and G match named variables in F and G formula is f & g

restrictRange

public Relation restrictRange(Relation input_r2)

F / G (the relation F restricted to range G) align the output tuples for F and G match named variables in F and G formula is f & g

domain

public Relation domain()

Domain and Range. Make output (input) variables wildcards and simplify. Move all UFS's to have have the remaining tuple as an argument, and maprel will move them to the set tuple RESET all leading 0's

range

public Relation range()

crossProduct

public Relation crossProduct(Relation input_B)

Cross Product. Give two sets, A and B, create a relation whose domain is A and whose range is B.

inverse

public Relation inverse()

inverse F -reverse the input and output tuples.

after

public Relation after(int carried_by,
                      int new_output,
                      int dir)

deltas

public Relation deltas()

Deltas(F) Return a set such that the ith variable is old Out_i - In_i Delta variables are created as input variables. Then input and output variables are projected out.

deltas

public Relation deltas(int eq_no)

deltasToRelation

public Relation deltasToRelation(int numberInputs,
                                 int numberOutputs)

composition

public Relation composition(Relation r2)

Composition(F, G) = F o G, where F o G (x) = F(G(x)) That is, if F = { [i] . [j] : ... } and G = { [x] . [y] : ... } then Composition(F, G) = { [x] . [j] : ... } align the output tuple for G and the input tuple for F, these become existensially quantified variables use the output tuple from F and the input tuple from G for the result match named variables in G and F formula is g & f If there are function symbols of arity > 0, we call special case code to handle them. This is not set up for the r2.isSet case yet.

difference

public Relation difference(Relation input_r2)

F minus G.

complement

public Relation complement()

complement. not F

gistSingleConjunct

public Relation gistSingleConjunct(Relation input_R2,
                                   int effort)

Compute (gist r1 given r2). Currently we assume that r2 has only one conjunct. r2 may have zero input and output OR may have # in/out vars equal to r1.

gist

public Relation gist(Relation r2,
                     int effort)

Compute gist(r1) given r2. Relation r2 can have multiple conjuncts.

projectOntoJust

public Relation projectOntoJust(VarDecl v)

decoupledConvexHull

public Relation decoupledConvexHull()

convexHull

public Relation convexHull()

affineHull

public Relation affineHull()

linearHull

public Relation linearHull()

conicHull

public Relation conicHull()

conicClosure

public Relation conicClosure()

hull

public Relation hull(boolean stridesAllowed,
                     int effort,
                     Relation knownHull)

checkForConvexPairs

public Relation checkForConvexPairs()

vennDiagramForm

public Relation vennDiagramForm(Relation Context_In)

checkForConvexRepresentation

public Relation checkForConvexRepresentation()

isDOK

public boolean isDOK(Relation D,
                     Relation AxA)

Check if we can use D instead of R. i.e. D intersection (A cross A) is Must_Be_Subset of R

tryConjunctTransitiveClosure

public Relation tryConjunctTransitiveClosure(Relation IterationSpace,
                                             Relation rPlus)

Try to get conjunct transitive closure. it we can get it easy get it, return true. if not - return false

equal

public boolean equal(Relation r2)

transitiveClosure0

public Relation transitiveClosure0(int maxExpansion,
                                   Relation iterationSpace)

Transitive closure of the relation containing multiple conjuncts.