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:

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

◆ PartialOrder_SimpleMemo() [1/2]

cogitant::PartialOrder_SimpleMemo::PartialOrder_SimpleMemo ( )

Constructeur d'un ensemble ordonné vide.

◆ PartialOrder_SimpleMemo() [2/2]

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é.

◆ ~PartialOrder_SimpleMemo()

virtual cogitant::PartialOrder_SimpleMemo::~PartialOrder_SimpleMemo ( )

virtual

Destructeur.

Member Function Documentation

◆ clear()

void cogitant::PartialOrder_SimpleMemo::clear ( )

virtual

Vide l'ensemble.

Reimplemented from cogitant::PartialOrder_Simple.

Reimplemented in cogitantcs::PartialOrderClient.

◆ isLessOrEqualThan()

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.

◆ optimize()

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.