Lattice.c File Reference

#include <stdlib.h>
#include <polylib/polylib.h>

Go to the source code of this file.

Classes
struct	factor
Functions
static factor	allfactors (int num)
void	PrintLatticeUnion (FILE *fp, char *format, LatticeUnion *Head)
void	LatticeUnion_Free (LatticeUnion *Head)
LatticeUnion *	LatticeUnion_Alloc (void)
Bool	sameAffinepart (Lattice *A, Lattice *B)
Lattice *	EmptyLattice (int dimension)
Bool	isEmptyLattice (Lattice *A)
Bool	isLinear (Lattice *A)
void	AffineHermite (Lattice *A, Lattice **H, Matrix **U)
void	AffineSmith (Lattice *A, Lattice **U, Lattice **V, Lattice **Diag)
Lattice *	Homogenise (Lattice *A, Bool Forward)
Bool	LatticeIncludes (Lattice *A, Lattice *B)
Bool	sameLattice (Lattice *A, Lattice *B)
Lattice *	ChangeLatticeDimension (Lattice *A, int dimension)
Lattice *	ExtractLinearPart (Lattice *A)
static Matrix *	MakeDioEqforInter (Matrix *A, Matrix *B)
Lattice *	LatticeIntersection (Lattice *X, Lattice *Y)
static void	AddLattice (LatticeUnion *, Matrix *, Matrix *, int, int)
LatticeUnion *	SplitLattice (Matrix *, Matrix *, Matrix *)
LatticeUnion *	Lattice2LatticeUnion (Lattice *X, Lattice *Y)
LatticeUnion *	LatticeDifference (Lattice *A, Lattice *B)
	Method :.
int	FindHermiteBasisofDomain (Polyhedron *A, Matrix **B)
Lattice *	LatticeImage (Lattice *A, Matrix *M)
Lattice *	LatticePreimage (Lattice *L, Matrix *G)
Bool	IsLattice (Matrix *m)
Bool	isfulldim (Matrix *m)
static Bool	Simplify (LatticeUnion **InputList, LatticeUnion **ResultList, int dim)
static int	LinearPartCompare (const void *A, const void *B)
static void	LinearPartSort (LatticeUnion *Head)
static int	AffinePartCompare (const void *A, const void *B)
static void	AffinePartSort (LatticeUnion *List)
static Bool	AlmostSameAffinePart (LatticeUnion *A, LatticeUnion *B)
static Bool	AffinePartSimplify (LatticeUnion *curlist, LatticeUnion **newlist)
static Bool	SameLinearPart (LatticeUnion *A, LatticeUnion *B)
LatticeUnion *	LatticeSimplify (LatticeUnion *latlist)
int	intcompare (const void *a, const void *b)
static int	polylib_sqrt (int i)

---

Function Documentation

static void AddLattice	(	LatticeUnion *	Head,
		Matrix *	B1,
		Matrix *	B2,
		int	NumofTimes,
		int	Colnumber
	)			[static]

Definition at line 928 of file Lattice.c.

