Quick links: Tutorial - Examples - Files - Symbols.
Classes: Hierarchy - Index - List - Members.
Namespaces: Index - base - cs - display.

Public Member Functions | List of all members
cogitant::PartialOrder_SimpleMemo Class Reference

Représentation d'un ordre partiel par une matrice stockant toutes les comparaisons. More...

#include "cogitant/partialorder_simplememo.h"

Inheritance diagram for cogitant::PartialOrder_SimpleMemo:
cogitant::PartialOrder_Simple cogitant::PartialOrder cogitantcs::PartialOrderClient

Public Member Functions

void clear ()
 Vide l'ensemble. More...
 
void optimize ()
 Optimiser. More...
 
void unoptimize ()
 Supprimer les structures optimisées. More...
 
bool isLessOrEqualThan (iSet i1, iSet i2) const
 Retourne true ssi i1 <= i2. More...
 
Constructeurs - destructeur.
 PartialOrder_SimpleMemo ()
 Constructeur d'un ensemble ordonné vide. More...
 
 PartialOrder_SimpleMemo (PartialOrder const &c)
 Constructeur par recopie. More...
 
virtual ~PartialOrder_SimpleMemo ()
 Destructeur. More...
 
- Public Member Functions inherited from cogitant::PartialOrder_Simple
void reserve (nSet s)
 Réservation d'espace dans l'ensemble. More...
 
void setSize (nSet n)
 Fixer le nombre d'éléments. More...
 
void setImmediateLess (iSet i1, iSet i2)
 Ajout d'un couple à l'ordre partiel. More...
 
void setImmediateLess (iSet i, std::vector< iSet > const &ie)
 Sélection des éléments immédiatement inférieurs. More...
 
void unsetImmediateLess (iSet i1, iSet i2)
 Retrait de l'information i1 > i2. More...
 
nSet maxSize () const
 Taille maximale de l'ensemble. More...
 
nSet size () const
 Taille actuelle de l'ensemble. More...
 
bool optimized () const
 Optimisation des structures de données. More...
 
void getImmediateLessElements (iSet i, std::vector< iSet > &result) const
 Accès aux éléments immédiatement inférieurs. More...
 
bool isImmediateLess (iSet i1, iSet i2) const
 Éléments immédiatement inférieurs. More...
 
 PartialOrder_Simple ()
 Constructeur d'un ensemble ordonné vide. More...
 
 PartialOrder_Simple (PartialOrder const &c)
 Constructeur par recopie. More...
 
virtual ~PartialOrder_Simple ()
 Destructeur. More...
 
- Public Member Functions inherited from cogitant::PartialOrder
 PartialOrder ()
 Constructeur d'un ordre partiel. More...
 
 PartialOrder (PartialOrder const &c)
 Constructeur par recopie. More...
 
virtual ~PartialOrder ()
 Destructeur. More...
 
virtual iSet iBegin () const
 Itérateur de début. More...
 
virtual iSet iEnd () const
 Itérateur de fin. More...
 
virtual void iNext (iSet &i) const
 Incrémente l'itérateur passé pour le parcours de l'ensemble. More...
 
virtual bool isGreaterOrEqualThan (iSet i1, iSet i2) const
 Comparaison : >=. More...
 
virtual bool isLessThan (iSet i1, iSet i2) const
 Comparaison : <. More...
 
virtual bool isGreaterThan (iSet i1, iSet i2) const
 Comparaison : > More...
 
virtual Comparison comparison (iSet i1, iSet i2) const
 Comparaison. More...
 
virtual void getImmediateGreaterElements (iSet i, std::vector< iSet > &result) const
 Accès aux éléments immédiatement supérieurs. More...
 
virtual bool isImmediateGreater (iSet i1, iSet i2) const
 Éléments immédiatement supérieurs. More...
 
bool isLessOrEqualThanSets (std::vector< iSet > const &i1, std::vector< iSet > const &i2) const
 Comparaison : <=. More...
 
bool isGreaterOrEqualThanSets (std::vector< iSet > const &i1, std::vector< iSet > const &i2) const
 Comparaison : >=. More...
 
virtual void getGreaterOrEqualElements (iSet i, std::vector< iSet > &result) const
 Accès à tous les éléments supérieurs. More...
 
virtual void getLessOrEqualElements (iSet i, std::vector< iSet > &result) const
 Accès à tous les éléments inférieurs. More...
 

Additional Inherited Members

