Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

abacus::NonDuplPool< BaseType, CoType > Class Template Reference

Standard pools without constraint duplication. More...

#include <ogdf/lib/abacus/nonduplpool.h>

+ Inheritance diagram for abacus::NonDuplPool< BaseType, CoType >:

Public Member Functions

 NonDuplPool (Master *master, int size, bool autoRealloc=false)
 Creates an empty pool. More...
 
virtual ~NonDuplPool ()
 The destructor. More...
 
virtual void increase (int size)
 Enlarges the pool to store up to size items. More...
 
virtual PoolSlot< BaseType, CoType > * insert (BaseType *cv)
 Insert constraint/variable cv in the pool. More...
 
virtual PoolSlot< BaseType, CoType > * present (BaseType *cv)
 Checks if constraint/variables cv is already contained in the pool. More...
 
virtual const PoolSlot< BaseType, CoType > * present (const BaseType *cv) const
 Checks if constraint/variables cv is already contained in the pool. More...
 
void statistics (int &nDuplications, int &nCollisions) const
 Returns some statistic information in nDuplicates and nCollisions. More...
 
- Public Member Functions inherited from abacus::StandardPool< BaseType, CoType >
 StandardPool (Master *master, int size, bool autoRealloc=false)
 Creates an empty pool. More...
 
virtual ~StandardPool ()
 The destructor. More...
 
int cleanup ()
 Cleans-up the pool. More...
 
virtual int separate (double *x, Active< CoType, BaseType > *active, Sub *sub, CutBuffer< BaseType, CoType > *cutBuffer, double minAbsViolation=0.001, int ranking=0)
 Checks if a pair of a vector and an active constraint/variable set violates any item in the pool. More...
 
int size () const
 Return the maximal number of constraints/variables that can be inserted in the pool. More...
 
PoolSlot< BaseType, CoType > * slot (int i)
 Returns a pointer to the i-th slot in the pool. More...
 

Private Member Functions

 NonDuplPool (const NonDuplPool &rhs)
 
virtual void hardDeleteConVar (PoolSlot< BaseType, CoType > *slot)
 Has to be redefined because the pool slot has to be removed from the hash table. More...
 
const NonDuplPooloperator= (const NonDuplPool &rhs)
 
virtual int softDeleteConVar (PoolSlot< BaseType, CoType > *slot)
 Has to be redefined because the slot has to be removed from the hash table if the constraint/variable can be deleted. More...
 

Private Attributes

AbaHash< unsigned, PoolSlot< BaseType, CoType > * > hash_
 A hash table for a fast access to the pool slot storing a constraint/variable. More...
 
int nDuplications_
 The number of insertions of constraints/variables that were rejected since the constraint/variable is stored already in the pool. More...
 

Additional Inherited Members

- Protected Member Functions inherited from abacus::StandardPool< BaseType, CoType >
virtual PoolSlot< BaseType, CoType > * getSlot ()
 Returns a free slot, or 0 if no free slot is available. More...
 
virtual void putSlot (PoolSlot< BaseType, CoType > *slot)
 Inserts the slot in the list of free slots. More...
 
int removeNonActive (int maxRemove)
 Tries to remove at most maxRemove inactive items from the pool. More...
 
- Protected Attributes inherited from abacus::StandardPool< BaseType, CoType >
bool autoRealloc_
 If the pool becomes full and this member is true, then an automatic reallocation is performed. More...
 
ogdf::SListPure< PoolSlot< BaseType, CoType > * > freeSlots_
 The linked lists of unused slots. More...
 
Array< PoolSlot< BaseType, CoType > * > pool_
 The array with the pool slots. More...
 

Detailed Description

template<class BaseType, class CoType>
class abacus::NonDuplPool< BaseType, CoType >

Standard pools without constraint duplication.

The class NonDuplPool provides an StandardPool with the additional feature that the same constraint is at most stored once in the pool. For constraints and variables inserted in this pool the virtual member functions name(), hashKey(), and equal() of the base class ConVar have to be defined. Using these three functions, we check at insertation time if a constraint or variable is already stored in the pool.

The implementation is unsafe in the sense that the data structure for registering a constraint is corrupted if a constraint is removed directly from the pool slot without using a function of this class.

Definition at line 58 of file nonduplpool.h.

Constructor & Destructor Documentation

◆ NonDuplPool() [1/2]

template<class BaseType , class CoType >
abacus::NonDuplPool< BaseType, CoType >::NonDuplPool ( Master master,
int  size,
bool  autoRealloc = false 
)
inline

Creates an empty pool.

Parameters
masterA pointer to the corresponding master of the optimization.
sizeThe maximal number of items which can be inserted in the pool without reallocation.
autoReallocIf this argument is true an automatic reallocation is performed if the pool is full.

Definition at line 69 of file nonduplpool.h.

◆ ~NonDuplPool()

template<class BaseType , class CoType >
virtual abacus::NonDuplPool< BaseType, CoType >::~NonDuplPool ( )
inlinevirtual