References AffineHermite(), LatticeUnion::M, Matrix_Copy(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, LatticeUnion::next, matrix::p, value_addmul, value_clear, value_init, and value_set_si.

Referenced by SplitLattice().

void AffineHermite	(	Lattice *	A,
		Lattice **	H,
		Matrix **	U
	)

Definition at line 176 of file Lattice.c.

References False, Hermite(), Homogenise(), isLinear(), Matrix_Copy(), Matrix_Free(), and True.

Referenced by AddLattice(), AddZPolytoZDomain(), CanonicalForm(), LatticeDifference(), LatticeIncludes(), LatticeIntersection(), main(), sameLattice(), and SplitZpolyhedron().

static int AffinePartCompare	(	const void *	A,
		const void *	B
	)			[static]

Definition at line 1484 of file Lattice.c.

References matrix::NbRows, p, value_gt, and value_lt.

Referenced by AffinePartSort().

static Bool AffinePartSimplify	(	LatticeUnion *	curlist,
		LatticeUnion **	newlist
	)			[static]

Definition at line 1549 of file Lattice.c.

References AffinePartSort(), AlmostSameAffinePart(), False, LatticeUnion::M, matrix::NbColumns, matrix::NbRows, LatticeUnion::next, matrix::p, Simplify(), value_assign, value_clear, and value_init.

Referenced by LatticeSimplify().

static void AffinePartSort

(

LatticeUnion *

List

)

[static]

Definition at line 1506 of file Lattice.c.

References AffinePartCompare(), LatticeUnion::M, and LatticeUnion::next.

Referenced by AffinePartSimplify().

void AffineSmith	(	Lattice *	A,
		Lattice **	U,
		Lattice **	V,
		Lattice **	Diag
	)

Definition at line 221 of file Lattice.c.

References False, Homogenise(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), Matrix_Inverse(), matrix::NbColumns, matrix::NbRows, p, matrix::p, Smith(), True, value_addmul, value_addto, value_assign, value_clear, value_decrement, value_division, value_init, value_modulus, value_neg_p, value_print, and value_set_si.

Referenced by main().

static factor allfactors

(

int

num

)

[static]

Definition at line 1677 of file Lattice.c.

References factor::count, factor::fac, intcompare(), and polylib_sqrt().

Referenced by Simplify().

static Bool AlmostSameAffinePart	(	LatticeUnion *	A,
		LatticeUnion *	B
	)			[static]

Definition at line 1530 of file Lattice.c.

References False, LatticeUnion::M, matrix::NbColumns, matrix::NbRows, matrix::p, True, and value_ne.

Referenced by AffinePartSimplify().

Lattice* ChangeLatticeDimension	(	Lattice *	A,
		int	dimension
	)

Definition at line 409 of file Lattice.c.

References Matrix_Alloc(), matrix::NbRows, matrix::p, value_assign, and value_set_si.

Referenced by CanonicalForm(), FindHermiteBasisofDomain(), and Lattice2LatticeUnion().

Lattice* EmptyLattice

(

int

dimension

)

Definition at line 95 of file Lattice.c.

References Matrix_Alloc(), matrix::p, and value_set_si.

Referenced by EmptyZPolyhedron(), LatticeImage(), LatticeIntersection(), LatticePreimage(), and main().

Lattice* ExtractLinearPart

(

Lattice *

A

)

Definition at line 439 of file Lattice.c.

References Matrix_Alloc(), matrix::NbColumns, matrix::NbRows, matrix::p, and value_assign.

Referenced by Lattice2LatticeUnion().

int FindHermiteBasisofDomain	(	Polyhedron *	A,
		Matrix **	B
	)

Definition at line 990 of file Lattice.c.

References ChangeLatticeDimension(), polyhedron::Constraint, polyhedron::Dimension, Domain_Free(), DomainImage(), emptyQ, findHermiteBasis(), Identity(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), Matrix_Inverse(), Matrix_Product(), MAXNOOFRAYS, matrix::NbColumns, polyhedron::NbConstraints, polyhedron::NbRays, matrix::NbRows, matrix::p, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, polyhedron::Ray, RemoveColumn(), value_assign, value_clear, value_division, value_init, value_lcm, value_multiply, value_notzero_p, value_set_si, value_subtract, and value_zero_p.

Referenced by CanonicalForm().

Lattice* Homogenise	(	Lattice *	A,
		Bool	Forward
	)

Definition at line 312 of file Lattice.c.

References Matrix_Copy(), matrix::NbColumns, matrix::NbRows, PutColumnFirst(), PutColumnLast(), PutRowFirst(), PutRowLast(), and True.

Referenced by AffineHermite(), AffineSmith(), and isinHnf().

int intcompare	(	const void *	a,
		const void *	b
	)

Definition at line 1663 of file Lattice.c.

Referenced by allfactors().

Bool isEmptyLattice

(

Lattice *

A

)

Definition at line 118 of file Lattice.c.

References False, matrix::NbColumns, matrix::NbRows, matrix::p, True, value_notzero_p, and value_one_p.

Referenced by IntegraliseLattice(), isEmptyZPolyhedron(), Lattice2LatticeUnion(), LatticeDifference(), LatticeIntersection(), main(), SplitZpolyhedron(), ZPolyhedron_Alloc(), ZPolyhedronImage(), ZPolyhedronIntersection(), and ZPolyhedronPreimage().

Bool isfulldim

(

Matrix *

m

)

Definition at line 1267 of file Lattice.c.

References False, Hermite(), Matrix_Free(), matrix::NbRows, matrix::p, True, and value_zero_p.

Referenced by ZPolyhedron_Alloc().

Bool IsLattice

(

Matrix *

m

)

Definition at line 1239 of file Lattice.c.

References False, matrix::NbColumns, matrix::NbRows, matrix::p, True, value_notone_p, and value_notzero_p.

Referenced by ZPolyhedron_Alloc().

Bool isLinear

(

Lattice *

A

)

Definition at line 145 of file Lattice.c.

References False, matrix::NbColumns, matrix::NbRows, matrix::p, True, and value_notzero_p.

Referenced by AffineHermite().

LatticeUnion* Lattice2LatticeUnion	(	Lattice *	X,
		Lattice *	Y
	)

Definition at line 674 of file Lattice.c.

References ChangeLatticeDimension(), ExtractLinearPart(), isEmptyLattice(), LatticeIntersection(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), Matrix_Inverse(), Matrix_Product(), matrix::NbColumns, matrix::NbRows, matrix::p, Smith(), SplitLattice(), True, value_assign, value_clear, value_division, and value_init.

Referenced by LatticeDifference(), and SplitZpolyhedron().

LatticeUnion* LatticeDifference	(	Lattice *	A,
		Lattice *	B
	)

Method :.

Definition at line 814 of file Lattice.c.

References AffineHermite(), isEmptyLattice(), isinHnf(), Lattice2LatticeUnion(), LatticeSimplify(), LatticeUnion::M, Matrix_Copy(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, LatticeUnion::next, and True.

Referenced by main(), and ZPolyhedronDifference().

Lattice* LatticeImage	(	Lattice *	A,
		Matrix *	M
	)

Definition at line 1126 of file Lattice.c.

References EmptyLattice(), LatticePreimage(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), Matrix_Inverse(), Matrix_Product(), matrix::NbColumns, matrix::NbRows, matrix::p, and value_one_p.

Referenced by IntegraliseLattice(), main(), and ZPolyhedronImage().

Bool LatticeIncludes	(	Lattice *	A,
		Lattice *	B
	)

Definition at line 340 of file Lattice.c.

References AffineHermite(), False, LatticeIntersection(), Matrix_Free(), sameLattice(), and True.

Referenced by main(), and ZPolyhedronIncludes().

Lattice* LatticeIntersection	(	Lattice *	X,
		Lattice *	Y
	)

Definition at line 475 of file Lattice.c.

References AffineHermite(), EmptyLattice(), isEmptyLattice(), isinHnf(), MakeDioEqforInter(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, Vector::p, matrix::p, SolveDiophantine(), value_assign, value_set_si, and Vector_Free().

Referenced by Lattice2LatticeUnion(), LatticeIncludes(), main(), and ZPolyhedronIntersection().

Lattice* LatticePreimage	(	Lattice *	L,
		Matrix *	G
	)

Definition at line 1165 of file Lattice.c.

References EmptyLattice(), Matrix_Alloc(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, Vector::p, matrix::p, SolveDiophantine(), value_assign, value_clear, value_init, value_multiply, value_oppose, value_set_si, value_subtract, and Vector_Free().

Referenced by LatticeImage(), main(), and ZPolyhedronPreimage().

LatticeUnion* LatticeSimplify

(

LatticeUnion *

latlist

)

Definition at line 1636 of file Lattice.c.

References AffinePartSimplify(), False, LinearPartSort(), LatticeUnion::next, SameLinearPart(), and True.

Referenced by LatticeDifference(), main(), and ZDomainSimplify().

LatticeUnion* LatticeUnion_Alloc

(

void

)

Definition at line 60 of file Lattice.c.

References LatticeUnion::M, and LatticeUnion::next.

Referenced by main().

void LatticeUnion_Free

(

LatticeUnion *

Head

)

Definition at line 44 of file Lattice.c.

References LatticeUnion::M, Matrix_Free(), and LatticeUnion::next.

Referenced by main(), and ZDomainSimplify().

static int LinearPartCompare	(	const void *	A,
		const void *	B
	)			[static]

Definition at line 1429 of file Lattice.c.

References matrix::NbRows, p, value_gt, and value_lt.

Referenced by LinearPartSort().

static void LinearPartSort

(

LatticeUnion *

Head

)

[static]

Definition at line 1452 of file Lattice.c.

References LinearPartCompare(), LatticeUnion::M, and LatticeUnion::next.

Referenced by LatticeSimplify().

static Matrix * MakeDioEqforInter	(	Matrix *	A,
		Matrix *	B
	)			[static]

Definition at line 569 of file Lattice.c.

References Matrix_Alloc(), matrix::NbColumns, matrix::NbRows, matrix::p, value_oppose, and value_set_si.

Referenced by LatticeIntersection().

static int polylib_sqrt

(

int

i

)

[static]

Definition at line 1739 of file Lattice.c.

Referenced by allfactors().

void PrintLatticeUnion	(	FILE *	fp,
		char *	format,
		LatticeUnion *	Head
	)

Definition at line 32 of file Lattice.c.

References LatticeUnion::M, Matrix_Print(), and LatticeUnion::next.

Referenced by main().

Bool sameAffinepart	(	Lattice *	A,
		Lattice *	B
	)

Definition at line 74 of file Lattice.c.

References False, matrix::NbColumns, matrix::NbRows, matrix::p, True, and value_ne.

Bool sameLattice	(	Lattice *	A,
		Lattice *	B
	)

Definition at line 371 of file Lattice.c.

References AffineHermite(), False, Matrix_Free(), matrix::NbColumns, matrix::NbRows, matrix::p, True, and value_ne.

Referenced by AddZPolytoZDomain(), and LatticeIncludes().

static Bool SameLinearPart	(	LatticeUnion *	A,
		LatticeUnion *	B
	)			[static]

Definition at line 1620 of file Lattice.c.

References False, LatticeUnion::M, matrix::NbRows, matrix::p, True, and value_ne.

Referenced by LatticeSimplify().

static Bool Simplify	(	LatticeUnion **	InputList,
		LatticeUnion **	ResultList,
		int	dim
	)			[static]

Definition at line 1306 of file Lattice.c.

References allfactors(), factor::count, factor::fac, False, LatticeUnion::M, Matrix_Copy(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, LatticeUnion::next, matrix::p, True, value_addto, value_assign, value_clear, value_division, value_eq, value_ge, value_gt, value_increment, value_init, value_lt, and value_set_si.

Referenced by AffinePartSimplify().

LatticeUnion * SplitLattice	(	Matrix *	B1,
		Matrix *	B2,
		Matrix *	C
	)

Definition at line 901 of file Lattice.c.

References AddLattice(), LatticeUnion::M, matrix::NbRows, LatticeUnion::next, and matrix::p.

Referenced by Lattice2LatticeUnion().