- Public Types inherited from cogitant::PartialOrder
enum  Comparison { EQUAL, LESS, GREATER, UNCOMPARABLE }
 Résultat de la comparaison de deux éléments d'un PartialOrder. More...
 
- Protected Member Functions inherited from cogitant::PartialOrder
virtual bool isValidIterator (iSet i1) const
 Vérification de la validité d'un identificateur. More...
 
- Protected Attributes inherited from cogitant::PartialOrder_Simple
nSet m_size
 Mémorisation de la taille (pour accès plus rapide).
 

Detailed Description

Représentation d'un ordre partiel par une matrice stockant toutes les comparaisons.

Cette classe stocke l'ordre partiel de la même façon que PartialOrder_Simple (dont elle hérite), la seule différence est que l'appel à la méthode optimize() calcule toutes les comparaisons entre les éléments de l'ordre et les stocke dans une matrice, ce qui permet une comparaison de deux éléments en O(1). L'inconvénient de cette méthode est bien sûr l'occupation mémoire qui est de n.(n-1)/8 octets, n étant le nombre d'éléments.

Stockage :
La variable d'instance m_memo est un tableau de caractères représentant chacun 4 comparaisons. Le nombre de comparaisons à stocker est n.(n-1)/2 ce qui correspond à la moitié de la matrice privée de la diagonale principale (inutile de stocker la comparaison de i, i). Chaque résultat de comparaison occupe 2 bits car, pour une comparaison de a et b, il nécessaire de stocker si a > b ou si b > a ou si a et b sont incomparables. Soit s le nombre d'éléments dans l'ordre partiel, la case de m_memo représentant la comparaison de a et b est donnée par t = (s-a)*(s-1-a)/2+a-b (l'entier a devant être strictement inférieur à l'entier b, sinon a et b sont inversés). t doit ensuite être converti pour obtenir l'indice dans le tableau d'octets (diviser par 4 puisque 4 comparaisons sont stockées dans un octet). Enfin, pour déterminer le bit correspondant à la comparaison de a et b, un modulo 4 est effectué sur t, les 4 premiers bits de l'octet servant à stocker les résultats des comparaisons pour lesquelles l'entier a est inférieur à b, les 4 autres pour a > b.

Constructor & Destructor Documentation

cogitant::PartialOrder_SimpleMemo::PartialOrder_SimpleMemo ( )

Constructeur d'un ensemble ordonné vide.

cogitant::PartialOrder_SimpleMemo::PartialOrder_SimpleMemo ( PartialOrder const &  c)

Constructeur par recopie.

Si c est optimisé (quelle que soit sa classe), l'ordre partiel construit sera optimisé.

virtual cogitant::PartialOrder_SimpleMemo::~PartialOrder_SimpleMemo ( )
virtual

Destructeur.

Member Function Documentation

void cogitant::PartialOrder_SimpleMemo::clear ( )
virtual

Vide l'ensemble.

Reimplemented from cogitant::PartialOrder_Simple.

Reimplemented in cogitantcs::PartialOrderClient.

bool cogitant::PartialOrder_SimpleMemo::isLessOrEqualThan ( iSet  i1,
iSet  i2 
) const
virtual

Retourne true ssi i1 <= i2.

Le résultat est retourné en O(1). Les autres méthodes d'accès à l'ordre (isGreaterOrEqualThan(), isLessThan(), isGreaterThan()) sont aussi en O(1) car elles appellent isLessOrEqualThan().

Exceptions
ExceptionISetOutOfBounds

Reimplemented from cogitant::PartialOrder_Simple.

void cogitant::PartialOrder_SimpleMemo::optimize ( )
virtual

Optimiser.

L'appel à cette méthode provoque un calcul des structures optimisées pour l'accès rapide à l'ordre partiel. Une fois optimisé, l'ordre partiel ne doit plus être modifié. Cette méthode doit être concrétisée dans les sous classes (éventuellement avec un code vide) et fournir une éventuelle optimisation.

Reimplemented from cogitant::PartialOrder_Simple.

Reimplemented in cogitantcs::PartialOrderClient.

void cogitant::PartialOrder_SimpleMemo::unoptimize ( )
virtual

Supprimer les structures optimisées.

Cette méthode peut être appelée après l'appel à optimize(). Après appel à unoptimize(), l'ordre partiel peut à nouveau être modifié. *.

Reimplemented from cogitant::PartialOrder_Simple.