The destructor.

Definition at line 74 of file nonduplpool.h.

◆ NonDuplPool() [2/2]

template<class BaseType , class CoType >
abacus::NonDuplPool< BaseType, CoType >::NonDuplPool ( const NonDuplPool< BaseType, CoType > &  rhs)
private

Member Function Documentation

◆ hardDeleteConVar()

template<class BaseType , class CoType >
virtual void abacus::NonDuplPool< BaseType, CoType >::hardDeleteConVar ( PoolSlot< BaseType, CoType > *  slot)
privatevirtual

Has to be redefined because the pool slot has to be removed from the hash table.

Parameters
slotA pointer to the pool slot from wich the constraint/variable should be deleted.

◆ increase()

template<class BaseType , class CoType >
virtual void abacus::NonDuplPool< BaseType, CoType >::increase ( int  size)
inlinevirtual

Enlarges the pool to store up to size items.

To avoid fatal errors we do not allow decreasing the size of the pool. This function redefines the virtual function of the base class StandardPool because we have to reallocate the hash table.

Parameters
sizeThe new size of the pool.

Reimplemented from abacus::StandardPool< BaseType, CoType >.

Definition at line 125 of file nonduplpool.h.

◆ insert()

template<class BaseType , class CoType >
virtual PoolSlot<BaseType, CoType>* abacus::NonDuplPool< BaseType, CoType >::insert ( BaseType *  cv)
virtual

Insert constraint/variable cv in the pool.

Before the function insert() tries to insert a constraint/variable in the pool, it checks if the constraint/variable is already contained in the pool. If the constraint/variable cv is contained in the pool, it is deleted.

Parameters
cvThe constraint/variable being inserted.
Returns
A pointer to the pool slot where the item has been inserted, or a pointer to the pool slot if the item is already contained in the pool, or 0 if the insertion failed.

Reimplemented from abacus::StandardPool< BaseType, CoType >.

◆ operator=()

template<class BaseType , class CoType >
const NonDuplPool& abacus::NonDuplPool< BaseType, CoType >::operator= ( const NonDuplPool< BaseType, CoType > &  rhs)
private

◆ present() [1/2]

template<class BaseType , class CoType >
virtual PoolSlot<BaseType, CoType>* abacus::NonDuplPool< BaseType, CoType >::present ( BaseType *  cv)
virtual

Checks if constraint/variables cv is already contained in the pool.

Parameters
cvA pointer to a constraint/variable for which it should be checked if an equivalent item is already contained in the pool.
Returns
A pointer to the pool slot storing a constraint/variable that is equivalent to cv according to the function ConVar::equal(). If there is no such constraint/variable 0 is returned.

◆ present() [2/2]

template<class BaseType , class CoType >
virtual const PoolSlot<BaseType, CoType>* abacus::NonDuplPool< BaseType, CoType >::present ( const BaseType *  cv) const
virtual

Checks if constraint/variables cv is already contained in the pool.

Parameters
cvA (const) pointer to a constraint/variable for which it should be checked if an equivalent item is already contained in the pool.
Returns
A const pointer to the pool slot storing a constraint/variable that is equivalent to cv according to the function ConVar::equal(). If there is no such constraint/variable 0 is returned.

◆ softDeleteConVar()

template<class BaseType , class CoType >
virtual int abacus::NonDuplPool< BaseType, CoType >::softDeleteConVar ( PoolSlot< BaseType, CoType > *  slot)
privatevirtual

Has to be redefined because the slot has to be removed from the hash table if the constraint/variable can be deleted.

Returns
0 If the constraint/variable could be deleted, 1 otherwise.
Parameters
slotA pointer to the pool slot from wich the constraint/variable should be deleted.

◆ statistics()

template<class BaseType , class CoType >
void abacus::NonDuplPool< BaseType, CoType >::statistics ( int &  nDuplications,
int &  nCollisions 
) const
inline

Returns some statistic information in nDuplicates and nCollisions.

Determines the number of constraints that have not been inserted into the pool, because an equivalent was already present.

Also the number of collisions in the hash table is computed. If this number is high, it might indicate that your hash function is not chosen very well.

Parameters
nDuplicationsThe number of constraints that have not been inserted into the pool because an equivalent one was already present.
nCollisionsThe number of collisions in the hash table.

Definition at line 144 of file nonduplpool.h.

Member Data Documentation

◆ hash_

template<class BaseType , class CoType >
AbaHash<unsigned, PoolSlot<BaseType, CoType>*> abacus::NonDuplPool< BaseType, CoType >::hash_
private

A hash table for a fast access to the pool slot storing a constraint/variable.

Definition at line 171 of file nonduplpool.h.

◆ nDuplications_

template<class BaseType , class CoType >
int abacus::NonDuplPool< BaseType, CoType >::nDuplications_
private

The number of insertions of constraints/variables that were rejected since the constraint/variable is stored already in the pool.

Definition at line 175 of file nonduplpool.h.


The documentation for this class was generated from the following file: