PIPS
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sc-private.h"
Go to the source code of this file.
Data Structures | |
struct | sort_ctx_t |
package sc More... | |
Macros | |
#define | ADD_COST (1) |
#define | MUL_COST (1) |
#define | AFF_COST (1) |
#define | DB_RESULT(e) |
for qsort, returns "is simpler than" More... | |
#define | RESULT(e) { return (e); } |
#define | RETURN_HARDER(b) RESULT(context->complex_first ? (b) : -(b)) |
#define | RETURN_ORDER(b) RESULT(context->inner_first ? (b) : -(b)) |
#define | same_sign_p(v, w) ((value_neg_p(v) && value_neg_p(w)) || (value_pos_p(v) && value_pos_p(w))) |
Functions | |
static void | set_sort_context (sort_ctx_t *context, Pbase base, Pbase sort_base, bool inner_first, bool complex_first) |
static void | clear_sort_context (sort_ctx_t *context) |
static int | cost_of_constant_operations (Pvecteur v, sort_ctx_t *context) |
static int | compare_the_constraints (const Pcontrainte *pc1, const Pcontrainte *pc2, sort_ctx_t *context) |
compare two constraints with a loop complexity cost in mind? not exactly, some of the choices attempt to avoid large coefs? More... | |
Pvecteur | highest_rank_pvector (Pvecteur v, Pbase b, int *prank) |
returns the highest rank pvector of v in b, of rank *prank More... | |
static Pcontrainte | constraints_sort_info (Pcontrainte c, Pbase sort_base, constraint_cmp_func_t compare, void *context, two_int_infop info) |
sorts the constraints according to the compare function, and set the number of constraints for each index of the sort base More... | |
Pcontrainte | constraints_sort_with_compare (Pcontrainte c, Pbase sort_base, constraint_cmp_func_t compare, void *context) |
Pcontrainte | contrainte_sort (Pcontrainte c, Pbase base, Pbase sort_base, bool inner_first, bool complex_first) |
Psysteme | sc_sort_constraints (Psysteme ps, Pbase base_index) |
Psysteme | sc_triang_elim_redund (Psysteme ps, Pbase base_index) |
sort contrainte c, base b, relatively to sort_base, as defined by the switches. More... | |
void | move_n_first_constraints (Pcontrainte *source, Pcontrainte *target, int n) |
void move_n_first_constraints(source, target, n) Pcontrainte *source, *target; int n; More... | |
void | sc_triang_elim_redund_n_first (Psysteme s, int n) |
void sc_triang_elim_redund_n_first(s, n) Psysteme s; int n; More... | |
Psysteme | sc_build_triang_elim_redund (Psysteme s, Pbase indexes) |
outer to inner More... | |
Psysteme | sc_sort_constraints_simplest_first (Psysteme ps, Pbase base_index) |
#define ADD_COST (1) |
Definition at line 77 of file sc_triang_elim_redond.c.
#define AFF_COST (1) |
Definition at line 79 of file sc_triang_elim_redond.c.
#define DB_RESULT | ( | e | ) |
for qsort, returns "is simpler than"
with the following criterion
1/ ranks 2/ coef of comparable ranks, +-1 or simpler... 3/
rational:
Definition at line 120 of file sc_triang_elim_redond.c.
#define MUL_COST (1) |
Definition at line 78 of file sc_triang_elim_redond.c.
#define RESULT | ( | e | ) | { return (e); } |
Definition at line 129 of file sc_triang_elim_redond.c.
Definition at line 131 of file sc_triang_elim_redond.c.
Definition at line 132 of file sc_triang_elim_redond.c.
#define same_sign_p | ( | v, | |
w | |||
) | ((value_neg_p(v) && value_neg_p(w)) || (value_pos_p(v) && value_pos_p(w))) |
Definition at line 134 of file sc_triang_elim_redond.c.
|
static |
Definition at line 70 of file sc_triang_elim_redond.c.
References assert, BASE_NULLE, and base_rm.
Referenced by contrainte_sort(), sc_build_triang_elim_redund(), and sc_triang_elim_redund().
|
static |
compare two constraints with a loop complexity cost in mind? not exactly, some of the choices attempt to avoid large coefs?
returns -1: c1<c2, 0: c1==c2, +1: c1>c2
Definition at line 142 of file sc_triang_elim_redond.c.
References BASE_NULLE_P, cost_of_constant_operations(), RETURN_HARDER, RETURN_ORDER, same_sign_p, Svecteur::succ, TCST, value_compare, value_ne, value_neg_p, value_pos_p, VALUE_ZERO, value_zero_p, var_of, and vect_coeff().
Referenced by contrainte_sort(), sc_build_triang_elim_redund(), and sc_triang_elim_redund().
|
static |
sorts the constraints according to the compare function, and set the number of constraints for each index of the sort base
the constraints are put in the table and info is set.
the list of constraints is generated again
clean!
Definition at line 275 of file sc_triang_elim_redond.c.
References BASE_NULLE_P, free(), highest_rank_pvector(), info(), malloc(), nb_elems_list(), rank, Scontrainte::succ, tc, val_of, value_pos_p, vect_size(), and Scontrainte::vecteur.
Referenced by constraints_sort_with_compare(), sc_build_triang_elim_redund(), and sc_triang_elim_redund().
Pcontrainte constraints_sort_with_compare | ( | Pcontrainte | c, |
Pbase | sort_base, | ||
constraint_cmp_func_t | compare, | ||
void * | context | ||
) |
Definition at line 327 of file sc_triang_elim_redond.c.
References constraints_sort_info(), free(), info(), malloc(), and vect_size().
Referenced by contrainte_sort().
Pcontrainte contrainte_sort | ( | Pcontrainte | c, |
Pbase | base, | ||
Pbase | sort_base, | ||
bool | inner_first, | ||
bool | complex_first | ||
) |
Definition at line 344 of file sc_triang_elim_redond.c.
References base, clear_sort_context(), compare_the_constraints(), constraints_sort_with_compare(), and set_sort_context().
Referenced by movement_computation(), sc_sort(), sc_sort_constraints(), and sc_sort_constraints_simplest_first().
|
static |
Definition at line 80 of file sc_triang_elim_redond.c.
References ADD_COST, AFF_COST, MUL_COST, Svecteur::succ, TCST, value_abs, value_notzero_p, value_one_p, var_of, and vect_coeff().
Referenced by compare_the_constraints().
returns the highest rank pvector of v in b, of rank *prank
Definition at line 246 of file sc_triang_elim_redond.c.
References BASE_NULLE_P, rank, Svecteur::succ, and var_of.
Referenced by constraints_sort_info().
void move_n_first_constraints | ( | Pcontrainte * | source, |
Pcontrainte * | target, | ||
int | n | ||
) |
void move_n_first_constraints(source, target, n) Pcontrainte *source, *target; int n;
moves the n first constraints from source to target, in order.
nothing to be done
nth points to the nth constraint.
Definition at line 498 of file sc_triang_elim_redond.c.
References Scontrainte::succ.
Referenced by sc_build_triang_elim_redund().
outer to inner
sort outer first and complex first
remove the redundancy on others then triangular clean of what remains.
what if s is empty or null ???
build the non redundant triangular system for each level and side.
clean!
Definition at line 541 of file sc_triang_elim_redond.c.
References assert, Ssysteme::base, clear_sort_context(), compare_the_constraints(), constraints_sort_info(), free(), Ssysteme::inegalites, info(), level, malloc(), move_n_first_constraints(), sc_elim_empty_constraints(), sc_elim_redund(), sc_kill_db_eg(), sc_normalize(), sc_triang_elim_redund_n_first(), set_sort_context(), and vect_size().
Definition at line 359 of file sc_triang_elim_redond.c.
References Ssysteme::base, contrainte_sort(), and Ssysteme::inegalites.
Referenced by algorithm_row_echelon_generic(), and constraints_to_loop_bound().
Definition at line 602 of file sc_triang_elim_redond.c.
References Ssysteme::base, contrainte_sort(), and Ssysteme::inegalites.
sort contrainte c, base b, relatively to sort_base, as defined by the switches.
inner_first: innermost first complex_first: the more complex the likely to be put earlier Psysteme sc_triang_elim_redond(Psysteme ps, Pbase base_index): elimination des contraintes lineaires redondantes dans le systeme ps par test de faisabilite de contrainte inversee; cette fonction est utilisee pour calculer des bornes de boucles, c'est pourquoi il peut etre necessaire de garder des contraintes redondantes afin d'avoit toujours au moins une borne inferieure et une borne superieure pour chaque indice.
resultat retourne par la fonction :
Psysteme : Le systeme initial est modifie. Il est egal a NULL si le systeme initial est non faisable.
Les parametres de la fonction :
Psysteme ps : systeme lineaire
Attention: pour chaque indice dans base_index, il doit rester au moins deux contraintes correspondantes (une positive et une negative). C'est la seule difference avec la fonction sc_elim_redond().
contrainte_reverse() is used. Rational points may be added by this procedure.
Yi-Qing YANG
Modifications:
only the variables that have more than one constraints on a given size and that deal with the variables of base_index are tested.
an old comment suggested that keeping contraints on variables out of base_index would help find redundancy on the base_index contraints, but this should not be true anymore, since the variables are sorted... just help to deal with larger systems...
FC 28/09/94
inversion du sens de l'inegalite par multiplication par -1 du coefficient de chaque variable
test de sc_faisabilite avec la nouvelle inegalite
restore the initial constraint
Definition at line 418 of file sc_triang_elim_redond.c.
References abs, Ssysteme::base, clear_sort_context(), compare_the_constraints(), constraints_sort_info(), contrainte_reverse(), eq_set_vect_nul(), fprintf(), free(), Ssysteme::inegalites, info(), level, level_contrainte(), malloc(), Ssysteme::nb_ineq, OFL_CTRL, sc_elim_empty_constraints(), sc_integer_feasibility_ofl_ctrl(), sc_kill_db_eg(), sc_normalize(), sc_rm(), set_sort_context(), Scontrainte::succ, and vect_size().
Referenced by algorithm_row_echelon_generic().
void sc_triang_elim_redund_n_first(s, n) Psysteme s; int n;
tries a triangular redundancy elimination on the n first constraints, which must all deal with the same side of the same index. if n is 0, nothing is done, but nothing is reported.
contrainte_reverse() is used and rational points may be added
nothing to be done
restore
remove
Definition at line 521 of file sc_triang_elim_redond.c.
References contrainte_reverse(), eq_set_vect_nul(), OFL_CTRL, sc_integer_feasibility_ofl_ctrl(), and Scontrainte::succ.
Referenced by sc_build_triang_elim_redund().
|
static |
Definition at line 52 of file sc_triang_elim_redond.c.
References assert, base, base_difference(), base_normalize(), BASE_NULLE, and base_reversal().
Referenced by contrainte_sort(), sc_build_triang_elim_redund(), and sc_triang_elim_redund().