PedAlignment

Alignment constraint model. More...

Files

file  natmath.h

Data Structures

struct  _PedAlignment

Defines

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

Typedefs

typedef _PedAlignment PedAlignment

Functions

PedSector abs_mod (PedSector a, PedSector b)
EuclidTriple extended_euclid (int a, int b)
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_div_round_to_nearest (PedSector numerator, PedSector divisor)
PedSector ped_div_round_up (PedSector numerator, PedSector divisor)
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 = &_any
const PedAlignment * ped_alignment_none
const PedAlignment * ped_alignment_none = NULL

Detailed Description

Alignment constraint model.

This part of libparted models alignment constraints.


Function Documentation

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

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

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

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.

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:

        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@hawthorn.csse.monash.edu.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

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


Generated on Fri May 4 05:15:31 2007 for libparted by  doxygen 1.5.2