PedAlignment

Alignment constraint model. More...

Files
file	natmath.h
file	natmath.h

Data Structures
struct	_PedAlignment

Macros
#define	PED_MAX(a, b)   ( ((a)>(b)) ? (a) : (b) )
#define	PED_MAX(a, b)   ( ((a)>(b)) ? (a) : (b) )
#define	PED_MIN(a, b)   ( ((a)<(b)) ? (a) : (b) )
#define	PED_MIN(a, b)   ( ((a)<(b)) ? (a) : (b) )

Typedefs
typedef struct _PedAlignment	PedAlignment
typedef struct _PedAlignment	PedAlignment

Functions
PedSector	ped_alignment_align_down (const PedAlignment *align, const PedGeometry *geom, PedSector sector)
	This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align.
PedSector	ped_alignment_align_nearest (const PedAlignment *align, const PedGeometry *geom, PedSector sector)
	This function returns the sector that is closest to sector, satisfies the align constraint and lies inside geom.
PedSector	ped_alignment_align_up (const PedAlignment *align, const PedGeometry *geom, PedSector sector)
	This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align.
void	ped_alignment_destroy (PedAlignment *align)
	Free up memory associated with align.
PedAlignment *	ped_alignment_duplicate (const PedAlignment *align)
	Return a duplicate of align.
int	ped_alignment_init (PedAlignment *align, PedSector offset, PedSector grain_size)
	Initialize a preallocated piece of memory for an alignment object (used by PedConstraint).
PedAlignment *	ped_alignment_intersect (const PedAlignment *a, const PedAlignment *b)
	This function computes a PedAlignment object that describes the intersection of two alignments.
int	ped_alignment_is_aligned (const PedAlignment *align, const PedGeometry *geom, PedSector sector)
	This function returns 1 if sector satisfies the alignment constraint align and lies inside geom.
PedAlignment *	ped_alignment_new (PedSector offset, PedSector grain_size)
	Return an alignment object (used by PedConstraint), representing all PedSector's that are of the form offset + X * grain_size.
PedSector	ped_greatest_common_divisor (PedSector a, PedSector b)
PedSector	ped_round_down_to (PedSector sector, PedSector grain_size)
PedSector	ped_round_to_nearest (PedSector sector, PedSector grain_size)
PedSector	ped_round_up_to (PedSector sector, PedSector grain_size)

Variables
const PedAlignment *	ped_alignment_any
const PedAlignment *	ped_alignment_any
const PedAlignment *	ped_alignment_any = &_any
const PedAlignment *	ped_alignment_none
const PedAlignment *	ped_alignment_none
const PedAlignment *	ped_alignment_none = NULL

Detailed Description

Alignment constraint model.

This part of libparted models alignment constraints.

Macro Definition Documentation

PED_MAX [1/2]

#define PED_MAX	(		a,
			b
	)		( ((a)>(b)) ? (a) : (b) )

PED_MAX [2/2]

#define PED_MAX	(		a,
			b
	)		( ((a)>(b)) ? (a) : (b) )

PED_MIN [1/2]

#define PED_MIN	(		a,
			b
	)		( ((a)<(b)) ? (a) : (b) )

PED_MIN [2/2]

#define PED_MIN	(		a,
			b
	)		( ((a)<(b)) ? (a) : (b) )

Typedef Documentation

PedAlignment [1/2]

typedef struct _PedAlignment PedAlignment

PedAlignment [2/2]

typedef struct _PedAlignment PedAlignment

Function Documentation

ped_alignment_align_down()

PedSector ped_alignment_align_down	(	const PedAlignment *	align,
		const PedGeometry *	geom,
		PedSector	sector
	)

This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align.

It prefers sectors that are before sector (are not larger than sector), but does not guarantee that this.

Returns

a PedSector on success, -1 on failure

ped_alignment_align_nearest()

PedSector ped_alignment_align_nearest	(	const PedAlignment *	align,
		const PedGeometry *	geom,
		PedSector	sector
	)

This function returns the sector that is closest to sector, satisfies the align constraint and lies inside geom.

Returns

a PedSector on success, -1 on failure

ped_alignment_align_up()

PedSector ped_alignment_align_up	(	const PedAlignment *	align,
		const PedGeometry *	geom,
		PedSector	sector
	)

This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align.

It prefers sectors that are beyond sector (are not smaller than sector), but does not guarantee that this.

Returns

a PedSector on success, -1 on failure

ped_alignment_destroy()

void ped_alignment_destroy

(

PedAlignment *

align

)

Free up memory associated with align.

ped_alignment_duplicate()

PedAlignment * ped_alignment_duplicate

(

const PedAlignment *

align

)

Return a duplicate of align.

ped_alignment_init()

int ped_alignment_init	(	PedAlignment *	align,
		PedSector	offset,
		PedSector	grain_size
	)

Initialize a preallocated piece of memory for an alignment object (used by PedConstraint).

The object will represent all sectors s for which the equation s = offset + X * grain_size holds.

ped_alignment_intersect()

PedAlignment * ped_alignment_intersect	(	const PedAlignment *	a,
		const PedAlignment *	b
	)

This function computes a PedAlignment object that describes the intersection of two alignments.

That is, a sector satisfies the new alignment object if and only if it satisfies both of the original ones. (See ped_alignment_is_aligned() for the meaning of "satisfies")

Apart from the trivial cases (where one or both of the alignment objects constraints have no sectors that satisfy them), this is what we're trying to do:

• two input constraints: a and b.
• the new grain_size is going to be the lowest common multiple of a->grain_size and b->grain_size
• hard part - solve the simultaneous equations, for offset, where offset, X and Y are variables. (Note: offset can be obtained from either X or Y, by substituing into either equation)

offset = \p a->offset + X * \p a->grain_size            (1)
offset = \p b->offset + Y * \p b->grain_size            (2)

or, abbreviated:

       o = Ao + X*Ag           (1)
       o = Bo + Y*Bg           (2)
 
=>     Ao + X*Ag    = Bo + Y*Bg     (1) = (2)
       X*Ag - Y*Bg  = Bo - Ao  (3)

As it turns out, there only exists a solution if (Bo - Ao) is a multiple of the GCD of Ag and Bg. Reason: all linear combinations of Ag and Bg are multiples of the GCD.

Proof:

A * Ag + B * Bg
= A * (\p a * gcd) + B * (\p b * gcd)
= gcd * (A * \p a + B * \p b)

gcd is a factor of the linear combination. QED

Anyway, a * Ag + b * Bg = gcd can be solved (for a, b and gcd) with Euclid's extended algorithm. Then, we just multiply through by (Bo - Ao) / gcd to get (3).

i.e.

A * Ag + B * Bg                         = gcd
A*(Bo-Ao)/gcd * Ag + B(Bo-Ao)/gcd * Bg  = gcd * (Bo-Ao)/gcd
X*Ag - Y*Bg                             = Bo - Ao               (3)
 
X = A*(Bo-Ao)/gcd
Y = - B*(Bo-Ao)/gcd

then:

 o = Ao + X*Ag                   (1)
= Ao + A*(Bo-Ao)/gcd*Ag
 o = Bo + Y*Bg                   (2)
= Bo - B*(Bo-Ao)/gcd*Ag

Thanks go to Nathan Hurst (njh@h.nosp@m.awth.nosp@m.orn.c.nosp@m.sse..nosp@m.monas.nosp@m.h.ed.nosp@m.u.au) for figuring this algorithm out :-)

Note

Returned NULL is a valid PedAlignment object, and can be used for ped_alignment_*() function.

Returns

a PedAlignment on success, NULL on failure

ped_alignment_is_aligned()

int ped_alignment_is_aligned	(	const PedAlignment *	align,
		const PedGeometry *	geom,
		PedSector	sector
	)

This function returns 1 if sector satisfies the alignment constraint align and lies inside geom.

Returns

1 on success, 0 on failure

ped_alignment_new()

PedAlignment * ped_alignment_new	(	PedSector	offset,
		PedSector	grain_size
	)

Return an alignment object (used by PedConstraint), representing all PedSector's that are of the form offset + X * grain_size.

ped_greatest_common_divisor()

PedSector ped_greatest_common_divisor	(	PedSector	a,
		PedSector	b
	)

ped_round_down_to()

PedSector ped_round_down_to	(	PedSector	sector,
		PedSector	grain_size
	)

ped_round_to_nearest()

PedSector ped_round_to_nearest	(	PedSector	sector,
		PedSector	grain_size
	)

ped_round_up_to()

PedSector ped_round_up_to	(	PedSector	sector,
		PedSector	grain_size
	)

Variable Documentation

ped_alignment_any [1/3]

const PedAlignment* ped_alignment_any

extern

ped_alignment_any [2/3]

const PedAlignment* ped_alignment_any

extern

ped_alignment_any [3/3]

const PedAlignment* ped_alignment_any = &_any

ped_alignment_none [1/3]

const PedAlignment* ped_alignment_none

extern

ped_alignment_none [2/3]

const PedAlignment* ped_alignment_none

extern

ped_alignment_none [3/3]

const PedAlignment* ped_alignment_none = NULL